Algorytmy
i struktury danych
Od problemu do jego
rozwiązania
Niech max ma
Sformułowanie
wartość równą
pierwszemu
problemu
elementowi ciągu.
Przykład: Dany Porównaj max z
kolejnymi
jest ciąg liczb.
elementami ciągu i
Znalez
ć
jeśli spotkasz
największą z nich.
wartość większą,
przyjmij ją jako
nową wartość max.
Rozwiązanie problemu
Algorytm to metoda postępowania, która prowadzi do
rozwiązania jakiegoś problemu.
1
Algorytm
l� skończony, uporządkowany ciąg jasno
zdefiniowanych czynności, koniecznych do
wykonania dowolnego zadania z określonej
klasy zadań.
l� Słowo "algorytm" pochodzi od nazwiska
Muhammeda Alchwarizmi - matematyka
perskiego z IX wieku.
l� Badaniem algorytmów zajmuje się algorytmika.
l� Algorytm może zostać zaimplementowany w
postaci programu komputerowego.
Algorytm  definicja formalna
Oznaczmy przez:
We - zestaw danych wejściowych
Wy - zestaw danych wyjściowych
stan
pamięci po
stan pamięci
wykonaniu
przed
algorytmu
wykonaniem
Dane Wyniki
algorytmu
Algorytm
We Wy
Algorytm jest rozumiany jako odwzorowanie O, które
dla określonego zestawu We generuje zestaw Wy:
O: We Wy,
gdzie liczności zbiorów We i Wy mogą być różne.
2
Przykład algorytmu I
l� Algorytm wyznaczania pola kwadratu o boku a:
l� Jako dane wejściowe pobierz wartość długości
boku kwadratu a
l� Oblicz wartość pola P = a2
l� Zwróć obliczoną wartość pola kwadratu P
Przykład algorytmu II
l� Algorytm Euklidesa wyznaczania NWD:
l� Dopóki x różne od y wykonuj:
l� Jeżeli x>y, to odejmij y od x i wynik podstaw na x;
l� W przeciwnym przypadku od y odejmij x i wynik
podstaw na y;
l� koniec dopóki
l� wynikiem jest y
Dane x =21, y =12.
(x,y) = (21,12)-> (9,12)-> (9,3)-> (6,3)-> (3,3)
Wynik 3
3
Cechy algorytmu
l� Ogólność
l� Rozwiązywanie określonej klasy zadań
l� Skończoność
l� Rozwiązanie zadania w skończonej liczbie kroków
l� Określoność
l� Jednoznaczność operacji
l� Efektywność
l� Czas wykonania, zapotrzebowanie na pamięć
Sposoby zapisu algorytmu
l� Język naturalny
l� Prostota, szeroki zasób słownictwa, mała precyzja
l� Schematy blokowe
l� Zapis sformalizowany, brak możliwości
przedstawienia skomplikowanych algorytmów
l� Języki formalne
l� Najczęściej używane w praktyce, ścisłość zapisu
4
Schematy blokowe
Proces
Zapis/odczyt
uprzednio
danych
zdefiniowany
A
ącznik A
ącznik
stronicowy międzystronicowy
Algorytm wyznaczania
iloczynu
5
Algorytm wyznaczania
iloczynu
Algorytm wyznaczania
iloczynu
l� Język Pascal
y := 1;
for i := 1 to n do y := y * x [ i ];
6
Klasyfikacja algorytmów
(wybrane kategorie)
l� algorytmy proste  rozgałęzione
l� algorytmy cykliczne  mieszane
l� algorytmy równoległe  sekwencyjne
l� algorytmy numeryczne  algorytmy
nienumeryczne
l� algorytmy rekurencyjne  algorytmy
iteracyjne
Algorytmy proste i
rozgałęzione
7
Algorytmy cykliczne i
mieszane
Algorytm równoległy i
sekwencyjny
8
Algorytm równoległy i
sekwencyjny
Algorytm rekurencyjny i
iteracyjny
9
Rekurencja
l� Rekurencja albo rekursja - odwoływanie się
np. funkcji lub definicji do samej siebie.
l� Ważne jest, aby kolejne wywołania funkcji
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
Obraz rekurencyjny
10
Przykłady funkcji
rekurencyjnych
l� Silnia
l� Ciąg Fibonacciego
Silnia - Algorytm iteracyjny
Dane:
n - liczba rzeczywista
Szukane:
s = n! wartość silni liczby naturalnej.
Pomocnicze :
i - liczba naturalna (licznik).
START:
wczytaj liczbę n
s :=1
i := 0
jeśli i = n, to KONIEC
i := i +1;
s := s*i; WARUNEK;
KONIEC:
wyświetl liczbę s
11
Silnia - Algorytm rekurencyjny
5!  porównanie algorytmów
12
Algorytmy zachłanne
l� Wykonują działanie które wydaje się najlepsze w
danej chwili, nie uwzględniając tego co może się
stać w przyszłości. Zaletą jest to że nie traci czasu
na rozważanie co może się stać póz
niej.
l� Decyzja lokalnie optymalna.
l� Jak wydać resztę przy minimalnej ilości monet?: użyj
zawsze najpierw monetę o największej dopuszczalnej
wartości.
l� Jak znalez
ć globalne maximum? Rozpocznij od
pewnej liczby, kolejno powiększaj ją o ustaloną
wielkość tak długo jak funkcja wzrasta. Gdy wartość
funkcji zaczyna się zmniejszać przerwij i cofnij się do
ostatniej pozycji.
Algorytmy  dziel i zwyciężaj
l� Dzielimy problem na mniejsze części tej samej postaci co
pierwotny.
l� Podproblemy dzielimy dalej na coraz mniejsze, używając tej
samej metody, aż rozmiar problemu stanie się tak mały, że
rozwiązanie będzie oczywiste lub będzie można użyć jakiejś
innej efektywnej metody rozwiązania.
l� Rozwiązania wszystkich podproblemów muszą być
połączone w celu utworzenia rozwiązania całego problemu.
l� Metoda zazwyczaj implementowana z zastosowaniem
technik rekurencyjnych.
l� Jak znalez
ć minimum ciągu liczb?: Dzielimy ciąg na dwie części,
znajdujemy minimum w każdej z nich, bierzemy minimum z obu
części jako minimum ciągu.
l� Jak sortować ciąg liczb?: Dzielimy na dwie części, każdą osobno
sortujemy a następnie łączymy dwa uporządkowane ciągi
(scalamy).
13
Upraszczanie algorytmów
Algorytm dodawania
1 przeniesienie1
dwóch liczb
naturalnych
15 15
+ 18 18
+
3 33
x1 x2
y1 y2
+
s1 s2
Upraszczanie algorytmów
14
Jak porównywać algorytmy?
Idealny algorytm to taki,
który ma prosty kod,
" prostota
jest napisany w ogólnie
" czytelność
dostępnym języku
programowania, łatwo
" długość kodu
go zrozumieć, liczy
" poprawność
szybko, nie wymaga
dużo miejsca w pamięci
" czas realizacji
i zawsze daje
" zajętość pamięci
poprawne wyniki.
Koszt algorytmu
Miary kosztu:
" Liczba instrukcji
" Liczba
zmiennych
" liczba operacji
arytmetycznych
" ilość miejsca
potrzebna dla
" liczba wywołań
danych
procedury
Ogólnie: wybór miary zależy od typu problemu, rodzaju
rozwiązania.
15
Efektywność algorytmów
l� Złożoność obliczeniowa
l� czas wykonania
l� Złożoność pamięciowa
l� Zapotrzebowanie na pamięć operacyjną
l� Zależy od
l� Rozmiaru danych wejściowych
l� Rodzaju danych wejściowych
Efektywność algorytmów
l� Sortowanie a < b < c
16
Sortowanie - algorytm 1
4,5,6
1
6
5 4 3 2
Sortowanie - algorytm 1
Razem:
Średnio: 2,7 1,2
17
Sortowanie - algorytm 2
y<=z
Sortowanie - algorytm 2
Średnio: 3,3 1,5
18
Porównanie efektywności
l� Algorytm 2:
l� Algorytm 1:
l� Pamięć
l� Pamięć
l� 2 operacje testu
l� 5 operacji testu
l� 2 operacje permutacji
l� 5 operacji permutacji
l� Czas (średni)
l� Czas (średni)
l� 3,3 ttestu + 1,5 tpermutacji
l� 2,7 ttestu + 1,2 tpermutacji
Operacje dominujące
Mnożenie macierzy Operacje + , *
Wyszukiwanie elementu w tablicy
porównywanie
Sortowanie
Mając dany algorytm, konkretne środowisko i konkretne
dane możemy policzyć liczbę operacji dominujących.
Koszt algorytmu dla danych Dn:
t(ą ,I)
algorytm
dane
19
Szacowanie złożoności
obliczeniowej
l� ą - algorytm rozwiązujący decyzyjny problem  ;
l� Dn - zbiór danych rozmiaru n dla rozważanego problemu;
l� t(ą , I) - liczba operacji potrzebna do rozwiązania problemu 
dla konkretnych danych I "Dn przy pomocy algorytmu ą.
l� Pesymistyczna złożoność obliczeniowa:
W(ą ,n) = max{t(ą , I): I�� Dn }
l� Średnia złożoność obliczeniowa:
W(ą ,n) = Ł{p(I)�t(ą , I): I�� Dn }
Szacowanie złożoności
obliczeniowej
l� Mówimy, że algorytm ą ma złożoność czasową:
wielomianową wttw T(ą,n)= Q�(nb) b ��N
wykładniczą wttw T(ą,n) = Q�(an) a �� R+
liniową wttw T(ą,n)= Q�(n)
kwadratową wttw T(ą,n)= Q�(n2)
logarytmiczną wttw T(ą,n)= Q�(lg n)
20
Rząd złożoności obliczeniowej
Rząd złożoności obliczeniowej
21
Rząd złożoności obliczeniowej
Struktury danych
l� Struktury są  pojemnikami na dane , które gromadzą
dane i układają je w odpowiedni sposób
l� Na strukturach danych operują algorytmy
l� Podstawowe struktury danych to:
l� rekord (struktura)
l� tablica
l� lista
l� stos
l� kolejka
l� drzewo (drzewo binarne)
l� graf
22
Rekord
l� W niektórych językach programowania nazywany
strukturą (ang. structure, struct, record)
l� Jest to obiekt programistyczny, grupujący dane
różnych typów
l� Posiada określone elementy (składowe), które mogą
być odczytywane i zmieniane
l� Odpowiednik rekordu w teorii relacyjnych baz danych
to krotka (wiersz tabeli)
Rekord - przykład
l� Rekord typu pracownik może zawierać np.:
l� Nazwisko  element danych typu tekstowego
l� Imię - element danych typu tekstowego
l� Data urodzenia - rekord typu data
l� Data zatrudnienia - rekord typu data
l� Miejsce zamieszkania - rekord typu adres
l� stanowisko - dana typu tekstowego
l� Użyty tutaj rekord typu data może być definiowany jako:
l� Rok - liczba całkowita lub tekst (4 cyfry)
l� Miesiąc - liczba całkowita lub tekst (2 cyfry)
l� Dzień - liczba całkowita lub tekst (2 cyfry)
23
Tablica
l� Zbiór danych tego samego typu, w którym
poszczególne komórki adresowane są za
pomocą indeksów.
l� Rozmiar tablicy
l� jest albo ustalony z góry (tablice statyczne)
l� może się zmieniać w trakcie wykonywania programu
(tablice dynamiczne).
l� Odpowiednikiem tablicy dwuwymiarowej w
matematyce jest macierz.
Tab[1,2]
Tab[0,0]
4 3 7
3 8 4
6 9 7
Lista
l� Lista to liniowo uporządkowany zbiór
elementów, z których dowolny element można
usunąć oraz dodać w dowolnym miejscu.
l� Lista jednokierunkowa - komórki zawierają
tylko wskaz
niki do kolejnej komórki.
l� Lista dwukierunkowa - komórki zawierają także
wskaz
nik do poprzedniej komórki.
24
Szczególne przypadki listy
l� stos
l� pobrać, odczytać i wstawić element można
tylko na końcu listy
l� kolejka
l� pobrać i odczytać element można tylko na
początku listy, a dodać na końcu
Algorytm wyszukiwania
l� Lista nieuporządkowana
l� Szukana wartość: 6
l� 5; 1; 7; 8; 2; 3; 4; 6; 0; 9
l� 8 sprawdzeń,
l� Średnio potrzeba n/2 sprawdzeń (n=10)
25
Algorytm wyszukiwania
l� Lista uporządkowana
l� Szukana wartość: 6
l� 0; 1; 2; 3; 4; 5; 6; 7; 8; 9
1
2
3
l� 4 sprawdzenia,
l� Średnio potrzeba � log2n sprawdzeń (n=10)
Stos
l� LIFO, Last In, First Out; ostatni na wejściu,
pierwszy na wyjściu
l� Jedynie ostatni element stosu, zwany
wierzchołkiem, jest w danym momencie
dostępny.
l� W wierzchołku odbywa się dołączanie
nowych elementów, również jedynie
wierzchołek można usunąć.
26
1
3
4
2
Kolejka
l� FIFO (ang. First In, First Out) - pierwszy na wejściu,
pierwszy na wyjściu
l� dołączać nowe dane można jedynie na koniec kolejki
a usuwać z początku
Drzewo
27
Drzewo
l� Przykład zastosowania: indeksy w bazach danych
(B-drzewo)
Graf
l� nieskierowany
l� skierowany
28
Macierz sąsiedztwa
1 2 3 4 5
1 0 1 1 0 1
2 1 0 1 1 1
3 1 1 0 1 0
4 0 1 1 0 1
5 1 1 0 1 0
Bibliografia
l� Algorytmy i struktury danych,
L. Banachowski, K. Diks, W. Rytter,
Wydawnictwa Naukowo - Techniczne, 2006.
l� Wprowadzenie do algorytmów,
Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, Clifford Stein,
Wydawnictwa Naukowo - Techniczne, 2004.
29