Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://sp.cs.msu.ru/courses/alg/exam.html
Дата изменения: Fri Oct 31 19:59:00 2008
Дата индексирования: Mon Oct 1 21:04:22 2012
Кодировка: koi8-r
Алгоритмы дискретной оптимизации.
Программа экзамена.
1.
Алгоритмы и их анализ. Оценка сложности алгоритмов.
Нахождение i-й порядковой статистики.
2.
Принцип динамического программирования. Нахождение оптимального
порядка перемножения матриц.
3.
Жадные алгоритмы. Задача о распределении ресурсов.
Сравнение алгоритмов динамического программирования и жадных алгоритмов.
4.
Поиск в строке. Конечные автоматы.
5.
Поиск в строке. Алгоритм Кнута--Морриса--Пратта.
6.
Представление графов. Поиск в ширину.
7.
Поиск в глубину. Классификация ребер графа.
8.
Применение поиска в глубину. Топологическая сортировка. Выделение
компонент сильной связности.
9.
Представление множеств в виде деревьев.
10.
Минимальное остовное дерево. Алгоритм Краскала.
11.
Структура данных <<пирамида>>.
12.
Минимальное остовное дерево. Алгоритм Прима.
13.
Кратчайшие пути в графе. Алгоритм Дейкстры.
14.
Алгоритм Форда--Беллмана. Кратчайшие пути в ориентированных ациклических
графах.
15.
Кратчайшие пути между всеми парами вершин.
16.
Максимальные потоки. Алгоритм Форда--Фалкерсона.
Алгоритм Эдмондса--Карпа. Задача о паросочетаниях.