В.А. Овчинников, Г.С. Иванова
8
<Заменяющий фрагмент> ::= <Элемент множества>
<Множество 2>,
<Условие допустимости> ::= <Множество 2> =
<Множество 1>,
<Условие целесообразности> ::=
Card
(<Множество 1>) >
Card
(<Множество 2>).
Правило трансформации будет иметь вид
((
A
) & (<Множество 2> =
<Множество 1>) &
(
Card
(<Множество 1>) >
Card
(<Множество 2>))) (
),
где
= <Заменяемый фрагмент>;
= <Заменяющий фрагмент>;
A
—
множество строк описания алгоритма.
Рассмотрим преобразование, заключающееся в замене
2
1
\
X X X
на
2
2
\
i
X X X
(
2
2
\
i
X X x
). Его применение требует проверки вы-
полнения условия «в алгоритме до операции
2
1
\
X X X
есть опера-
ция
1
1
i
X X X
(
1
1
i
X X x
)». Следовательно, это преобразование
относится к классу контекстно зависимых. Такая ситуация характер-
на для последовательных и итерационных алгоритмов компоновки,
применяемых как по методу последовательного выделения, так и по
методу дихотомического разделения. Покажем эквивалентность за-
мены. Обозначив
н
1
X
и
н
2
X
множества
X
1
и
X
2
после перестановки
X
i
из
X
2
в
X
1
, запишем
н
1
1
\
i
X X X
и
н
н
2
1
\
X X X
. Отсюда
н
1
2
2
\
\
\
i
i
X X X X X X
. Таким образом, условием корректности
будет наличие в алгоритме операции
1
1
i
X X X
.
Оценим целесообразность выполнения преобразования. Количе-
ство операций сравнения для определения
2
1
\
X X X
и
2
\
i
X X X
равно
1
X X
и
2
i
X X
. Так как в указанных алгоритмах к моменту
формирования множества
X
2
справедливо
2
i
X X
и
X
i
X
1
, данное
преобразование приводит к снижению вычислительной сложности
алгоритма. Условие целесообразности рассматриваемого преобразо-
вания для таких и аналогичных алгоритмов тождественно истинно.
Наличие в алгоритме операции
1
1
i
X X X
(
1
1
i
X X x
) реализуем
как фрагмент условия допустимости, а проверку ее предшествования
операции
2
1
\
X X X
включим в правило трансформации. Тогда син-
таксис данного оптимизирующего преобразования будет иметь вид:
<Заменяемый фрагмент> ::= <Объект 1> = <Объект 2> \ <Объект 3>,
<Заменяющий фрагмент> ::= <Объект 1>
=
<Объект 1> \ <Объект 4>,
<Фрагмент условия допустимости> ::= <Объект 3> =
= <Объект 3> • <Объект 4>,
