Aisd W01

WOJSKOWA AKADEMIA TECHNICZNA Wydział Cybernetyki

Algorytmy i struktury danych r.a. 2006/2007

Prowadzący: dr hab. inż. Kazimierz Worwa, prof. WAT e-mail: [email protected]

ALGORYTMY I STRUKTURY DANYCH RAZEM 60

Algorytmy i struktury danych

Wykłady 30x

Ćwiczenia 10

Laboratoria 20+

2

LITERATURA 1. Aho A.V., Hopcroft J.E., Ullman J.D.: Algorytmy i struktury danych. Wydawnictwo Helion, Gliwice, 2003. 2. Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza algorytmów. Wydawnictwo Helion, Gliwice, 2003. 3. Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych. WNT, Warszawa, 2006. 4. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Wprowadzenie do algorytmów. WNT, Warszawa, 2005. 5. Drozdek A.: C++. Algorytmy i struktury danych. Wydawnictwo Helion, Gliwice, 2004. 6. Kotowski P.: Algorytmy + struktury danych = abstrakcyjne typy danych. Wydawnictwo BTC, Warszawa, 2006. 7. Loudon K.: Algorytmy w C.: Wydawnictwo Helion, Gliwice, 2003. 8. Wirth N.: Algorytmy + struktury danych = programy. WNT, Warszawa, 2004. 9. Wróblewski P.: Algorytmy, struktury danych i techniki programowania. Wydawnictwo Helion, Gliwice, 2006. Algorytmy i struktury danych

3

Materiały do wykładów z przedmiotu AiSD

■

adres strony www zostanie podanie później

Algorytmy i struktury danych

4

Algorytmy i struktury danych Wykład 1

Pojęcia podstawowe. Złożoność obliczeniowa algorytmów (cz. 1).

Tematyka wykładu      

Pojęcia podstawowe Klasyfikacja algorytmów Własności algorytmów Metody oceny algorytmów Pojęcie złożoności obliczeniowej algorytmów Złożoność asymptotyczna: O-notacja, Ω-notacja, Θnotacja

Algorytmy i struktury danych

6

Potoczne rozumienie pojęcia „algorytm”  Algorytmika jest dziedziną wiedzy zajmującą się badaniem algorytmów  Potocznie algorytm jest rozumiany jako pewien przepis na wykonanie zestawu czynności, prowadzących do osiągnięcia oczekiwanego i z góry określonego celu  Mówi się również, że algorytm jest pewną ściśle określoną procedurą obliczeniową, która dla zestawu właściwych danych wejściowych generuje określone dane wyjściowe  Dzisiejsze, uogólnione znaczenie słowa algorytm: zbiór reguł postępowania, umożliwiających rozwiązanie określonego zadania w skończonej liczbie kroków i w skończonym czasie

Algorytmy i struktury danych

7

Pochodzenie słowa „algorytm”  Słowo „algorytm” pochodzi od łacińskiego słowa „algorism”, rozumianego w średniowieczu jako sztuka rachowania na liczbach w systemie decymalnym  Słowo „algorism” zostało utworzone od nazwiska perskiego matematyka z 9-tego wieku n.e., Muhameda ibu-Musy alChoresmi, twórcy systemu dziesiętnego

Algorytmy i struktury danych

8

Pojęciowy model algorytmu Algorytm może być rozumiany jako pewne odwzorowanie f, które dla określonego zestawu danych wejściowych We generuje określony zestaw danych wyjściowych Wy: f: We

Dane wejściowe

Algorytmy i struktury danych

Wy

Dane wyjściowe

9

Pojęcie dziedziny algorytmicznej  Każdy algorytm działa na pewnym zbiorze obiektów (np. liczb) wraz z operacjami pierwotnymi, które można wykonywać na tych obiektach  Zbiór obiektów wraz z operacjami wykonywanymi na tych obiektach nazywamy dziedziną algorytmiczną  Przykłady dziedzin algorytmicznych: ◆ dziedzina algorytmiczna liczb całkowitych: ✦ (C, +, -, *, div, mod, abs) ◆ dziedzina algorytmiczna rachunku logicznego: ✦ (B, not, and, or, =>, <=>) ◆ dziedzina algorytmiczna dla języków programowania: ✦ zbiór symboli alfanumerycznych oraz reguł syntaktycznych i semantycznych języka programowania Algorytmy i struktury danych

10

Sposoby zapisu algorytmów  Algorytm powinien precyzyjnie opisywać kolejne jego kroki.  Do przedstawienia algorytmu stosuje się: ◆

opis werbalny,

◆

zapis formalny, np.: ✦

zapisy graficzne (schematy blokowe),

✦

formalne specyfikacje programów (np.VDM)

✦

zapisy w postaci pseudokodu (paraprogramu)

✦

zapis algorytmu w dowolnym języku programowania

Algorytmy i struktury danych

11

