Читать онлайн «Введение в теоретическое программирование»

А. П. ЕРШОВ ВВЕДЕНИЕ В ТЕОРЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ БЕСЕДЫ О МЕТОДЕ Допущено Министерством высшего и среднего специального образования СССР в качестве учебного пособия для студентов вузов, обучающихся по специальности «Прикладная математика» ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1977 518 E80 УДК 519. 95 Введение в теоретическое программирование (беседы о методе). А. П. Ершов. Главная редакция физико-математической литературы изд-ва «Наука», М. , 1977. Книга представляет собой цикл лекций, написанных в виде беседы с читателем. Подробно рассматриваются две, классические задачи теоретического "программирования, решения которых и развитые на этих решениях методы привели к созданию теоретического программирования как самостоятельной математической дисциплины. Это — задача экономии памяти в схемах Лаврова и задача построения полной системы преобразований в схемах Янова. Книга рассчитана на студентов вузов. Андрей Петрович Ершов ВВЕДЕНИЕ В ТЕОРЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ (беседы о методе) М. , 1977 г. , 288 стр. с илл. Редактор Г. Я. Пирогова Технический редактор Е. В. Морозова Корректор Т. С. Вайсберг Сдано в набор 15. 07. 1977 г. Подписано к печати 17. 11. 1977 г. Бумага 60χ907ιβ. Физ. печ. л. 18. Условн. печ. л. 18. Уч. -изд. л. 18,48. Тираж 55 000 экз. Т-207И. Цена книги 80 коп. Заказ № 620. Издательство «Наука» Главная редакция физико-математической литературы 11701, Москва, В-71, Ленинский проспект, 15 4-я типография изд-ва «Наука», 630077, Новосибирск, 77, Станиславского, 25 ρ 20204 — ШПо по о» 77 (©Главная редакция Пго/по\ пп "в-оо-01 — ι/ ν^физико-математической ллтератуиь» VOQ(02)-77 издательства «Наука», 1977 ОГЛАВЛЕНИЕ Предисловие 5 Часть I ЭКОНОМИЯ ПАМЯТИ В ОПЕРАТОРНЫХ СХЕМАХ Г л а в а 1. Содержательный анализ задачи 9 §1. 1. Краткое повторение программирования 9 § 1. 2. Накопление фактов. Линейные программы 14 § 1. 3. Накопление фактов. Программы общего вида ч 29 § 1. 4. Накопление фактов. Подведение итогов 43 Глава 2. Постановка задачи и общая теория 52 § 2. 1. Краткое повторение математических основ 52 § 2. 2. Исходные определения 62 § 2. 3. Общая теория . . « ♦ 83 Глава 3. Алгоритмизация ♦ « 90 § 3. 1. Информационный граф 90 § 3. 2. Граф несовместимости 99 § 3. 3. Раскраска вершин графа. Общее исследование 110 § 3. 4. Раскраска вершин графа. Поиск алгоритма 128 Глава 4. Реализация 143 § 4. 1. Вступление 143 § 4. 2. Структурированное программирование 145 § 4. 3. Общая организация экономии памяти 151 § 4. 4. Каноническое распределение памяти 153 § 1. 5. Получение графа несовместимости 160 § 4. 6. Раскраска вершин графа 164 Глава 5. Заключительный анализ 168 § 5. 1. Связке теорией и практикой 168 § 5. 2. Исторический обзор 179 Часть II ПРЕОБРАЗОВАНИЯ СХЕМ ЯНОВА Глава 6. Краткое повторение математической логики 189 § 6. 1. Логические формулы и булевы функции 189 § 6. 2. Алгебра логики 200 § 6. 3. Исчисление высказываний 210 4 ОГЛАВЛЕНИЕ Глава 7. Определение схем Янова 22$ § 7. 1. Начальные наблюдения 226 § 7. 2.