книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

Рассматривая столбец с суммами элементов строк, устанавли­

должения пути обращаемся к строке матрицы с номером Х\. Бэтой строке первым элементом, не равным нулю, является элемент, стоящий в столбце с номером х0. Фиксируем значение этого эле­ мента, равное единице. Проверяем номер столбца на соответствие

и переходим к определению объема информации по данному пути,

60

§ 3. 1. ЭКВИВАЛЕНТНОСТЬ АЛГОРИТМОВ И ПРОГРАММ

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

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

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

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

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

62

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

В теории алгоритмов проблема эквивалентных преобразований алгоритмов ставится как проблема отыскания конечной и полной

вводятся понятия входа и выхода. Для каждого входа из области

имеет место тогда, когда равенство входов приводит к равенству выходов.

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

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

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

63

конструктивных объектов А и В «быть в соответствии, заданном изоморфизмом» будем обозначать через

А~В.

Определение эквивалентности теперь будет следующим. Алго­ ритмы А{ и А2 считаются эквивалентными, если из условия

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

На степень широты понятия эквивалентности наиболее сущест­ венно влияет выбор определения выхода алгоритма. Не во всех случаях нас могут интересовать в качестве выхода только те конст­

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

64

ченной в ходе выполнения алгоритма, несет в себе выход, тем более сильным оказывается отношение эквивалентности, основан­ ное на таком определении выхода. Другими словами, все разнооб­ разие эквивалентных алгоритмов состоит в том, что они приводят к одному конечному результату разными путями. Следовательно, чем больше истории о том, как выполнялся алгоритм, несет в себе выход, тем к более жесткому понятию эквивалентности он приво­ дит. Это объясняется тем, что в один класс эквивалентных алго­ ритмов попадают только те алгоритмы, история выполнения кото­ рых соответствует истории, зафиксированной в данном выходе. Таким образом, можно определить сильную и слабую эквивалент­ ность алгоритмов.

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

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

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

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

Рассмотрим основные типы историй применительно к алгорит­ мам, представленным в виде программ. Так как с точки зрения теории алгоритмов программа — это алгоритм на языке машины, то понятия эквивалентности существуют и для программ.

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

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

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

операционная, операционно-логическая, информационная, инфор­

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

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

Термальная история — история, содержащая последователь­ ность термальных значений результативных переменных. Под тер­ мальным значением понимается дерево, отражающее историю из­ менения аргумента в процессе выполнения программы.

66

jei-i-JCg-^- составные реквизиты исходного документа;

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

68

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

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

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

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

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

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

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

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

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

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

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

69