Wróblewski P. - Algorytmy, struktury danych i techniki programowania. Wydanie II.pdf

(10024 KB) Pobierz
Algorytmy
struktury danych
'r
i techniki programowania
1 1 1 1 1 1
ii
1 1 1 1
11111 111
j.i J r E
(liiiiihiM
i
oryrbesi
t/votw*
Ktnrt
.5
Klop
i,
°>0 1
0 .5
,
0 .0
¡Mjil mli
i ii
Spis treści
Przedmowa.......................................................................................................................... 9
Rozdział 1 Zanim wystartujemy.......................................................................................17
l . I , Jak to wcześniej bywało, czyliwyjątki zhistorii maszyn algorytmicznych..................... 19
1.2. Jak to się niedawno odbyło, czylio tym kto „wymyślił"metodologię programowania 21
1.3. Proces koncepcji programów.....................................................................................22
1.4. Poziomy abstrakcji opisu i wybór języka.................................................................... 23
1.5. Poprawność algorytmów........................................................................................... 25
Rozdział 2 R eku ren cja.................................................................................................... 29
2.1. Definicja rekurencji................................................................................................. 29
2.2. Ilustracja pojęcia rekurencji.......................................................................................31
2.3. Jak wykonują się programy rekurencyjne?..................................................................... 33
2.4. Niebezpieczeństwa rekurencji................................................................................... 34
2.4.1. Ciąg Fibonacciego........................................................................................35
2.4.2. Stack overflow!............................................................................................ 36
2.5. Pułapek ciąg dalszy.................................................................................................. 37
2.5.1. Stąd do wieczności.......................................................................................38
2.5.2. Definicja poprawna, ale................................................................................ 38
2.6. Typy programów rckurcncyjnych.............................................................................. 40
2.7. Myślenie rekurencyjne..............................................................................................42
2.7.1. Spirala.........................................................................................................42
2.7.2. Kwadraty „parzyste".....................................................................................44
2.8. Uwagi praktyczne na temat technik rekurencyjnych....................................................45
2.9. Zadania................................................................................................................... 47
2.10. Rozwiązania i wskazówki Ho zadań..........................................................................49
Rozdział 3 Analiza sprawności algorytmów....................................................................53
3.1. Dobre samopoczucie użytkownika programu..............................................................54
6
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
Spis treści
Przykład I: Jeszcze raz funkcja silnia......................................................................... 57
Przykład 2: Zerowanie fragmentu tablicy....................................................................61
Przykład 3: Wpadamy w pułapkę...............................................................................64
Przykład 4: Różne typy złożoności obliczeniowej........................................................65
Nowe zadanie: uprościć obliczenia!........................................................................... 68
Analiza programów rekurencyjnych........................................................................... 68
3.7.1 Terminologia............................................................................................... 69
.
3.7.2. Ilustracja metody na przykładzie....................................................................7
1
3.7.3. Rozkład „logarytmiczny” ..............................................................................72
3.7.3..................................................................................................................... 72
3.7.4. Zamiana dziedziny równania rekurencyjnego.................................................. 74
3.7.5. Funkcja Ackermanna, czyli coś dla smakoszy................................................. 75
3.8. Zadania................................................................................................................... 76
3.9. Rozwiązania i wskazówki do zadań...............................................
78
Rozdział 4 Algorytmy sortowania..................................................................................... 81
4.1. Sortowanie przez wstawianie, algorytm klasy 0 (N ").................................................... 82
4.2. Sortowanie bąbelkowe, algorytm klasy
0(N ~).............................................................
84
4.3. Quicksort, algorytm klasy 0(N log?N)....................................................................... 87
4.4. 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 jednokierunkow ej..................................................................98
5.1.3. Listy jednokierunkowe - teoria i rzeczywistość............................................. 108
5.2. Tablicowa implementacja list...................................................................................122
5.2.1. Klasyczna reprezentacja tablicowa................................................................122
5.2.2. Metoda tablic równoległych.........................................................................124
5.2.3. Listy innych typów..................................................................................... 127
5.3. Stos....................................................................................................................... 128
5.3.1. Zasada działania stosu................................................................................. 128
5.4. Kolejki F IF O ..........................................................................................................133
5.5. Sterty i kolejki priorytetowe.....................................................................................136
5.6. Drzewa i ich reprezentacje....................................................................................... 143
5.6.1. Drzewa binarne i wyrażenia arytmetyczne.....................................................147
5.7. Uniwersalna struktura słownikowa........................................................................... 152
5.8. Zbiory....................................................................................................................159
5.9. Zadania..................................................................................................................161
5.10. Rozwiązania zadań................................................................................................162
Rozdział 6 D erekursyw acja............................................................................................165
6.1. Jak pracuje kompilator?........................................................................................... I66
6.2. Odrobina formalizmu... nie zaszkodzi!...................................................................... 1
69
6.3. Kilka przykładów derekursywacji algorytmów.............................................................. 170
6.4. Derekursywacja z wykorzystaniem stosu................................................................... 174
6.4.1. Eliminacja zmiennych lokalnych.................................................................. 175
6.5. Metoda funkcji przeciwnych.................................................................................... 17?
6.6. Klasyczne schematy derekursywacji..........................................................................180
Spis treści
7
6.6.1. Schemat typu
while.....................................................................................
1 1
8
6.6.2. Schemat typu
if... ehe..................................................................................
182
6.6.3. Schemat z podwójnym wywołaniem rekurencyjnym..................................... 185
6.7. Podsumowanie....................................................................................................... 187
Rozdział 7 Algorytmy przeszukiwania........................................................................... 189
7.1. Przeszukiwanie liniowe...........................................................................................189
7.2. Przeszukiwanie binarne...........................................................................................1
90
7.3. Transformacja kluczowa.......................................................................................... I9l
7.3.1. W poszukiwaniu funkcji
H
.......................................................................... 193
7.3.2. Najbardziej znane funkcje
H
....................................................................... 194
7.3.3. Obsługa konfliktów dostępu........................................................................ 197
7.3.4. Zastosowania transformacji kluczowej......................................................... 204
7.3.5. Podsumowanie metod transformacji kluczowej............................................. 204
Rozdział 8 Przeszukiwanie tekstów ..............................................................................207
8.1. Algorytm typu
brute-force.......................................................................................207
8.2. Nowe algorytmy poszukiwań................................................................................... 210
8.2.1 Algory tm K-M-P....................................................................................... 211
.
8.2.2. Algorytm Boyera i Moore'a ........................................................................ 216
8.2.3. Algorytm Rabina i Karpa.............................................................................218
Rozdział 9 Zaawansowane techniki program owania......................................................223
9.1. Programowanie typu „dziel-i-rządź” ................................................,.......................221
9.1.1. Odszukiwanie minimum i maksimum w' tablicy liczb..................................... 225
9.1.2. Mnożenie macierzy o rozmiarze N * N .......................................................... 229
9.1.3. Mnożenie liczb całkowitych........................................................................ 232
9.1.4. Inne znane algorytmy „dzicl-i-rządź” ..,........................................................ 233
9.2. Algorytmy „żarłoczne” , czyli przekąsić coś nadszedł już czas................................... 234
9.2.1. Problem plecakowy, czyli niełatwe jest życie turysty-piechura............................. 235
9.3. Programowanie dynamiczne....................................................................................238
9.4. Uwagi bibliograficzne............................................................................................. 243
Rozdział 10 Elementy algorytmiki grafów .................................................................... 245
10 I. Definicje i pojęcia podstawowe............................................................................. 246
1
0.2. Sposoby reprezentacji grafów'................................................................................ 248
1
0.3. Podstawowe operacje na grafach............................................................................249
10.4. Algorytm Koy-Warshalla...................................................................................... 251
1
0.5. Algorytm Floyda.................................................................................................. 254
1
0.6. Przeszukiwanie grafów ........................................................................................ 257
1
0.6.1. Strategia „w głąb” .....................................................................................257
1
0.6.2. Strategia „wszerz” ....................................................................................259
1
0.7. Problem właściwego doboru.................................................................................. 261
10.8. Podsumowanie..................................................................................................... 266
Rozdział 11 Algorytmy numeryczne.............................................................................. 267
11.1. Poszukiwanie miejsc zerowych funkcji.................................................................. 268
11.2. Iteracyjne obliczanie wartości funkcji.................................................................... 269
11.3. Interpolacja funkcji metodą Lagrange’a ................................................................. 270
11.4. Różniczkowanie funkcji........................................................................................ 272
8
Spis treści
11.5. Całkowanie funkcji metodą Simpsona....................................................................274
I 1.6. Rozwiązywanie układów równań liniowych metodą Gaussa..................................... 276
11.7. Uwagi końcowe................................................................................................... 279
Rozdział 12
W
stronę sztucznej inteligencji.................................................................. 281
12.1. Reprezentacja problemów..................................................................................... 282
12.2. Gry dwuosobowe i drzewa gier..............................................................................283
12.3. Algorytm mini-max............................................................................................... 286
Rozdział 13 Kodowanie i kompresja danych................................................................ 293
1
3.1. Kodowanie danych i arytmetyka dużych liczb............................................................. 294
13.2. Kompresja danych metodą Huffmana......................................................................302
Rozdział 14 Zadania ró żn e........................................................................................... 309
1
4.1. Teksty zadań..................................
309
14.2. Rozwiązania......................................................................................................... 312
Dodatek A
Poznaj
C + +
w pięć minut.............................................................................. 317
Literatura......................................................................................................................... 337
Spis ilustracji.................................................................................................................. 339
Spis tab lic........................................................................................................................343
Skorowidz........................................................................................................................345

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin