1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 57
Текст из файла (страница 57)
Еще один исторический обзор Схемы программ А. А. Ляпунова. А. А. Ляпунов, внесший болывой вклад в формирование программирования как научной дисциплинм, был одним иа первых математиков, рааработавшвм в начале 50-х годов символику программирования, сохраняющую и поныне аиачимость принципиальных своих положений. Важнейшим понятием, введевиым А.
А. Ляпуновым, было понятие оператора, являющегося одновременно и единицей действия и единицей конструирования программы. Как единица действия оператор выполняет некоторое преобразование содержимого памяти машины, т. е. отображает одно состояние памяти на другое. Это и объясняет название «операторы Как единица конструирования программы оператор имеет некоторое обовпаченке, показывающее тип оператора, его место в программе, и конкретное содержание оператора (спецификация). Важным свойством оператора было то, что трактовка оператора как единицы действия носит относительный характер. Два оператора А и В, выполненные друг аа другом, осуществляют какое-то совокупное преобразование состояния памяти, т. е.
также образуют некоторый оператор С. Для того чтобы операторы А и В выполнялись подряд, их надо в программе поместить один аа другим: АВ. Их связь с оператором С выглядит тогда таким образом: С = АВ, а информация, например, о том, что А и В можно выполнять в любом порядке, получая один и тот же результат, может быть выражена равенством АВ = ВА. Выражаясь языком алгебры, можно сказать, что операторы программ образуют полугруппу, в которой могут существовать определяющие отношения. Изучение полугруппы операторов приобрело фундаментальную роль в теоретическом программировании. Аналогия двух рядом стоящих операторов АВ с произведением двух чисел делала понятными такие обозначения, введенные А. А.
Ляпуновым, 282 ГЛ. 8. ИСЧИСЛЕНИЕ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ иак Ц А (П В С (1). 1=1 Эта запись обозначает и-кратыое повторение операторов АВС, причем сямволы А(1) и С(1) показывают, что спецификация этих операторов зависит от виачеыкя индекса повторения 1 (например, коочередиое ваятие величии ив последовательности ячеек, образующей вектор). Для записи передач управления в зависимости от условий А.
А. Ляпунов ввел понятие логических операторов, отображающих состояние памяти яа два вмбраыкых значения, скажем 0 и 1 или истина и ложь, и два парных символа, передающую 11 и приемную '„стрелки, употребляемые в программе следующим образом (Р— символ логического оператора): 1 Обозиачевие ( (ыапример, число) яспользуется, чтобы выделять пары соответствующих друг другу приемных и передающих стрелок. При одыом виачеыыи Р управлсиие передается иа оператор, стоящий вслед аа передающей стрелкой „', а при другом — иа оператор, стоящий вслед еа принимающей стрелкой Запись программы по А.
А. Ляпунову состоит из двух частей. Первая часть — схема програ»1мы — образована символами операторов и показывает порядок расположения операторов в программе, а также направления передач улравлекия. Вторая часть — вто спецификация всех операторов, образующих программу.
Вот как примерно выглядела бы в этом символике программа решеиия 50 квадратных уравнений вида аск»+ ь х + + с = 0 (1 = 1, ..., 50, см. пример 9 в $1.8). Схема программы: 50 1 2 1 2 А»Ц(А«(1] А«А«Р«('А«( ~ А» ~ А«А»(1)) А»«СТОП 1=1 Спецкф»иикацыя: А — ввод всех коаффяциектов ак Ь, с (с = 1,..., 50). Л» — перенос коэффицяевтов а, Ь1, с в ячейки а, Ь, с. А, — вычисление дискркмикаита: 1, = 2а, 1» = 2с, дискр = Ь» — 1 гю А, — вычисление заготовок для корней: р = — 5111, 9 = 'г )дискр)(11.
Є— проверка: дискр ( О? Л, — вычисление модуля и аргумента комплексной пары кориеи: с = р'+ 9«, кор1 = г 1, кор2 = агсвш (дlкор1). Л, — вычисление пары действительных корней: кор1 = р+ д, кор2 = р — д. А« — сохранение знака дискримииаита1 приск = 819п (дискр). А » — перенос в массив решений пары корней с-го уравнения. Ам — печать всех решений. Оригияальиая статья А. А. Ляпунова, содержащаи подробпоя опвсаиие его символики, была опубликована в 1-м выпуске «Проблем кибернетики» (М., Физматгиз, 1958, стр.
46 — 74) под иаввапыем «О логических схемах программ». Паучиая жизнь этой методики, получившей иазваыие «операторного метода Ляпунова», началась, однако, горавдО раншие — В 1953 году, сразу после прочтения А. А. Ляпуновым курса лекций «Принципы програм- $ В.Ь. ЕЩИ ОДИН ИСТОРИЧИСКИИ ОБЗОР 283 мирования» в Москойском государственном университете.
На основе операторного метода были созданы первые алгоритмические языки и трансляторы «доалгольного» периода 1955 — 2960 гг, а также разработаны первые формализмы теоретического программирования. Более подробно об этом можно прочесть в работе М. Р. Шура-Буры и автора «Становление программирования в СССР», опубликованной в 5-и номере журнала «Кибернетика» (Квев) за 1976 г. Логическиесхемы алгоритмовЮ.И. Янова.
В 2953 г. А. А. Ляпунов взял к себе в аспиравтуру молодого математика Ю. И. Янова, рекомендовав ему исследовать возможность систематических преобразований логических условшй в схемах программ. Это исследование Ю. И. Яновым было блестяще выполнено, став одной нз классических работ в теоретическом программировании.
Ю. И. Янов рассмотрел следующую модель программ. Память программ состоят из некоторой общей памяти данных и й логических переменных р»,..., рь. Каждый иэ в операторов программы А»,..., Ае действует на всю память данных и может менять некоторые из логических переменных. Логические операторы (названные вм логическими условиями) имеют вид произвольной булевой функции логических переиенных. Вместо стрелок 7 н ' у А. А. Ляпунова' были ванты леван 7 и правая ! полускобки с тем же смыслом. В качестве значений булевых функций брались О (ложь) и ! (исткна). Ложное условие передает управление на правую полускобку, а истинное — на оператор, стоящий за условием.
Ниже следует запись задачи о трех экспертах (9 7.2) в виде «логической схемы алгоритма» по Ю. И. Янову: ) х») А! (х,) ) х» ( А» (х») ) х» ( А» (т») ) х»х» 4/ х»х»х» ~/ х!х»х»( 14 1 ! 2 2 2 з 4 х!ххз( О( ) ) )А1»(хмх») э»=х»( О) )А»»(х», хз)х»=х»! 0 В 4 Ь 7 з э 8 10 О( ) А»» (х», х») х»=х» ) ) )х»х» ~/х»х»х»»7х»х»х») О! ) !! 10 7 0 !1 12 12 12 А(х,х„х)О~ ) ) !4 0!э Ю.
И. Янов не привлекал понятия интерпретации, превращающей схему в программу, а трактовал выполнение схемы как процесс порождения множества значений схемы (последовательностей операторов) по заданной («допустимой») последовательности значений логических условий (конфигурации в нашем рассмотрении). В множество значений схемы включались не только конечные цепочки, выходящие на останов, но и значения, оканчивающиеся пустым циклом, а также бесконечные последовательности операторов.
Две схемы ' объявлялись равносильными (формально эквивалентными в $ 7.3), если они имели совпадающие множества конфигураций. Отношение формальной эквивалентности, совпадающее с приведенным в этой книге И 7.3), было также введено Ю. И. Яновым и называлось слабой равносильностью. Для.обоих видов формальной эквивалентности (т. е.
равносильность и слабая равносильность) Ю. И. Яновым были описаны алгоритмы распозна вания эквивалентности. Алгоритмы не 'опирались иа формальные преобра аования и не использовали в явном виде канонической формы. Для равносильности (но не слабой равносильности) Ю. И. Яновым была построена в виде исчисления полная система преобразований, состоящая из 26 схем аксиом и 4-х правил вывода. Свойство продуктивности наборов не аксиоматнзировалось, поскольку этоне требовалось прн выбранном определении эквивалентности. Свойство достижцмостн также не аксиоматиэнровалось, и вместо аксиом верхней разметки имелось содержательно описываемое правило 284 ГЛ. З. ИСЧИСЛЕНИЕ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ «среааиия» иедопустимых наборов.
Полное изложение результатов )О. И. Янова содержится в его работе «О логических схемах алгоритмов», также опубликованной в 1-и выпуске «Проблем киберяетикиэ рядом с основополагающей работой его учителя (М., Фиэматгиз, 1958, 75 — 127). Работа Дж.Ратледжа.
Америкаяскии математик Дж. Ратледж внес важяый вклад в раавитие теории схем программ. Кстати, именно ои ввел в литературу выражение «схемы (программ) Якова». Ои дал независимое определеиие функциональной эквивалевтиости схем Янова и доказал равно- объемность функциональной и формальной эквивалеитяостей. Изложение в 6 7.8 в аяачительной степени следует методике Дж. Ратледжа. Ов рассматривает схемы Янова в абстрактиой форме, ие связываясь с каким бы то ия было текстуальиым иля графическим представлением схемы. Вместо графя переходов ои использует абстрактное отображение 7 »,Фх Рь -ч- .э ()(~:1) (я — множество операторов и РЬ вЂ” множество наборов логических зиачеиий длины А), которое для оператора А ««ы эя и набора Л «и РА выдает символ оператора Аэ или оюавова эб или оказывается не определенным.
В то же. время иа этоы абстрактном уровяе он вводит понятие канонической (матричвой) формы, в которой все неэквивалеятяые схеэ«ы оказываются различными„ В общих чертах Дж. Ратледж описывает процесс получеиия «всех» эквивалентных схем иэ каяояической фориы, при атом в виде прямого и обратного траязитивяых замыканий оя описывает процессы, аналогичные верхией и нижней раэметкам. Дополнительно Дяс Ратледж делает еще одво существеиное наблюдение„ Назовем пару (Аь Л) — состоянием, пару (Дх, Л) — эаключительяым состоянием, пару (о, Л) — начальным состоянием (о — символ «иачалаэ). Для любой схемы Янова любое состояние (А, Л) (А ш А () (о) ) вадает конечный (может быть, пустой) яабор «иепосредствеиио достижимых» состояиий ((А', Л')), где А' — единственный преемник оператора А(А' '«и лФ Ц Щ)), а любой Л' образует с Л допустимую пару для оператора А'.
Построим граф, вершинами которого будут все возможные состояния, а дуга иэ вершииы-состояиия Р ведет ко всем вершииам-состояииям, непосредственно достигаемым иэ У. Двигаясь вдоль дуг такого графа, мы будем переходить иэ одного состояния в другое, а любой путь от любой начальной вершины (бесконечный, обрывающийся или выходящий яа заключительное состояние) соответствует некоторой конфигурации исходиок схемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
