Lectures.htm — различия между версиями

Текущая версия на 20:55, 25 ноября 2010

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

Доска курса — самая актуальная информация по курсу: программа, обьявления, контакты и т.п.

Download

Студентам

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

Лекторам

Набор лекций в виде слайд-презентаций (гипертекстовые PDF-слайды):

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

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

Элементы теории сложности

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 Полиномиальные сводимости и NP-полнота
 1.3.5 Сводимость по Куку
 1.3.6 Недетерминированные алгоритмы
 1.3.7 Сводимость по Карпу
1.4 Вероятностные вычисления
 1.4.1 Классы RP и coRP. Распознавание с односторонней ошибкой.
 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.
• А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления — замечательная книга. Содержит отличное введение в теорию сложности.