Формализация оптимизирующих преобразований алгоритмов на графах и множествах
9
<Объект 1> ::= <Множество 1>,
<Объект 2> ::= <Множество 2>,
<Объект 3> ::= <Множество 3>,
<Объект 4> ::= <Множество 4> \ <Элемент>.
Правило трансформации:
(
A
)
(
A
)
(
=
next
(
)) (
),
где
= <Заменяемый фрагмент>;
= <Фрагмент условия допустимо-
сти>;
= <Заменяющий фрагмент>;
A
— множество упорядоченных
строк описания алгоритма;
=
next
(
) — проверка того, что фраг-
мент условия допустимости предшествует заменяемому фрагменту.
Сформулируем решающее правило исключения лишних вычис-
лений при определении показателей связности вершин гиперграфа.
Будем считать, что гиперграф описан и задан в виде
H
(
X
,
U
, Г
X
,
F
1
X
).
Здесь: Г
X
— образы вершин относительно предиката инцидентности;
F
1
X
— образы вершин относительно предиката смежности [6]. Ис-
пользуя, как и выше, для определения мощности множества функцию
Card
, получим заменяемый и заменяющий фрагменты соответственно:
x
i
X
: (
x
j
X
:
s
i
,
j
:=
Card
(Г
x
i
Г
x
j
)) и
x
i
X
: (
x
j
F
1
x
i
:
s
i
,
j
:=
Card
(Г
x
i
Г
x
j
)).
Если невычисляемые во втором случае показатели связности в
алгоритме не используются, то такой замены достаточно. Иначе эти
показатели в процессе вычислений следует обнулить, например, ис-
пользуя в качестве заменяющего фрагмент
x
i
X
: (
x
j
X
:
s
i
,
j
:= 0,
x
j
F
1
x
i
:
s
i
,
j
:=
Card
(Г
x
i
Г
x
j
)).
Информацию о необходимости обнуления нерассчитываемых по-
казателей из описания алгоритма получить сложно: требуется рас-
смотреть все конструкции, использующие показатели связности, и
оценить, анализируются ли эти показатели. Поэтому будем считать,
что обнуление показателей необходимо.
Синтаксически заменяемый фрагмент определяется следующим
образом:
<Заменяемый фрагмент> ::=
<Элемент множества 1>
<
Множество 1
>
: (
<Элемент множества 1>
<Множество 1
>
:
<
Элемент матрицы
>
:=
Card
(Г
<
Элемент множества 1
>
Г
<
Элемент множества 1
>
)).
Заменяющий фрагмент определяем так:
