Теоретическое программирование Математические основы программирования; Теория схем программ; Семантическая теория программ; Теория параллельных вычислений; Прикладные задачи теоретического программирования.

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

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

Программа: void main(void) { int x, y; cin>>x; y=1; while (x>0) { y=x*y; x--; } cout

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

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

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

Графовая форма стандартной схемы Виды вершин графа ССП: 1.Начальная вершина. 2.Заключительная вершина. 3.Вершина - преобразователь. 4.Вершина - распознаватель. 5.Вершина - петля. Память схемы S (X S ) – конечное множество переменных

ССП в графовой форме:

Линейная форма стандартной схемы 0: старт (х 1,...х n ) на l ; l : x:=t на l 1; l : стоп (t 1,...,t m ); l : если р(t 1,...,t k ) то l 1 иначе l 0; l : петля; 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, которая сопоставляет: 1) х => d= I (x); 2) а => d= I (а); 3) f (n) (n>=1) => F (n) = I (f (n) ); 4) р (0) => {0,1}; 5) р (n) (n>=1) => P (n) = I (p (n) ).

Стандартная программа (СП)(S, I ) Состояние памяти программы (S, I ) W:X S DW(x) Начальное состояние памяти W 0 (x)= I (x) Значение терма t (t I (W)) определяется: 1) если t=х, то t I (W)= W (x); 2) если t=а, то t I (W)= I (a); 3) если t=f (n) (t 1, t 2... t n ), то t I (W)= I (f (n) )(t 1 I (W), t 2 I (W),... t n I (W)). Значение теста ( I (W)) определяется: если =р (n) (t 1, t 2... t n ), n>=0, то I (W)= I (p (n) )(t 1 I (W), t 2 I (W),... t n I (W)).

Конфигурация программы (состояние выполнения) U=( l,W) Протокол (U 0, U 1,...U i, U i+1,...) выполнения программы (S, I ) определяется: 1. U 0 =(0, W 0 ); 2. Пусть U i =(K i, W i ) - i- конфигурация ПВП, а О - оператор схемы S в вершине с меткой K i. а) О - начальный оператор => K i+1 = l и W i+1 = W i ; б) О - оператор присваивания х:=t => K i+1 = l, W i+1 (х)= t I (W i ); в) О - условный оператор и I (W i )=Δ, где Δ 0,1, K i+1 = l и W i+1 = W i ; г) О - оператор петли => K i+1 = l и W i+1 = W i

Интерпретация: область интерпретации D - множество целых неотрицательных чисел; I(x)=4; I(y)=0; I(a)=1; I(g)=G, где G - функция умножения чисел, т. е. G(d1,d2)= d1*d2; I(h)=H, где H - функция вычитания единицы, т. е. H(d)= d-1; I(p)=P, где P - предикат "равно 0", т.е. P (d)=1, если d=0, иначе P (d)=0. Программа (S, I) вычисляет 4! Конфигурация U0U0 U1U1 U2U2 U3U3 U4U4 U5U5 U6U6 U7U7 U8U8 U9U9 U 10 U 11 U 12 Метка Значения X Y