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

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

УДК 681.3.06

ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ

О ПРОБЛЕМЕ МИНИМИЗАЦИИ ДЛЯ СХЕМ ПРОГРАММ С ПЕРЕСТАНОВОЧНЫМИ БЛОКАМИ*

© 2008 г. Р. И. Подловченко

Научно-исследовательский вычислительный центр МГУ 119992 Москва, Воробьевы горы

E-mail: rip@vvv.srcc.msu.su Поступила в редакцию 15.01.2008 г.

Нами рассматривается специального вида алгебраическая модель программ и обсуждается проблема минимизации для схем программ из этой модели.

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

Как модели вычислений, алгебраические модели программ введены в [1] и исследовались во многих работах, относящихся к теоретическому программированию. В [2] описано множество алгебраических моделей программ, для которого проблема эквивалентности взаимносво-дима к проблеме эквивалентности многоленточных автоматов. Выбранная нами модель принадлежит этому можеству, а адэкватным ей в указанном выше смысле является множество бинарных двухленточных автоматов. В [3] исследовано подмножество последних, обозначаемое там как М. Установлена разрешимость в М проблемы минимизации.

Задача данной статьи состоит в том, чтобы выделить из рассматриваемой модели, обозначим ее 5о, такое множество 5 схем программ, для которого проблема минимизации сводится

* Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант 06-01-00106).

к одноименной проблеме в М, и показать адаптируемость алгоритма ее решения в М к решению в 5.

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

Статья состоит из трех разделов.

В первом разделе воспроизводится определние общего вида алгебраической модели программ и описывается модель 5о.

Во втором разделе дается содержательный очерк того, как проблема эквивалентности в 5о сводится к проблеме эквивалентности в подмножествах, принадлежащих 5о схем программ. Ссылки на поэтапную сводимость, строго описанную в [2], сопровождаются поясняющими примерами.

В третьем разделе определяется множество 5 и отмечается адаптируемость алгоритма, предложенного в [3] для решения проблемы минимизации в М, к решению аналогичной проблемы в 5.

1. РАЗДЕЛ 1

Алгебраическая модель программ строится над конечными алфавитами У, Р, в совокупности составляющими базис. Элементы алфавита У называются операторными символами, элементы алфавита Р - логическими переменными; каждая из них принимает значения из множества {0,1}.

Схема программы над базисом У, Р (в дальнейшем - просто схема) задается конечным ори-

ентированным графом с размеченными вершинами и дугами. В нем выделены две вершины: вход - вершина без входящих в нее дуг и с единственной исходящей дугой и выход - вершина без исходящих из нее дуг. Обе вершины не имеют меток. Остальные вершины графа делятся по своему типу на преобразователи и распознаватели. Из каждого преобразователя исходит одна дуга, и ему сопоставлен символ из У. Из каждого распознавателя исходят две дуги, несущие метки 0 и 1 соответственно, и ему сопоставлена логическая переменная из Р. Другие дуги, кроме исходящих из распознавателей, меток не имеют.

На рис. 1 дан пример схемы над базисом У', Р', где

У' = {У1,У2},Р' = {Р1,Р2}.

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

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

Функциональное описание схемы связано с процессом ее выполнения. Последнее осуществляется на функции разметки. Введем ее.

Пусть

X = {х | х : Р ^ {0,1}};

элементы X интерпретируются как наборы значений всех логических переменных. Слова в алфавите У именуются операторными цепочками, их множество обозначается У*. По определению, функция разметки - это отображение У * в X. Множество всех функций разметки, построенных над базисом У, Р, обозначим С.

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

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

Эквивалентность схем индуцируется двумя параметрами - эквивалентностью V в множестве У * и подмножеством Ь множества С.

По определению, схемы О1, О2 эквивалентны, если, какой бы не была функция разметки / из Ь, всякий раз, как одна из схем останавливается на останавливается и другая схема, причем цепочки, являющиеся результатами их выполнения, эквивлентны по отношению V.

Алгебраической моделью программ назывется множество схем над базисом У, Р с введенной в нем эквивалентностью схем.

