Теоретическое программирование

Схемы программ
Программа – способ задания алгоритма.
Свойства программ:
является конструктивным объектом;
работает конечное время;
характерны массовость и однозначность.

Схемы программ – математические модели программ.
Свойства схем программ:
позволяют изучать свойства широких классов программ;
сохраняют все свойства и особенности рассматриваемого класса программ;
позволяют игнорировать несущественные свойства;
изобразительно подобны программе.

Стандартные схемы программ
Класс стандартных схем включает:
константы;
простые переменные;
выражения;
операторы присваивания;
условные операторы;
метки;
переходы на метки.
Класс стандартных схем характеризуется:
базисом класса;
структурой схем.

Базис В класса стандартных схем состоит:
4 счетных множества символов;
множество операторов.
Множества символов:
Переменные:
Х={х1, х2...хn; у, у1 у2...; z, z1, z2...};
Функциональные символы:
F={f(0), f(1), f(2)...; g(0), g(1), g(2)...; h(0), h(1), h(2)...};
Предикатные символы:
Р={р(0), р(1), р(2)...; q(0), q(1), q(2)...;};
Специальные символы:
старт, стоп, (, ), := и т. д.

Множество операторов:
1) начальный оператор:
старт(х1, х2...хk);
2) заключительный оператор:
стоп (t1, t2...tn);
3) оператор присваивания:
х:=t;
4) условный оператор (тест);
5) оператор петли.

Программа:
void main(void)
{ int x, y;
cin>>x;
y=1;
while (x>0)
{ y=x*y;
x--; }
cout<
}
Схема программы:
0: старт (х) на 1,
1: у: = а на 2,
2: если р(х) то 5 иначе 3,
3: у: = g (x,y) на 4,
4: х: = h (x) на 2,
5: стоп (у).
старт (х),
у: = а,
2: если р(х) то 5 иначе 3,
3: у: = g (x,y),
х: = h (x) на 2,
5: стоп (у).

Интерпретация:
область интерпретации D - множество целых неотрицательных чисел;
I(x)=4; I(y)=0; I(a)=1;
I(g)=G, где G(d1,d2)= d1*d2;
I(h)=H, где H(d)= d-1;
I(p)=P, где P - предикат
0, если d>0
P(d)= 1, иначе

Рекурсивные схемы
FACT(x),
FACT(x)=если х=0 то 1 иначе x*FACT(x-1).
FACT(4)=если 4=0 то 1 иначе 4*FACT(4-1)= =4*FACT(3)=4*(если 3=0 то 1 иначе 3*FACT(3-1))= =4*3*FACT(2)=12*(если 2=0 то 1 иначе 2*FACT(2-1))= =12*2*FACT(1)=24*(если 1=0 то 1 иначе 1*FACT(1-1))= =24*1*FACT(0)=24*(если 0=0 то 1 иначе 0*FACT(0-1))=24

Базис РС включает:
4 счетных множества символов:
Переменные;
Функциональные символы;
Предикатные символы;
Специальные символы.
Множество логических выражений.
Множество термов.
Множество функциональных символов:
Множество базовых функциональных символов (f(1), g(2));
Множество определяемых функциональных символов (F(1), G(2)).

Термы:
1. Простые термы
Базовые термы;
Вызовы (F(n)(t1, t2, …, tn)).
2. Условные термы:
если π то t1 иначе t2.
Пример:
базовые термы - f(x, g(x, y)); h(h(a));
вызовы - F(x); H(H(a)); F(H(x), f(x,y));
условный терм
если p(x, y) то h(h(a)) иначе F(x).

Рекурсивное уравнение:
F(n)(x1, x2, …, xn)=t(x1, x2, …, xn)
Рекурсивная схема: (t, M)
Рекурсивная программа: (RS, I)
Примеры РС:
1) RS1: F(x),
F(x)=если p(x) то a иначе g(x, F(h(x))).
2) RS2: A(x, y),
A(x, y)=если p(x) то f(x) иначе B(x, y),
B(x, y)=если p(y) то A(g(x), a) иначе C(x, y);
C(x, y)=A(g(x), A(x, g(y))).
3) RS3: F(x),
F(x)=если p(x) то x иначе f(F(g(x)), F(h(x))).

Протокол выполнения рекурсивной программы
RS1: F(x),
F(x)=если p(x) то a иначе g(x, F(h(x))).
I(x)=4; I(a)=1;
I(g)=G, где G(d1,d2)= d1*d2;
I(h)=H, где H(d)= d-1;
I(p)=P, где P (d)=1, если d=0, иначе P (d)=0.

Трансляция схем программ
Теорема Маккарти: Класс стандартных схем транслируем в класс рекурсивных схем.
Алгоритм трансляции:
Точки сечения
i ⬄ Fi(x, y, …, z);
старт ⬄ F1(x, y, …, z);
стоп(х) ⬄ x;
Граф рассекается по точкам сечения;
Для каждого фрагмента строится рекурсивное уравнение:
Fi(x, y, …, z)=…

Fi(x, y, …, z) = t(x, y, …, z);

Пример 1:
F1(x, y)
F2(x, y)
y

F2(x, a)
=F2(x, a)
y
F2(h(x), y)
F2(h(x), g(x, y))
F1(x, y) = F2(x, a),
F2(x, y) = если P(x) то y иначе F2(h(x), g(x,y))

Пример 2:
F1(x, y)
F2(x, y)
F3(x, y)
y
F2(x, f(x))
F1(x, y) = F2(x, f(x)),
y
h(x)
h(f(y))
F3(f(x), y)
F2(x, y) = если p(y) то h(f(y)) иначе F3(f(x), y),
h(x)
F2(x, f(x))
F3(x, y) = если p(x) то h(x) иначе F2(x, f(x)).

Линейные унарные рекурсивные схемы
F(x),
F(x) = если p(x) то f(x) иначе F(F(g(x))).
F(a),
F(x) = если p(x) то x иначе G(x),
G(x) = если q(x) то f(F(f(x))) иначе g(F(g(x))).
Теорема (Патерсон-Хьюит). Класс линейных унарных рекурсивных схем транслируем в класс стандартных схем.

Схемы с процедурами
Главная схема
x=F(n)(y1, y2, …, yn)
Множество схем процедур.

Трансляция рекурсивных схем в схемы с процедурами
(старт (y1, y2, …, yn),
1: y:=t (y1, y2, …, yn),
2: стоп (y)).
Fi(x1, …, xn) = если p(xi, …, xn) то ti1 иначе ti0
Fi(x1, …, xn) = (старт,
1: если p(xi1, …, xil) то 2 иначе k,
2: S(v, ti1) на m,
k: S(v, ti0),
m: стоп (v)).
S(v, t) :
а) если t=х, то S(v, t) => v:=x;
б) если t=ϕ(n) (t1, …,tn), то
S(v, t) = σ1, σ2, …, σn, v:=ϕ(n) (z1, …, zn),
⎧ zi:=x, если ti – переменная х,
σi = ⎨
⎩S(zi, ti) в противном случае.

Рекурсивная схема:
S: F(x),
F(x)=если p(x) то x иначе f(F(g(x)), F(h(x)))
Схема с процедурами:

F0(x,x1,y,y1)
F1(x,x1,y,y1)
y
F1(x,b,y,y1)
F1(x,b,y,a)
F1(x,b,a,a)
F0(x,x1,y,y1)=F1(x,b,a,a)
y
F1(x,x1,y,y1)
F1(x,f4(x1),y,y1)
F1(x,f4(x1),f3(y,y1),y1)
F1(x,f4(x1),f3(y,f2(y1,x1)),f2(y1,x1))
F1(x,f4(x1),f3(y,f2(f1(x1),x1)),f2(f1(x1),x1))
F1(x,x1,y,y1)= если p(x1,x) то y
иначе
F1(x,f4(x1),f3(y,f2(f1(x1),x1)),
f2(f1(x1),x1))

F0(x,x1,y,y1)=F1(x,b,a,a)
F1(x,x1,y,y1)= если p(x1,x) то y
иначе F1(x,f4(x1),f3(y,f2(f1(x1),x1)),f2(f1(x1),x1))
S: (старт (x),
1: x1:=b;
2: y:=a;
3: y1:=a;
4: y:=F1(x,x1,y,y1);
5: стоп (y))
F1(x,x1,y,y1)=(старт,
1: если p(x1,x) то 7 иначе 2
2: y1:=f1(x1);
3: y1:=f2(y1,x1);
4: y:=f3(y,y1);
5: x1:=f4(x1);
6: v:=F1(x,x1,y,y1) на 8;
7: v:=y;
8: стоп (v))

Обогащенные схемы
класс счетчиковых схем;
интерпретированные операторы:
c:=c+1; c:=c-1; c=0; c1:=c2;
F(x),
F(x)= если р(х) то х
иначе f(x, F(g(x)))

класс магазинных схем;
интерпретированные
операторы:
M:=x; x:=M; M=Ø;
класс схем с массивами;
интерпретированные
операторы:
A[c]:=x; x:=A[c].

Трансляция обогащенных схем:
Y — стандартные схемы; Y(М) — магазинные схемы;
Y(R) — рекурсивные схемы; Y(А) — схемы с массивами;
Y(с) — счетчиковые схемы; Y(P) — схемы с процедурами.

Структурированные схемы
(о0, о1, …, оn)
Специальные символы: если, то, иначе, пока, цикл, конец.
Три типа схемных операторов:
простой оператор;
условный оператор:
если π то σ1 иначе σ0 конец.
оператор цикла:
пока π цикл σ конец
до π цикл σ конец.