Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Теоретическое программирование

Содержание

Схемы программПрограмма – способ задания алгоритма.Свойства программ:является конструктивным объектом;работает конечное время;характерны массовость и однозначность.
Теоретическое программированиеМатематические основы программирования;Теория схем программ;Семантическая теория программ;Теория параллельных вычислений;Прикладные задачи теоретического программирования. Схемы программПрограмма – способ задания алгоритма.Свойства программ:является конструктивным объектом;работает конечное время;характерны массовость и однозначность. Схемы программ – математические модели программ.Свойства схем программ:позволяют изучать свойства широких классов Стандартные схемы программКласс стандартных схем включает:константы; простые переменные; выражения; операторы присваивания; условные Базис В класса стандартных схем состоит:4 счетных множества символов;множество операторов.Множества символов:Переменные: Х={х1, Множество операторов:1) начальный оператор: старт(х1, х2...хk);2) заключительный оператор: стоп (t1, t2...tn);3) оператор Программа:void main(void){ int x, y; cin>>x; y=1; while (x>0) { y=x*y; x--; } cout Интерпретация:область интерпретации D - множество целых неотрицательных чисел;I(x)=4; I(y)=0; I(a)=1;I(g)=G, где G(d1,d2)= Рекурсивные схемыFACT(x),FACT(x)=если х=0 то 1 иначе x*FACT(x-1).FACT(4)=если 4=0 то 1 иначе 4*FACT(4-1)= Базис РС включает:4 счетных множества символов:Переменные;Функциональные символы;Предикатные символы;Специальные символы.Множество логических выражений.Множество термов.Множество Термы:1. Простые термыБазовые термы;Вызовы (F(n)(t1, t2, …, tn)).2. Условные термы: если π Рекурсивное уравнение:F(n)(x1, x2, …, xn)=t(x1, x2, …, xn)Рекурсивная схема: (t, M)Рекурсивная программа: (RS, I)Примеры Протокол выполнения рекурсивной программы RS1: F(x), F(x)=если p(x) то a иначе g(x, F(h(x))).I(x)=4; Трансляция схем программТеорема Маккарти: Класс стандартных схем транслируем в класс рекурсивных схем.Алгоритм Fi(x, y, …, z) = t(x, y, …, z); Пример 1:F1(x, y)F2(x, y)y F2(x, a)=F2(x, a)yF2(h(x), y)F2(h(x), g(x, y))F1(x, y) = F2(x, a),F2(x, y) = Пример 2:F1(x, y)F2(x, y)F3(x, y)yF2(x, f(x))F1(x, y) = F2(x, f(x)),yh(x)h(f(y))F3(f(x), y)F2(x, y) Линейные унарные рекурсивные схемыF(x),F(x) = если p(x) то f(x) иначе F(F(g(x))).F(a),F(x) = Схемы с процедурамиГлавная схема x=F(n)(y1, y2, …, yn)Множество схем процедур. Трансляция рекурсивных схем в схемы с процедурами(старт (y1, y2, …, yn), 1: Рекурсивная схема: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)yF1(x,b,y,y1)F1(x,b,y,a)F1(x,b,a,a)F0(x,x1,y,y1)=F1(x,b,a,a)yF1(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: Обогащенные схемыкласс счетчиковых схем; интерпретированные операторы: c:=c+1; c:=c-1; c=0; c1:=c2;F(x),F(x)= если р(х) класс магазинных схем; интерпретированные операторы: M:=x; x:=M; M=Ø;класс схем с массивами; Трансляция обогащенных схем:Y — стандартные схемы; Y(М) — магазинные схемы;Y(R) — рекурсивные схемы; Y(А) Структурированные схемы(о0, о1, …, оn) Специальные символы: если, то, иначе, пока, цикл,
Слайды презентации

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

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

объектом;
работает конечное время;
характерны массовость и однозначность.

Слайд 3 Схемы программ – математические модели программ.
Свойства схем программ:
позволяют

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

изучать свойства широких классов программ;
сохраняют все свойства и особенности

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

Слайд 4 Стандартные схемы программ
Класс стандартных схем включает:
константы;
простые переменные;

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


выражения;
операторы присваивания;
условные операторы;
метки;
переходы на метки.


Класс стандартных схем характеризуется:
базисом класса;
структурой схем.

Слайд 5 Базис В класса стандартных схем состоит:
4 счетных множества

Базис В класса стандартных схем состоит: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)...;};
Специальные символы: старт, стоп, (, ), := и т. д.

