F T. p1 (1->2) p2 (2->2) p3 (2->6) Пример: Доказательство правильности рекурсивных программ Пример 1: F(x) if x=1 then 1 else x*F(x-1); 1.F(1)=1!

Презентация:



Advertisements
Похожие презентации
Денотационная семантика 0 |1|1 | 0 | 1 Mb:Mb: М b ('0') = 0, М b ('1')=1 М b ( '0') = =2 * М b ( ) М b ( 1) = =2 * М b ( ) + 1.
Advertisements

Рекурсия Презентация разработана учителем информатики лицея 124 г.Барнаула Воловиковой Л.Л.
Основы алгоритмизации и программирования Лекция 2. А.Ф.ОСЬКИН ПГУ, Полоцк.
Пример1 Мир
Правило вывода для условного оператора if В then А 1 else А 2 {P B} A1 {Q}, {P } А 2 {Q} |-{P} if B then A1 else A2 {Q} (6) Задача Докажем истинность {t}
Информатика ЕГЭ Уровень А5. Вариант 1 Определите значения переменных a, b, c после выполнения следующего фрагмента программы: a:=5; b:=1; a:=a+b; if a>10.
Найдите ошибки: 1. if a = b then begin c:=1 else c:=0; 2. if a = b then c:=1; end else c:=0; 3. if a = b then c:=1; d:=1; else x:=1; Исправлено if a =
Пример 2 Записать корректно подстановку Решение. Пример 3 Вычислить функцию-константу: Решение.
Ветвление и условный оператор Паскаль-3. Ветвление – это такой вычислительный процесс При котором выбирается одно из нескольких заранее предусмотренных.
Основные типы алгоритмических структур. Линейный алгоритм ( следование ) Алгоритм, в котором команды выполняются последовательно одна за другой, называется.
Рекурсия Начальные сведения о рекурсии. Определение рекурсии Рекурсия (от латинского recursio - возвращение) - это такой способ организации вычислительного.
Логарифмическая функция. Её свойства и график. Определение.
Рекурсивное программирование Рекурсия – это метод, сводящий общую задачу к некоторым задачам более узкого, простого типа Рекурсивный алгоритм – это алгоритм,
Приближенное решение уравнений Найти корень уравнения x 3 – cosx = 0 приближенными методами (графическим и численным методом деления числового отрезка.
Алгоритмические конструкции. Решить задачу при х=16, у=2.
Выбор действий в Бейсике (ветвление). Задача: найти максимальное число из двух чисел. Словесная форма записи: Алгоритм MAX Начало 1. Запросить числа A,
Перестановки и факториалы Фамилии авторов Яковлева О.Е Егорова Е.Н
Языки и методы программирования Преподаватель – доцент каф. ИТиМПИ Кузнецова Е.М. Лекция 5.
Условный оператор. Определение линейного алгоритма. Линейный алгоритм – это алгоритм, этапы которого выполняются однократно и строго последовательно.
Теория вычислительных процессов 4 курс, 8 семестр Преподаватель: Веретельникова Евгения Леонидовна 1.
Транксрипт:

F T

p1 (1->2) p2 (2->2)

p3 (2->6)

Пример:

Доказательство правильности рекурсивных программ Пример 1: F(x) if x=1 then 1 else x*F(x-1); 1.F(1)=1! 2.Если F(N)=1*2*…*N=N!, то F(N+1)=1*2*…*N*(N+1)=(N+1)! F(N)=N! – гипотеза N 1 F(N+1) = (N+1)*F(N) =(N+1)*(N!)= (N+1)*(1*2*…*N) = =(1*2*…*N)*(N+1) = (N+1)!

Пример 2: A(X1, X2) IF X1=0 THEN X2+1 ELSE IF X2=0 THEN A(X1-1, 1) ELSE A(X1-1, A(X1, X2-1)) А(1, 2)= =А(0, А(1, 1))= =А(0, А(0, А(1, 0)))= =А(0, А(0, А(0, 1)))= =А(0, А(0, 2))= =А(0, 3)= =4

(Х1, X2)

Х1=0, А(Х1, Х2) Х10, Х2=0, А(Х1, Х2)=А(Х1-1, 1) (Х1-1, 1)< (Х1, Х2), А(Х1-1, 1) А(Х1, Х2) – заканчивается! Х10, Х20, А(Х1, Х2)= A(X1-1, A(X1, X2-1)) А(Х1, Х2-1), (Х1, Х2-1)< (Х1, Х2) А(Х1, Х2-1) – заканчивается! А(Х1-1, Н) (Х1-1, Н)< (Х1, Х2), А(Х1-1, Н) вычисление (Х1, Х2) заканчивается.

Пример 3: F(N) IF N>100 THEN N-10 ELSE F(F(N+11)) Если N>100, то F(N)=N-10. F(N)=91 при N

2. F(N)=91 – гипотеза индукции N

Анализ завершения последовательных программ Метод счетчиков Метод Флойда

Метод фундированных множеств Флойда Частично упорядоченное множество (W, R): a, b, c W, R(a,b) R(b,c) R(a,c) a, b W, R(a,b) R(b,a) a W R(a,a) 1.Точки сечения iq i (x, y) 2.Оценочные функции (W, R) iu i (x, y) 3.Условия завершимости i u i (x, y) j u j (x, y)