1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 50
Текст из файла (страница 50)
условия, мы будем считать, что граф переходов состоит из абстрактных вершин, которым сопоставлены конкретные операторы и логические условия., Определение схемы Янова. Пусть даны счетное множество предикатных символов ~ — (Р1 Рв ° ° ) и операторных символов Ф = (А„Ав, ...). Условием называется любая логическая формула с предикатными символами из Зо в качестве логических переменных. Оператором А = А (Р) называется пара, состоящая из операторного символа А и некоторого множества (возможно, пустого) Р предикатных символов. Множество Р = Р (А) называется сдвигом оператора А. Гра$ом переходов называется ориентированный граф, множество вершин которого состоит иэ неотрицательного числа преобразователей, неотрицательного числа распознавателей и одного останови.
Каждый преобразователь имеет одного преемника, люмаа аазевм каждый распознаватель — двух чр,улов-озирав преемников. Дуги, исходящие из рааааааглстеаа распознавателя, различаются дш арааааасврь а и называются соответственно плюс-стрелкой и минус-стрел- "~~ ааааае кой. Останов преемника не имеет. Одна вершина в графе переходов называется входной и поааранааарааааа Мечается входной стрелкой. ~ЩГ Пусть (р„..., р„) про ОраРрамаамав извольное непустое 'множество предикатных символов. Схемой Янова О(рп..., Рв) называется любой граф переходов, рас- К познавателям которого сопо- ставлены условия, а преобра; йиюла зователям — операторы; при этом логические переменные Рнс.
7.9. Схема Янова, каждого из условий и каясдого из сдвигов операторов принад'лежат множеству (р,..., Р ), а 'все операторные символы операторов схемы попарно различны. На рис. 7Я приведен пример схемы Янова, который одновременно поясняет принятые нами графические обозначения всех элементов формального определения. % Ьз.
ПОИСК ОСНОВНЫХ ОПРЕДБЛВНИН 2«Э Рис. 7 10 содержит примеры разного рода дегенеративных ~ схем, которые позволят нам, в частности, проверить правильность теории для различных «крайних случаев». в'4 .4Ф в) в) Рис. 7ЛО. Примеры дегеиератиюгых схем Янова. е) Самая нусгаи схема. 6) Многосвязная схема. е) Неполносзизные схемы з) Схема без онератороз. д) Схема без условий. ' На рис. 7.11 изображена схема Янова для «задачи о трех вкспертах».
Сделаем необходимые пояснения к схеме. Три вксперта, Э» Э, и Э„отвечают за принятие или отклонение ГЛ. Е ОПРЕДЕЛЕНИЕ СХЕМ ЯНОВА некоторого документа. Процедура прохождения документа через экспертный совет состоит в следующем. Вначале эксперты понаслышке имеют какое-то предварительное мнение о документах х, = 1 означает, что Э, одобряет документ. Э и Э, — скептики. рис. 7.П. Задача о трех акснертах. Это значит, что если они знают о документе с плохой стороны, то они готовы, не читая документа, отправиться на голосование.
Если же документ понаслышке хорош, то они предпочитают прочитать документ (Аа(хД для Эа и Аа(ха) для Эа», что, естественно, 5 хз. эквивялвнтность схем янОВА может повлиять на их оценку. Э, — доброжелатель и поступает противоположным образом: если документ понаслышке хорош, он готов голосовать, не читая документа, а в противном случае занимается его научением (оператор А«(х,)). После этого имеет место пробное голосование (пронзводящееся по формуле рассмотренной ранее «машины голосования«). Если пробное голосование оказалось единогласным и положительным, то документ считается принятым.
В остальных случаях он становится предметом серии кулуарных бесед. Эти беседы происходят при попарных встречах экспертов (оператор А!! (х!, х!) означает согласительную беседу зкспертов Э, и Э!). Если им удается сблокироваться, то, полагая результат предрешенным, они отправляются на повторное голосование. Серия кулуарных разговоров повторяется, если до этого ни одна иа трех парных бесед к обрааованию блока не привела.
Положительное повторное голосование оаначает принятие документа. В случае отрицательного заключения имеет место переработка документа (оператор А(х„х«, х,)), после чего цикл прохождения документа повторяется. в 7.3. Эквивалентность схем Янова Функциональная эквивалентность. Пусть дана схема Янова Р(р„..., рь) с операторными символами А„..., А . Для того чтобы превратить схему в способную к действию программу, нам нужно дать некоторую интерпретацию ее операторным и предикатным символам, а потом описать алгоритм выполнения интерпретироеанной схемы. Прежде всего аадаемся некоторым множеством Р состояний памяти а: Р = (а). Поскольку мы изучаем такие свойства схем, которые справедливы для любых интерпретаций, природа этого множества нас не интересует. Далее, мы сопоставляем каждому предикатному символу р! (! = 1,..., )с) некоторую функцию-предякат и!(а), отображающую Р на множество логических значений (1, 1): и;: Р-«-(1, Ц.
Сам символ р! будем при этом трактовать как предипатную переменную. Наконец, каждому операторному символу А! () = 1, ..., и) сопоставляется некоторая (возможно, частичная) функция ц!!(с!), отображающая Р в Р: (р! !Р Р После такого сопоставления алгоритм работы интерпретированной схемы выглядит следующим образом. ГЛ.7. ОПРЕДЕЛЕНИЕ СХЕМ ЯНОВА П а ч а л ь н ы й ш а г. Берем произвольное д~В в качество исходного состояния памяти, затем производим присваивание значений всем предикатным переменным: Р7:= п,(д) (7 = 1, ..., Й), после чего передаем управление на входную вершину графа переходов. ща г з ы и о л не н и я.
Пусть и — текущее состояние памяти д = (и„..., Оь) — упорядоченный набор текущих значений предикатных переменных и управление передано на вершину с. а) Пусть Π— останов. Тогда 7( объявляется результатом выполнения схемы в данной интерпретации, а само выполнение завершается. б) Пусть Ю вЂ” распознаватель с условием г'(рм ..., р„).
Вычисляем О = г(Л), и передаем управдение на преемника распознавателя по плюс-стРелке, если и = 1, и на преемника по минус-стрелке, если и = г. в) Пусть Ю вЂ” оператоР Ат(Р7). Вычисляем новое текущее сост (® Каждой предикатной перемени - ~р присваиваем новое значение Р7.= Я;(Ы'), тате чего обр~~уе~~~ новый набор Л~ текущих значени предикатных переменных.
После этого передается управление на единственного преемника опеРатора Ап Поскольку каждый шаг выполнения схемы 6 с интерпретацией 1 однозначно определяется текущим состоянием памяти, заключительное состояние памяти о' становится тем самым функцией Е, исходного состояния Н,: 6. 3 "= ~'о.г(4). Очевидно, что в общем случае эта функция частична.
Кроме частичной определенности функций, интерпретирующих формальные символы схемы, логически возмол<ны еще две причины неопределенности результата: а) бесконечное выполнение — выполняя оператор за оператоРом,мы никогда не попадаем на останов; б) пустой цикл — переходя от распознавателя к распознавателю, минуя операторы, мы попадаем вновь на Ранее пройденный распознаватель. Так как каждый распознаватель срабатывает однозначно, а значения предикатных переменных не изменились, цикл передач управления будет выполняться неограниченное число раэ. Мы назовем Две схемы Янова О:, и 7'э СРавнимыми, если онп заданы каждая над одним и тем же множеством предикатных сим- $ ХЗ.
ВНВНВАлентность схем янОВА' волов, а также, если операторные символы в операторах А,ыС7 и АэенСэ одни и те же, то и Р(А,) = Р(Аэ). Сравнимость схем позволяет дать каждой из них совместную интерпретацию, когда всем предикатным и общим операторным символам будут сопоставлены одни и те же функции, а одинаковость сдвигов приведет к тому, что на одинаковых состояниях памяти одинаковые операторы будут также одинаково срабатывать.
О и р е д е л е н и е. Две сравнимые схемы Сд и С, эяэивалгнт яы в совместной интерпрбтации 1, если го,г(")=гсвг(") ° Под равенством частичных функций мы понимаем такое полол<ение, что если для некоторого Ы определена одна функция, то определена и другая, и их значения совпадают.
О п р е д е л е н и е.Две сравнимые схемы Сд и С функционально эквивалентны, если они эквивалентны в любой совместной интерпретации. В определенном смысле — зто наиболее естественное онределемие эквивалентности схем. Однако само по себе оно не дает подходящей зацепки для того, чтобы устанавливать эквивалентность схем или строить систему равносильных преобразований. Операционная эквивалентность.
Опыт отладки реальных программ подсказывает нам, что гораздо легче устанавливать правильность работы программы, если располагать не только результатами вычисления, но еще и некоторой историей их получения. По-видимому, легко согласиться, что весьма детальной историей работы программы будет полная последовательность выполняемых опер%торов и наборов значений предикатных переменных. Последовательность операторов позволит восстановить последовательность состояний памяти, а наборы значений предикатных переменных восстанавлива7от путь от одного оператора к другому.
Эту двойную последовательность мы назовем операционной историей выполнения интерпретированной схемы Янова. Дадим более точное онределенне операционной истории. Пусть дана интерпретация 1 схемы С. Будем называть последовательность значений преднкатных переменных верхней последовательностью, а последовательность операторов — нижней. Н а ч а л ь н ы й шаг. Верхняя и нижняя последовательности пусты. Пусть дано исходное состояние памяти И. Вычисляем текущий набор Л значений предикатных переменных и помещаем его в верхнюю последовательность. Переходим ко входной вершине.
Ш а г в ы и о л н е н и я. Управление передано на вершину 8 с текущим набором Л значений предикатных переменных. а) Если о — это распознаватель с условием Р, то смотрим, помечен он или нет. Если он не помечен, то помечаем его н гл. и опгвдвлвнив схим янова переходим к нужному преемнику в зависимости от вычисленного условия г"(Л). Если о' оказался помеченным, то это значит, что мы попали в пустой цикл.
Выполнение схемы обрывается, операционная история и результат выполнения схемы не определяются. б) Если о — это останов, в нижнюю последовательность записывается символ астапова ьг', выполнение схемы завершается, операционная история построена, текущее состояние памяти объявляется результатом работы программы.
в) Если 8 — это оператор, то он выполняется, образуя новое состояние памяти, его операторный символ записывается в нижнюю последовательность, должным образом перевычисляется набор значений предикатных переменных, вся разметка распознавателей снимается, управление передается единственному преемнику оператора. Операционная история, так определенная, становится тем самым для схемы 6 з интерпретации 1 однозначной функцией На г (д) исходного состояния памяти д. Аналогично предыдущему, мы скажем, что две сравнимые схемы Сг и С, одинаково работают в совместной интерпретации 1, если 11о, (д) = Н„ля. О п р е де л е н и е.
Две сравнимые схемы 6, и Сг операционно эквивалентны, если опи одинаково работают в любой совместной интерпретации. Связь введенных эквивалентностей. Появление двух независимых определений эквивалентности схем Янова требует их совместного изучения. Взаимную связь функциональной и операционной эквивалентности исчерпывает Т е о р е м а 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
