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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Import Blogger entry)
 
(нет различий)

Текущая версия на 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 декабря. Но в любом случае, все ваши комментарии полученные до экзамена будут учтены и будут положительно влиять на оценку.