Слайд 6 Множество операторов:

1) начальный оператор: старт(х1, х2...хk);
2) заключительный оператор: стоп (t1,

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

t2...tn);
3) оператор присваивания: х:=t;
4) условный оператор (тест);
5) оператор петли.

Слайд 7 Программа:

void main(void)
{ int x, y;
cin>>x;
y=1;
while

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

(x>0)
{ y=x*y;
x--;
}
cout

(х) на 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: стоп (у).

Слайд 8 Интерпретация:
область интерпретации D - множество целых неотрицательных чисел;
I(x)=4;

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

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, иначе



Слайд 9 Рекурсивные схемы
FACT(x),
FACT(x)=если х=0 то 1 иначе x*FACT(x-1).

FACT(4)=если 4=0

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

то 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

Слайд 10 Базис РС включает:
4 счетных множества символов:
Переменные;
Функциональные символы;
Предикатные символы;
Специальные

Базис РС включает:4 счетных множества символов:Переменные;Функциональные символы;Предикатные символы;Специальные символы.Множество логических выражений.Множество

символы.
Множество логических выражений.
Множество термов.
Множество функциональных символов:
Множество базовых функциональных символов

(f(1), g(2));
Множество определяемых функциональных символов (F(1), G(2)).

Слайд 11 Термы:
1. Простые термы
Базовые термы;
Вызовы (F(n)(t1, t2, …, tn)).
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).

Слайд 12 Рекурсивное уравнение:
F(n)(x1, x2, …, xn)=t(x1, x2, …, xn)
Рекурсивная

Рекурсивное уравнение:F(n)(x1, x2, …, xn)=t(x1, x2, …, xn)Рекурсивная схема: (t, M)Рекурсивная программа: (RS,

схема: (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))).

Слайд 13 Протокол выполнения рекурсивной программы
RS1: F(x),
F(x)=если p(x) то

Протокол выполнения рекурсивной программы RS1: F(x), F(x)=если p(x) то a иначе g(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.

Слайд 14 Трансляция схем программ
Теорема Маккарти: Класс стандартных схем транслируем

Трансляция схем программТеорема Маккарти: Класс стандартных схем транслируем в класс рекурсивных

в класс рекурсивных схем.
Алгоритм трансляции:
Точки сечения i ⬄ Fi(x, y,

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

Слайд 15 Fi(x, y, …, z) = t(x, y, …,

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

z);



Слайд 16 Пример 1:
F1(x, y)
F2(x, y)
y

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

Слайд 17
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, a)yF2(h(x), y)F2(h(x), g(x, y))F1(x, y) = F2(x, a),F2(x, y)

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

F2(h(x), g(x,y))

Слайд 18 Пример 2:


F1(x, y)
F2(x, y)
F3(x, y)
y
F2(x, f(x))
F1(x, y) =

Пример 2:F1(x, y)F2(x, y)F3(x, y)yF2(x, f(x))F1(x, y) = F2(x, f(x)),yh(x)h(f(y))F3(f(x), y)F2(x,

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)).

Слайд 19 Линейные унарные рекурсивные схемы
F(x),
F(x) = если p(x) то

Линейные унарные рекурсивные схемыF(x),F(x) = если p(x) то f(x) иначе F(F(g(x))).F(a),F(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))).

Теорема (Патерсон-Хьюит). Класс линейных унарных рекурсивных схем транслируем в класс стандартных схем.

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

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

процедур.