Język programowania  Język programowania jest środkiem umożliwiającym zapis algorytmów w postaci zrozumiałej dla człowieka, a równocześnie przetwarzalnej do postaci zrozumiałej dla komputera.  Zapis algorytmu w języku programowania jest traktowany jako zapis formalny. Program komputerowy może być uznawany za jeden z rodzajów modeli matematycznych.

Przetworzenie programu źródłowego w kod maszynowy Kod źródłowy programu (w języku programowania)

Algorytmy i struktury danych

Kod wynikowy programu (w języku maszynowym)

12

Klasyfikacja algorytmów

Rozważać będziemy następujące klasy algorytmów: ◆ ◆ ◆

algorytmy sekwencyjne - algorytmy równoległe; algorytmy numeryczne - algorytmy nienumeryczne; algorytmy rekurencyjne - algorytmy iteracyjne.

Algorytmy i struktury danych

13

Przykład - pierwiastki równania kwadratowego ax 2 + bx + c = 0 Algorytm równoległy: sekwencyjny: START ∆=b2-4ac

Algorytm START ∆=b2-4ac x1=(-b-sqrt(∆))/2a

x1=(-b-sqrt(∆))/2a

x2=(-b+sqrt(∆))/2a

x2=(-b+sqrt(∆))/2a

Wypisz x1, x2

Wypisz x1, x2

STOP

STOP

Algorytmy i struktury danych

14

Wywołanie funkcji rekurencyjnej  Rekurencja oznacza wywołanie funkcji (procedury) przez tę samą funkcję (procedurę)  Niepożądana cecha definicji rekurencyjnych: aby wyznaczyć n-tą wartość trzeba najpierw wyznaczyć wszystkie „wcześniejsze” wartości  Ważne jest, aby kolejne wywołania funkcji (procedury) rekurencyjnej były realizowane dla kolejnych wartości parametrów formalnych w taki sposób, aby nie doszło do zjawiska „nieskończonej pętli rekurencyjnych wywołań funkcji”

Algorytmy i struktury danych

15

Przykład obliczania n! dla n=5 Algorytm rekurencyjny: iteracyjny

START

Algorytm

START Silnia = 1 i=1

= 5 * 4! == 44**3!3! =3 3* *2!2!

i≤5

= 22**1! 1! =1

STOP Algorytmy i struktury danych

1

N

T Silnia = Silnia*i i=i+1 STOP 16

Dno stosu programu

Adres powrotu do systemu operacyjnego

Stos programu w wywołaniach rekurencyjnych – funkcja main() przykład C/C++

Adres powrotu z funkcji Zwracana wartość Parametry przez adres

funkcja f1

Parametry przez wartość Zmienne lokalne Adres powrotu z funkcji Zwracana wartość Parametry przez adres

funkcja f2

Kolejne poziomy rekurencji wymagają odkładania na stosie programu kolejnych rekordów aktywacji funkcji

Parametry przez wartość Zmienne lokalne

. . .

Adres powrotu z funkcji Zwracana wartość Parametry przez adres Parametry przez wartość Zmienne lokalne Algorytmy i struktury danych

funkcja fN

Stos programu w wywołaniach rekurencyjnych jest bardziej eksploatowany niż wtedy, gdy wywołania nie są rekurencyjne 17

Przykłady funkcji rekurencyjnych ■

Funkcja „silnia”: 1

dla n=0

n*(n-1)!

dla n>0

(warunek zakończenia rekurencji)

n!=

■

Definicja pewnego ciągu liczb wymiernych: 1

dla n=0

(warunek zakończenia

rekurencji)

f(n)= f(n-1) + 1/f(n-1), dla n>0, określa ciąg o wartościach: 1, 2, 5/2, 29/10, 941/290, 969581/272890,................. Algorytmy i struktury danych

18

Funkcja rekurencyjna – ciąg Fibonacciego ■

Ciąg Fibonacciego jest wyliczany wg formuły: n

dla n<2

Fib(n)= Fib(n-2) + Fib(n-1)

■

dla n>=2

Rekurencyjna implementacja w języku C: long int Fib (int n) { if (n<2) return n; else

Czy na pewno stos programu „wytrzyma” taką realizację funkcji rekurencyjnej Fib?

return Fib(n-2) + Fib (n-1); } Algorytmy i struktury danych

19

Efektywność rekurencyjnego wykonania funkcji Fibonacciego (cd.)  Rekurencyjna implementacja funkcji Fibonacciego jest bardzo nieefektywna.  Stos programu nie jest praktycznie w stanie zrealizować tego algorytmu już dla liczb większych od 9.  że program madla zbyt dużą „złożoność pamięciową”.  Oznacza Przykład:to, drzewo wywołań F(6): F(6) F(5)

F(4) F(2) F(0)

0

F(3) F(1)

1

F(1)

1

Algorytmy i struktury danych

F(3) F(2)

F(1)

F (0)

F (1)

0

1

1

F(4) F(2)

F(2)

F(3)

F (0)

F (1)

F (0)

F (1)

F (1)

0

1

0

1

1

F (2) F (0)

F (1)

0

1 20