Рассматриваемая нами модель Б§ строится над базисом У', Р'.

Эквивалентность V в (У')* определяется следующим образом: цепочки из (У')* эквивалентны тогда и только тогда, когда совпадают их проекции на символ У1 и соответственно - на

Рис. 2.

символ у2. Множество Ь состоит из всех функций разметки, удовлетворяющих требованию: для любой цепочки Н из (У')*

г = 2 ^ цНу^р) = цН(р]),г = 1,2;2 = 1,2.

2. РАЗДЕЛ 2

В [3] демонстрируется, что эквивалентность в модели 50 сводится к эквивалентности в принадлежащих модели подмножествах. Это осуществляется следующим образом.

Сначала для всякой схемы О из 5о строится эквивалентная ей унифицированная схема, принадлежащая 50. Ее унифицированность заключается в том, что схема состоит из однотипных фрагментов, каждый из которых начинается либо входом (такой фрагмент едиственен), либо преобразователем и содержит полное дерево распознавателей. Требуется при этом, чтобы любой преобразователь принадлежал некоторому пути из входа схемы в ее выход.

На рис. 2 представлена унифицированная схема, построенная для схемы с рис. 1.

Ветви полного дерева распознавателей идентифицируются наборами х из X. Для всякого х по унифицированной схеме О конструируется

схема Ох: она включает в себя все и только такие вершины схемы О, которые достижимы из ее входа по ветви х дерева, произрастающего из входа схемы О.

Имеет место

Лемма 1. Унифицированные схемы О1 и О2 эквивалентны тогда и только тогда, когда при любом х из X эквивалентны схемы ОХ и ОХ.

Леммой 1 проблема эквивалентности схем в модели 50 сводится к проблеме эквивалентности в ее подмножествах 5ох, где 5Х = {ОХ | х £ е Х,О £ 5о}.

Далее в рассматриваемых нами примерах для схемы с рис. 2 обсуждается схема, соответствующая выбору х = 10.

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

Рис. 3.

XX-

Рис. 4.

На рис. 3 представлена маркированная схема, построенная для схемы Ох, где О изображена на рис. 2 и х = 10. В ней пунктирным прямоугольником охвачен фрагмент, появившийся в процессе построения и удаляемый в связи с тем, что он недостижим из входа схемы Ох. Для лучшей обозримости на рис. 3 опущены метки распознавателей, составляющих полные деревья.

Далее. Всякая маркированная схема из S0 преобразуема в эквивалентную ей приведенную схему. В ней каждое полное дерево распознавателей, растущее из преобразователя, заменяется одним распознавателем. Это осуществляется на основании следующего факта. Если преобразователь с символом yi, i = 1, 2, имеет маркер X, то при выполнении схемы путь из этого преобразо-

ь

Рис. 5.

Л?

V у

Ца Ць

Рис. 6.

вателя пойдет по ветви дерева, в которой переменная р3_г равна числу х(р3-г).

На рис. 4 изображена приведенная схема, построенная для маркированной схемы с рис. 3.

Подведем итог: проблема эквивалентности в модели 50 сводится к проблемам эквивалентности в множествах приведенных схем, принадлежащих 5Х, где х е X.

3. РАЗДЕЛ 3

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

Алгоритм пострения автомата по заданной приведенной схеме состоит в следующем: всякий фрагмент схемы, имеющий вид, который приведен слева на рис. 5, заменяется фрагментом ав-

томата, представленным справа на рис. 5. Здесь дг - метка состояния автомата, соответствующего символу уг, г = 1, 2. Вход схемы с растущим из него деревом распознавателей опускается, а состояние автомата, соответствующее преобразователю, в который вела ветвь из входа, объявляется инициальным.

На рис. 6 приведен автомат, соответствующий схеме с рис. 4.

На основании этого алгоритма следует

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

В [3] приводится алгоритм минимизации для множества М бинарных двухленточных автоматов, которые определяются требованиями: 1) из состояния с меткой д2 дуга, помеченная меткой 1, всегда ведет в мертвое состояние автомата;

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

Множе

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

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