Документ взят из кэша поисковой машины. Адрес оригинального документа : http://sp.cs.msu.ru/courses/alg/program.html
Дата изменения: Fri Oct 31 19:59:00 2008
Дата индексирования: Mon Oct 1 21:30:19 2012
Кодировка: koi8-r
Программа спецкурса "Алгоритмы дискретной оптимизации"

Спецкурс: алгоритмы дискретной оптимизации.
Лектор: асп. Чернов А. В., каф. СП.

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




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

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

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

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

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


Alexander Chernov
2000-02-14