Понятие алгоритма ивляется одним из наиболее фундаментальных понятий информатики и математики. Систематическое изучение алгоритмов привело к созданию особой дисциплины, пограничной между математикой и информатикой — теория алгоритмов.

В книге даётся обзор важнейших достижений теории алгоритмов за последние полвека, т.е. с момента зарождения этой теории. Излагаются в систематизированном виде основные открытия, связанные с понятием алгоритма, приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др. Рассматривается влияние теории алгоритмов на алгоритмическую практику.

Для специалистов по математике, информатике, кибернетике, а также для студентов вузов.

Библиогр. 465 назв.

Предисловие	6
Обозначения и терминология	11
Введение	13

Ч а с т ь I. Основные открытия общей теории алгоритмов	15

§ 1.0. Предварительные понятия теории алгоритмов: конструктивные
объекты и их ансамбли, локальные свойства и локальные действия	17
1.0.1. Первые примеры конструктивных объектов: слова и деревья
(18). 1.0.2. Конструктивные объекты: попытка общего описания
(19). 1.0.3. Локальные свойства и локальные действия:
неформальное изложение (21). 1.0.4. Колмогоровские комплексы
(22). 1.0.5. (Б, k)-комплексы (24). 1.0.6. Ансамбли (25). 1.0.7.
Локальные свойства и локальные действия: формальное определение
(27).
§ 1.1. Общее понятие алгоритма как самостоятельное (отдельное)
понятие	29
1.1.1. X—Y-алгоритмы (34).
§ 1.2. Представительные вычислительные модели	34
1.2.1. Машины Колмогорова (35). 1.2.2. Формальные задания (37).
1.2.3. Представительные модели (39). 1.2.4. Тезис Чёрча (41).
1.2.5. Языки программирования (41).
Добавление к § 1.2. Машины Шёнхаге	42
§ 1.3. Общее понятие исчисления как самостоятельное (отдельное)
понятие	44
1.3.1. Исчисления со входом (52).
Добавление к § 1.3. Алгебраические примеры	53
§ 1.4. Представительные порождающие модели	62
§ 1.5. Выяснение связей между алгоритмами и исчислениями	63
§ 1.6. Время и ёмкость как сложности вычисления и порождения	65
1.6.1. Машины Тьюринга (66). 1.6.2. Время (69). 1.6.3. Ёмкость
(71). 1.6.4. Норма (74). 1.6.Б. Примеры нормированных ансамблей
(75). 1.6.6. Ограниченно-искажающие отображения и изоморфизмы
(75). 1.6.7. Дополнительные требовании к нормам (75). 1.6.8.
Сложности порождения (76). 1.6.9. Эффективные алгоритмы (76).
Добавление к § 1.6. Моделирование в реальное время	77
§ 1.7. Вычислимые функции и породимые множества; перечислимые
множества; разрешимые множества	78
§ 1.8. Понятие μ-рекурсивной функции	87
§ 1.9. Возможность арифметического и даже диофантова представления
любого перечислимого числового множества	89
§ 1.10. Построение неразрешимого породимого множества	91
§ 1.11. Проблема сводимости Поста	93
§ 1.12. Понятие относительного алгоритма, или алгоритма с оракулом	98
§ 1.13. Понятие вычислимой операции	101
§ 1.14. Понятие программы: программы как объекты вычисления
и порождения	106
1.14.1. Способы программирования (106). 1.14.2. Универсальные
алгоритмы и универсальные функции (110). 1.14.3. Главные, или
гёделевы, универсальны: функции (112). 1.14.4. Вычислительные
структуры (114). 1.14.5. Экономные по норме, или оптимальные
функции (117). 1.14.6. Программирование исчислений (119).
1.14.7. Преобразования программ (120).
§ 1.15. Понятие нумерации и теория нумераций	122
1.15.1. Вычислимые нумерации (126). 1.15.2. Нумерованные
множества (132). 1.15.3. Операции над нумерованными
множествами (133).
§ 1.16. Начало создания инвариантной, или машинно-независимой,
теории сложности вычисления	133
§ 1.17. Теория сложности и энтропии конструктивных объектов	135
§ 1.18. Удобные вычислительные модели.141

