Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения

Москва: Наука, 1987. — 288 с.— (Библиотечка программиста).Понятие алгоритма является одним из наиболее фундаментальных понятий информатики и математики. Систематическое изучение алгоритмов привело к созданию особой дисциплины, пограничной между математикой и информатикой — теории алгоритмов.
В книге дается обзор важнейших достижений теории алгоритмов за последние полвека, т. е. с момента зарождения этой теории. Излагаются в систематизированном виде основные открытия, связанные с понятием алгоритма, приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др. Рассматривается влияние теории алгоритмов на алгоритмическую практику.
Книга предназначена для специалистов по математике, информатике, кибернетике, а также для студентов вузов.Предисловие
Обозначения и терминология
Введение
Основные открытия общей теории алгоритмов
Общее понятие алгоритма.
Представительные вычислительные модели.
Общее понятие исчисления.
Представительные порождающие модели.
Связи между алгоритмами и исчислениями.
Вычислимые функции и породимые множества.
Понятие μ-рекурсивной функции.
Построение неразрешимого породимого множества.
Проблема сводимости Поста.
Понятие относительного алгоритма, или алгоритма с оракулом.
Понятие вычислимой операции.
Понятие программы: программы как объекты вычисления и порождения.
Понятие нумерации и теория нумераций.
Начало создания инвариантной, или машинно-независимой, теории сложности вычисления.
Теория сложности и энтропии конструктивных объектов.
Удобные вычислительные модели.
Основные математические приложения теории алгоритмов
Исследование массовых проблем.
Приложения к основаниям математики.
Приложения к математической логике.
Вычислимый анализ. Нумерованные структуры.
Приложения к теории вероятностей.
Приложения к теории информации: алг. подход к понятию количества информации.
Оценки сложности решения отдельных задач.
Влияние теории алгоритмов на алгоритмическую практику.
Список сокращений
Список литературы
Именной указатель.
Предметный указатель.