algorytmy, struktury danych i techniki programowania. wydanie iv cała książka.pdf

(9617 KB) Pobierz
887726069.001.png
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
Spis treści
7
Programowanie obiektowe w C++ ............................................................................... 304
Terminologia .......................................................................................................... 304
Obiekty na przykładzie ........................................................................................... 305
Składowe statyczne klas ......................................................................................... 308
Metody stałe klas .................................................................................................... 308
Dziedziczenie własności ......................................................................................... 308
Kod warunkowy w C++ ............................................................................................... 311
Dodatek B Systemy obliczeniowe w pigułce ................................................... 313
Kilka definicji ............................................................................................................... 313
System dwójkowy ........................................................................................................ 313
Operacje arytmetyczne na liczbach dwójkowych ................................................... 315
Operacje logiczne na liczbach dwójkowych ........................................................... 315
System ósemkowy ........................................................................................................ 317
System szesnastkowy ................................................................................................... 317
Zmienne w pamięci komputera .................................................................................... 317
Kodowanie znaków ...................................................................................................... 318
Dodatek C Kompilowanie programów przykładowych ...................................... 321
Zawartość archiwum ZIP na ftp .................................................................................... 321
Darmowe kompilatory C++ .......................................................................................... 321
Kompilacja i uruchamianie ........................................................................................... 322
GCC ....................................................................................................................... 322
Visual C++ Express Edition ................................................................................... 323
Dev C++ ................................................................................................................. 327
Literatura ..................................................................................... 329
Spis tabel ................................................................................... 331
Spis ilustracji .............................................................................. 333
Skorowidz ................................................................................... 339

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin