Алгоритмы дискретной оптимизации.
Программа экзамена.
- 1.
- Алгоритмы и их анализ. Оценка сложности алгоритмов.
Нахождение i-й порядковой статистики.
- 2.
- Принцип динамического программирования. Нахождение оптимального
порядка перемножения матриц.
- 3.
- Жадные алгоритмы. Задача о распределении ресурсов.
Сравнение алгоритмов динамического программирования и жадных алгоритмов.
- 4.
- Поиск в строке. Конечные автоматы.
- 5.
- Поиск в строке. Алгоритм Кнута--Морриса--Пратта.
- 6.
- Представление графов. Поиск в ширину.
- 7.
- Поиск в глубину. Классификация ребер графа.
- 8.
- Применение поиска в глубину. Топологическая сортировка. Выделение
компонент сильной связности.
- 9.
- Представление множеств в виде деревьев.
- 10.
- Минимальное остовное дерево. Алгоритм Краскала.
- 11.
- Структура данных <<пирамида>>.
- 12.
- Минимальное остовное дерево. Алгоритм Прима.
- 13.
- Кратчайшие пути в графе. Алгоритм Дейкстры.
- 14.
- Алгоритм Форда--Беллмана. Кратчайшие пути в ориентированных ациклических
графах.
- 15.
- Кратчайшие пути между всеми парами вершин.
- 16.
- Максимальные потоки. Алгоритм Форда--Фалкерсона.
Алгоритм Эдмондса--Карпа. Задача о паросочетаниях.
Alexander Chernov
2000-06-23