Efektywność rekurencyjnego wykonania funkcji Fibonacciego

Algorytmy i struktury danych

n

Liczba dodawań

Liczba wywołań

6

12

25

10

88

177

15

986

1 973

20

10 945

21 891

25

121 392

242 785

30

1 346 268

2 692 537 21

Iteracyjne wykonanie rekurencyjnej funkcji Fibonacciego ■

■

Bardziej efektywna jest iteracyjna implementacja funkcji Fibonacciego. Nie przepełniamy wtedy stosu programu i wykonujemy mniejszą liczbę przypisań wartości niż w implementacji rekurencyjnej Przykład iteracyjnej implementacji funkcji Fibonacciego: long int IteracyjnyFib(int n) { register int i=2, last=0, tmp; long int current =1; if (n<2) return n; else { for ( ; i<=n; i++) { tmp = current; current += last; last = tmp; } return current; } }

Algorytmy i struktury danych

22

Efektywność iteracyjnego wykonania rekurencyjnej funkcji Fibonacciego n

Liczba przypisań w algorytmie iteracyjnym

Liczba przypisań (wywołań) w algorytmie rekurencyjnym

6

15

25

10

27

177

15

42

1 973

20

57

21 891

25

72

242 785

30

87

2 692 537

Algorytmy i struktury danych

23

Pułapki rekurencji - przykład rekurencji bez końca int StadDoWiecznosci(int n) { if (n==1) return 1; else if ((n%2)==0) // return StadDoWiecznosci(n-2)*n; else return StadDoWiecznosci(n-1)*n; }

Algorytmy i struktury danych

24

Jak porównywać algorytmy?

Idealny algorytm to taki, który:    

ma czytelny i zrozumiały kod, jest napisany w ogólnie dostępnym języku programowania, jest efektywny obliczeniowo (szybko liczy, nie wymaga dużej pamięci), zawsze daje poprawne wyniki.

Algorytmy i struktury danych

25

Jak porównywać algorytmy – przykładowe kryteria

     

prostota, czytelność kodu, długość kodu, poprawność, czas realizacji (obliczeń), zajętość pamięci.

Algorytmy i struktury danych

26

Częściowa poprawność algorytmu

 Specyfikacją algorytmu nazywamy parę warunków (własności):

< wp , wk > Warunek końcowy

Warunek początkowy

wp

A

wk

Algorytm A wykorzystujący strukturę danych S jest częściowo poprawny ze względu na specyfikację <wp, wk> jeżeli dla wszystkich danych spełniających warunek początkowy i dla których algorytm zatrzyma się, uzyskane wyniki spełniają warunek końcowy. Algorytmy i struktury danych

27

Całkowita poprawność algorytmu

wp

A

wk

Mówimy, że algorytm A wykorzystujący strukturę danych S jest całkowicie poprawny ze względu na specyfikację <wp, wk> jeżeli dla wszystkich danych w strukturze S spełniających warunek początkowy wp, algorytm zatrzymuje się i daje wyniki spełniające warunek końcowy wk.

Algorytmy i struktury danych

28

Złożoność obliczeniowa algorytmów

 Złożoność obliczeniowa - miara służąca do porównywania efektywności algorytmów. Mamy dwa zasadnicze kryteria efektywności: czas i pamięć.  Do oceny efektywności stosujemy jednostki logiczne, wyrażające związek miedzy rozmiarem danych n (np. wielkość pliku lub tablicy) a ilością czasu T potrzebną na ich przetworzenie.

Algorytmy i struktury danych

29

Rodzaje złożoności obliczeniowej algorytmów  Złożoność pamięciowa - wyrażana w skali zajętości pamięci (PAO, pamięci zewnętrznej), niezbędnej dla realizacji algorytmu  Złożoność czasowa - wyrażana w skali czasu wykonania algorytmu (liczba kroków, czas rzeczywisty)  Na ogół (obecnie) złożoność czasowa jest ważniejsza od złożoności pamięciowej

Algorytmy i struktury danych

30

Czynniki wpływające na czas wykonania programu  Rozmiar danych wejściowych algorytmu  Jakość kodu wynikowego generowanego przez kompilator (język kodu źródłowego)  Architektura i szybkość komputera, na którym program jest wykonywany  Efektywność wykorzystanego algorytmu (jego złożoność czasowa)

Algorytmy i struktury danych

31

Złożoność czasowa algorytmu  Do oszacowania czasu realizacji algorytmu nie powinno się używać zwykłych jednostek czasu  Zamiast tego powinny być stosowane jednostki logiczne, określające związek między rozmiarem danych wejściowych a czasem potrzebnym na ich przetworzenie  Czas wykonywania algorytmu, gdy rozmiar danych wejściowych wynosi n, będziemy oznaczać przez T(n)  Funkcje opisujące związek między T(n) a n mogą być bardzo złożone; w praktyce upraszczamy je, pozostawiając składowe mające największy wpływ na wartości czasu T(n)

Algorytmy i struktury danych

32

Algorytmy i struktury danych

33