1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 51
Текст из файла (страница 51)
Затем зги переменные замещаются в логическом выражении найденными термами, которые считаются термами-выражениями. Например, для последовательности (х: = ) (х), у:= й(у), г:=' у(х, у)) и логического выран«ения р (х, ) (г)) получится выражение р Ц (х), ~ (у (/ (х), й (у)))).
234 Фрагмент М, соответствующий фрагменту К, совпадает с фрагментом М„соответствующим фрагменту К,. в) Уэ не является баэовым фрагментом. В этом случае для каждой той переменной памяти исходной схемы, которая входит хозя бм в одно выходное условие фрагмента Ум эаводится переменная-дублер. Выходные последовательности для выходов фраз мента К совпадают с выходными последовательностями соответствующих выходов фрагментов Я, н К . Для тех выходов, которые являются выходами фрагмента Я, выходные условия получаются иэ соответствующих выходнйх условий фрагмента Яз заменой всех встречающихсн в них переменных исходной схемы на переменные-дублеры. Для выходов К, являющихся вь«ходами фрагмента Кз, выходные условия имеют вид «э,' /««и» где «р« — условия выхода 1 фрагмента К, но в нем все переменные заменены па переменные-дублеры, а яз — условие выхода ) фрагмента Уэ.
Фрагмент Ж, соответствующий фрагменту л, имеет внд (Мм эз « = х,..., э„: = у, если «р«то о„Жз юэаче конец), где Ж, Мэ— фрагменты, соответствующие Я' и Я, переменные э„.. „э„— дублеры переменных х,..., у, а «у«и ૠ— выходные условие н последовательность выхода «фрагмента Кп Пусзь У вЂ” реэулътат эацикливання фрагменза К по некоторому выходу, предположим, для определенности, по первому. Выходные последователъностн для всех выходов, кроме первого, сохраняются (первый выход теряет как выходную последовательность, так и выходное условие). В качестве выходных условий фрагмента К берутся новые логические выражения ят, составленные нэ тех же атомарных формул, что и старые выходные условия «рп но удовлетворяющие следующим требованинм: (а) «уз ~из для всех ))1 (старое условие имплпцнрует новое); (б) пэ '«/...
'«/ я„=1 (совокупность новых условий полна); (в) и« /~я„= О для всех пар ) н й таких, что у ~ хчъ 1 (новые условия вэаимно исключают друг друга). Новые условия легко найти, если эаметнть, что выходные условия представляют собой коньюнкцви атомарных формул илк нх отрицаний. Поэтому, если представизь совокупность старых условий в виде дерева, вершинами которого являются простые лопзческие выражения, а лисзьямн — старые условия, то удаление той вершины, которая ведет к «р, дает новое дерево, листъями которого являются новые условия. Фрагмент М, соответствующий л, имеет вид (Ж, пека «рз цикл и, М конец), где «р, о — выходные условие и последовательность для К и М, — фрагмент, соответствующий К,.
После того, как построены структурированные фрагменты, выходные последовательности и условия для всех нормальных фрагментов, начиная с баэовых и кончая максимальным Я««в«„ строится сама структурированная схема, которая имеет внд (старт, Мщд„, если я то о иначе ' если я то о ниаче...
яы. Введение выходных последовательностей и условий для нор- мальных фрагментов поэволяет сначала расщепить заданную схе- му на отдельные ветви-альтернативы, а эатем скомпоновать иэ них структурированные операторы. Дополнительные переменные обеспечивают воэможность «стягивания» раэбросанных по схеме условий выхода иэ цикла в одно условие проверки окончания структурированного оператора цикла. С этой целью переменные- дублеры эапоминают состояния памяти в тех точках исходной схемы, где воэможвы выходы иэ цикла в исходной схеме, а про- верка осуществляется в одном месте. Д В стандартной схеме 8м,» на рис.
10.3 выделены нормальные фрагменты Кы..., Я'», Я;~,«(более мелкие фрагменты не пока- эаны). Прокллюстрируем на примере этой схемы описанный выше алгоритм. В важдом иэ выделенных фрагментов выходы считаем упорядоченными слева направо. Для каждого фрагмента Я; (3 = 1,..., шах) выпишем выход- ные последовательности и условия, а также фрагмент Ж;. Фрагмент К,. Вых.
посл.: (х:= у (х)), (х:= у (х)), (х:= у (х)). Вых. уел.: р (х), 1Р (х) /~ д (х), ~Р (х) /~ ~д(х). Фрагмент Ж« — пустой, Фрагмент У». Вых. посл.: (х:= у (х)), (х:= у (х)). Вых. усл.: о (х), ~д (х). Фрагмент Ж: пека Р (х) цикл х:=. у(х) конец ' Фрагмент К». Вых. зюсл.: (х:= У (х)), (х: = У (х)).
(х-= У (х)). Вых. уел.: д (х), 3у (х) Л Р (х), М (х) Л 1Р (х) Фрагмент Я вЂ” пустой. Фрагмент х ° . Вых. посл.: (х:= /(х)), (ж= /(х)). Вых. уел.: р (х), )Р (х]. Фрагмент Ж«: пека у (х) цикл х:= /(х) конец Фрагмент К». Вых. посл.: (х:= У(х)) (х:= /(х)), (х:= Ю(х)). Вых. уел.: д (у) Д Р (х)1 т (у) Л ~Р (х)~ где у — новая переменная, дублирующая х. Фрагмзнт Ж»: (Ж», у = х, если у (х) то х:= у (х), Ж иначе конец). Фрагмент Ув««- Вых. посл.: (х:= У (х))е (х:= у(х)) Вых. уел,: у(у). )т (у) Фрагмент Я»«- (Я„пока д (у) /~, р (х) цикл х:= 7 (х), Я, конец).
Искомая структурированная схема имеет в|щ: (старт (х), иова Р (х) цикл щ= у (х) конец, у: х, если д (х) чо х:= я (х), пека д (х) цикл х:= У(х) конец иначе конец, е а д (р) Л р (х) цикл х:= у (х), пека р (х) цнкл х:= д (х) венец, у:=х, если д(х) те ж= л(х), пеяа д (х) цикл х:= у (х) конец иначе конец певец, ееаэ д (р) те х:= у (х) иааче ж= а (х) конец, егеп (х)). Переменная у используется для того, чтобы запомнить состоя- ние памяти в точке а схемы Яте.е, где существует воэможность выхода иэ цикла, и провервть соответствующее условие выхода в точке Ь, где также можно уйти иэ цикла, во состояние памяти Приведенный пример показывает, что получаинцаяся струк- туркровавная схема достаточно сложна и плохо обоэрнма.
Ашкрофт и Манна предложили другой алгоритм, который требует введе- ния антеряретнроваивых логических переменных со эиачениями э (истнна) к О (ложь). Алгоритм поаволяет строить структуриро- ванные схемы так, что прп обратной трансляцюг с помощьто ал- горитма, описанного в теореме т0.1, волучаютсл стандартные схе- мы той же структуры, что и исходные. Схема Ятес транглвру ется таким методом в следующую структурированную схему, гж е — дополнительная логкческан переменная: (старт (х), Ф:= 1, пека Ф цввл пека р (х) цнкл х:= л (х) конец, если д (х) те х:= у (х), пена д (х) цикл х:=у (х) конец, есле р (х) те х:=- у (х). нивке х:= у (х), г:= О жжец иначе х:= я(х), и= О конец конец, степ (х)).
Схему Ю, нельзя транслировать в структурированную, ие добавляя новых переменных. 3 а д е и и е 10Л. А. Покажите, что клесс структурироееикмл стем с логвческвма оперецилми трекслкруем э класс стеидерткмк схем. Б. Постройте елгорктм траисллцкк стеклертимх схем к структурироеэкаме с логическкмк оперецвкми, лобеелкк счетчики вместо логических перепелки к. В. Тракслируйте к структурировеккме скемм Л .е к Яс.е ие гл. 4. СПИСОК ЛИТЕРАТУРЫ 1.
А х о А., Х о п к р о ф т Дж., У л ь и а и Дж. Построение и аиалвэ вычислительных алгоритмоз.— М.: Мир, 1979.— 536 с. 2. Б а р р о в Д. Рекурсизвые методы з нраграммврозаиив.— М.: Мир, 1974.— 80 с. 3. Б яр к г оф Г. Теорвя решеток.— Мл Наука, 1984.— М4 с. 4. Б уд а А. О. Абстрактные машины программ.— Преприат/ВЦ СО АН СССР.— Новосибирск, 1978.— № 108.— 45 с. 5. Б у л ь о к к о а М.
А. Итератизвне алгоритмы разметки з травсформациовиой машине//Программное обеспечение задач ивформатикв: Сб. статей.— Ноэосвбирск: ВЦ СО АН СССР, 1932.— С. 33 — 52. 6. Г л ушко з В. М. Теорвя авгоматоз и формалъвые преобрааоваииа микропрограмм // Кнбериегика.— 1965.— № 5. — С. 1 — 9. 7. Глушков В.М., Летичезсквй А.
А. 'Георвя дискрствых преобразозателев П Избранные вопросы алгебры в логики. — Новосвбирск: ИМ СО АН СССР, 1973.— С. 5 — 39. 8. Г о д л е з с к в й А. Б. Некоторые спецвальвые случаи проблемы остановки и фузкциовальиов зкавзалеиткости автоматов д Кибернетика.— 1973.— № 4.— С.
90 — 97. 9. Г о д л е в с к в й А. Б. Об одком случае снецвальвой проблемы фуикциоиальвой экзввалеитиости двскретвых преобрааозателей// Кибернетика. — 1974. — № 3. — С. 32 — 36. 10. Г одле в с к вй А. Б. Об одном разрешимом случае специальной проблемы функциональной эквивалентности дискретных преобразователей // Вопросы проектврозавия ЭВМ и других дискретных устровстз.— Киез: ИК АН СССР, 1974.— С.
16 — 40. СС Г о д л е з с к и й А. Б. О связи логике-термальной зкзиаалеитвости схем прогримм с одины случаем специальной проблемм фуикциональвой эквивалентности дискретных нреобрааозателей// Кибериетииа.— 1975, № 5.— С. 32 — 34. 12. Д а л У., Д е й к с т р а Э., Х о о р К. Структурное нрограммвроваиве.— М.: Мир, 1975.— 248 с.
13. Е р ш о в А. П. Операторные алгоритмы! // Проблемы кибернетики: Сб статей. Вып. 3.— М.: Физкатгиа, 1960.— С. 5 — 48. 14. Е р шов А. П. Сведевве задачи эиоиомии памяти при составлении программ к задаче раскраски иершви графов// Доки. АН СССР.— 1962.— Т. 142, № 4.— С. 785 — 787. 15. Е р ш е в А. П. Об операторных схемах Ввоза // Проблемы кибернетики: Сб. статей. Вып.
20.— М.: Наука, 1967.— С. 181 — 200. 16. Е р ш о в А. П. Об операторзшх схемах иад общей к распределенной памятно Д Кибернетика.— 1968, № 4.— С. 63 — 71. 17. Е р ш е в А. П. Современное состояюш теории схем программ П Проблемы кибернетики: Сб. статей. Вып. 27. — М.: Наука, 1973. — С. 87 — МО. 18. Е р шо и А. П., Л я пупов А. А. О формалвэацвв повятвя программы // 'Кибернетика.— 1967.— № 5. — С. 40 — 57. 19.
Е ржев А.П., Сабельфелад В. К. Очерк схемкой теории екурсинвых программ Л Трансляция к модели программ: Сб. статей.— овосибирск: ВЦ СО АН СССР, 1980.— С. 23 — 4™3. 20. Э ы к о н А. А. Теория ковечвйх графов.— Ноаосвбирск: Наука, 1969.— 543 с. 21. И т к и к В. Э. Операторные схемы Ввоза с тождествеввкмк операторама// Труды всесоюавой конференции по программвроэаквю (ВКП1Е вып. А,— Киев: ИК АН УССР, 1968.— С. 27 — 46. 22.
И т к к к В. Э. Логвко-термальная экэвэалеитиость схем программ // Квбсриеткка. — 1972. — г4 1. — С. 5 — 27. 23. И т к к и В. Э. Комбкккроеакпав зкэкэалентность схем программ П Системное и теоретическое программврозавве: Теэ. докл. П! Всесоюэи. симпозиума.— Квшвнеэ. Иад-эо Кжн. Рос. Ук-та, 1974.— С. 174 — 177. 24. К а л у ж в и к Л. А. Об алгорнтмиэацин математических аадач Л Проблемы квбсриепаки: Сб. статей. Вып. 2.— М.: Физматгиз, 1959.— С. 51 — 67. 25. К а с ь я к о в В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
