WikiSysop: Import Blogger entry

2008-12-10T13:59:00Z

Import Blogger entry

Новая страница

[http://www.blogger.com/profile/18127426428751477675 Stas Fomin]: Темы к экзамену совпадают с текущим списком опубликованных слайдов:
# «Несложно о сложности. Примеры алгоритмов».
# «Формально об алгоритмах. Вычислительные модели».
# «Временная и пространственная сложность алгоритмов».
# «Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC».
# «Вероятностные вычисления. Классы RP, coRP, ZPP, BPP».
# «Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема».
# «PCP и аппроксимируемость».
# «Жадный алгоритм в задачах о покрытии».
# «Жадный алгоритм покрытия для почти всех исходных данных».
# «Приближенный алгоритм для метрической задачи коммивояжера».
# «Жадный алгоритм в задаче о рюкзаке».
# «Динамическое программирование для задачи о рюкзаке».
# «Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке».
# «Полиномиальный в среднем алгоритм для задачи упаковки».
# «Полиномиальный в среднем алгоритм для задачи о рюкзаке».
# «Полиномиальный в среднем алгоритм для SAT».
# «Вероятностный подсчет числа выполняемых наборов для ДНФ».
# «MAX-SAT: вероятностное округление».
# «MAX-SAT: дерандомизация».
# «Дерандомизация Люби».
# «MAX-CUT: вероятностное округление».
# «Параллельный алгоритм Люби для максимального по включению независимого множества».Т.е. другие темы («византийское соглашение» и т.п. ) — читать и учить необязательно. Выбор счастливчиков, получивших отлично автоматом будет проведен 17 декабря. Но в любом случае, все ваши комментарии полученные до экзамена будут учтены и будут положительно влиять на оценку.
{{wl-publish: 2008-12-10 16:59:00 +0300 | WikiSysop}}

Blog:Advanced Algorithms/2008-12-10 Темы к экзамену - История изменений

WikiSysop: Import Blogger entry