Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М., 1987. -288 с.
Понятие алгоритма является одним из наиболее фундаментальных понятий информатики и математики. Систематическое изучение алгоритмов привело к созданию особой дисциплины, пограничной между математикой и информатикой—теория алгоритмов. В книге дается обзор важнейших достижений теории алгоритмов за последние полвека, т. е. с момента зарождения этой теории. Излагаются в систематизированном виде основные открытия, связанные с понятием алгоритма, приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др. Рассматривается влияние теории алгоритмов на алгоритмическую практику.
Для специалистов по математике, информатике, кибернетике, а также для студентов вузов.
Содержание
Предисловие........................
Обозначения и терминология................
Введение . .....................
Часть I. Основные открытия общей теории алгоритмов.....
§ 1.0. Предварительные понятия теории алгоритмов: конструктивные объекты и их ансамбли» локальные свойства и локальные действия.............
1.0.1. Первые примеры конструктивных объектов: слова и деревья (18). 1.0.2, Конструктивные объекты: попытка общего описания (19). 1.0.3, Локальные свойства и локальные действия: неформальное изложение (21). 1.0.4. Колмогоровские комплекси (22). 1.0.5. (Б, /г)-комплексы (24). 1.0.6. Ансамбли (25). 1.0.7, Локальные свойства я локальные действия: формальное определение (27).
§ 1.1. Общее понятие алгоритма как самостоятельное (отдельное) понятие ................
1.1.1. X — К-алгоритмы (34).
§ 1.2. Представительные вычислительные модели....
1.2.1. Машины Колмогорова (35). 1.2.2. Формальные задания (37),1.2.3. Представительные моделя (39).1.2.4. Тезис Чёрча (41), 1.2.5. Языки программирования (41).
Добавление к § 1.2. Машины Шёнхаге...........
§ 1.3. Общее понятие исчисления как самостоятельное (отдельное) понятие. 1.3.1. Исчисления со входом (52). Добавление к § 1.3. Алгебраические примеры .......
§ 1.4. Представительные порождающие модели........
§ 1.5. Выяснение связей между алгоритмами и исчислениями .
§ 1.6. Время и емкость как сложности вычисления и порождения 1.6.1, Машины Тьюринга (66). 1.6.2. Время (69), 1.6.3. Емкость (71). 1.6.4. Норма (74). 1.6.6. Примеры нормированных ансамблей (75). 1.6.6. Ограниченно-искажающие отображения и изоморфизмы (75). 1.6.7. Дополнительные требовании к нормам (75). 1.6.8. Сложности порождения (76). 1.6.9. Эффективные алгоритмы (76), Добавление к § 1.6. Моделирование в реальное время ....
§ 1.7. Вычислимые функции и породимые множества; перечислимые множества; разрешимые множества.......
§ 1.8. Понятие k-рекурсивной функции...........
§ 1.9. Возможность арифметического и даже диофантова представления любого перечиелимого числового множества
§ 1.10. Построение неразрешимого породимого множества . .
§ 1.11. Проблема сводимости Поста ...........
§ 1.12. Понятие относительного алгоритма, или алгоритма с оракулом . ....... ................
§ 1.13. Понятие вычислимой операции ..........
§ 1.14. Понятие программы: программы как объекты вычисления и порождения.....................
1.4.1. Способы программирования (106). 1.14.2. Универсальные алгоритмы и универсальные функции (110), 1.14.3. Главные, или геделевы, универсальные функции (112). 1.14.4. Вычислительные структуры (114). 1.14.5. Экономные по норме, или оптимальные функции (117) Л Л4.6* Программирование исчислений (119). 1.14.7. Преобразования программ (120).
§ 1.15. Понятие нумерации и теория нумераций
1.15.1. Вычислимые нумерации (126). 1.15.2. Нумерованные множества (132). 1.15.3. Операции над нумерованными множествами (133).
§ 1.16. Начало создания инвариантной, или машинно-независимой, теории сложности вычисления..........
11.17. Теория сложности и энтропии конструктивных объектов § 1.18. Удобные вычислительные модели....
Часть II. Основные математические приложения теории алгоритмов .....................
§2.1. Исследование массовых проблем ... 2.1.0. Основные понятия (146). 2.1.1. Семь нерешимых проблем (151), 2.1.2. Массовые проблемы в математике (154). 2.1.3. Массовые проблемы в смысле Медведева (163). 2.1.4. О пользе правильной терминологии (165).
§2.2. Приложения к основаниям математики: конструктивная семантика ..............
§2.3. Приложения к математической логике: анализ формализованных языков логики и арифметики......
§2.4. Вычислимый анализ.............
2.4.0. Ранняя история: Борель и Тьюринг (173). 2.4.1. Конструктивный анализ (175). 2.4.2. Начальные понятия (176). 2.4.3. Главные результаты (178). 2.4.4. Эффективно метрические пространства (179), 2.4.5. Эффективно топологические пространства (180). 2.4.6. Отчасти вычислимый анализ (181), 2,4.7. Эффективно пренебрежимые множества (182)
§2.5. Нумерованные структуры...............
2.5.1. Нумерации программного типа (185). 2.5.2. Квазистандартные нумерации (186). 2.5.3. Конструктивизации (186). 2.5.4. Расширения конструктивных структур (188). 2.5.5. Алгебраически корректные массовые проблемы (189). 2.5.6. Алгоритмические размеры (190), 2.5.7. Конструктивные и конструктивизнруемые модели (195). 2.5.8. Модели арифметики (197).
§2.6. Приложения к теории вероятностей: определения случайной последовательности................
2.6.1. Частотный подход (200), 2.6.2. Каким должен быть класс всех допустимых правил выбора? (206). 2.6.3, Слож-ностный подход (208). 2.6.4. Количественный или теоретико-мерный подход (209). 2.6.5. Соотношения между различными определениями (210), 2.6.6. Конечные последовательности о точки зрения случайности (212),
§ 2.7. Приложения к теории информации: алгоритмический подход к понятию количества информации ....... .
§ 2.8. Оценки сложности решения отдельных задач.....
2.8.1. Верхние оценки (220). 2.8.2. Нижние оценки (223).
§2.9. Влияние теории алгоритмов на алгоритмическую практику 2.9.1. Общее понятие алгоритма и возможность его формализации (225), 2.9.2. Существование нерешимых алгоритмических проблем в математике и нерешаемость многих естественно возникающих проблем (225). 2.9.3. Появление различных понятий сложности вычисления и порождения (225). 2.9.4. Неалгоритмическое описание вычислимых функций (226). 2.9.5. Вычислительные и порождающие модели (226). 2.9.6. Трактовка программ как объектов вычисления (227). 2.9,7. Рассмотрение программ как объектов порождения (227), 2.9.8. Смешанные вычисления (227). 2.9.9.Методы программирования (229). 2.9.10. Программирование как вторая грамотность (229). 2.9.11. Математическая логика и вычислительная техника (230).
Дополнение. О вероятностных алгоритмах (как использование случайности позволяет укорачивать вычисления)
§ Д.1. Предварительные замечания...........
§ Д.2. Основные результаты..............
§ Д.З. Формальные определения............
Список сокращений.....................
