1.Введение в предмет
2.Понятие машины Тьюринга
3.Представление машины Тьюринга
4.Альтернативы машине Тьюринга
5.Нумерация машин Тьюринга
6.Невычислимые функции
7.Примеры алгоритмически неразрешимых проблем
8.Современное программирование с точки зрения машины Тьюринга
9.Рекурсивные функции и множества
10.Операция примитивной рекурсии
11.Графическое и схемное описание алгоритмов
12.Табличный способ представления алгоритмов
13.Уменьшение числа состояний
14.Алгоритмы и исчисления
15.Информационная сложность (энтропия)
16.Вычислительная сложность
17.Классы P и NP
18.Понятие о полной задаче
19.Задача ВЫПОЛНИМОСТЬ
20.Задаче о раскраске графа (представить логически)
21.Задача о парасочетании (представить логически)
22.Представление арифметических уравнений логическими
23.Теорема Кука (общий подход)
24.Задача о покрытии
25.Задача о максимальной нулевой подматрице
26.Принцип резолюций Робинсона для задачи ВЫПОЛНИМОСТЬ
27.Метод отсечения литер
28.Метод группировки резольвент для задач о покрытии
29.Использование слабых методов и эвристик
30.Жадные алгоритмы на матроидах