Algorytmy struktury danych i ...

[ Pobierz całość w formacie PDF ]
IDZ DO
PRZYK£ADOW
Algorytmy, struktury danych
i techniki programowania.
Wydanie III
SPIS TRECI
KATALOG KSI¥¯EK
KATALOG ONLINE
Autor: Piotr Wróblewski
ISBN: 83-7361-101-0
Format: B5, stron: 360
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
Algorytmika stanowi ga³¹ wiedzy, która w ci¹gu ostatnich kilkudziesiêciu lat
dostarczy³a wielu efektywnych narzêdzi wspomagaj¹cych rozwi¹zywanie ró¿norodnych
problemów za pomoc¹ komputera. Teoria algorytmów i struktur danych jest jednym
z podstawowych przedmiotów wyk³adanych na studiach informatycznych i pokrewnych.
Ksi¹¿ka, której trzecie i poprawione wydanie trzymasz w rêku, od wielu lat stanowi
podstawowy podrêcznik z dziedziny algorytmiki. Ró¿ni siê od klasycznych
podrêczników akademickich: skierowana jest nie tylko do adeptów informatyki.
Dziêki naciskowi na praktyczn¹ stronê prezentowanych zagadnieñ powinna
zainteresowaæ tak¿e osoby programuj¹ce hobbystycznie, jak równie¿ tych wszystkich,
dla których programowanie jest dzia³alnoci¹ wa¿n¹, lecz nie podstawow¹ w pracy
zawodowej. Jest to nowoczesny podrêcznik dla wszystkich, którzy w codziennej pracy
programistycznej odczuwaj¹ potrzebê szybkiego odszukania pewnych informacji
z dziedziny algorytmiki w celu zastosowania ich w swoich programach.
W ksi¹¿ce opisano m.in.:
• Techniki rekurencyjne: co to jest rekurencja i jak j¹ stosowaæ w praktyce?
• Sortowanie danych: najpopularniejsze procedury sortuj¹ce.
• Struktury danych: listy, kolejki, zbiory i drzewa w ujêciu praktycznym.
• Derekursywacja: jak zmieniæ program rekurencyjny (czasami bardzo
czasoch³onny) na wersjê iteracyjn¹?
• Algorytmy przeszukiwania: przeszukiwanie liniowe, binarne i transformacja
liniowa (ang. hashing).
• Przeszukiwanie tekstów: opis najbardziej znanych metod przeszukiwania tekstów
(Boyera i Moore'a, Rabina i Karpa, brute-force, K-M-P).
• Zaawansowane techniki programowania: dziel i rz¹d, programowanie
dynamiczne, algorytmy ¿ar³oczne (ang. greedy).
• Algorytmika grafów: opis jednej z najciekawszych struktur danych
wystêpuj¹cych w informatyce.
• Sztuczna inteligencja: czy komputery mog¹ myleæ?
• Kodowanie i kompresja danych: opis najpopularniejszych metod kodowania
i kompresji danych — systemu kryptograficznego z kluczem publicznym
i metody Huffmana
W ksi¹¿ce znajdziesz równie¿ liczne przyk³ady i zadania, które pomog¹ Ci sprawdziæ
swoj¹ wiedzê. Kod ród³owy znajdziesz na do³¹czonej dyskietce.
DODAJ DO KOSZYKA
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treci
Przedmowa......................................................................................11
Rozdział 1. Zanim wystartujemy ........................................................................19
1.1. Jak to wczeniej bywało, czyli wyjtki z historii maszyn algorytmicznych..............21
1.2. Jak to si niedawno odbyło, czyli o tym, kto „wymylił”
metodologi programowania .....................................................................................23
1.3. Proces koncepcji programów .....................................................................................24
1.4. Poziomy abstrakcji opisu i wybór jzyka...................................................................25
1.5. Poprawno( algorytmów............................................................................................27
Rozdział 2. Rekurencja......................................................................................29
2.1. Definicja rekurencji....................................................................................................29
2.2. Ilustracja pojcia rekurencji .......................................................................................31
2.3. Jak wykonuj si programy rekurencyjne?...................................................................32
2.4. Niebezpiecze0stwa rekurencji....................................................................................34
2.4.1. Cig Fibonacciego ............................................................................................34
2.4.2. Stack overflow!.................................................................................................36
2.5. Pułapek cig dalszy....................................................................................................37
2.5.1. Std do wiecznoci............................................................................................37
2.5.2. Definicja poprawna, ale... .................................................................................38
2.6. Typy programów rekurencyjnych..............................................................................39
2.7. Mylenie rekurencyjne...............................................................................................41
2.7.1. Przykład 1.: Spirala...........................................................................................42
2.7.2. Przykład 2.: Kwadraty „parzyste”.....................................................................44
2.8. Uwagi praktyczne na temat technik rekurencyjnych .................................................45
2.9. Zadania.......................................................................................................................46
2.9.1. Zadanie 2.1........................................................................................................46
2.9.2. Zadanie 2.2........................................................................................................46
2.9.3. Zadanie 2.3........................................................................................................48
2.9.4. Zadanie 2.4........................................................................................................48
2.9.5. Zadanie 2.5........................................................................................................49
2.10. Rozwizania i wskazówki do zada0.........................................................................49
2.10.1. Zadanie 2.1......................................................................................................49
2.10.2. Zadanie 2.2......................................................................................................50
2.10.3. Zadanie 2.3......................................................................................................50
2.10.4. Zadanie 2.4......................................................................................................51
2.10.5. Zadanie 2.5......................................................................................................52
 6
Algorytmy, struktury danych i techniki programowania
Rozdział 3. Analiza sprawnoci algorytmów........................................................53
3.1. Dobre samopoczucie u@ytkownika programu............................................................54
3.2. Przykład 1: Jeszcze raz funkcja silnia........................................................................56
3.3. Przykład 2: Zerowanie fragmentu tablicy..................................................................60
3.4. Przykład 3: Wpadamy w pułapk...............................................................................62
3.5. Przykład 4: Ró@ne typy zło@onoci obliczeniowej.....................................................63
3.6. Nowe zadanie: uproci( obliczenia! ............................................................................66
3.7. Analiza programów rekurencyjnych ...........................................................................66
3.7.1. Terminologia.....................................................................................................67
3.7.2. Ilustracja metody na przykładzie ......................................................................68
3.7.3. Rozkład logarytmiczny .....................................................................................70
3.7.4. Zamiana dziedziny równania rekurencyjnego ..................................................71
3.7.5. Funkcja Ackermanna, czyli co dla smakoszy .................................................72
3.8. Zadania.......................................................................................................................73
3.8.1. Zadanie 3.1........................................................................................................73
3.8.2. Zadanie 3.2........................................................................................................74
3.8.3. Zadanie 3.3........................................................................................................74
3.8.4. Zadanie 3.4........................................................................................................74
3.9. Rozwizania i wskazówki do zada0...........................................................................75
3.9.1 Zadanie 3.2.........................................................................................................75
3.9.2. Zadanie 3.4........................................................................................................76
Rozdział 4. Algorytmy sortowania ......................................................................77
4.1. Sortowanie przez wstawianie, algorytm klasy O(N
2
) ................................................78
4.2. Sortowanie bbelkowe, algorytm klasy O(N
2
)...........................................................80
4.3. Quicksort, algorytm klasy O(N log N).......................................................................82
4.4. Heap Sort — sortowanie przez kopcowanie ..............................................................85
4.5. Sortowanie przez scalanie..........................................................................................88
4.6. Uwagi praktyczne.......................................................................................................90
Rozdział 5. Struktury danych .............................................................................93
5.1. Listy jednokierunkowe...............................................................................................94
5.1.1. Realizacja struktur danych listy jednokierunkowej ..........................................96
5.1.2. Tworzenie listy jednokierunkowej....................................................................97
5.1.3. Listy jednokierunkowe — teoria i rzeczywisto(................................................106
5.2. Tablicowa implementacja list...................................................................................119
5.2.1. Klasyczna reprezentacja tablicowa.................................................................119
5.2.2. Metoda tablic równoległych ...........................................................................121
5.2.3. Listy innych typów .........................................................................................123
5.3. Stos...........................................................................................................................125
5.3.1. Zasada działania stosu.....................................................................................125
5.4. Kolejki FIFO ............................................................................................................129
5.5. Sterty i kolejki priorytetowe.....................................................................................132
5.6. Drzewa i ich reprezentacje .......................................................................................139
5.6.1. Drzewa binarne i wyra@enia arytmetyczne.....................................................142
5.7. Uniwersalna struktura słownikowa..........................................................................147
5.8. Zbiory.......................................................................................................................152
5.9. Zadania.....................................................................................................................155
5.9.1. Zadanie 5.1......................................................................................................155
5.9.2. Zadanie 5.2......................................................................................................155
5.9.3. Zadanie 5.3......................................................................................................155
5.10. Rozwizania zada0.................................................................................................155
5.10.1. Zadanie 5.1....................................................................................................155
5.10.2. Zadanie 5.3....................................................................................................156
Spis treci
7
Rozdział 6. Derekursywacja i optymalizacja algorytmów ...................................157
6.1. Jak pracuje kompilator? ...........................................................................................158
6.2. Odrobina formalizmu nie zaszkodzi!..........................................................................160
6.3. Kilka przykładów derekursywacji algorytmów ...........................................................162
6.4. Derekursywacja z wykorzystaniem stosu ................................................................165
6.4.1. Eliminacja zmiennych lokalnych....................................................................166
6.5. Metoda funkcji przeciwnych....................................................................................168
6.6. Klasyczne schematy derekursywacji........................................................................170
6.6.1. Schemat typu while.........................................................................................171
6.6.2. Schemat typu if-else........................................................................................173
6.6.3. Schemat z podwójnym wywołaniem rekurencyjnym.....................................175
6.7. Podsumowanie .........................................................................................................177
Rozdział 7. Algorytmy przeszukiwania ..............................................................179
7.1. Przeszukiwanie liniowe............................................................................................179
7.2. Przeszukiwanie binarne............................................................................................180
7.3. Transformacja kluczowa (hashing)..........................................................................181
7.3.1. W poszukiwaniu funkcji H .............................................................................183
7.3.2. Najbardziej znane funkcje H...........................................................................184
7.3.3. Obsługa konfliktów dostpu ...........................................................................187
7.3.4. Powrót do Lródeł.............................................................................................187
7.3.5. Jeszcze raz tablice!..........................................................................................188
7.3.6. Próbkowanie liniowe ......................................................................................189
7.3.7. Podwójne kluczowanie ...................................................................................191
7.3.8. Zastosowania transformacji kluczowej...........................................................193
7.3.9. Podsumowanie metod transformacji kluczowej ...............................................193
Rozdział 8. Przeszukiwanie tekstów.................................................................195
8.1. Algorytm typu brute-force .......................................................................................195
8.2. Nowe algorytmy poszukiwa0...................................................................................197
8.2.1. Algorytm K-M-P.............................................................................................198
8.2.2.Algorytm Boyera i Moore’a.............................................................................203
8.2.3. Algorytm Rabina i Karpa................................................................................205
Rozdział 9. Zaawansowane techniki programowania.........................................209
9.1. Programowanie typu „dziel i zwyci@aj”.................................................................210
9.1.1. Odszukiwanie minimum i maksimum w tablicy liczb....................................211
9.1.2. Mno@enie macierzy o rozmiarze N×N............................................................214
9.1.3. Mno@enie liczb całkowitych ...........................................................................217
9.1.4. Inne znane algorytmy „dziel i zwyci@aj”......................................................218
9.2. Algorytmy „@arłoczne”, czyli przeksi( co nadszedł ju@ czas... ............................219
9.2.1. Problem plecakowy, czyli niełatwe jest @ycie turysty-piechura ...........................220
9.3. Programowanie dynamiczne ....................................................................................223
9.4. Uwagi bibliograficzne..............................................................................................227
Rozdział 10. Elementy algorytmiki grafów..........................................................229
10.1. Definicje i pojcia podstawowe .............................................................................230
10.2. Sposoby reprezentacji grafów................................................................................232
10.3. Podstawowe operacje na grafach ...........................................................................234
10.3.1. Suma grafów.................................................................................................234
10.3.2. Kompozycja grafów......................................................................................234
10.3.3. Potga grafu ..................................................................................................235
10.4. Algorytm Roy-Warshalla.......................................................................................236
10.5. Algorytm Floyda-Warshalla...................................................................................239
10.6. Algorytm Dijkstry ..................................................................................................243
8
Algorytmy, struktury danych i techniki programowania
10.7. Drzewo rozpinajce minimalne..............................................................................244
10.8. Przeszukiwanie grafów ..........................................................................................245
10.8.1. Strategia „w głb”.........................................................................................246
10.8.2. Strategia „wszerz”.........................................................................................247
10.9. Problem właciwego doboru..................................................................................249
10.10. Podsumowanie .....................................................................................................254
Rozdział 11.Algorytmy numeryczne....................................................................255
11.1. Poszukiwanie miejsc zerowych funkcji .................................................................255
11.2. Iteracyjne obliczanie wartoci funkcji....................................................................257
11.3. Interpolacja funkcji metod Lagrange’a ................................................................258
11.4. Ró@niczkowanie funkcji.........................................................................................260
11.5. Całkowanie funkcji metod Simpsona...................................................................262
11.6. Rozwizywanie układów równa0 liniowych metod Gaussa ................................263
11.7. Uwagi ko0cowe......................................................................................................266
Rozdział 12. Czy komputery mog. myle/?........................................................267
12.1. Przegld obszarów zainteresowa0 Sztucznej Inteligencji......................................268
12.1.1. Systemy eksperckie.......................................................................................269
12.1.2. Sieci neuronowe............................................................................................271
12.2. Reprezentacja problemów......................................................................................272
12.2.1. Qwiczenie 12.1..............................................................................................274
12.3. Gry dwuosobowe i drzewa gier..............................................................................274
12.4. Algorytm mini-max................................................................................................276
Rozdział 13. Kodowanie i kompresja danych ......................................................281
13.1. Kodowanie danych i arytmetyka du@ych liczb...........................................................283
13.1.1. Kodowanie symetryczne...............................................................................284
13.1.2. Kodowanie asymetryczne .............................................................................285
13.1.3. Metody prymitywne......................................................................................292
13.1.4. Łamanie szyfrów...........................................................................................293
13.2. Techniki kompresji danych....................................................................................294
13.2.1. Kompresja poprzez modelowanie matematyczne.........................................296
13.2.2. Kompresja metod RLE................................................................................297
13.2.3. Kompresja danych metod Huffmana ..........................................................298
13.2.4. Kodowanie LZW ..........................................................................................304
13.2.5. Idea kodowania słownikowego na przykładach ...........................................304
13.2.6. Opis formatu GIF..........................................................................................307
Rozdział 14. Zadania ró2ne................................................................................311
14.1. Teksty zada0...........................................................................................................311
14.1.1. Zadanie 14.1..................................................................................................311
14.1.2. Zadanie 14.2..................................................................................................312
14.1.3. Zadanie 14.3..................................................................................................312
14.1.4. Zadanie 14.4..................................................................................................312
14.1.5. Zadanie 14.5..................................................................................................312
14.1.6. Zadanie 14.6..................................................................................................312
14.1.7. Zadanie 14.7..................................................................................................312
14.1.8. Zadanie 14.8..................................................................................................313
14.1.9. Zadanie 14.9..................................................................................................313
14.1.10. Zadanie 14.10..............................................................................................313
14.1.11. Zadanie 14.11..............................................................................................313
14.1.12. Zadanie 14.12..............................................................................................313
[ Pobierz całość w formacie PDF ]