1 Imperatywne modele obliczeń Copyright, 2000 © Jerzy R. Nawrocki [email protected] http://www.cs.put.poznan.pl/~nawrocki/ics/ Wprowadzenie do informatyki Wykład 2

2 J.Nawrocki, Wprowadzenie.., Wykład 2 Plan wykładu Model maszyny RAM Język schematów blokowych Obliczanie n! Koncepcja von Neumanna Kodowanie rozkazów Obliczanie wielomianu Problem stopu

3 J.Nawrocki, Wprowadzenie.., Wykład 2 Model maszyny RAM

4 J.Nawrocki, Wprowadzenie.., Wykład 2 Model maszyny RAM Przykładowe operacje maszyny: przesłanie stałej do rejestru: R1 1 przesłanie iloczynu do rej.: R1 R1 * R2 porównanie rejestru ze stałą: R2 > 0 przesłanie komórki pamięci do rejestru: R1 M [1000]

5 J.Nawrocki, Wprowadzenie.., Wykład 2 Język schematów blokowych R1 1 R2 0 R2 > 0 Tak Nie Start Stop

6 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 A 4 B A x 3 C B x 2 R1 C x 1

7 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 A 4 B A x 3 C B x 2 R1 C x 1

8 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 A 4 B A x 3 C B x 2 R1 C x 1

9 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 A 4 B A x 3 C B x 2 R1 C x 1

10 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 A 4 B A x 3 R1 B x 2 R1 R1 x 1

11 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 A 4 R1 A x 3 R1 R1 x 2 R1 R1 x 1

12 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 4 R1 R1 x 3 R1 R1 x 2 R1 R1 x 1

13 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 4 R1 R1 x 3 R1 R1 x 2 R1 R1 x 1

14 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 R2 R1 R1 x 3 R1 R1 x 2 R1 R1 x 1

15 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 R2 R1 R1 x (R2 - 1) R1 R1 x 2 R1 R1 x 1

16 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 R2 R1 R1 x (R2 - 1) R1 R1 x (R2 - 2) R1 R1 x 1

17 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 R2 R1 R1 x (R2 - 1) R1 R1 x (R2 - 2) R1 R1 x (R2 - 3) R2 R2 - 1

18 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 R2 R1 R1 x R2 R1 R1 x (R2 - 2) R1 R1 x (R2 - 3) R2 R2 - 1

19 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 R2 R1 R1 x R2 R1 R1 x (R2 - 3) R2 R2 - 1

20 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 R2 R1 R1 x R2 R2 R2 - 1 aż R2 = 0

21 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 R2 R2 R2 - 1 czy R2 = 0 ? R1 R1 x R2 R2 R2 - 1 czy R2 = 0 ?...

22 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = 0 Warunek końc.: R1 = 1 0!= 1 R1 R2 R2 R2 - 1 czy R2 = 0 ? R1 R1 x R2 R2 R2 - 1 czy R2 = 0 ?...

23 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = 0 Warunek końc.: R1 = 1 0!= 1 R1 0 R2 R2 - 1 czy R2 = 0 ? R1 R1 x R2 R2 R2 - 1 czy R2 = 0 ?...

24 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = 0 Warunek końc.: R1 = 1 0!= 1 R1 0 R2 R2 - 1 czy R2 = 0 ? R1 R1 x R2 R2 R2 - 1 czy R2 = 0 ?... NIE

25 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = 0 Warunek końc.: R1 = 1 0!= 1 R1 1 czy R2 = 0 ? R1 R1 x R2 R2 R2 - 1 czy R2 = 0 ?... R1 R2 R2 R2 - 1

26 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 x 1 R1 1 czy R2 = 0 ? R1 R1 x R2 R2 R2 - 1 czy R2 = 0 ?...

27 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 R1 1 czy R2 1 ? R1 R1 x R2 R2 R2 - 1 czy R2 = 0 ?...

28 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Warunek pocz.: R2 = n Warunek końc.: R1 = n! 4!= 4 x 3 x 2 R1 1 czy R2 1 ? R1 R1 x R2 R2 R2 - 1 czy R2 1 ?...

29 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! StartStop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie Warunek pocz.: R2 = n Warunek końc.: R1 = n!

30 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 4 We Wyj

31 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 4 We Wyj 1

32 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 We Wyj

33 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 4 We Wyj

34 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 We Wyj

35 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 We Wyj

36 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 We Wyj

37 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 12 We Wyj

38 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 122 We Wyj

39 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 122 We Wyj

40 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 122 We Wyj

41 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 122 24 We Wyj

42 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 122 24 1 We Wyj

43 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 122 24 1 We Wyj

44 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 122 24 1 We Wyj

45 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 122 24 1 We Wyj

46 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie n! Start Stop R1 1 R1 1 R1 R1 * R2 R1 R1 * R2 R2 R2 - 1 R2 R2 - 1 R2 > 1 Tak Nie R2R1 41 43 122 24 1 4! = 24 We Wyj

