Algorytmy od podstaw

[ Pobierz całość w formacie PDF ]
IDZ DO
PRZYK£ADOW
Algorytmy. Od podstaw
SPIS TREŒCI
KATALOG KSI¥¯EK
Autorzy: Simon Harris, James Ross
T³umaczenie: Andrzej Gra¿yñski
ISBN: 83-246-0372-7
Tytu³ orygina³u:
Format: B5, stron: 610
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
Wprowadzenie do problematyki algorytmów i struktur danych
Badanie z³o¿onoœci algorytmów
Analiza i implementacja algorytmów
Zasady testowania kodu
Algorytmy le¿¹ u podstaw programowania. Zasady rozwi¹zywania typowych problemów
programistycznych, opisane w postaci blokowej lub za pomoc¹ uniwersalnego
„pseudokodu”, s¹ wykorzystywane codziennie przez tysi¹ce informatyków na ca³ym
œwiecie. W³aœciwe zrozumienie zarówno samych algorytmów, jak i zasad ich
stosowania w praktyce, jest kluczem do tworzenia wydajnych aplikacji. Umiejêtnoœæ
oceny efektywnoœci i z³o¿onoœci algorytmów przyda siê równie¿ przy wyborze
najlepszego rozwi¹zania okreœlonego problemu.
Ksi¹¿ka „Algorytmy. Od podstaw” przedstawia podstawowe zagadnienia zwi¹zane
z algorytmami. Dziêki niej nauczysz siê wyznaczaæ z³o¿onoœæ obliczeniow¹ algorytmów
i implementowaæ algorytmy w programach. Poznasz algorytmy sortowania,
przeszukiwania i przetwarzania danych. Dowiesz siê, czym s¹ testy jednostkowe
i dlaczego ich stosowanie jest tak wa¿ne podczas tworzenia oprogramowania.
W ksi¹¿ce omówiono m.in. nastêpuj¹ce zagadnienia:
Testy jednostkowe i biblioteka JUnit
Iteracja i rekurencja
Kolejki FIFO
Listy i stosy
Algorytmy sortowania
Binarne wyszukiwanie i zastêpowanie
Zbiory, mapy i drzewa wyszukiwawcze
Wyszukiwanie tekstu
Poznaj sprawdzone i powszechnie u¿ywane algorytmy
i zastosuj je w swoich aplikacjach
DODAJ DO KOSZYKA
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
ONOWOŒCIACH
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
O autorach ................................................................................................................................................... 9
Podziękowania ............................................................................................................................................11
Wprowadzenie ........................................................................................................................................... 13
Rozdział 1. Zaczynamy .............................................................................................................................. 23
Czym są algorytmy? ..................................................................................................... 23
Co to jest złożoność algorytmu? .................................................................................... 26
Porównywanie złożoności i notacja „dużego O” ............................................................... 27
Złożoność stała — O(1) ........................................................................................... 29
Złożoność liniowa — O(N) ........................................................................................ 29
Złożoność kwadratowa — O(N
2
) ............................................................................... 30
Złożoność logarytmiczna — O(log N) i O(N log N) ....................................................... 31
Złożoność rzędu silni — O(N!) .................................................................................. 32
Testowanie modułów .................................................................................................... 32
Czym jest testowanie modułów? .............................................................................. 33
Dlaczego testowanie modułów jest ważne? ............................................................... 35
Biblioteka JUnit i jej wykorzystywanie ........................................................................ 35
Programowanie sterowane testami ........................................................................... 38
Podsumowanie ............................................................................................................ 39
Rozdział 2. Iteracja i rekurencja .............................................................................................................. 41
Wykonywanie obliczeń .................................................................................................. 42
Przetwarzanie tablic ..................................................................................................... 44
Iteratory jako uogólnienie przetwarzania tablicowego ................................................. 45
Rekurencja .................................................................................................................. 62
Przykład — rekurencyjne drukowanie drzewa katalogów ............................................. 64
Anatomia algorytmu rekurencyjnego ......................................................................... 68
Podsumowanie ............................................................................................................ 69
Ćwiczenia .................................................................................................................... 70
 4
