научная статья по теме ИССЛЕДОВАНИЕ ДВУХПАРАМЕТРИЧЕСКОЙ АЛГЕБРАИЧЕСКОЙ МОДЕЛИ ПРОГРАММ ПО МЕТОДИКАМ, РАЗРАБОТАННЫМ ДЛЯ ОДНОПАРАМЕТРИЧЕСКИХ МОДЕЛЕЙ Математика

Текст научной статьи на тему «ИССЛЕДОВАНИЕ ДВУХПАРАМЕТРИЧЕСКОЙ АЛГЕБРАИЧЕСКОЙ МОДЕЛИ ПРОГРАММ ПО МЕТОДИКАМ, РАЗРАБОТАННЫМ ДЛЯ ОДНОПАРАМЕТРИЧЕСКИХ МОДЕЛЕЙ»

ПРОГРАММИРОВАНИЕ, 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 рублей.

Показать целиком

Пoхожие научные работыпо теме «Математика»