Тихомирова А.Н. Теория алгоритмов

Учебное пособие. Москва, МИФИ, 2008. 176 стр. - ISBN 978-5-7262-1078-0 Книга посвящена теории алгоритмов и содержит основные сведения о свойствах алгоритмов и способах их формального представления (машины Тьюринга, алгоритмы Маркова, рекурсивные функции). Изложены основы теории бесконечных множеств, рассмотрены вопросы нахождения эффективных процедур для перечисления объектов различной природы. Затронуты проблемы алгоритмической неразрешимости и базовые понятия сложности алгоритмов.
Книга представляет интерес для студентов технических вузов, аспирантов, научных работников и всех, интересующихся теорией алгоритмов и связанными с ней аспектами истории развития математики. Содержание
Предисловие
Введение
Формальные описания алгоритмов
Алгоритмы: определение и основные свойства
Классические машины Тьюринга
Специальные машины Тьюринга
Теоремы Шеннона
Алгоритмически неразрешимые задачи
Нормальные алгоритмы
Эффективные перечислимость и распознаваемость
Задачи к главе
Числовые множества
Множества: определение и основные свойства
Классификация множеств
Счетные множества
Несчетные множества
Множества с мощностью, больше чем мощность континуума
Вычислимые числа
Задачи к главе
Арифметические вычисления
Арифметические функции
Частичные арифметические функции
Эффективное распознавание и сравнение функций
Задачи к главе
Рекурсивные функции
Роль рекурсивных функций
Примитивно-рекурсивные функции
Частично рекурсивные функции
Общерекурсивные функции
Задание рекурсивных функций
Мажорируемые неявные функции
Возвратная рекурсия и функция Фибоначчи
Эффективная перечислимость и распознаваемость
Нерекурсивные и непримитивно рекурсивные функции
Границы применимости формальных моделей алгоритмов
Задачи к главе
Сложность алгоритмов
Сравнение функций с точки зрения сложности
Полиномиальные и экспоненциальные алгоритмы
Временная и пространственная сложность машин Тьюринга
Задачи к главе
Краткий справочник имен
Список литературы