ББК 22. 18
У77
УДК 519. 6
Успенский В. Д. , Семенов А. Л. Теория алгоритмов;
основные открытия н приложения. — М. : Наука. Гл. ред. фнз. -мат. лит. , 1987. — (Б-чка программиста). — 288 с. Понятие влгоритма является одним из наиболее фундаментальных
понятий информатики и математики. Систематическое изучение алго-
алгоритмов привело к созданию особой дисциплины, пограничной между
математикой и информатикой — теория алгоритмов. В книге дается обзор важнейших достижений теории алгоритмов
за последние полвека, т. е. с момента зарождения этой теории. Изла-
Излагаются в систематизярованном виде основные открытия, связанные
с понятием алгоритма, приложения теории алгоритмов к математиче-
математической логике, теории вероятностей, теории информации и др. Рассмат-
Рассматривается влияние теории алгоритмов на алгоритмическую практику. Для специалистов по математике, информатике, кибернетике,
а также для студентов вузов. Библиогр. 465 назв. Рецензент
член-корреспондент АН СССР Ю. Л. Ершов
Владимир Андреевич Успенский,
Алексей Львович Семенов
теория алгоритмов? основные
открытия и приложения
Серия; «Библиотечка программиста», № 49
Редактор Л. Р. Полвкоеа
Художественный редактор Р. М. Коровина
Технический редактор Б. В. Морозова
Корректоры ?. 10. Рынагоеа, Н. Б. Румянцева
ИБ № 82406
Сдано в набор 19. 05. 86. Подписано к печати 20. 01. 87. Т-0Б219. Формат
84x108/32. Бумага типографском № 2, Гарнитура литературная. Печать
высокая. Усл. пёч. л. 15,12. ' Усл. кр. -отт. 15,33. Уч. -изд. л. 18,22. Тираж 25000 экз. Заказ № 2548.
Цена 1 р. 20 к. Ордена Трудового Красного Знамени издательство *Наука*
Главная редакция физико-математической лнтературы
117071 Москва В. 71, Ленинский проспект, 15
Ордена Октябрьской Революции н ордена Трудового", Красного Знамени МПО
«Первая Образцовая типография» имени А. А. Жданова Союзполнграфпрома при
Государственном комитете СССР по делам издательств, полиграфии и книжной
торговлн. П-30Б4 Москва М-54, Валовая, 28
¦Отпечатано в\типографии № 2 издательства «Наука». 121099 Москва Г-99,
Шубинскнй пер», 6. Главная редакция
физико-математической
лнтературы, 1987
СОДЕРЖАНИЕ
Предисловие
Обозначения и терминология
Введение ,,,,. . . Часть I. Основные открытия общей теории алгоритмов . . .
1,0, Предварительные понятия теории алгоритмов: конструк-
конструктивные объекты и их ансамбли, локальные свойства и ло-
локальные действия
1. 0. 1. Первые примеры конструктивных объектов: слова
и деревья A8). 1. 0. 2. Конструктивные объекты: попытка
общего описания A9). 1. 0. 3. Локальные свойства и ло-
локальные действия: неформальное изложение B1). 1. 0. 4. Колмогоровские комплексе! B2). 1. 0. 5. (Б, ^-комплексы
B4). 1. 0. 6. Ансамбли B5). 1. 0. 7. Локальные свойства
я локальные действия: формальное определение B7). § 1,1, Общее понятие алгоритма как самостоятельное (отдельное)
понятие
1. 1. 1. X — К-алгоритмы C4). § 1,2! Представительные вычислительные модели . ... ...
1. 2. 1. Машины Колмогорова C5). 1. 2. 2. Формальные
задания C7). 1. 2. 3.