1 Imperatywne modele obliczeń Copyright, 2003 © Jerzy R. Nawrocki [email protected] http://www.cs.put.poznan.pl/jnawrocki/tpi/ Teoretyczne podstawy informatyki Wykład 2

2 J.Nawrocki, Imperatywne modele obliczeń Język schematów blokowych R 1 R 1 S S + 1 S S + 1 R2 > 0 Tak Nie Start Stop

3 J.Nawrocki, Imperatywne modele obliczeń Plan wykładu Schematy blokowe Liczba automorficzna Obliczanie wielomianu Podział zbioru Problem stopu

4 J.Nawrocki, Imperatywne modele obliczeń 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, Imperatywne modele obliczeń Liczba automorficzna Start 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, Imperatywne modele obliczeń 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, Imperatywne modele obliczeń 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, Imperatywne modele obliczeń Liczba automorficzna Jak obliczyć rzad(n) ? rząd(n) = 10, 100, 1000,.. rząd(n) > n rz 10 rz

9 J.Nawrocki, Imperatywne modele obliczeń Liczba automorficzna rz 10 rz

10 J.Nawrocki, Imperatywne modele obliczeń Liczba automorficzna rz 10 rz

11 J.Nawrocki, Imperatywne modele obliczeń Liczba automorficzna rz 10 rz

12 J.Nawrocki, Imperatywne modele obliczeń Liczba automorficzna rz 10 rz

13 J.Nawrocki, Imperatywne modele obliczeń Liczba automorficzna rz 10 rz

14 J.Nawrocki, Imperatywne modele obliczeń Liczba automorficzna rz 10 rz

15 J.Nawrocki, Imperatywne modele obliczeń Liczba automorficzna rz 10 rz

16 J.Nawrocki, Imperatywne modele obliczeń Liczba automorficzna Program główny Automor(n) rzad(n) Czy można połączyć Automor i rzad?

17 J.Nawrocki, Imperatywne modele obliczeń Liczba automorficzna function Automor (n: integer): Boolean; var rz: integer; begin rz:= 10; while rz

18 J.Nawrocki, Imperatywne modele obliczeń Plan wykładu Schematy blokowe Liczba automorficzna Obliczanie wielomianu Podział zbioru Problem stopu

19 J.Nawrocki, Imperatywne modele obliczeń 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

20 J.Nawrocki, Imperatywne modele obliczeń Obliczanie wielomianu Start 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

21 J.Nawrocki, Imperatywne modele obliczeń 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

22 J.Nawrocki, Imperatywne modele obliczeń Obliczanie wielomianu Start 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

23 J.Nawrocki, Imperatywne modele obliczeń Obliczanie wielomianu Start 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:= 0; while i

24 J.Nawrocki, Imperatywne modele obliczeń 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

25 J.Nawrocki, Imperatywne modele obliczeń 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 ) + a 0

26 J.Nawrocki, Imperatywne modele obliczeń Plan wykładu Schematy blokowe Liczba automorficzna Obliczanie wielomianu Podział zbioru Problem stopu

27 J.Nawrocki, Imperatywne modele obliczeń 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

28 J.Nawrocki, Imperatywne modele obliczeń Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456

29 J.Nawrocki, Imperatywne modele obliczeń Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 1. Kopiuj poprzedni wiersz

30 J.Nawrocki, Imperatywne modele obliczeń Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 2. Uwzględnij bieżący element

31 J.Nawrocki, Imperatywne modele obliczeń Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 2. Uwzględnij bieżący element + 2

32 J.Nawrocki, Imperatywne modele obliczeń Problem podzbioru o danej sumie = 12 s = / 2 = 6 1223412234 123456 + 3 2. Uwzględnij bieżący element

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

34 J.Nawrocki, Imperatywne modele obliczeń Problem stopu function ZatrzymaSię(P: procedure): Boolean; { ??? } procedure X; { while ZatrzymaSię(X) do ; }

35 J.Nawrocki, Imperatywne modele obliczeń Problem stopu ZatrzymaSię(X) procedure X Tak Nie Wniosek: Problem stopu jest nierozstrzygalny

36 J.Nawrocki, Imperatywne modele obliczeń Ocena wykładu 1. Wrażenie ogólne? (1 - 6) 2. Zbyt wolno czy zbyt szybko? 3. Czy dowiedziałeś się czegoś ważnego? 4. Co poprawić i jak?