Теория алгоритмов. Введение в сложность вычислений
- Раздел 1. Машины Тьюринга
- Тема 1. Неформальное введение
- Тема 2. Модели Тьюринга
- Тема 3. Многоленточные машины Тьюринга
- Раздел 2. Время и память
- Тема 1. Время и зона машины Тьюринга
- Тема 2. Цена сокращения алфавита
- Тема 3. Цена сокращения количества лент
- Раздел 3. Универсальные машины Тьюринга
- Тема 1. Машина Тьюринга, универсальная для класса С
- Тема 2. Конструкция универсальной машины
- Тема 3. Теоремы об иерархии по времени и по зоне
- Раздел 4. Моделирование других языков программирования
- Тема 1. Схема моделирования других языков программирования машинами Тьюринга
- Тема 2. Моделирование RAM
- Тема 3. Моделирование булевых схем
- Раздел 5. Класс Р
- Тема 1. Определение класса Р
- Тема 2. Примеры: целочисленная арифметика
- Тема 3. Примеры: арифметика остатков
- Тема 4. Примеры: сложение и умножение матриц
- Тема 5. Примеры: связность в графе
- Раздел 6. Класс P/Poly
- Тема 1. Распознавание языков последовательностями булевых схем
- Тема 2. Континуальность класса P/Poly
- Тема 3. Включение Р ⊂ P/Poly
- Раздел 7. Класс NP
- Тема 1. Определение класса NP
- Тема 2. О проблеме P ≠ NP
- Тема 3. Примеры задач класса NP
- Раздел 8. Примеры NP-полных задач
- Тема 1. Сводимость  (Карп), NP-полнота.
- Тема 2. NP-полнота проблемы выполнимости булевых формул
- Тема 3. NP-полнота задачи о клике
- Тема 4. NP-трудность задачи целочисленного линейного программирования
- Раздел 9. Класс BPP
- Тема 1. Вероятностные вычисления за полиномиальное время
- Тема 2. Частотные распознаватели
- Тема 3. Включение ВРР ⊂ P/Poly
- Раздел 10. Вероятностный алгоритм распознавания простых чисел
- Тема 1. Сведения из теории чисел
- Тема 2. Извлечение корней
- Тема 3. Вероятностный алгоритм распознавания простых чисел
- Тема 4. Верификация алгоритма
- Тема 5. Оценка сложности
- Раздел 11. Конечные игры и класс PH
- Тема 1. Конечные игры
- Тема 2. Определение класса РН
- Тема 3. Замкнутость относительно ∩, ∪ и ( )с
- Раздел 12. Полиномиальная иерархия
- Тема 1. Классы полиномиальной иерархии
- Тема 2. Структурные свойства классов полиномиальной иерархии
- Тема 3. Пример
- Тема 4. Включение ВРР ⊂  ∩ 
- Раздел 13. Класс PSPACE
- Тема 1. Класс PSPACE и игры с полиномиальным числом ходов
- Тема 2. Моделирование игры
- Тема 3. Моделирование на полиномиальной памяти
- Тема 4. Игровая характеризация класса PSPACE