Algorytmy. Od podstaw
Rozdział 3. Listy ......................................................................................................................................... 71
Czym są listy? ............................................................................................................. 71
Testowanie list ............................................................................................................ 74
Implementowanie list ................................................................................................... 86
Lista tablicowa ....................................................................................................... 87
Lista wiązana ......................................................................................................... 95
Podsumowanie .......................................................................................................... 104
Ćwiczenia .................................................................................................................. 104
Rozdział 4. Kolejki ....................................................................................................................................105
Czym są kolejki? ........................................................................................................ 105
Operacje kolejkowe ............................................................................................... 106
Interfejs kolejki ..................................................................................................... 107
Kolejka FIFO .............................................................................................................. 107
Implementowanie kolejki FIFO ................................................................................ 111
Kolejki blokujące ........................................................................................................ 113
Przykład — symulacja centrum obsługi ........................................................................ 117
Uruchomienie aplikacji .......................................................................................... 127
Podsumowanie .......................................................................................................... 128
Ćwiczenia .................................................................................................................. 129
Rozdział 5. Stosy .......................................................................................................................................131
Czym są stosy? ......................................................................................................... 131
Testy ........................................................................................................................ 133
Implementacja ........................................................................................................... 136
Przykład — implementacja operacji „Cofnij/Powtórz” .................................................... 140
Testowanie cofania/powtarzania ............................................................................ 141
Podsumowanie .......................................................................................................... 149
Rozdział 6. Sortowanie
—
proste algorytmy .........................................................................................151
Znaczenie sortowania ................................................................................................. 151
Podstawy sortowania .................................................................................................. 152
Komparatory .............................................................................................................. 153
Operacje komparatora ........................................................................................... 153
Interfejs komparatora ............................................................................................ 154
Niektóre komparatory standardowe ........................................................................ 154
Sortowanie bąbelkowe ............................................................................................... 159
Interfejs ListSorter ................................................................................................ 161
Abstrakcyjna klasa testowa dla sortowania list ........................................................ 161
Sortowanie przez wybieranie ....................................................................................... 165
Sortowanie przez wstawianie ...................................................................................... 170
Stabilność sortowania ................................................................................................ 173
Porównanie prostych algorytmów sortowania ................................................................ 175
CallCountingListComparator .................................................................................. 176
ListSorterCallCountingTest .................................................................................... 177
Jak interpretować wyniki tej analizy? ....................................................................... 180
Podsumowanie .......................................................................................................... 180
Ćwiczenia .................................................................................................................. 181
Spis treści
5
Rozdział 7. Sortowanie zaawansowane .................................................................................................183
Sortowanie metodą Shella .......................................................................................... 183
Sortowanie szybkie .................................................................................................... 189
Komparator złożony i jego rola w zachowaniu stabilności sortowania .............................. 195
Sortowanie przez łączenie ........................................................................................... 198
Łączenie list ......................................................................................................... 198
Algorytm Mergesort ............................................................................................... 199
Porównanie zaawansowanych algorytmów sortowania ................................................... 205
Podsumowanie .......................................................................................................... 208
Ćwiczenia .................................................................................................................. 209
Rozdział 8. Kolejki priorytetowe .............................................................................................................211
Kolejki priorytetowe .................................................................................................... 212
Prosty przykład kolejki priorytetowej ....................................................................... 212
Wykorzystywanie kolejek priorytetowych ....................................................................... 215
Kolejka priorytetowa oparta na liście nieposortowanej ............................................. 218
Kolejka priorytetowa wykorzystująca listę posortowaną ............................................ 220
Kolejki priorytetowe o organizacji stogowej .............................................................. 222
Porównanie implementacji kolejek priorytetowych ......................................................... 229
Podsumowanie .......................................................................................................... 233
Ćwiczenia .................................................................................................................. 233
Rozdział 9. Binarne wyszukiwanie i wstawianie ................................................................................. 235
Wyszukiwanie binarne ................................................................................................ 235
Dwa sposoby realizacji wyszukiwania binarnego ...................................................... 238
Interfejs wyszukiwania binarnego ........................................................................... 238
Iteracyjna wyszukiwarka binarna ............................................................................. 244
Ocena działania wyszukiwarek ............................................................................... 247
Wstawianie binarne .................................................................................................... 253
Inserter binarny .................................................................................................... 254
Porównywanie wydajności ...................................................................................... 257
Podsumowanie .......................................................................................................... 261
Rozdział 10. Binarne drzewa wyszukiwawcze .................................................................................... 263
Binarne drzewa wyszukiwawcze ................................................................................... 264
Minimum ............................................................................................................. 265
Maksimum ........................................................................................................... 265
Następnik ............................................................................................................ 265
Poprzednik ........................................................................................................... 266
Szukanie .............................................................................................................. 266
Wstawianie .......................................................................................................... 268
Usuwanie ............................................................................................................. 269
Trawersacja in-order .............................................................................................. 272
Trawersacja pre-order ............................................................................................ 272
Trawersacja post-order .......................................................................................... 273
Wyważanie drzewa ................................................................................................ 273
Testowanie i implementowanie binarnych drzew wyszukiwawczych ................................. 275
Ocena efektywności binarnego drzewa wyszukiwawczego .............................................. 299
Podsumowanie .......................................................................................................... 302
Ćwiczenia .................................................................................................................. 303
6
Algorytmy. Od podstaw
Rozdział 11. Haszowanie .......................................................................................................................... 305
Podstawy haszowania ................................................................................................. 305
Praktyczna realizacja haszowania ................................................................................ 311
Próbkowanie liniowe ............................................................................................. 314
Porcjowanie .......................................................................................................... 321
Ocena efektywności tablic haszowanych ...................................................................... 326
Podsumowanie .......................................................................................................... 332
Ćwiczenia .................................................................................................................. 332
Rozdział 12. Zbiory .................................................................................................................................. 333
Podstawowe cechy zbiorów ......................................................................................... 333
Testowanie implementacji zbiorów ......................................................................... 336
Zbiór w implementacji listowej .................................................................................... 342
Zbiór haszowany ........................................................................................................ 344
Zbiór w implementacji drzewiastej ............................................................................... 349
Podsumowanie .......................................................................................................... 356
Ćwiczenia .................................................................................................................. 356
Rozdział 13. Mapy .................................................................................................................................... 357
Koncepcja i zastosowanie map ................................................................................... 357
Testowanie implementacji map ................................................................................... 362
Mapa w implementacji listowej .................................................................................... 369
Mapa w implementacji haszowanej .............................................................................. 373
Mapa w implementacji drzewiastej .............................................................................. 377
Podsumowanie .......................................................................................................... 384
Ćwiczenia .................................................................................................................. 384
Rozdział 14. Ternarne drzewa wyszukiwawcze .................................................................................. 385
Co to jest drzewo ternarne? ........................................................................................ 385
Wyszukiwanie słowa .............................................................................................. 386
Wstawianie słowa ................................................................................................. 389
Poszukiwanie prefiksu ........................................................................................... 391
Dopasowywanie wzorca ......................................................................................... 392
Drzewa ternarne w praktyce ........................................................................................ 395
Przykład zastosowania — rozwiązywanie krzyżówek ....................................................... 409
Podsumowanie .......................................................................................................... 412
Ćwiczenie .................................................................................................................. 412
Rozdział 15. B-drzewa .............................................................................................................................413
Podstawowe własności B-drzew ................................................................................... 413
Praktyczne wykorzystywanie B-drzew ............................................................................ 419
Podsumowanie .......................................................................................................... 431
Ćwiczenie .................................................................................................................. 431
Rozdział 16. Wyszukiwanie tekstu ......................................................................................................... 433
Interfejs wyszukiwarki łańcuchów ................................................................................ 433
Zestaw testowy dla wyszukiwarki łańcuchów ................................................................ 435
Prymitywny algorytm wyszukiwania ............................................................................... 438
Algorytm Boyera-Moore’a ............................................................................................ 441
Tworzenie testów dla algorytmu Boyera-Moore’a ...................................................... 443
Implementowanie algorytmu Boyera-Moore’a .......................................................... 444
[ Pobierz całość w formacie PDF ]