Равносильные преобразования алгоритмов
Равносильные преобразования алгоритмов
Основные понятия
Два алгоритма называются равносильными, если равносильность между исходными данными приводит к равносильности между их результатами.
Комплекс – алгоритм с исходными данными и результатами.
Преобразование комплекса, приводящее к возникновению нового, алгоритм которого равносилен исходному, называется равносильным преобразованием алгоритма.
Свойства отношения равносильности алгоритма:
1. Рефлексивность
A = A
Рекомендуемые материалы
2. Симметричность
A = B ® B = A
3. Транзитивность
если A = B , B = C то A = C
В дальнейшем будем рассматривать однородные комплексы.
На однородные комплексы наложены определенные ограничения, такие как единственный выход из цикла.
Запишем все операторы в виде нормальной последовательности формул.
………………………
X = <
> - входной кортеж
Y = <
> - выходной кортеж
u:=x-y
v:=x+z
v:=v*u
X=<x,y,z>
Y=<v>
Z=<u>
N=0 , то Y
X (Y включено в X)
Z – рабочий кортеж
Выявление равносильностей алгоритмов
u:=x-y
v:=x+z
v:=v*u
v:=(x+z) * (x-y)
x = <
>
y = <
>
…………………………….
,
где 
- функция получения ответа
- выходные переменные
Очередность элементов может быть любой.
Пусть существуют два однородных комплекса K1 и K2 и на них наложены определенные ограничения.
K1
…………………………….
K2
…………………………….
В каждом комплексе выберем нетождественные функции (не повторяющиеся функции)
Для K1 это 
, а для K2 это 
Для равносильности K1 и K2 необходимо и достаточно:
1. Число отобранных функций должно быть одинаково
2. = и т.д. 
= 
Алгоритмы:
K1
u:=x+sin2z+cos2z
v:=y*u
w:=v
K2
u:=x+
(arccos t + arcsin t)
v:=y*u
x1 = <x,y,z> входной кортеж x2 = <x,y,t>
y1 = <u,v,w> выходной кортеж y2 = <u,v>
K1 выразим
K2 выразим
Тождественные функции:
K1
=
=
Вывод: K1 равносилен K2
K2
Операции над комплексами
Сумма:
K = K1 + K2
=
G’ - область задания K1
G’’ - область задания K2
G = G’ + G’’
Произведение:
K = K1 * K2
X2 
Z1 = 0 Z1 – рабочий кортеж K1
- соединяем два алгоритма
x=x1+(x2-y1) y1 – результат в 
y=y2+(y1-z2)
K1K2 ¹ K2K1
K1(K2K3) = (K1K2)K3
Пример:
K1:=a:=2*b+c
K2:=e:=3*c-a
x1 = <b,c>
x2 = <c,a>
y1 = <a>
y2 = <e>
x = <b,c>
y = <e,a>
Единичный комплекс
Если x = y, то комплекс единичный K = 
Обратный комплекс
Если Kn*K-n = , то K-n обратный справа
Равносильные преобразования алгоритмов заданных на ЯЛС
1)
2)
Пример:
Преобразуем схемы – убираем метки правых знаков перехода, если нет соответствующих левых знаков перехода.
3)
Если после левого знака перехода стоит правый, то его убираем.
Замыкание оператора
Замыкание – элементарное выражение + правый знак перехода слева от него.
4)
5)
TW=, если в схеме нет левого знака перехода, соответствующего правым знакам перехода в TW.
Выражение называется совершенным, если у одинаковых операторов:
1. одинаковые внешние левые знаки перехода (выходящие за данное выражение)
2. внутренним левым знакам перехода соответствуют правые знаки перехода у одинаковых операторов
6)
Любой правый знак перехода, принадлежащий одному из одинаковых операторов совершенного выражения, можно отнести к другому.
- совокупность правых знаков перехода.
7)
8)
9)
10)
11)
12)
13)
если D1 и D2 отвечают равносильным комплексам с одинаковыми входными и выходными кортежами.
14)
если D – произведение D1 и D2
15)
если не пересекаются кортежи:
входной и выходной
рабочий и выходной
16)
если D2 обратен справа D1
17)
если элементы выходного кортежа D1 являются несущественными аргументами D2 и наоборот, а их рабочие кортежи не пересекаются ни с входом ни с выходомкортежей другого.
18)
Обратите внимание на лекцию "5. Репортаж".
D y:=x+1
P y>5
P’ x+1 > 5
