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! - презентация

1 F T

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

3 p3 (2->6)

4 Пример:

5

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

7 Пример 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

8 (Х1, X2)

9 Х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) заканчивается.

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

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

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

13 Метод фундированных множеств Флойда Частично упорядоченное множество (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)