Первое занятие состоится: 14 февраля 2000 г., 16:20, ауд. 779

Предметом данного курса являются алгоритмы решения оптимизационных задач на дискретных математических структурах. К настоящему времени сформировалась и оформилась система знаний о разработке, реализации и анализе алгоритмов.

Во всех областях программирования активно используются дискретные (комбинаторные) математические структуры и алгоритмы работы с ними. Например, алгоритмы работы с графами являются фундаментальными для теории конструирования компиляторов.

Одним из критериев качества алгоритмов является его сложность по времени и сложность по памяти, то есть время работы и размер памяти, необходимый для работы алгоритма в худшем случае. Алгоритм считается хорошим, если время его работы оценивается как полином некоторой небольшой степени от характерного размера входных данных. В данном курсе будут рассматриваться только полиномиальные алгоритмы.

1.

Порядковые статистики.

2.

Методы разработки алгоритмов: алгоритмы динамического программирования; жадные алгоритмы.

3.

Алгоритмы на графах: элементарные алгоритмы (поиск в ширину и глубину); построение остова (алгоритмы Прима и Краскала); кратчайшие пути от одной вершины (алгоритмы Форда--Беллмана, Дейкстры); кратчайшие пути между всеми вершинами (<<перемножение матриц>>, алгоритм Флойда); потоки в сетях и родственные задачи (алгоритм Форда--Фалкерсона, паросочетания в двудольных графах).

4.

Избранные алгоритмы: поиск подстроки в строке (алгоритмы Кнута--Морриса--Пратта, Бойера--Мура).

Спецкурс рассчитан на студентов 2--4 курсов.