ПРОГРАММИРОВАНИЕ, 2014, No 3, с. 3-14
- ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ -
УДК 519.6
ИССЛЕДОВАНИЕ ДВУХПАРАМЕТРИЧЕСКОЙ АЛГЕБРАИЧЕСКОЙ МОДЕЛИ ПРОГРАММ ПО МЕТОДИКАМ, РАЗРАБОТАННЫМ ДЛЯ ОДНОПАРАМЕТРИЧЕСКИХ
МОДЕЛЕЙ *
© 2014 г. Р.И. Подловченко
Научно-исследовательский вычислительный центр МГУ 119991 Москва, Ленинские горы, дом 1, стр. 4 E-mail: rip@vvv.srcc.msu.ru Поступила в редакцию 25.08.2013
Для конкретной двухпараметрической алгебраической модели программ решены две фундаментальные проблемы: распознавание эквивалентности схем программ в этой модели и построение полной системы эквивалентных преобразований схем программ в модели. Решение проведено применением методик, разработанных для однопараметрических алгебраических моделей программ. Этим подведён итог предыдущим исследованиям данной модели. Выявлена важная функциональная особенность этой модели - существование нескольких канонических форм представления схем в классе их эквивалентности.
1. ВВЕДЕНИЕ
Рассматриваемые в статье алгебраические модели программ введены в [1] как обобщение моделей программ, предложенных в [2] и [3]. Объектами моделей являются схемы программ, построенные над некоторым символьным базисом операторов и логических условий. Все модели имеют общим множество схем программ и отличаются одна от другой отношением эквивалентности схем. Эти отношения индуцируются в общем случае двумя параметрами.
Центральными при изучении алгебраических моделей программ являются проблема эквивалентности схем в модели и проблема построения системы эквивалентных преобразований (э.п.) схем, полной в модели. Первая состоит в поиске алгоритма, который, получив на свой вход две произвольные схемы из данной модели, распознаёт, эквивалентны они или нет. Система э.п. схем называется полной в модели, если, какими бы ни были две эквивалентные схемы из модели, любая из них трансформируема в другую применением преобразований, принадлежащих этой
* Работа поддержана грантом РФФИ № 12-01-00706а.
системе, причём трансформация осуществляется алгоритмом.
Для однопараметрических моделей разработаны две методики: одна в [4] для решения проблемы эквивалентности в модели, вторая в [5] для построения полной в модели системы э.п.
Задачи данной статьи состоят в следующем: для конкретной двухпараметрической модели программ продемонстрировать эффективность применения методик, изложенных в [4] и [5], построить полиномиальный по сложности алгоритм, распознающий эквивалентность схем в этой модели, и построить полную в ней систему э.п.
В качестве исследуемой двухпараметрической модели нами рассмотрена модель программ с перестановочными и монотонными операторами, введённая в [6]. Схемами, принадлежащими этой модели, аппроксимируются программы, в которых порядок выполняемых операторов не влияет на результат вычислений, осуществляемых программой, и, если по ходу вычислений получено истинное значение какого-либо логического условия, используемого программой, то оно со-
храняется при любом продолжении работы программы.
Эта модель изучалась ранее в [6-8]. Применяемые там методы исследований, нацеленные на решение центральных задач теории алгебраических моделей программ, ориентированы исключительно на данную модель, а полученные результаты таковы:
о в [8] решена проблема эквивалентности в модели, причём разрешающий алгоритм имеет трудно оценимую сложность;
о
щая на полноту в модели, но фактически не являющаяся таковой.
Выполненными здесь исследованиями установлено следующее:
о
в [4], то для выбранной нами модели осуществимо построение алгоритма, разрешающего эквивалентность в ней с легко определяемой полиномиальной сложностью;
о
построение которых предписывается методикой, разработанной в [5], составляют для изучаемой модели в общем случае многоэлементные множества;
о
действительно полная в модели система э.п.
Таким образом, решены поставленные выше задачи.
Материал статьи распределён по шести разделам, и в начале каждого описываются решаемые в нём задачи.
2. ОСНОВНЫЕ ПОНЯТИЯ
Здесь даётся определение изучаемой нами алгебраической модели программ, обозначаемой М. Она является подмоделью той модели, которая введена в [6]; там же доказана сводимость к этой подмодели проблемы эквивалентности, что
М.
М
сутствуют элементы, не принимающие участия в функционировании схемы. Это отмечается в данном разделе.
Модель M строится над двумя конечными алфавитами Y rn P. Элементы первого именуются операторными символа,ми, элементы второго -логическими переменными; последние принимают значения из множества {0,1}. Введём множество X :
X = {x\x : P ^ {0,1}}.
Его элементы называются наборами значений логических переменных или просто наборам,и. В множестве учреждается отношение
xi < Х2 ^ Vp е P(xi(p) < X2(p));
здесь x1, x2 е X.
Схема программы, являющаяся объектом мо-M,
рованный граф, в котором выделены три вершины: вход, не имеющий оканчивающихся в нём дуг, выход, из которого не исходят дуги, и вершина loop, не имеющая исходящих дуг. Все остальные вершины графа называются преобразователями. Каждому преобразователю v сопоставлены набор x(v), называемый его индексом, и операторный символ y(v) из алфавита Y. Из входа исходят дуги, каждая из которых помечена своим набором, при этом используются все наборы X. v
x,
ванию
x > x(v);
при этом каждая дуга имеет свою метку, и ис-
X.
ватель входят дуги, метки которых совпадают с его индексом. Всякий преобразователь находится на ориентированном пути из входа схемы в её выход.
Структура схемы описана. Пример схемы над Y, P,
Y = {уъЫ, P = {Pi}, представлен на рис. 1.
Y
операторными цепочками или просто цепочками, и обозначать как Y* их множество.
Прежде, чем описать функционирование схе-M,
ской модели программ оно определяется её параметрами. Таковыми являются: отношение эквивалентности и в множестве Y* и подмножество
Рис. 1
L множества, элементы которого - это отображения множества Y* в множество X; они называются функциями разметки. Условимся функцию, принадлежащую L, называть допустимой.
Схемы выполняются на допустимых функциях разметки, и результатом выполнения, если оно завершаемо достижением выхода схемы, является операторная цепочка. Для модели M отношение ^определяется так: цепочки hi и h2 из Y* эквивалентны тогда и только тогда, когда, ка-
Y,
в одну из них совпадает с числом его вхождений в другую. Эквивалентность цепочек hi, записывается в виде hi — h2.
M
д, удовлетворяющая двум требованиям:
1. Vhi, h2 е Y* [hi - h2 ^ Mhi) = Mh2)];
2. Vy е Y, Vh е Y* [^(h) < Mhy)].
Пусть д - допустимая функция разметки. Выполнение схемы G из M на функции д представляет собой обход схемы, начинающийся в её входе с пустой цепочкой А и совершаемый по следующим правилам. Из входа путешествие идёт с пустой цепочкой по дуге с меткой д(А). Пусть при обходе достигнута с цепочкой h вершина v. Если v - преобразователь, то путешествие продолжается с цепочкой hy (v) по дуге с меткой д^у^)). Если v - выход схемы или вершина loop, то обход прекращается; в первом случае результатом выполнения схемы G на д считаем цепочку ^обозначаемую G^); во втором случае
выполнение схемы на д объявляем безрезультатным, а значение С(д) неопределённым.
На рис. 1 пунктиром отмечен путь выполнения схемы на функции разметки д, удовлетворяющей требованиям
д(А) = д(у1) = д(у1 ,у2) = Д(У1 ,У2 ,У1) =
д(у1 ,У2,У1 ,У2) = д(у1 ,У2,У1 ,У2,У1) = 0; д =
(У1 ,У2 ,У1 ,У2 ,У1 ,У2 ) = 1
и равной значению 0 на всех других цепочках.
Схемы , ^2 из моде ли М называем эквивалентными; если
Уд е (д) = С2(д)).
Далее параметры и и Ь модели М, как неизменяемые, опускаются в обозначениях.
Ориентированный путь из входа схемы назовём маршрутом; говорим, что маршрут прокладывается в схеме; если он является началом пути, по которому идёт выполнение схемы на некоторой допустимой функции разметки.
М
водной; если любой маршрут в ней прокладывается. Из описания структуры схемы и её функционирования следует:
М
является свободной.
Описание основных понятий считаем завершенным.
Далее рассматриваются схемы, непременно
М,
нания. Вместе с тем, говоря об эквивалентности схем, будем подчёркивать, что речь идёт об
М.
3. МЕТОДИКА РЕШЕНИЯ ПРОБЛЕМЫ ЭКВИВАЛЕНТНОСТИ И ЕЁ ПРИМЕНЕНИЕ
М
Эта методика разработана в [4] для однопара-
М.
Исходная концепция методики состоит в том, чтобы сформулировать отношение эквивалентности схем в требованиях, предъявляемых к маршрутам в них, и исследовать его.
Пусть т - конечный ориентированный путь в схеме. Сопоставим ему несомую им цепочку ^т), определив её выписыванием друг за другом символов, метящих преобразователи этого
маршрута, при его просмотре от начала к концу; при этом, если конец маршрута - преобразователь, то его символ игнорируется.
Маршрут, оканчивающийся в выходе схемы, называем маршрутом через неё.
Два маршрута в схемах назовём сочетаемыми, если они прокладываются общей для них допустимой функцией разметки.
Формулировке отношения эквивалентности схем на языке требований к маршрутам в них предпошлём лемму 3.1.
Лемма 3.1. В эквивалентных схемах из мо-M
маршруты в них оканчиваются в вершинах общего типа, и если это - выходы схем, то несут эквивалентные цепочки.
Доказательство. Пусть w1, w2 - конечные равновеликие маршруты в эквивалентных схемах из M, и ^ - прокладывающая их допустимая функция разметки. Если один из маршрутов оканчивается в выходе схемы, то из эквивалентности схем следует, что другой тоже оканчивается в выходе, и несомые ими цепочки эквивалентны, то есть утверждение леммы верно.
Предположим, что wi оканчивается в преобразователе, a W2 в верши не loop, и придём к противоречию, что схемы эквивалентны. Построим простой ориентированный путь w, продолжающий маршрут wi до выхода схемы. Это возмож-
M
лежит на маршруте через неё. Затем построим допустимую функцию разметки ^i, определив её следующим образом: на префиксах цепочек h(wiw) и h(w2) она совпадает с функцией а на других цепочках равна некоторому набору xo X.
M
wi w
вивалентных цепочек. Очевидно, что функция ^i прокладывает маршруты wiw и w2, но первый оканчи
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.