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

лекторы:   д.ф.-м.н. Н.Н. Кузюрин, С.А. Фомин.

Семестровый курс для студентов 4го курса МФТИ (группы с базой ИСП РАН). 

Место чтения курса - ИСП РАН (Москва, м. Таганская, Большая Коммунистическая, д. 25). Комната 110.
Время: по средам, 13:30 (возможны подвижки по времени).

Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса .

---

Новости

---

Набор лекций в виде слайд-презентаций (гипертекстовые 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. «Параллельный алгоритм Люби для максимального по включению независимого множества».

Будем рады ответить на любые вопросы — пишите на stanislav.fomin@gmail.com Станиславу Фомину. 


 

---

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

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