1626435694-d107b4090667f8488e7fa1ea1b3d0faa (Ершов 1977 - Введение в теоретическое программирование)

А. П. КРШОВ ВВЕДЕНИЕ В ТЕОРЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ БЕСЕДЫ О МЕТОДЕ Допущено Министерстюм енюиего и среднею сп грюл но о оброгооание СССР е кпчестее учебного пособия Аы студентое аргос, обучающиеся ко спеуиалености «Прикладное математичке ИЗЛАТЕЛЬСТВО уНАУКА» ГЛАВНАЯ РЕЛАКНИЯ ° ВИЗИКОгМАТЕМАТИЧЕСКОН ЛИТЕРАТУРЫ МОСКВА 1977 5(8 Е 80 УДК 5(9.95 Введение в теоретическое программирование (беседы о методе).

А. П. Е р ш о в. Главнан редакция фкзиьо-математической литературы квд-ва «Наука», 5(., 1977. Андрей Петрович Ершов ВВЕДЕНИЕ В ТЕОРЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ (беседы о методе) М., 1977 г.. 288 отр. е илл. Редактор Г. Я. Пирогова Технический редактор Е. В. Морозова Корректор Т. С. В айсберг сдано в набор ! 5,07л977 г, подписано н печати 17.1!л977 г. Бумага ббх90%» Фиа. печ. л. 18. Условн. печ. л.

!8. Уч.-иад. л. 18,48. Тираж 55 000 знз. Т-2071!. Цена ннвги 80 коп. Запев Га 020. Издательство «Наука» Глазная редакция физино-математической дитераттж» П701.Москва, В-71, Ленинский проспект, 15 5-я типография изд-ва «Наука», 020077, Нозоеибиос«. 77. Станиславского, 25 Е 20208 (88БЗ-33-3( — 77 Оо«3(02)-77 © Главная недавняя физико-матеиатичЕской готевагтоь« издатель«гав «Наука». 19)7 Книга представляет собой цикл лекций, написанных в виде беседы с читателем.

Подробно рассматрнвак»тся две, классические аадачп теоретического 'программпрования, решения которых н развитые на этих решенгях методы привели к созданню теоретического программирования как самостоятельной математической дисциплины. Зто — задача вкономии памяти в схемах Лаврова и задача построения полной системы преобравований в схемах Янова. Книга рассчитана на студентов вузов.

ОГЛАВЛЕИИЕ 1!редпсловпе Г л а в а 1. Содержательный анализ задачи .. 1 1Л. Краткое повторение программирования 1 1.2. Накопление фантов. 1!инейвые программы 1 1.3. Накопление фактов. Программы оощего вида 1 1.4. Накопление фактов. Подведение итогов .. Г л а в а 2. Постановка задачн и общая теории 1 2.1. Краткое повторение матеыатических основ 1 2.2. Исходные определения 1 2.3. Общая тьюрня 52 бе 83 Г л а в а 3.

Алгоритмизацня 1 ЗЛ. Ииформациояный граф 1 3.2. Граф несовместимости 1 З.З. Раскраска вершин графа. Общее псслеаоваяие 1 3.4. Раскраска вершин графа. Поиск алгоритма Г л а в а 5. Заключительный анализ 1 5.1. Связь с теорией и практикой 1 5.2. Исторический обзор 168 168 179 Глав 1 1'лав 1 1 1 1 Часть 1 ЭКОНОМИЯ ПАМЯТИ В ОПЕРАТОРНЫХ СХЕМАХ а 4. Реализации 4Л.

Вступление . 4.2. Структурированное програмгпгроваиие . 4.3. Общая организация зкономии памяти 4.4. Каноническое распределение памяти 1.5. Получение графа несоачестимости 4.6. Раскраска вершин графа Часть П ПРЕОБРАЗОВАНИЯ СХЕМ ЯНОВА а 6. Краткое повторение математической логики 6Л. Логические формулы н булезы функции 6.2. Алгебра логики . 6.3. Исчисление высказываний...

9 9 14 , 29 43 90 90 99 !ГО !28 143 143 445 151 153 160 164 189 189 200 210 ОГЛАВЛЕНИЕ Р л а в а 7. Определение схем Янова . 5 7Л. Начальные наблвдения 4 7.2. Поиск основных определений 4 7.3. Эквивалентность схем Янова Г л а в а 8. Исчисление равносильных преобразований 4 8Л. Построение исчисления $ 8.2. Корректность ксчислеиия $ 8.3. Канонические схемы и технические теоремы $8.4. Полнота начисления... $8.5. Вше один исторяческий обзор Указатель терминов 226 226 239 245 254 254 265 279 276 284 287 ПРЕДИСЛОВИЕ Для автора эта книга носит экспериментальный характер. Положительным исходом этого эксперимента будет заполнение некоторого пробела в математической литературе.

Насколько, однако, актуально ааполнение этого пробела, покажет время, а пока автор постарается объяснить предпосылки своего эксперимента. Книга адресована в первую очередь тем, кто изучает математику. Целью математического образования является получение математических знаний и выработка умения применять эти знания либо в решении прикладных задач, либо в строительстве и перестройке самого постоянно раавивающегося здания математики. К сожалению, в той части математического образования, которая определяется. учебными планами и обязательными занятиями, имеет место заметный разрыв между его информационным и творческим компонентами. В значительной степени атот разрыв неизбежен. Большой объем накопленных ананий, впрессованный в учебник или лекционный курс, просто'не оставляет времени и места для познания природы и объема творческих усилий, затраченкых на добывание этих знаний.

Беаупречная логика в организации лекционного материала, совершенство в его подаче делают для слушателей неааметными швы и элементы конструкций, создают у студентов ощущение незыблемости идеального; они чувствуют себя скорее посетителями храма науки, нежели его обитателями и тем более строителями. Разделы учебного плана„ требующие активной работы студентов (упражнения, практикумы) ~часто носят тренировочный, целевой характер, при котором отсутствует элемент постановки задачи или поиска метода решения, столь необходимый для развития творческого воображения. Общеиавестно, что именно первые три года учебы в вуае являются решающими для формирования профессионального, а аачастую и общего мировоззрения студента.

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

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

Родившись частично из практических потребностей, частично из желания познать природу новых явлений, вызванных электронными вычислительными машинами (ЭВМ1, теоретическое программирование, освоив средства и понятия фундаментальных математических дисциплин — логики, теории алгоритмов, алгебры П комбинаторики, начинает в дополнение к этому постепенно формировать собственный круг понятий и методов. Рассказать о некоторых из них — одна из задач книги, хотя н не главнаж Главная цель книги — на примере подробного рассмотрения двух аадач, решение которых сыграло очень ва)Иную роль в появлении теоретического программирования как првдмета, объяснить ход мысли при решении этих задач, продеповстрировать математический метод мышления в действии, внимательно проанализировать атапы содержательного анализа и постановки задачи, раскрыть эстетическую компоненту в поиске решения, другими словами, сделать читателя активным свидетелем процесса получения математического результата.

Эта цель Предопределила форму излонгення: книга написана в виде беседы с читателем и предназначена больше для чтении, нежели изучения. В первой части рассматривается задача акопомии памяти в операторных схемах программ. Конструкции и понятия, вошедшие в теоретическое программирование в связи с ре|пением этой аадачи, не только внесли существенный вклад в развитие йредмета, но и стали основой широкого класса преобразований программ, применяемых в системах автоматизации программирования и при проверке правильности программ.

Задача экономии памяти рассматривается как пример решения прикладной задачи с применением математических методов. Изложение разбито на главы, в каждой из которых анализируется один из неотьемлемых этапов полного решения прикЛадной задачи: содержательная постановка задачи, точная постановка и общая теория, поиски конструктивного метода решения, затем его алгоритмизацяя и, наконец, составление программ на алгоритмическом языке.

пгвдисловив Во второй части излагается теория операторных схем Янова— классическая работа, общепризнано послужившая началом математической теории программирования. В созданной А. А. Ляпуновым и Ю. 11. Яновым модели программ последний рааработал формальное исчисление, в котором полностью решалась вадача распознавания эквивалентности моделей программ и строилась система независимых преобразований программы в любую, ей эквивалентную. Теория операторных схем Янова разбирается в этой книге как методологический пример распространения развитой математической теории (в данном случае формального исчисления высказываний) на новый класс явлений и обьектов— операторных схем н их конфигураций.

Еще несколько слов в обоснование предмета изложения. Как известно, программирование сейчас становится массовой профессией. К сонсалению, как в преподавании программирования, так и в его повседневной практике зачастую преобладает поверхностный, рецептурный подход к его научению и применению, при котором элементарная грамотность во владении алгоритмическими языками представляется чуть ли не исчерпывающим содерз;авнем профессии. Разрыв между высоким математическим зарядом, получаемым математикамн-программистами, и обыденностью рутинной работы по составлению программ создает у некоторых ощущение девальвации их математической квалификации при занятии программированием. Автор надеется, что содержание этой книги поможет практикующим программистам увидеть точки приложения математических методов к объектам н содержанию их деятельности. Другой «удобной» чертой теоретического программирования является то, что ата наука рождается у нас на глазах.

Это поаволяет более живо и достоверно проследить механизм добывания научных результатов и этапы развития предмета. Одним из признаков молодости науки является преобладание прямых методов доказательств и элементарности постановки многих задач. Это также делает изложение более живым, непосредственным и ке требующим высокого порога предварительного знания. Наконец, последним по счету, но не по вал'ности соображением является то, что эта область совпадает с конкретными научными интересами автора,что дает ему возможность излагать материал, полученный из первых рук.

Элементарность 'изложения позволила сделать содержание книги аамкнутым и не требующим обязательного предварительного чтения других работ. Тот минимум начального знания, которое все же считается полезным или необходимым, перечисляется или кратко излагается в повторнтельных параграфах, вставленных в нужных местах. Говоря об элементарности наложения, автор все же должен предупредить читателя, что возможность постигать ПРеднсловип содержание книги в темпе чтения будет требовать от него постоянной концентрации внимания и работы мысли.