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

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

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

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

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

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

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

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

63

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

А~В.

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

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

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

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

64

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

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

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

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

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

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

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

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

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

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

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

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

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

66

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

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

68