теперь функцию
f
i
(
X, V
i
−
1
, Y
i
−
1
, V
i
, Y
i
)
. Предположим, что единствен-
ной еe задачей является копирование входных данных в выходные:
Y
=
V
=
X
. Предположим также для упрощения, что размерность
векторов
X, Y, V
одинакова. Совершенно очевидно, что для данной
функции невозможно найти такую функцию
f
i
+1
(
X, V
i
, Y
i
, V
i
+1
, Y
i
+1
)
,
которая за полиномиальное время находила бы векторы
V
i
+1
, Y
i
+1
, та-
кие, что
V
i
+1
=
V
i
−
1
и
Y
i
+1
=
Y
i
−
1
, т.е. для функции, приведенной
ранее, не существует обратной.
Очевидно, чтобы функция
f
i
(
X, V
i
−
1
, Y
i
−
1
, V
i
, Y
i
)
была обратима,
необходимо, чтобы значение каждого из элементов выходных векто-
ров
V
i
, Y
i
зависело от соответствующих элементов векторов
V
i
−
1
, Y
i
−
1
.
Однако это требование не является достаточным. Зависимость долж-
на быть такой, чтобы обратные вычисления могли быть проведены за
полиномиальное время.
Все сказанное о функциях справедливо и для функциональных
свойств по определению.
Теперь изучим детально процесс оптимизации запутанного кода.
Рассмотрим равенство
π
исх
=
π
1
∗
π
2
∗
. . .
∗
π
n
,
(5)
где
π
исх
— функциональное свойство подпрограммы
М
до применения
запутывающих преобразований;
π
i
— элементарные свойства подпро-
граммы, из которых складывается
π
исх
;
i
= [1
. . .
]
.
Приведем определение элементарных свойств подпрограммы.
Определение 5.
Элементарное свойство подпрограммы — это свой-
ство подпрограммы, соответствующее одной трехадресной инструк-
ции.
Определение 6.
Произведение элементарных свойств подпрограм-
мы называется оптимальным по отношению к указанному алгоритму
оптимизации, если применение к этому произведению указанного ал-
горитма не изменяет сомножителей произведения.
Предположим, что правая часть равенства (5) содержит оптималь-
ное произведение свойств подпрограмм по отношению к определен-
ному алгоритму оптимизации (алгоритму
А
).
После применения запутывающих преобразований, делающих по-
следовательность из правой части равенства (5) неоптимальной по
отношению к алгоритму
А
, получаем:
π
исх
=
π
1
∗
ν
1
∗
π
2
∗
ν
2
∗
. . .
∗
π
n
∗
ν
n
(6)
или
π
исх
=
π
0
∗
ν
0
∗
π
1
∗
ν
1
∗
π
2
∗
ν
2
∗
. . .
∗
π
n
∗
ν
n
,
(7)
где
ν
0
, ν
1
, ν
2
, . . . , ν
n
— добавленные функциональные свойства;
π
0
=
e
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2 97
