Раздел I. Модели вычислений

• Тема 1. Машины Тьюринга (154мин.)
• • 1.1. Неформальное введение (44мин.)
  • 1.2. Модели Тьюринга (44мин.)
  • 1.3. Многоленточные машины Тьюринга (66мин.)
• Тема 2. Время и память (154мин.)
• • 2.1. Время и зона машины Тьюринга (22мин.)
  • 2.2. Цена сокращения алфавита (66мин.)
  • 2.3. Цена сокращения количества лент (66мин.)
• Тема 3. Универсальные машины Тьюринга (110мин.)
• • 3.1. Машина Тьюринга, универсальная для класса С (22мин.)
  • 3.2. Конструкция универсальной машины (44мин.)
  • 3.3. Теоремы об иерархии по времени и по зоне (44мин.)
• Тема 4. Моделирование других языков программирования (154мин.)
• • 4.1. Схема моделирования других языков программирования машинами Тьюринга (22мин.)
  • 4.2. Моделирование машин с неограниченными регистрами (44мин.)
  • 4.3. Моделирование булевых схем (88мин.)
• Тест:  Модели вычислений (62мин.)

Раздел II. Сложностные классы

• Тема 5. Класс P (132мин.)
• • 5.1. Определение класса P (22мин.)
  • 5.2. Примеры: целочисленная арифметика (22мин.)
  • 5.3. Примеры: арифметика остатков (22мин.)
  • 5.4. Примеры: сложение и умножение матриц (44мин.)
  • 5.5. Примеры: связность в графе (22мин.)
• Тема 6. Класс P/Poly (110мин.)
• • 6.1. Распознавание языков последовательностями булевых схем (22мин.)
  • 6.2. Континуальность класса P/Poly (22мин.)
  • 6.3. Включение P P/Poly (66мин.)
• Тема 7. Класс NP (132мин.)
• • 7.1. Определение класса NP (44мин.)
  • 7.2. О проблеме P NP (22мин.)
  • 7.3. Примеры задач класса NP (66мин.)
• Тема 8. Примеры NP-полных задач (110мин.)
• • 8.1. Сводимость Карпа, NP-полнота (22мин.)
  • 8.2. NP-полнота проблемы выполнимости булевых формул (44мин.)
  • 8.3. NP-полнота задачи о клике (22мин.)
  • 8.4. NP-трудность задачи целочисленного линейного программирования (22мин.)
• Тема 9. Класс BPP (110мин.)
• • 9.1. Вероятностные вычисления за полиномиальное время (22мин.)
  • 9.2. Частотные распознаватели (44мин.)
  • 9.3. Включение BPP P/Poly (44мин.)
• Тема 10. Вероятностный алгоритм распознавания простых чисел (132мин.)
• • 10.1. Сведения из теории чисел (22мин.)
  • 10.2. Извлечение корней (22мин.)
  • 10.3. Вероятностный алгоритм распознавания простых чисел (22мин.)
  • 10.4. Верификация алгоритма (44мин.)
  • 10.5. Оценка сложности (44мин.)
• Тема 11. Конечные игры и класс PH (110мин.)
• • 11.1. Конечные игры (22мин.)
  • 11.2. Определение класса PH (44мин.)
  • 11.3. Замкнутость относительно операций пересечения, объединения и дополнения (44мин.)
• Тема 12. Полиномиальная иерархия (154мин.)
• • 12.1. Классы полиномиальной иерархии (22мин.)
  • 12.2. Структурные свойства классов полиномиальной иерархии (22мин.)
  • 12.3. Пример использования полиномиальной иерархии (44мин.)
  • 12.4. Включение класса BPP в пересечение классов полиномиальной иерархии (66мин.)
• Тема 13. Класс PSPACE (132мин.)
• • 13.1. Класс PSPACE и игры с полиномиальным числом ходов (22мин.)
  • 13.2. Моделирование игры (22мин.)
  • 13.3. Моделирование на полиномиальной памяти (22мин.)
  • 13.4. Игровая характеризация класса PSPACE (66мин.)
• Тема 14. Полные задачи для класса PSPACE и классов полиномиальной иерархии (110мин.)
• • 14.1. Квантифицированные булевы формулы (22мин.)
  • 14.2. Полные задачи для классов полиномиальной иерархии (44мин.)
  • 14.3. Пример PSPACE-полной задачи (44мин.)
• Тест:  Сложностные классы (108мин.)

Рекомендуемая литература

Завершение курса

• Тест:  Итоговое тестирование (30мин.)