Слайд 21 Трансляция рекурсивных схем в схемы с процедурами
(старт (y1,

Трансляция рекурсивных схем в схемы с процедурами(старт (y1, y2, …, yn),

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) в противном случае.

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

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

F(h(x)))

Схема с процедурами:

Слайд 23 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,x1,y,y1)yF1(x,b,y,y1)F1(x,b,y,a)F1(x,b,a,a)F0(x,x1,y,y1)=F1(x,b,a,a)yF1(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))

Слайд 24 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:

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:

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))

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

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

если р(х) то х
иначе f(x, F(g(x)))

Слайд 26 класс магазинных схем; интерпретированные операторы: M:=x; x:=M; M=Ø;

класс схем с

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

массивами; интерпретированные операторы: A[c]:=x; x:=A[c].

Слайд 27 Трансляция обогащенных схем:

Y — стандартные схемы; Y(М) — магазинные

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

схемы;
Y(R) — рекурсивные схемы; Y(А) — схемы с массивами;
Y(с) —

счетчиковые схемы; Y(P) — схемы с процедурами.

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

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

то, иначе, пока, цикл, конец.

Три типа схемных операторов:


простой оператор;
условный оператор: если π то σ1 иначе σ0 конец.
оператор цикла: пока π цикл σ конец до π цикл σ конец.
  • Имя файла: teoreticheskoe-programmirovanie.pptx
  • Количество просмотров: 210
  • Количество скачиваний: 0
- Предыдущая Первые общерусские князья (10 класс)
Следующая - Перелiк пам'яток архiтектури та образотворчого мистецтва, обов'язкових для розпiзнавання абiтурiєнтами

Похожие презентации

Презентация по теме: Счастливый случай Презентация по теме: Счастливый случай 164
Презентация к уроку Графика в Паскаль 8 класс Презентация к уроку Графика в Паскаль 8 класс 131
Порядок действий Порядок действий 116
Вирусы и антивирусные программы Вирусы и антивирусные программы 97
Основы работы с файловым менеджером Тotal Сommander Основы работы с файловым менеджером Тotal Сommander 121
Компьютер и программное обеспечение компьютера Компьютер и программное обеспечение компьютера 122
Лекция 1 - Платформа .NET и ее особенности Лекция 1 - Платформа .NET и ее особенности 140
Кодирование информации. (5 класс) Кодирование информации. (5 класс) 125
Геоинформационная система (ГИС) Геоинформационная система (ГИС) 134
Подготовка к контрольной работе по 3-му разделу Подготовка к контрольной работе по 3-му разделу 131
Проект на тему Лабиринты Итернета Проект на тему Лабиринты Итернета 142
Информационные модели Информационные модели 133
История создания средств коммуникаций История создания средств коммуникаций 121
Подготовка к 1му заданию ОГЭ информатика Подготовка к 1му заданию ОГЭ информатика 224
Решение задач на кодирование звуковой информации Решение задач на кодирование звуковой информации 187
Презентация Нетикет Презентация Нетикет 155
Современные носители информации Современные носители информации 108
Назначение и устройство компьютера. Компьютерная память Назначение и устройство компьютера. Компьютерная память 121
xml xml 208
Урок 11. Разные объекты с общим названием Урок 11. Разные объекты с общим названием 164
Графический способ решения систем уравнений Графический способ решения систем уравнений 96
Оформление списка литературы. Библиографические БД Оформление списка литературы. Библиографические БД 122
Мультимедийные технологии Мультимедийные технологии 169
ПОСТРОЕНИЕ ДИАГРАММ И ГРАФИКОВ ПОСТРОЕНИЕ ДИАГРАММ И ГРАФИКОВ 123
Безопасная работа в социальных сетях: общение, публикация материалов Безопасная работа в социальных сетях: общение, публикация материалов 173
Деректер қорын басқаратын жүйелердің басты функциялары Деректер қорын басқаратын жүйелердің басты функциялары 128
Задачи на дроби Задачи на дроби 139
Из чего состоит системный блок? Из чего состоит системный блок? 135
Возможности и использование МКК (мобильного компьютерного класса) в учебном процессе Возможности и использование МКК (мобильного компьютерного класса) в учебном процессе 145
Алгоритм и его формальное исполнение Алгоритм и его формальное исполнение 112