Курс лекций «Сложность комбинаторных алгоритмов».

Download

Студентам

Материалы к курсу — книга Эффективные алгоритмы и сложность вычислений

Лекторам

1. «Несложно о сложности. Примеры алгоритмов».^Mindmap
2. «Формально об алгоритмах. Вычислительные модели».^Mindmap
3. «Временная и пространственная сложность алгоритмов».^Mindmap
4. «Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC».^Mindmap
5. «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP».^Mindmap
6. «Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема».^Mindmap
7. «PCP и аппроксимируемость».^Mindmap
8. «Жадный алгоритм в задачах о покрытии».^Mindmap
9. «Жадный алгоритм покрытия для почти всех исходных данных».^Mindmap
10. «Приближенный алгоритм для метрической задачи коммивояжера».^Mindmap
11. «Жадный алгоритм в задаче о рюкзаке».^Mindmap
12. «Динамическое программирование для задачи о рюкзаке».^Mindmap
13. «Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке».^Mindmap
14. «Полиномиальный в среднем алгоритм для задачи упаковки».^Mindmap
15. «Полиномиальный в среднем алгоритм для задачи о рюкзаке».^Mindmap
16. «Полиномиальный в среднем алгоритм для SAT».^Mindmap
17. «Вероятностный подсчет числа выполняемых наборов для ДНФ».^Mindmap
18. «MAX-SAT: вероятностное округление».^Mindmap
19. «MAX-SAT: дерандомизация».^Mindmap
20. «Дерандомизация Люби».^Mindmap
21. «MAX-CUT: вероятностное округление».^Mindmap
22. «Параллельный алгоритм Люби для максимального по включению независимого множества».^Mindmap

Приблизительное содержание курса лекций

Элементы теории сложности
 1.1 Примеры алгоритмов
  1.1.1 Примеры задач на натуральных числах.
  1.1.2 Примеры задач на графах. Кратчайшие пути, остовные деревья и задача коммивояжера.
  1.1.3 Приближенные алгоритмы. Многопроцессорные расписания
  1.1.4 Сортировка слиянием
  1.1.5 Быстрая сортировка. Анализ в среднем и вероятностная версия.
 1.2 Формально об алгоритмах
  1.2.1 Машины с произвольным доступом к памяти
  1.2.2 Машины Тьюринга и вычислимость
 1.3 Сложность алгоритмов
  1.3.1 Сложность в худшем случае
  1.3.2 Полиномиальные алгоритмы
  1.3.3 Классы DTIME, DSPACE
  1.3.4 Полиномиальные сводимости и -полнота
  1.3.5 Сводимость по Куку
  1.3.6 Недетерминированные алгоритмы
  1.3.7 Сводимость по Карпу
 1.4 Вероятностные вычисления
  1.4.1 Классы и co. Распознавание с односторонней ошибкой.
  1.4.2 Класс BPP. Эффективное распознавание с двухсторонней ошибкой.
  1.4.3 Класс PP.
  1.4.4 Класс ZPP. Вероятностное распознавание без ошибок.
 1.5 Вероятностно проверяемые доказательства
  1.5.1 PCP и неаппроксимируемость
 1.6 Схемы и схемная сложность
 1.7 Диаграмма классов сложности
2 Приближенные алгоритмы с гарантированными оценками точности
 2.1 Приближенные алгоритмы с фиксированными оценками точности
  2.1.1 Жадный алгоритм в задаче о покрытии
  2.1.2 Приближенные алгоритмы для задачи покрытия с минимальной суммой
  2.1.3 Жадный алгоритм для задачи о рюкзаке
  2.1.4 Алгоритм Кристофидеса для метрической задачи коммивояжера
 2.2 Приближенные алгоритмы с выбираемыми оценками точности
  2.2.1 Динамическое программирование для задачи о рюкзаке. Псевдополиномиальный алгоритм
  2.2.2 Полностью полиномиальная приближенная схема для задачи о рюкзаке
3 Вероятностные алгоритмы и вероятностный анализ.
 3.1 Полиномиальные в среднем алгоритмы
  3.1.1 Анализ сложности в среднем
 3.2 Задача упаковки
  3.2.1 Точность жадного алгоритма для почти всех исходных данных
 3.3 Полиномиальный в среднем алгоритм для задачи о рюкзаке
 3.4 Вероятностные алгоритмы (Лас-Вегас и Монте-Карло).
  3.4.1 Алгоритм Фрейвалда и проверка полиномиальных тождеств
 3.5 Вероятностное округление и дерандомизация
  3.5.1 Вероятностное округление
  3.5.2 Дерандомизация и метод условных вероятностей.
4 Приложения
 4.1 Глоссарий
 4.2 Введение в Python

Полезная сопутствующая литература по курсу.

• Очень хорошие лекции по классической теории сложности, написанные одним из корифеев оной: Introduction to Complexity Theory by Oded Goldreich
• Более краткий курс по классической теории сложности, университет Technion.
• Еще один классический курс лекций по теории сложности от László Lovász.
• А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления — замечательная книга. Содержит отличное введение в теорию сложности.