47 J.Nawrocki, Wprowadzenie.., Wykład 2 Koncepcja von Neumanna Specjalizowane kalkulatory (obliczanie toru pocisku) a uniwersalne komputery Jak zrealizować uniwersalność: program jako łącznice kablowe program jako dane przechowywane w pamięci (koncepcja von Neumanna)

48 J.Nawrocki, Wprowadzenie.., Wykład 2 Koncepcja von Neumanna Dwie fazy: 1. Ściąganie rozkazu i jego dekodowanie 2. Wykonanie rozkazu Specjalny rejestr (licznik rozkazów) pokazuje następny rozkaz do wykonania.

49 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów Kod Rozkaz Przykład 1 MovRegCon(R, C) 1 1 0 R1 0 2 IfRegLeCon(R, C, I) 2 2 1 20 R2 1.. 3 MulRegReg(Rd, Rs) 3 1 2 R1 R1*R2 4 SubRegCon(Rd, C) 4 2 1 R2 R2-1 5 Jump(I) 5 14 6 Stop 6

50 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop

51 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 10 IC We Wyj

52 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 13 IC 1 We Wyj

53 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 17 IC 1 We Wyj

54 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 20 IC 1 3 We Wyj

55 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 23 IC 1 32 We Wyj

56 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 13 IC 1 32 We Wyj

57 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 17 IC 1 32 We Wyj

58 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 20 IC 1 32 6 We Wyj

59 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 23 IC 1 32 61 We Wyj

60 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 13 IC 1 32 61 We Wyj

61 J.Nawrocki, Wprowadzenie.., Wykład 2 Kodowanie rozkazów 1 1 1 MovRegCon R1 1 10 2 2 1 13 25 IfRegLeCon 3 17 MulRegReg 1 2 4 2 1 20SubRegCon 5 13 6 23 Jump 25Stop R2R1 3 13 IC 1 32 61 We Wyj

62 J.Nawrocki, Wprowadzenie.., Wykład 2 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).

63 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie wielomianu Idea algorytmuStart Stop P 0 P 0 P P + a n x n n n - 1 n 0 Tak Nie

64 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie wielomianu Idea algorytmuStart Stop P 0 P 0 P P + S n n - 1 n 0 Tak Nie S = a n x n

65 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie wielomianu Obliczanie a n x nStart Stop S a n ; k n S a n ; k n S S * x k k - 1 k 0 Tak Nie

66 J.Nawrocki, Wprowadzenie.., Wykład 2 Obliczanie wielomianu Złożoność alg.:Start Stop S a n ; k n S a n ; k n S S * x k k - 1 k 0 Tak Nie (n+1) razy S każde S: k mnożeń Razem: 0 + 1 +.. + (n+1) = Złożoność= O(n 2 )

67 J.Nawrocki, Wprowadzenie.., Wykład 2 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ń?

68 J.Nawrocki, Wprowadzenie.., Wykład 2 Problem stopu Dany jest podprogram X. Czy ten podprogram skończy obliczenia w skończonym czasie?

69 J.Nawrocki, Wprowadzenie.., Wykład 2 Problem stopu Pewien Grek powiedział, że każdy Grek jest kłamcą. Paradoksy logiczne

70 J.Nawrocki, Wprowadzenie.., Wykład 2 Problem stopu Pewien Grek powiedział, że każdy Grek jest kłamcą. Paradoksy logiczne

71 J.Nawrocki, Wprowadzenie.., Wykład 2 Problem stopu Czy istnieje zbiór wszystkich zbiorów? Z - zbiór wszystkich zbiorów Q = Z { Z } { Z } Z Q Z Q Z Paradoksy logiczne

72 J.Nawrocki, Wprowadzenie.., Wykład 2 Problem stopu procedure ZatrzymaSię(P: procedure): Boolean; { ??? } procedure X; { while ZatrzymaSię(X) do ; }

73 J.Nawrocki, Wprowadzenie.., Wykład 2 Problem stopu ZatrzymaSię(X) procedure X Tak Nie Wniosek: Problem stopu jest nierozstrzygalny

74 J.Nawrocki, Wprowadzenie.., Wykład 2 Podsumowanie Język schematów blokowych jest wygodnym narzędziem opisu algorytmów. Koncepcja von Neumanna polegała na kodowaniu programów za pomocą liczb i pamiętaniu ich kodu w pamięci operacyjnej. Nie wszystko można obliczyć. Wreszcie!

75 J.Nawrocki, Wprowadzenie.., Wykład 2 Literatura J. Nawrocki, Programowanie komputerów IBM metodą systematyczną, Wydawnictwo Politechniki Poznańskiej, Poznań, 1991.

76 J.Nawrocki, Wprowadzenie.., Wykład 2 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?