Формализация оптимизирующих преобразований алгоритмов на графах и множествах
5
мого и заменяющего фрагментов и указанных выше условий. Это
описание должно базироваться на синтаксисе и семантике средств
описания алгоритмов — соглашениях о символике объектов и опера-
ций теории множеств, математической логики и теории графов.
Синтаксические правила оптимизирующих преобразований
должны задавать структуру фрагмента, определяя тип его объектов и
порядок их связывания конкретными операциями.
В отличие от разработки синтаксиса заменяемого и заменяющего
фрагментов, для синтеза логических выражений, реализующих усло-
вия допустимости или оценки эффективности, нередко необходима
информация, не содержащаяся в описании алгоритма. Те преобразо-
вания, для формулировки и проверки условий выполнения которых
достаточно информации, содержащейся в алгоритме, отнесем к под-
классу автоматических. В противном случае преобразование может
быть выполнено только в диалоговом режиме, т. е. является автома-
тизированным.
Синтез заменяемого и заменяющего фрагментов является творче-
ской задачей. Для успешного ее решения необходимо знание дис-
кретной математики, в том числе теории множеств, математической
логики, теории графов, методов и алгоритмов решения задач дис-
кретного программирования. Исходными данными для этой задачи
являются результаты анализа процесса преобразования модели ис-
ходного представления проектируемой структуры в модель результа-
та, сущности, свойств и количества операций над объектами алго-
ритма, свойств и характеристик этих объектов.
Рассмотрим контекстно свободное преобразование, выполняющее
замену выражения вида
X Y Z
или
X Y Z
, где
Z X Z X
,
на конструкцию вида
\
X Z Y
или
\
X Z Y
, где
X
,
Y
,
Z
— не пу-
стые множества.
Эквивалентность и эффективность этого преобразования пока-
жем на примере операции строгого включения. В эквивалентности
выражения
X Y Z
выражению
\
X Z Y
нетрудно убедиться.
Действительно,
X Y Z
x X x Y x Z
и
\
X Z Y
x X x Z x Y
&
.
Количество сравнений элементов множеств
X
,
Y
и
Z
при реализа-
ции выражения
X Y Z
равно
1
op
k
X Y Z
. Для выражения
\
X Z Y
при
X Z
количество операций сравнения
2
op
k
X Z X X Z Y
. Таким образом,
1
2
op op
k k
X Z Y
.
