Читать онлайн «Теория алгоритмов: основные открытия и приложения»
Автор Успенский В.А.
Успенский В. А. , Смирнов А. Л. “Теория алгоритмов: основные открытия и приложения”, - М. : Наука, гл. ред. ф. -м. лит, 1987г – 288с.
TOC \o "1-3" ПРЕДИСЛОВИЕ PAGEREF _Toc515447464 \h 2
ОБОЗНАЧЕНИЯ И ТЕРМИНОЛОГИЯ PAGEREF _Toc515447465 \h 8
ВВЕДЕНИЕ PAGEREF _Toc515447466 \h 11
1. 0. Предварительные понятия теории алгоритмов: конструктивные объекты и их ансамбли, локальные свойства и локальные действия PAGEREF _Toc515447467 \h 17
1. 1. Общее понятие алгоритма как самостоятельное (отдельное) понятие PAGEREF _Toc515447468 \h 34
1. 2. Представительные вычислительные модели PAGEREF _Toc515447469 \h 42
1. 3. Общее понятие исчисления как самостоятельное PAGEREF _Toc515447470 \h 58
(отдельное) понятие PAGEREF _Toc515447471 \h 58
1. 4. Представительные порождающие модели PAGEREF _Toc515447472 \h 84
1. 5. Выяснение связей между алгоритмами и исчислениями PAGEREF _Toc515447473 \h 86
1. 6. Время и емкость как сложности вычисления и порождения PAGEREF _Toc515447474 \h 90
1. 7. Вычислимые функции и породимые множества; перечислимые множества; разрешимые множества PAGEREF _Toc515447475 \h 108
1. 8. Понятие рекурсивной функции PAGEREF _Toc515447476 \h 122
1. 9. Возможность арифметического и даже диофантова представления любого перечислимого числового множества PAGEREF _Toc515447477 \h 125
1. 10. Построение неразрешимого породимого множества PAGEREF _Toc515447478 \h 128
1. 11. Проблема сводимости Поста PAGEREF _Toc515447479 \h 132
1. 12. Понятие относительного алгоритма, или алгоритма с оракулом PAGEREF _Toc515447480 \h 138
1. 13. Понятие вычислимой операции PAGEREF _Toc515447481 \h 144
1. 14. Понятие программы: программы как объекты вычисления и порождения PAGEREF _Toc515447482 \h 150
1. 15. Понятие нумерации и теория нумераций PAGEREF _Toc515447483 \h 176
1. 16. Начало создания инвариантной, или машинно-независимой, теории сложности вычисления PAGEREF _Toc515447484 \h 194
1. 17. Теория сложности и энтропии конструктивных объектов PAGEREF _Toc515447485 \h 197
1. 18. Удобные вычислительные модели PAGEREF _Toc515447486 \h 205
ИМЕННОЙ УКАЗАТЕЛЬ PAGEREF _Toc515447487 \h 209
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ PAGEREF _Toc515447488 \h 219
ПРЕДИСЛОВИЕ
Понятие «алгоритм» давно уже стало привычным не только для математиков: оно является концептуальной основой разнообразных процессов обработки информации; именно наличие соответствующих алгоритмов и обеспечи вает возможность автоматизации таких процессов. Вместе с математической логикой теория алгоритмов образует тео ретический фундамент современных вычислительных наук (см. [Семенов, Успенский, 1986] 1)).
Не всегда достаточно отчетливо осознается, однако, что само слово алгоритм содержит в своем составе преобразо ванное географическое название, а именно слово Хорезм. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока, чье имя — Мухаммад ибн Муса ал-Хорезми (причем «ал-Хорезми» означает «Хо-резмиец»). Он жил приблизительно с 783 по 850 гг. , и 1983 г.
TOC \o "1-3" ПРЕДИСЛОВИЕ PAGEREF _Toc515447464 \h 2
ОБОЗНАЧЕНИЯ И ТЕРМИНОЛОГИЯ PAGEREF _Toc515447465 \h 8
ВВЕДЕНИЕ PAGEREF _Toc515447466 \h 11
1. 0. Предварительные понятия теории алгоритмов: конструктивные объекты и их ансамбли, локальные свойства и локальные действия PAGEREF _Toc515447467 \h 17
1. 1. Общее понятие алгоритма как самостоятельное (отдельное) понятие PAGEREF _Toc515447468 \h 34
1. 2. Представительные вычислительные модели PAGEREF _Toc515447469 \h 42
1. 3. Общее понятие исчисления как самостоятельное PAGEREF _Toc515447470 \h 58
(отдельное) понятие PAGEREF _Toc515447471 \h 58
1. 4. Представительные порождающие модели PAGEREF _Toc515447472 \h 84
1. 5. Выяснение связей между алгоритмами и исчислениями PAGEREF _Toc515447473 \h 86
1. 6. Время и емкость как сложности вычисления и порождения PAGEREF _Toc515447474 \h 90
1. 7. Вычислимые функции и породимые множества; перечислимые множества; разрешимые множества PAGEREF _Toc515447475 \h 108
1. 8. Понятие рекурсивной функции PAGEREF _Toc515447476 \h 122
1. 9. Возможность арифметического и даже диофантова представления любого перечислимого числового множества PAGEREF _Toc515447477 \h 125
1. 10. Построение неразрешимого породимого множества PAGEREF _Toc515447478 \h 128
1. 11. Проблема сводимости Поста PAGEREF _Toc515447479 \h 132
1. 12. Понятие относительного алгоритма, или алгоритма с оракулом PAGEREF _Toc515447480 \h 138
1. 13. Понятие вычислимой операции PAGEREF _Toc515447481 \h 144
1. 14. Понятие программы: программы как объекты вычисления и порождения PAGEREF _Toc515447482 \h 150
1. 15. Понятие нумерации и теория нумераций PAGEREF _Toc515447483 \h 176
1. 16. Начало создания инвариантной, или машинно-независимой, теории сложности вычисления PAGEREF _Toc515447484 \h 194
1. 17. Теория сложности и энтропии конструктивных объектов PAGEREF _Toc515447485 \h 197
1. 18. Удобные вычислительные модели PAGEREF _Toc515447486 \h 205
ИМЕННОЙ УКАЗАТЕЛЬ PAGEREF _Toc515447487 \h 209
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ PAGEREF _Toc515447488 \h 219
ПРЕДИСЛОВИЕ
Понятие «алгоритм» давно уже стало привычным не только для математиков: оно является концептуальной основой разнообразных процессов обработки информации; именно наличие соответствующих алгоритмов и обеспечи вает возможность автоматизации таких процессов. Вместе с математической логикой теория алгоритмов образует тео ретический фундамент современных вычислительных наук (см. [Семенов, Успенский, 1986] 1)).
Не всегда достаточно отчетливо осознается, однако, что само слово алгоритм содержит в своем составе преобразо ванное географическое название, а именно слово Хорезм. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока, чье имя — Мухаммад ибн Муса ал-Хорезми (причем «ал-Хорезми» означает «Хо-резмиец»). Он жил приблизительно с 783 по 850 гг. , и 1983 г.
