Что такое 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
  • Количество просмотров: 188
  • Количество скачиваний: 0
- Предыдущая Первые общерусские князья (10 класс)
Следующая - Перелiк пам'яток архiтектури та образотворчого мистецтва, обов'язкових для розпiзнавання абiтурiєнтами

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

Устройства ввода информации Устройства ввода информации 183
История символа @ История символа @ 122
Информационная безопасность Информационная безопасность 98
Устройства компьютера Устройства компьютера 114
Преобразование рисунка Преобразование рисунка 139
Информация и знания Информация и знания 100
Конспект урока информатики в 6 классе Тема Нумерованный и маркированный списки Конспект урока информатики в 6 классе Тема Нумерованный и маркированный списки 121
Информационные технологии Информационные технологии 110
Ветвящаяся алгоритмическая конструкция Ветвящаяся алгоритмическая конструкция 126
Презентация по информатике для 6 класса Алгоритмы и исполнители Презентация по информатике для 6 класса Алгоритмы и исполнители 114
Модели и моделирование. Модели и их типы Модели и моделирование. Модели и их типы 136
Компьютер архитектурасы Компьютер архитектурасы 137
prezentatsiya no1 kinostudiya prezentatsiya no1 kinostudiya 122
Презентация к уроку Разработка плана действий и его запись (Босова 5 класс) Презентация к уроку Разработка плана действий и его запись (Босова 5 класс) 103
Программирование на алгоритмическом языке. Часть III (9 класс) Программирование на алгоритмическом языке. Часть III (9 класс) 112
Презентация по информатике Префиксные коды Презентация по информатике Префиксные коды 174
Работа с DOM-моделью и пользовательский интерфейс Работа с DOM-моделью и пользовательский интерфейс 123
Методы шифрования Методы шифрования 135
Алгоритмы Алгоритмы 102
Реляционная база данных Реляционная база данных 134
Презентация по информатике Информационные процессы и технологии Презентация по информатике Информационные процессы и технологии 149
Презентация по информатике Роль информации в современном обществе Презентация по информатике Роль информации в современном обществе 152
Форматирование документа. Выбор параметров страницы Форматирование документа. Выбор параметров страницы 105
Система требований к электронным учебным презентациям Система требований к электронным учебным презентациям 115
Требования к кабинету информатики Требования к кабинету информатики 126
Компьютерные вирусы и антивирусные программы Компьютерные вирусы и антивирусные программы 108
Задача о потоке минимальной стоимости Задача о потоке минимальной стоимости 123
Эволюция данных Эволюция данных 105
Презентация к уроку информатики Устройство ПК Презентация к уроку информатики Устройство ПК 124
Анализ образовательного сайта Анализ образовательного сайта 72