Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

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

Конкретные алгоритмы и программы получаются из схем в результате сопоставления формальным переменным и операциям некоторых конкретных переменных и операций.

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

совокупность операторов, образующих схему алгоритма, изоб­

при построении реализаций преемник оператора обычно выби­ рается произвольно, без учета истории движения к данному опе­ ратору;

если в рассмотрение вовлекается некоторая величина, «выра­ батываемая» некоторым оператором, то она трактуется как неза­ висимая переменная, т. е. считается, что после выполнения данно­ го оператора она может принимать любое значение, независимо от предыдущей истории;

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

вать следующим образом. Два алгоритма эквивалентны по отно­

результирующее значение переменного для данных исходных зна­ чений функциональных переменных.

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

Для определения эквивалентности операторных алгоритмов рассмотрим два алгоритма Ах и Л2 . Для каждого из алгоритмов выделим те переменные, которые нас интересуют в качестве ре­ зультатов выполнения этих алгоритмов. Выделяемые переменные могут быть различными у алгоритма А, и алгоритма Л2 , но число их должно быть одинаковым и между ними должно быть установ-

69

Sn(Xinl'• • • > x i v m n , pjni,..., P j n l n ) =$-yn •

Можно также определить эквивалентность между двумя алго­

70

Следует отметить, что если вводится понятие эквивалентности для алгоритмов из разных классов, то может оказаться, что алго­ ритмы, эквивалентные в смысле 5-представлений, будут неэкви­ валентны в смысле совпадения значений выделенных переменных. Это может произойти в том случае, если изоморфные операции не будут совпадать функционально. Например, в одном случае арифметические действия выполняются в двоичной системе, а в другом — в десятичной.

явились: формализация понятия схемы алгоритма; задание отно­ шения эквивалентности; нахождение алгоритма, распознающего

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

Для доказательства полноты преобразований Яновым был применен аппарат теории логических исчислений, при котором правило преобразования трактуется как аксиома, постулирующая сохранение эквивалентности при выполнении преобразования.

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

т

71

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

вой полускобки с индексом i, входящей в эту строку, в ней найдет­ ся одна и только одна правая полускобка с тем же индексом i, и обратно, для каждой правой полускобки J найдется одна и толь-

ко одна левая с тем же индексом.

Логические условия и операторы называются элементарными выражениями.

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

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

чения логических переменных изменяются согласно этой последо­

последовательность называется значением схемы для данной по­ следовательности наборов. Задание распределения сдвигов выде­ ляет для каждой схемы из всех возможных последовательностей наборов множество допустимых последовательностей. Таким обра­

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

72