Ч а с т ь II. Основные математические приложения теории
алгоритмов	144

§ 2.1. Исследование массовых проблем	146
2.1.0. Основные понятия (146). 2.1.1. Семь нерешимых проблем
(151). 2.1.2. Массовые проблемы в математике (154). 2.1.3.
Массовые проблемы в смысле Медведева (163). 2.1.4. О пользе
правильной терминологии (165).
§ 2.2. Приложения к основаниям математики: конструктивная семантика	165
§ 2.3. Приложения к математической логике: анализ формализованных
языков логики н арифметики	169
§ 2.4. Вычислимый анализ	173
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. Нумерованные структуры	184
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. Приложения к теории вероятностей! определения случайной
последовательности	198
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. Приложения к теории информации: алгоритмический подход
к понятию количества информации	215
§ 2.8. Оценки сложности решения отдельных задач	220
2.8.1. Верхние оценки (220). 2.8.2. Нижние оценки (223).
§ 2.9. Влияние теории алгоритмов на алгоритмическую практику	224
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).

Д о п о л н е н и е. О вероятностных алгоритмах (как использование
случайности позволяет укорачивать вычисления)	231

§ Д.1. Предварительные замечания	231
§ Д.2. Основные результаты	235
§ Д.З. Формальные определения	238

Список сокращений	244
Список литературы	245
Именной указатель	272
Предметный указатель	276

Книги на ту же тему

Информатика, Луенбергер Д. Д., 2008
Машины Тьюринга и рекурсивные функции, Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г., 1972
Арифметика. Алгоритмы. Сложность вычислений: Популярное введение в теорию чисел и арифметическую теорию сложности, Гашков С. Б., Чубариков В. Н., 1996
Задачи по теории множеств, математической логике и теории алгоритмов, Лавров И. А., Максимова Л. Л., 1975
Графы, сети и алгоритмы, Свами М., Тхуласираман К., 1984
Анализ алгоритмов. Вводный курс, Макконнелл Д., 2002
Теорема Гёделя о неполноте, Успенский В. А., 1982
Алгебраическая алгоритмика (с упражнениями и решениями), Ноден П., Китте К., 1999
История информатики в России: учёные и их школы, Захаров В. Н., Подловченко Р. И., Фет Я. И., сост., 2003
Алгебра. Языки программирования. — 2-е изд., перераб., Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л., 1978
Алгоритмы и вычислительные автоматы, Трахтенброт Б. А., 1974
Алгоритмы + структуры данных = программы, Вирт Н., 1985
Введение в теоретическое программирование (беседы о методе), Ершов А. П., 1977
Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры, Кокс Д., Литтл Д., О'Ши Д., 2000
Библиотека алгоритмов 151б—200б: Справочное пособие. Вып. 4, Агеев М. И., Алик В. П., Марков Ю. И., сост., 1981
Машины клеточных автоматов, Тоффоли Т., Марголус Н., 1991
Математическая логика, Клини С. К., 1973
Математическая логика в программировании: Сборник статей 1980—1988 гг., Захарьящев М. В., Янов Ю. И., ред., 1991
Дискретная математика для программистов, Хаггарти Р., 2004
Введение в дискретную математику, Яблонский С. В., 1979
Основания теории множеств, Бар-Хиллел И., Френкель А. А., 1966
Введение в теорию множеств и общую топологию, Александров П. С., 1977
Теория множеств и метод форсинга, Йех Т., 1973
Современная теория множеств: начала дескриптивной динамики, Кановей В. Г. , Любецкий В. А., 2007
Теоретико-множественные модели языков, Маркус С., 1970
Алгебра логики в задачах, Гиндикин С. Г., 1972
Жемчужины теории формальных языков, Саломаа А., 1986
Теория формальных грамматик, Гросс М., Лантен А., 1971
Нечёткие множества в моделях управления и искусственного интеллекта, Аверкин А. Н., Батыршин И. 3., Блишун А. Ф., Силов В. Б., Тарасов В. Б., 1986

elapsed time 0.021 sec

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему