Algorytmy

[ Pobierz całość w formacie PDF ]
Algorytmy, struktury danych
i techniki programowania.
Wydanie IV
Autor
ISBN: 978-83-246-2306-8
Format: 158

235, stron: 452
Podstawowy podrêcznik do nauki algorytmiki
• Przystêpne wprowadzenie do algorytmiki
• Bez zbêdnej teorii
• Gotowe rozwi¹zania w C++
Oto kolejne wydanie sprawdzonej i cenionej przez programistów, wyk³adowców
oraz studentów ksi¹¿ki, bêd¹cej podstawowym podrêcznikiem do nauki algorytmiki.
W pierwszej kolejnoœci autor zapozna Ciê z elementarnymi zagadnieniami z tej
dziedziny oraz wyjaœni, sk¹d bierze siê tak szybki postêp w tej dyscyplinie nauki.
Podczas dalszej lektury poznasz takie pojêcia, jak rekurencja, analiza z³o¿onoœci oraz
algorytmy sortowania i przeszukiwania czy algorytmy numeryczne. Szybko opanujesz
metody optymalizacji algorytmów, sposoby kodowania i kompresji danych oraz elementy
algorytmiki grafów. Przedstawione w ksi¹¿ce algorytmy zilustrowane zosta³y przyk³adowymi
kodami Ÿród³owymi w C++ , u³atwiaj¹cymi zrozumienie poznawanych zagadnieñ.
Przejrzysta forma, praktyczne przyk³ady oraz przystêpny jêzyk sprawiaj¹, ¿e ksi¹¿ka
ta pozwala szybko, a tak¿e bezboleœnie opanowaæ zarówno algorytmy, jak i struktury
danych oraz najlepsze techniki programowania.
• Historia algorytmiki
• Wykorzystanie rekurencji
• Analiza z³o¿onoœci algorytmów
• Algorytmy sortowania
• Algorytmy przeszukiwania
• Przeszukiwanie tekstów
• Struktury danych i ich implementacja
• Optymalizacja algorytmów
• Zaawansowane techniki programowania
• Wykorzystanie grafów
• Wprowadzenie do sztucznej inteligencji
• Kodowanie i kompresja danych
• Algorytmy numeryczne
• Poradnik kompilacji i uruchamiania programów (GCC, DevC++, Microsoft Visual
C++ Express Edition).
Szybko i bezboleœnie opanuj wszystkie zagadnienia algorytmiki!
Spis treści
Przedmowa ...................................................................................... 9
Rozdział 1. Zanim wystartujemy ....................................................................... 17
Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych ................... 18
Jak to się niedawno odbyło,
czyli o tym, kto „wymyślił” metodologię programowania ........................................... 21
Proces koncepcji programów .......................................................................................... 22
Poziomy abstrakcji opisu i wybór języka ....................................................................... 23
Poprawność algorytmów ................................................................................................ 24
Rozdział 2. Rekurencja .................................................................................... 27
Definicja rekurencji ........................................................................................................ 27
Ilustracja pojęcia rekurencji ............................................................................................ 28
Jak wykonują się programy rekurencyjne? ..................................................................... 30
Niebezpieczeństwa rekurencji ........................................................................................ 31
Ciąg Fibonacciego .................................................................................................... 31
Stack overflow! ........................................................................................................ 33
Pułapek ciąg dalszy ........................................................................................................ 34
Stąd do wieczności ................................................................................................... 34
Definicja poprawna, ale... ......................................................................................... 35
Typy programów rekurencyjnych ................................................................................... 36
Myślenie rekurencyjne ................................................................................................... 38
Przykład 1.: Spirala .................................................................................................. 38
Przykład 2.: Kwadraty „parzyste” ............................................................................ 40
Uwagi praktyczne na temat technik rekurencyjnych ...................................................... 41
Zadania ........................................................................................................................... 42
Rozwiązania i wskazówki do zadań ............................................................................... 44
Rozdział 3. Analiza złożoności algorytmów ........................................................ 49
Definicje i przykłady ...................................................................................................... 50
Jeszcze raz funkcja silnia ......................................................................................... 53
Zerowanie fragmentu tablicy .................................................................................... 57
Wpadamy w pułapkę ................................................................................................ 58
Różne typy złożoności obliczeniowej ...................................................................... 59
Nowe zadanie: uprościć obliczenia! ............................................................................... 61
 4
