На главную страницу НМУ

Н.К.Верещагин, А.Х.Шень

Сложность вычислений и алгоритмы (вводный курс)

Программа курса

1. Вычислимые и невычислимые функции, общая теория алгоритмов
2. Полиномиальные алгоритмы. Примеры.
3. Класс NP, полнота, сводимость
4. Вероятностные алгоритмы
5. Полиномиальная иерархия, класс PSPACE
6. Сложностные классы и игры
7. Диагонализация, теорема об иерархии
8. Схемная сложность
9. Интерактивные доказательства, классы AM, IP