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

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

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

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

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

Rambler's Top100