А.Плотников, 2003 (Rus)
Элементы теории алгоритмов  

ВВЕДЕНИЕ 
Реферат. Рассматриваются первичные сведения теории алгоритмов. Обсуждается интуитивное понятие алгоритма. Определяются примитивно-рекурсивные функции. Описывается одноленточная машина Тьюринга и ее работа. Определяется понятие сложности алгоритмов и основные классы задач, решаемые при помощи компьютера. В заключении рассматривается пример полиномиальной сводимости задачи построения кратчайшей дизъюнктивной нормальной формы булевой функции к задаче разбиения графа на минимальное число клик

ОГЛАВЛЕНИЕ

1 Предмет теории алгоритмов
2 Интуитивное понятие алгоритма
3 Примитивно-рекурсивные функции
4 Машина Тьюринга
5 Композиция машин Тьюринга
6 Алгоритмически неразрешимые проблемы
7 Понятие сложности алгоритма
8 Асимптотические оценки функций сложности
9 Трудноразрешимые задачи
10 Класс NP
11 NP-полные задачи
12 Пример полиномиального сведения
   12.1 Постановка задачи
   12.2 Графовая модель задачи минимизации

ЛИТЕРАТУРА