Программа курса лекций «Анализ Алгоритмов»
(зимний семестр 2008-09 учебного года)
Тема 1. Искусство представления и доказательства корректности алгоритмов.
1. Псевдокод – человеко-ориентированный подход к представлению и анализу алгоритмов.
2. Методы доказательства корректности и завершаемости алгоритмов.
3. Примеры представления, анализа и доказательства простых алгоритмов.
4. Машина с произвольным доступом к памяти – базовая модель для описания и анализа алгоритмов.
5. Понятие асимптотической (временной) сложности алгоритмов. Примеры оценки асимптотической сложности.
Тема 2. Методы проектирования алгоритмов.
1. Вспомогательные алгоритмы: алгоритмы поиска, сортировки (сравнениями, выбором, вставкой, слиянием), умножение матриц (алгоритм Штрассена) .
2. Метод отката: общая форма и примеры.
3. Метод ветвей и границ: общая форма и примеры.
4. Динамическое программирование: примеры и общая форма.
5. Другие методы проектирования алгоритмов (сведения к задаче меньшей размерности, разделяй и властвуй, жадные алгоритмы и так далее).
Тема 3. Недетерминированные и альтернирующие вычисления.
1. Понятие недетерминированного/альтернирующего алгоритма, временной сложности недетерминированных/альтернирующих вычислений.
2. Понятия класса сложности по времени, определение классов P и NP, проблема P=NP.
3. Детерминированное моделирование альтернирующих вычислений, связь соответствующих классов сложности.
4. Детерминированное моделирование недетерминированных вычислений, связь соответствующих классов сложности.
5. NP-полнота проблемы булевской выполнимости.
6. Примеры NP-полных проблем: изоморфное вложение графов, проблема клики (с доказательством).
7. NP-полнота проблемы Гамильтонова цикла.
Образцы вопрос к экзамену
(предварительный список, будет уточнен)
1. Понятие псевдокода в контексте разных парадигм программирования.
2. Понятие аннотированного алгоритма. Привести примеры.
3. Метод доказательства корректности алгоритмов по Флойду. Привести примеры.
4. Методы доказательства завершаемости алгоритмов. Привести примеры.
5. Меры сложности алгоритмов. Методы оценки эффективности. Машина с произвольным доступом к памяти.
6. Метод разделяй и властвуй. Привести примеры.
7. Динамическое программирование. Привести примеры.
8. Метод отката (backtracking). Привести примеры.
9. Метод ветвей и границ. Привести примеры.
10. Основные понятие сортировки и поиска. Сортировки с помощью сравнений.
11. Основные понятие сортировки и поиска. Сортировка выбором.
12. Основные понятие сортировки и поиска. Сортировки вставками.
13. Алгоритмы произведения для матриц.
14. Алгоритмические проблемы для регулярных языков. Алгоритм синтаксического анализа регулярных языков.
15. Понятие недетерминированного алгоритма. Определение классов P и NP, проблема P=NP.
16. Примеры NP-полных проблем.
17. Понятия альтернирующего алгоритма. Детерминированные, недетерминированные и альтернирующие иерархии по времени.
18. Связи между классами сложности в различных иерархиях.
Рекомендуемая литература
1. Д. Грисс Наука программирования. М.: Наука, 1985.
2. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
3. Корнмэн Т, Лейзерсон Ч, лгоритмы: построение и анализ. М.: МЦНМО, 2000.
4. лассификация вычислительной сложности проблем. В Кибернетический сборник (новая серия), вып. 26. 1989, М.: Мир. Стр.20-83.
5. Мучник переводчика к статьям «Об альтернации, I, II». Кибернетический сборник (новая серия), вып. 20. 1983, М.: Мир. С.141-158.
