2008-12-10 Темы к экзамену

Текущая версия на 13:59, 10 декабря 2008

Stas Fomin: Темы к экзамену совпадают с текущим списком опубликованных слайдов:

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