Algorytmy i Struktury Danych(2)

[ Pobierz całość w formacie PDF ]
Uniwersytetim.AdamaMickiewiczawPoznaniu
WydziałFizyki,kierunekinformatykastosowana
Algorytmyistrukturydanych
NotatkidowykładówdrinŜ.PawłaPrałata
Opracowaneprzez:PiotrKnychała
pi_knychala@o2.pl
Kalisz20042005
OstatniaaktualizacjaVIII2005
Zabłędywtreścimateriałównieodpowiadam.
Algorytmy i struktury danych
Spis tre
ś
ci:
Efektywno
ść
........................................................................................................................................................... 5
Notacja ”wielkie O”........................................................................................................................................... 5
Notacje:
i
Θ
.................................................................................................................................................... 6
Listy ........................................................................................................................................................................ 6
Dokładanie elementu do listy ............................................................................................................................. 7
Wyszukiwanie elementu w li
ś
cie ......................................................................................................................... 7
Usuwanie elementu z listy .................................................................................................................................. 7
Listy cykliczne (rozwi
ą
zanie problemu Josephusa)............................................................................................ 8
Stos (LIFO – Last In First Out) ........................................................................................................................... 9
Implementacja stosu z wykorzystaniem tablicy .................................................................................................. 9
Implementacja stosu z wykorzystaniem listy jednokierunkowej ....................................................................... 10
Kolejka (FIFO – First In First Out) .................................................................................................................. 10
Implementacja kolejki z wykorzystaniem tablicy .............................................................................................. 11
Implementacja kolejki z wykorzystaniem listy jednokierunkowej ..................................................................... 12
Kolejka priorytetowa (wykorzystanie kopca) ................................................................................................... 12
Kopiec................................................................................................................................................................... 13
Naprawianie kopca .......................................................................................................................................... 14
Tworzenie kopca............................................................................................................................................... 15
Sortowanie danych .............................................................................................................................................. 16
Sortowanie przez wstawianie (ang. insertion sort)........................................................................................... 16
Sortowanie przez wybór (ang. selection sort) .................................................................................................. 17
Sortowanie b
ą
belkowe - wersja standardowa i ulepszona (ang. bubble exchange sort).................................. 17
Sortowanie Shella (ang. shellsort) ................................................................................................................... 18
Sortowanie przez kopcowanie (ang. heapsort)................................................................................................. 19
Sortowanie szybkie – wersja standardowa oraz z losowym elementem dziel
ą
cym (ang. quicksort) ................ 20
Sortowanie przez scalanie (ang. mergesort) .................................................................................................... 21
Sortowanie przez zliczanie (ang. counting sort)............................................................................................... 22
Sortowanie stabilne .......................................................................................................................................... 23
Sortowanie pozycyjne (ang. radix sort) ............................................................................................................ 23
Sortowanie kubełkowe (ang. bucket sort)......................................................................................................... 24
Algorytmy rekurencyjne .................................................................................................................................... 25
Proste algorytmy rekurencyjne......................................................................................................................... 26
Silnia............................................................................................................................................................ 26
NWD – najwi
ę
kszy wspólny dzielnik (algorytm Euklidesa)....................................................................... 26
Wypisywanie wyrazu od ko
ń
ca ................................................................................................................... 26
Algorytmy zachłanne (ang. greek algorithm) ................................................................................................... 27
Problem kasjera ........................................................................................................................................... 27
Szukanie minimum funkcji.......................................................................................................................... 27
2
Algorytmy i struktury danych
Strategia ”dziel i rz
ą
d
ź
”................................................................................................................................... 28
Wyznaczanie warto
ś
ci maksymalnej ........................................................................................................... 28
Linijka ......................................................................................................................................................... 28
Wie
Ŝ
a Hanoi ................................................................................................................................................ 28
Ci
ą
g liczb Fibonacciego .............................................................................................................................. 29
Programowanie dynamiczne ............................................................................................................................ 29
Ci
ą
g liczb Fibonacciego .............................................................................................................................. 29
Liczba kombinacji – trójk
ą
t Pascala ............................................................................................................ 29
Problem pakowania plecaka (ang. knapsack problem) ................................................................................ 30
Rozkład na czynniki pierwsze liczb naturalnych (0-1000) .......................................................................... 32
Metoda powrotów – ”prób i bł
ę
dów” (ang. backtracking) .............................................................................. 32
Problem skoczka szachowego ..................................................................................................................... 32
Problem o
ś
miu hetmanów ........................................................................................................................... 33
Co
ś
na deser ..................................................................................................................................................... 34
Krzywa Kocha (płatek
ś
niegu) .................................................................................................................... 34
Trójk
ą
t i dywan Sierpi
ń
skiego..................................................................................................................... 34
Krzywa Hilberta .......................................................................................................................................... 34
Zliczanie białych obszarów i liczby białych pól w ka
Ŝ
dym obszarze ......................................................... 35
Drzewo binarne – implementacja podstawowych operacji ............................................................................. 36
Dodawanie elementu ........................................................................................................................................ 36
Wyszukiwanie elementu, element minimalny i maksymalny ............................................................................. 37
Usuwanie elementu (3 przypadki) .................................................................................................................... 38
Przechodzenie drzewa w gł
ą
b i wszerz............................................................................................................. 40
Równowa
Ŝ
enie drzewa ..................................................................................................................................... 41
Metoda z wykorzystaniem pomocniczej tablicy.......................................................................................... 41
Algorytm DSW............................................................................................................................................ 42
Tablice haszuj
ą
ce ................................................................................................................................................ 48
Funkcje haszuj
ą
ce – metody ich wyznaczania.................................................................................................. 49
Rozwi
ą
zywanie kolizji metod
ą
ła
ń
cuchow
ą
...................................................................................................... 50
Adresowanie otwarte ........................................................................................................................................ 50
Teoria grafów ...................................................................................................................................................... 53
Podstawowe definicje ....................................................................................................................................... 53
Reprezentacja grafów w komputerze................................................................................................................ 58
Przechodzenie grafu w gł
ą
b, wyznaczanie spójnych składowych..................................................................... 59
Przechodzenie grafu wszerz ............................................................................................................................. 60
Sortowanie topologiczne .................................................................................................................................. 60
Wyznaczanie silnych spójnych składowych w grafie skierowanym .................................................................. 61
Troch
ę
o ł
ą
czeniu w zbiory............................................................................................................................... 64
Minimalne drzewo rozpinaj
ą
ce ........................................................................................................................ 66
Algorytm Kruskala ...................................................................................................................................... 67
Algorytm Prima ........................................................................................................................................... 68
Najkrótsze
ś
cie
Ŝ
ki z jednym
ź
ródłem ................................................................................................................ 69
Algorytm Dijkstry ....................................................................................................................................... 69
Algorytm Bellmana – Forda ........................................................................................................................ 73
Maksymalny przepływ ...................................................................................................................................... 74
Maksymalne skojarzenia w grafie dwudzielnym .............................................................................................. 77
3
Algorytmy i struktury danych
Obliczanie wielomianu chromatycznego .......................................................................................................... 78
Dodatek: Algorytmy wyszukiwania wyrazu wzorcowego w tek
ś
cie
................................................... 81
Metoda „naiwna” ............................................................................................................................................ 81
Metoda Rabina-Karpa...................................................................................................................................... 81
Metoda Knuta-Morrisa-Pratta ......................................................................................................................... 82
Zako
ń
czenie
....................................................................................................................................................... 83
4
Algorytmy i struktury danych
Efektywno
ść
Początkowi programiści pisząc program cieszą się, gdy się kompiluje, a gdy działa
poprawnietojuŜwogólesąwraju.Jednakimbardziejskomplikowaneprogramypiszemy,
naleŜycorazbardziejzwracaćuwagęnaszybkośćichdziałania.WaŜnejesttoszczególnie
wtedy,gdyprogrammaoperowaćnaduŜejliczbiedanych.ProblemymoŜnarozwiązaćna
wielesposobów,chodzioto,abywybraćnajbardziejefektywny(czylitaki,którynajszybciej
doprowadzinasdocelu).Właśnieefektywnośćalgorytmówporównujesięobliczająctzw.
złoŜonośćobliczeniową. Określa ona m.in. ilość czasu i pamięci, jaka jest potrzebna do
rozwiązaniaproblemu.
Szybkość wykonywania danego programu zaleŜy od wielu czynników, nie tylko od
złoŜoności algorytmu. Na ten czynnik ma takŜe wpływ rodzaj sprzętu, na którym
uruchomionyjestprogram.ZnaczeniematakŜejęzyk,wjakimprogramzostałnapisany.
DoopisuzłoŜonościalgorytmuniestosujesięjednostekczasu,takichjaksekundaczy
mikrosekunda,leczopisujesięjąpodajączaleŜność,zjakązmieniasięczaswstosunkudo
wzrostuliczbydanych.Przykładowo:jeŜelizwiększeniedanychdoprzetworzeniawzrasta
3krotnie, to czas potrzebny na tą operację teŜ wzrośnie 3krotnie. MoŜna tą zaleŜność
przedstawiaćwpostaciwzorut(n).np.t(n)=n(zaleŜnośćliniowa).Funkcjeprzedstawiające
takązaleŜnośćsąwrzeczywistościbardziejskomplikowaneibardzoczęstopomijasięw
nichskładnikiniemająceznaczącegowpływunajejwartość.WtedyzłoŜonośćobliczonaw
takimwzorzejestprzybliŜona,aledlabardzoduŜegonjestitakdośćdokładna.Takisposób
obliczaniaefektywnościalgorytmuokreślasięmianemzłoŜonościasymptotycznej.
Szybkość wzrostu poszczególnych składników przykładowej funkcji wyznaczającej
złoŜonośćasymptotycznąpodanowponiŜszejtabeli.
f
(
n
)
=
n
2
+
100
n
+
log
n
+
1000
10
n
f(n)
n
2
100n
log
10
n 1000
1
1101
1
100
0
1000
10
2101
100
1000
1
1000
100
21002
10000
10000
2
1000
1000
1101003
1000000
100000
3
1000
10000
101001004
100000000
1000000
4
1000
100000
10010001005
10000000000
10000000
5
1000
Tabela 1:
Efektywno
ść
- przykład (
ź
ródło: A. Drozdek - "Struktury danych w j
ę
zyku C").
Analizująctabelewidzimy,Ŝedlamałychwartościnnajwiększywkładdowynikufunkcji
wnosiostatniskładnik(1000).Przywzrościendowartości10zarównoskładnik100n,jaki
1000dajątakisamwkład.Dlanrównego100największywkładwnosiczęśćn
2
oraz100n.
DlawartościnpowyŜej100widaćwyraźnie,Ŝekwadratowaszybkośćwzrostuskładnikn
2
powoduje,ŜewnosionnajwiększywkładiwartośćfunkcjizaleŜygłównieodniego.Zatem
dladostatecznieduŜychnpozostałeskładnikimoŜnazaniedbać.
Notacja ”wielkie O”
JesttojednazpowszechniejstosowanychnotacjiopisującazłoŜonośćasymptotyczną.
Funkcja f(n) jest O(g(n)), jeśli istnieją liczby dodatnie c i N takie, Ŝe f(n) ≤ cg(n) dla
wszystkichn≥N.
Coznaczytyle,Ŝejeślimamydanąfunkcję:
f
tofunkcjacg(n)dlawszystkichn≥NopisujeprzybliŜonawartośćzłoŜonościasymptotycznej
funkcjif(n).StałeciNwyznaczasięzrównania:
(
n
)
=
2
n
2
+
3
n
+
1
5
[ Pobierz całość w formacie PDF ]