Формализация оптимизирующих преобразований алгоритмов на графах и множествах
7
где
= <Заменяемый фрагмент 1>;
= <Заменяющий фрагмент>;
A
— множество строк описания алгоритма;
— символ вывода —
замещение найденного фрагмента на синтезированный заменяющий
фрагмент.
В качестве второго примера рассмотрим, как строится решающее
правило для замены операции объединения множеств или множества
и элемента операцией конкатенации:
1
2
X X X
на
1 2
X X X
или
1
i
X X x
на
1
i
X X x
.
Эта замена возможна, т. е. результаты вычислений будут эквива-
лентны, только в том случае, если эти множества не пересекаются
или элемент не принадлежит множеству — условие корректности.
Таким образом, преобразование является контекстно зависимым.
Информация о выполнении условия корректности может присутство-
вать в разделе описаний алгоритма или получена от разработчика.
Преобразование не требует дополнительной памяти и целесообразно.
Синтаксически заменяемый и заменяющий фрагменты имеют
вид:
<Заменяемый фрагмент> ::= <Фрагмент 1> \ <Фрагмент 2>,
<Фрагмент 1> ::= <Множество 1>
<Множество 2>,
<Фрагмент 2> ::= <Множество 1>
<Элемент>,
<Заменяющий фрагмент> ::= <Фрагмент 31> \ <Фрагмент 32>,
<Фрагмент 31> ::= <Множество 1> • <Множество 2>,
<Фрагмент 32> ::= <Множество 1> • <Элемент>.
Поскольку фрагмент 1 заменяется на фрагмент 31, а фрагмент 2 —
на фрагмент 32, правило трансформации будет включать две части:
((
A
) & (<Множество 1>
<Множество 2> =
)) (
),
((
A
) & (<Элемент>
<Множество 1>)) (
),
где
= <Фрагмент 1>,
= <Фрагмент 2> — заменяемые строки;
= <Фрагмент 31>,
= <Фрагмент 32> — заменяющие строки;
A
—
множество строк описания алгоритма.
Выполним формализацию контекстно зависимого преобразова-
ния, заключающегося в замене операции
x
i
X
1
на
x
i
X
2
. Условие
допустимости — наличие в алгоритме множества
X
2
=
X
1
, а условие
целесообразности — |
X
1
| > |
X
2
|. Для определения мощности множеств
будем использовать функцию
Card
.
<Заменяемый фрагмент> ::= <Элемент множества>
<Множество 1>,
