Читать онлайн «Теория алгоритмов. Основные открытия и приложения»

ББК 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.