Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

менных. Если считать, что при выполнении схемы они изменяются согласно этой последовательности, т. е. после выполнения т - го оператора логические переменные принимают набор значений A S j n + 1 , то получим определенную последовательность выполненных опера­ торов, которую будем называть значением схемы для данной после­ довательности наборов. Задание распределения сдвигов выделяет для каждой схемы из всех возможных последовательностей набо­ ров множество допустимых последовательностей. Таким образом, допустимые последовательности отличаются значениями только тех переменных, которые данным распределением сдвигов постав­ лены в соответствие оператору, выполненному при предыдущем наборе.

Понятие равносильности схем при заданном распределении сдвигов требует совпадения значений равносильных схем для любой допустимой последовательности наборов. Это означает, что мно­ жество всех равносильных схем при любой подстановке конкрет­ ных операторов и предикатов (связь которых соответствует дан­ ному распределению сдвигов) переходит во множество схемных за­ писей одного и того же алгоритма.

Ю. И. Яновым вводится система аксиом и правил вывода, опи­ сывающая понятие равносильности логических схем алгоритмов при данном распределении сдвигов. А. П. Ершовым теория логиче­ ских схем алгоритмов Янова была перенесена на язык граф-схем, что-позволило упростить аксиоматику преобразований. Вместо 14 аксиом Янова Ершов использует только 7 аксиом. Н. А. Криницкий расширил систему преобразований Янова, вводя в рассмотре­ ние информационные связи между операторами. Оператор рас­ сматривается как система функций, берущих свои аргументы из не­ которых входных величин и записывающих результаты в выходные величины оператора.

Дальнейшее расширение системы преобразований Янова шло в направлении преобразования не алгоритмов, а программ. Преоб­ разование программ рассматривается в работах Н. А. Криницкого, Р. И. Подловченко и др.

Поскольку преобразование алгоритмов в изложении Янова яв­ ляется довольно трудным, то мы рассмотрим упрощенную систему преобразований, предложенную Ершовым.

Операторной схемой Янова называется конечный ориентиро­ ванный граф, обладающий следующими свойствами. Вершины гра­ фа имеют не более двух выходящих на них стрелок. Вершины, из которых выходят по две стрелки (одна из стрелок некоторым об­ разом помечается), называются распознавателями, остальные на­ зываются операторами. К одной из вершин ведет специальная вход­ ная стрелка.

Помеченные стрелки называются плюс-стрелками, а непомечен­ ные— минус-стрелками. В графе имеется только одна вершина, не имеющая выходной стрелки, называемая конечным оператором.

75

ческих переменных pi,..., ph. Распознаватель R с сопоставленным ему условием а обозначается R(a).

Каждому оператору А, кроме конечного, приписывается неко­ торый набор

^ • 1 Л Л )

логических переменных, называемый сдвигом по логическим пере­

Ph.

Для операторной схе­ мы G определим понятие конфигурации, строящейся с помощью порождающего процесса

блуждения по схеме G, задаваемого по индукции. Сама конфигу­ рация будет получаться в виде двойной последовательности наборов значений логических переменных ри • •., рк и символов операторов

76

При построении конфигурации основываемся на некотором ба­ зисе индукции, от которого осуществляются последующие шаги ин­

должается по плюс-стрелке, выходящей из распознавателя R. Если а(Д) = 0, то движение происходит по минус-стрелке. Если стрелка

Набор А' выписывается в верхнюю строку конфигурации, и дви­ жение продолжается по стрелке, выходящей из А.

Если стрелка приводит к конечному оператору, то его символ выписывается в нижнюю строку и построение конфигурации обры­ вается.

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

значениями только тех переменных, которые входят в сдвиг опера­

77

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

78

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

Поясним сделанные определения на примере фрагмента, представлен­ ного на рис. 9.

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

Сами аксиомы и утверждение правил вывода имеют вид соотно­ шений равносильности, т. е. двух фрагментов, разделенных знаками равносильности ~ . Аксиомы и пра­ вила вывода представлены на рис. 10.

Правила имеют вид:

79