1 Programowanie imperatywne i granice obliczalności Copyright, 2004 © Jerzy R. Nawrocki [email protected] http://www.cs.put.poznan.pl/jnawrocki/tpi/ Teoretyczne podstawy informatyki Wykład 2

2 J.Nawrocki, Programowanie imperatywne.. Plan wykładu Schematy blokowe Liczba automorficzna Obliczanie wielomianu Podział zbioru Problem stopu

3 J.Nawrocki, Programowanie imperatywne.. Język schematów blokowych R 1 R 1 S S + 1 S S + 1 R2 > 0 Tak Nie Start Stop

4 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna Liczba naturalna znajdująca się na końcu swego kwadratu. 5 bo 5 2 = 25 6 bo 6 2 = 36 7 nie bo 7 2 = 49 25 bo 25 2 = 625

5 J.Nawrocki, Programowanie imperatywne.. Liczba automorficznaStart Czytaj n Automor(n) TakDrukuj(TAK) NieDrukuj(NIE) Stop var n; begin read(n); if Automor(n) then writeln(TAK) else writeln(NIE) end. Funkcja nie- standardowa

6 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna Liczba naturalna znajdująca się na końcu swego kwadratu. rząd(n) = 10 liczba_cyfr(n) n = n*n mod rząd(n) Jak obliczyć Automor(n) ? 5 = 5*5 mod rząd(5) = 25 mod 10 = 5 6 = 6*6 mod rząd(6) = 36 mod 10 = 6 7 7*7 mod 10 = 9

7 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna Tak Wynik true Nie Wynik false n=n*n mod rząd(n) function Automor (n: integer): Boolean; begin if n=n*n mod rzad(n) then Automor:= true else Automor:= false end; Deklaracja funkcji Automor

8 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna function Automor (n: integer): Boolean; begin if n=n*n mod rzad(n) then Automor:= true else Automor:= false end; function Automor (n: integer): Boolean; begin Automor:= n=n*n mod rzad(n) end;

9 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna Jak obliczyć rzad(n) ? rząd(1)=.. = rząd(9)=10 rząd(10)=.. = rząd(99)=100 rząd(100)=.. = rząd(999)=1000 rząd(n) = 10 liczba_cyfr(n) rząd(n) = 10, 100, 1000,.. rząd(n) > n

10 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna rz 10 rz

11 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna rz 10 rz

12 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna rz 10 rz

13 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna rz 10 rz

14 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna Program główny Automor(n) rzad(n) Czy można połączyć Automor i rzad?

15 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna function rzad (n: integer): integer; var rz: integer; begin rz:= 10; while rz

16 J.Nawrocki, Programowanie imperatywne.. Liczba automorficzna function Automor (n: integer): Boolean; var rz: integer; begin rz:= 10; while rz

17 J.Nawrocki, Programowanie imperatywne.. Obliczanie wielomianu Wielomian n-tego stopnia ma postać: p(x) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 +.. + a n x n Mając dane wartości: n a 0, a 1,.., a n x należy obliczyć wartość p(x).

18 J.Nawrocki, Programowanie imperatywne.. Obliczanie wielomianu p(x) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 +.. + a n x n p(x) = s(0) + s(1) + s(2) +.. + s(n) gdzie s(i) = a i x i s(i) = a i *x*x*.. *x Dekompozycja problemu Suma n liczb Iloczyn n liczb

19 J.Nawrocki, Programowanie imperatywne.. Obliczanie wielomianuStart Stop i 0 P 0 P P + s(i) i i + 1 i n Tak Nie function p(n: integer): real; var i,P: integer; begin i:= 0; P:= 0; while i

20 J.Nawrocki, Programowanie imperatywne.. Obliczanie wielomianu S= c(0) * c(1) *.. * c(j) 0, 1,.. jStart Stop i 0 S 1 S S * c(i) i i + 1 i j Tak Nie Obliczanie s(j) = a j x j c(0) = a j c(1) = x c(2) = x... c(j) = x

21 J.Nawrocki, Programowanie imperatywne.. Obliczanie wielomianuStart Stop S a j i 1 S S * x i i + 1 i j Tak Nie i 0 S 1 S S * c(i) i i + 1 Obliczanie s(j) = a j x j S= c(0) * c(1) *.. * c(j) 0, 1,.. j c(0) = a j c(1) = x c(2) = x... c(j) = x

22 J.Nawrocki, Programowanie imperatywne.. Obliczanie wielomianuStart Stop S a j i 1 S S * x i i + 1 i j Tak Nie Obliczanie s(j) = a j x j function s(j: integer): real; var i,S: integer; begin S:= a[j]; i:= 1; while i

23 J.Nawrocki, Programowanie imperatywne.. Obliczanie wielomianu Złożoność algorytmu (n+1) razy s(i): s(0).. s(n) Każde s(i): i mnożeń Razem: 0 + 1 +.. + (n+1) = Złożoność= a*n 2 + b*n + c

24 J.Nawrocki, Programowanie imperatywne.. Obliczanie wielomianu P(x)= (((a n )*x + a n-1 )*x + a n-2 )*x + a n-3... Schemat Hornera Jak zmniejszyć liczbę mnożeń? a 1 *x + a 0 = a 1 *x + a 0 a 2 *x 2 + a 1 *x + a 0 = (a 2 *x + a 1 )*x + a 0 a 3 *x 3 + a 2 *x 2 + a 1 *x + a 0 = ((a 3 *x + a 2 )*x + a 1 )x + a 0

25 J.Nawrocki, Programowanie imperatywne.. Problem podzbioru o danej sumie Dane: zbiór A zawierający n liczb całkowitych dodatnich i liczba s. Pytanie: Czy można w A znaleźć podzbiór B taki, że suma liczb w B jest równa s? = 12 s = / 2 = 6 3 4 2 1 2

26 J.Nawrocki, Programowanie imperatywne.. Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456

27 J.Nawrocki, Programowanie imperatywne.. Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 Rozważamy kolejną dwójkę

28 J.Nawrocki, Programowanie imperatywne.. Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 To co było jest nadal osiągalne

29 J.Nawrocki, Programowanie imperatywne.. Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 Dodaj 2 do każdej poprzednio osiągalnej wart. + 2

30 J.Nawrocki, Programowanie imperatywne.. Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 + 2 Dodaj 2 do każdej poprzednio osiągalnej wart.

31 J.Nawrocki, Programowanie imperatywne.. Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 + 2 Dodaj 2 do każdej poprzednio osiągalnej wart.

32 J.Nawrocki, Programowanie imperatywne.. Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 Końcowa postać tabelki

33 J.Nawrocki, Programowanie imperatywne.. Problem stopu Dany jest podprogram X. Czy ten podprogram skończy obliczenia w skończonym czasie?

34 J.Nawrocki, Programowanie imperatywne.. Problem stopu function ZatrzymaSię(P: procedure): Boolean; { ??? } procedure X; { while ZatrzymaSię(X) do ; }

35 J.Nawrocki, Programowanie imperatywne.. Problem stopuZatrzymaSię(X) procedure X Tak Nie Wniosek: Problem stopu jest nierozstrzygalny

36 J.Nawrocki, Programowanie imperatywne.. Podsumowanie Język schematów blokowych jest wygodnym narzędziem opisu algorytmów. Nie wszystko można obliczyć. Wreszcie!