Algorytmy, struktury danych i techniki programowania
Analiza programów rekurencyjnych ............................................................................... 62
Terminologia i definicje ........................................................................................... 62
Ilustracja metody na przykładzie .............................................................................. 63
Rozkład logarytmiczny ............................................................................................. 64
Zamiana dziedziny równania rekurencyjnego .......................................................... 66
Funkcja Ackermanna, czyli coś dla smakoszy ......................................................... 66
Złożoność obliczeniowa to nie religia! ........................................................................... 68
Techniki optymalizacji programów ................................................................................ 68
Zadania ........................................................................................................................... 69
Rozwiązania i wskazówki do zadań ............................................................................... 70
Rozdział 4. Algorytmy sortowania ..................................................................... 73
Sortowanie przez wstawianie, algorytm klasy O(N
2
) ..................................................... 74
Sortowanie bąbelkowe, algorytm klasy O(N
2
) ............................................................... 75
Quicksort, algorytm klasy O(N log N) ........................................................................... 77
Heap Sort — sortowanie przez kopcowanie ................................................................... 80
Scalanie zbiorów posortowanych ................................................................................... 82
Sortowanie przez scalanie ............................................................................................... 83
Sortowanie zewnętrzne ................................................................................................... 84
Uwagi praktyczne ........................................................................................................... 87
Rozdział 5. Typy i struktury danych .................................................................. 89
Typy podstawowe i złożone ........................................................................................... 89
Ciągi znaków i napisy w C++ ......................................................................................... 90
Abstrakcyjne struktury danych ....................................................................................... 92
Listy jednokierunkowe ............................................................................................. 93
Tablicowa implementacja list ................................................................................. 115
Stos ......................................................................................................................... 119
Kolejki FIFO .......................................................................................................... 123
Sterty i kolejki priorytetowe ................................................................................... 125
Drzewa i ich reprezentacje ..................................................................................... 131
Zbiory ..................................................................................................................... 143
Zadania ................................................................................................................... 145
Rozwiązania zadań ................................................................................................. 146
Rozdział 6. Derekursywacja i optymalizacja algorytmów .................................. 147
Jak pracuje kompilator? ................................................................................................ 148
Odrobina formalizmu nie zaszkodzi! ............................................................................ 150
Kilka przykładów derekursywacji algorytmów ............................................................ 151
Derekursywacja z wykorzystaniem stosu ..................................................................... 154
Eliminacja zmiennych lokalnych ............................................................................ 154
Metoda funkcji przeciwnych ........................................................................................ 156
Klasyczne schematy derekursywacji ............................................................................ 158
Schemat typu while ................................................................................................ 159
Schemat typu if-else ............................................................................................... 160
Schemat z podwójnym wywołaniem rekurencyjnym ............................................. 162
Podsumowanie .............................................................................................................. 163
Rozdział 7. Algorytmy przeszukiwania ............................................................. 165
Przeszukiwanie liniowe ................................................................................................ 165
Przeszukiwanie binarne ................................................................................................ 166
Transformacja kluczowa (hashing) ............................................................................... 167
W poszukiwaniu funkcji H ..................................................................................... 169
Najbardziej znane funkcje H .................................................................................. 169
Obsługa konfliktów dostępu ................................................................................... 171
Spis treści
5
Powrót do źródeł .................................................................................................... 172
Jeszcze raz tablice! ................................................................................................. 173
Próbkowanie liniowe .............................................................................................. 173
Podwójne kluczowanie ........................................................................................... 175
Zastosowania transformacji kluczowej ................................................................... 176
Podsumowanie metod transformacji kluczowej ..................................................... 176
Rozdział 8. Przeszukiwanie tekstów ............................................................... 179
Algorytm typu brute-force ............................................................................................ 179
Nowe algorytmy poszukiwań ....................................................................................... 181
Algorytm K-M-P .................................................................................................... 182
Algorytm Boyera i Moore’a ................................................................................... 185
Algorytm Rabina i Karpa ....................................................................................... 187
Rozdział 9. Zaawansowane techniki programowania ....................................... 191
Programowanie typu „dziel i zwyciężaj” ...................................................................... 192
Odszukiwanie minimum i maksimum w tablicy liczb ............................................ 193
Mnożenie macierzy o rozmiarze N×N .................................................................... 195
Mnożenie liczb całkowitych ................................................................................... 197
Inne znane algorytmy „dziel i zwyciężaj” .............................................................. 198
Algorytmy „żarłoczne”, czyli przekąsić coś nadszedł już czas... .................................. 199
Problem plecakowy, czyli niełatwe jest życie turysty piechura .............................. 200
Programowanie dynamiczne ......................................................................................... 202
Ciąg Fibonacciego .................................................................................................. 203
Równania z wieloma zmiennymi ........................................................................... 204
Najdłuższa wspólna podsekwencja ........................................................................ 205
Inne techniki programowania ....................................................................................... 208
Uwagi bibliograficzne .................................................................................................. 210
Rozdział 10. Elementy algorytmiki grafów ......................................................... 211
Definicje i pojęcia podstawowe .................................................................................... 212
Cykle w grafach ............................................................................................................ 214
Sposoby reprezentacji grafów ....................................................................................... 217
Reprezentacja tablicowa ......................................................................................... 217
Słowniki węzłów .................................................................................................... 218
Listy kontra zbiory ................................................................................................. 219
Podstawowe operacje na grafach .................................................................................. 220
Suma grafów .......................................................................................................... 220
Kompozycja grafów ............................................................................................... 220
Potęga grafu ........................................................................................................... 220
Algorytm Roy-Warshalla ............................................................................................. 221
Algorytm Floyda-Warshalla ......................................................................................... 224
Algorytm Dijkstry ........................................................................................................ 227
Algorytm Bellmana-Forda ............................................................................................ 228
Drzewo rozpinające minimalne .................................................................................... 228
Algorytm Kruskala ................................................................................................. 229
Algorytm Prima ...................................................................................................... 230
Przeszukiwanie grafów ................................................................................................. 230
Strategia „w głąb” (przeszukiwanie zstępujące) ..................................................... 231
Strategia „wszerz” .................................................................................................. 232
Inne strategie przeszukiwania ................................................................................. 234
Problem właściwego doboru ......................................................................................... 235
Podsumowanie .............................................................................................................. 239
Zadania ......................................................................................................................... 239
6
Algorytmy, struktury danych i techniki programowania
Rozdział 11. Algorytmy numeryczne ................................................................. 241
Poszukiwanie miejsc zerowych funkcji ........................................................................ 241
Iteracyjne obliczanie wartości funkcji .......................................................................... 243
Interpolacja funkcji metodą Lagrange’a ....................................................................... 244
Różniczkowanie funkcji ............................................................................................... 245
Całkowanie funkcji metodą Simpsona .......................................................................... 247
Rozwiązywanie układów równań liniowych metodą Gaussa ....................................... 248
Uwagi końcowe ............................................................................................................ 251
Rozdział 12. Czy komputery mogą myśleć? ....................................................... 253
Przegląd obszarów zainteresowań Sztucznej Inteligencji ............................................. 254
Systemy eksperckie ................................................................................................ 255
Sieci neuronowe ..................................................................................................... 256
Reprezentacja problemów ............................................................................................ 257
Ćwiczenie 1. ........................................................................................................... 258
Gry dwuosobowe i drzewa gier .................................................................................... 259
Algorytm mini-max ...................................................................................................... 260
Rozdział 13. Kodowanie i kompresja danych .................................................... 265
Kodowanie danych i arytmetyka dużych liczb ............................................................. 267
Kodowanie symetryczne ........................................................................................ 267
Kodowanie asymetryczne ....................................................................................... 268
Metody prymitywne ............................................................................................... 274
Łamanie szyfrów .................................................................................................... 275
Techniki kompresji danych ........................................................................................... 275
Kompresja poprzez modelowanie matematyczne ................................................... 277
Kompresja metodą RLE ......................................................................................... 278
Kompresja danych metodą Huffmana .................................................................... 279
Kodowanie LZW .................................................................................................... 283
Idea kodowania słownikowego na przykładach ..................................................... 284
Opis formatu GIF ................................................................................................... 286
Rozdział 14. Zadania różne .............................................................................. 289
Teksty zadań ................................................................................................................. 289
Rozwiązania ................................................................................................................. 291
Dodatek A Poznaj C++ w pięć minut! ............................................................. 295
Elementy języka C++ na przykładach .......................................................................... 295
Pierwszy program ................................................................................................... 295
Dyrektywa #include ............................................................................................... 296
Podprogramy ................................................................................................................ 296
Procedury ............................................................................................................... 296
Funkcje ................................................................................................................... 297
Operacje arytmetyczne ................................................................................................. 298
Operacje logiczne ................................................................................................... 298
Wskaźniki i zmienne dynamiczne .......................................................................... 299
Referencje ..................................................................................................................... 300
Typy złożone ................................................................................................................ 300
Tablice .................................................................................................................... 300
Rekordy .................................................................................................................. 301
Instrukcja switch .................................................................................................... 301
Iteracje .......................................................................................................................... 302
Struktury rekurencyjne ................................................................................................. 303
Parametry programu main() .......................................................................................... 303
Operacje na plikach w C++ .......................................................................................... 303
[ Pobierz całość w formacie PDF ]