Algorytmy, struktury danych i techniki programowania

Co odróżnia tę książkę od innych podręczników?......Page 9
Dlaczego C++?......Page 10
Rozdział 3. Typy i struktury danych......Page 11
Rozdział 10. Elementy algorytmiki grafów......Page 12
Programy przykładowe......Page 13
Konwencje typograficzne i oznaczenia......Page 14
Uwagi do wydania V......Page 15
Rozdział 1. Zanim wystartujemy......Page 17
Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych......Page 19
Jak to się niedawno odbyło, czyli o tym, kto „wymyślił” metodologię programowania......Page 23
Proces koncepcji programów......Page 24
Poziomy abstrakcji opisu i wybór języka......Page 25
Poprawność algorytmów......Page 26
Rozwiązania i wskazówki do zadań......Page 28
Definicja rekurencji......Page 31
Ilustracja pojęcia rekurencji......Page 33
Jak wykonują się programy rekurencyjne?......Page 34
Ciąg Fibonacciego......Page 36
Stack overflow!......Page 38
Pułapek ciąg dalszy......Page 39
Definicja poprawna, ale…......Page 40
Typy programów rekurencyjnych......Page 41
Myślenie rekurencyjne......Page 43
Przykład 1.: Spirala......Page 44
Przykład 2.: Kwadraty „parzyste”......Page 45
Uwagi praktyczne na temat technik rekurencyjnych......Page 46
Zadania......Page 47
Rozwiązania i wskazówki do zadań......Page 50
Rozdział 3. Typy i struktury danych......Page 55
Typy podstawowe i złożone......Page 56
Tablice......Page 57
Ciągi znaków i napisy w C++......Page 58
Struktury i wprowadzenie pojęcia referencji......Page 60
Klasy i programowanie obiektowe......Page 62
Abstrakcyjne struktury danych......Page 63
Listy jednokierunkowe......Page 64
Tablicowa implementacja list......Page 84
Stos......Page 89
Kolejki FIFO......Page 93
Sterty i kolejki priorytetowe......Page 96
Drzewa i ich reprezentacje......Page 101
Zbiory......Page 113
STL, czyli struktury danych dla leniuchów......Page 115
Klasyczne kontenery sekwencyjne......Page 116
Adaptery (nakładki na inne kontenery)......Page 120
Kontenery asocjacyjne......Page 121
Algorytmy w STL......Page 122
Zadania......Page 123
Rozwiązania zadań......Page 124
Rozdział 4. Analiza złożoności algorytmów......Page 125
Definicje i przykłady......Page 126
Jeszcze raz funkcja silnia......Page 129
Zerowanie fragmentu tablicy......Page 133
Wpadamy w pułapkę......Page 134
Różne typy złożoności obliczeniowej......Page 136
Nowe zadanie: uprościć obliczenia!......Page 137
Terminologia i definicje......Page 138
Rozkład logarytmiczny......Page 140
Zamiana dziedziny równania rekurencyjnego......Page 142
Funkcja Ackermanna, czyli coś dla smakoszy......Page 143
Techniki optymalizacji programów......Page 144
Zadania......Page 145
Rozwiązania i wskazówki do zadań......Page 146
Rozdział 5. Derekursywacja i optymalizacja algorytmów......Page 149
Jak pracuje kompilator?......Page 150
Odrobina formalizmu nie zaszkodzi!......Page 151
Kilka przykładów derekursywacji algorytmów......Page 153
Eliminacja zmiennych lokalnych......Page 156
Metoda funkcji przeciwnych......Page 158
Schemat typu while......Page 160
Schemat typu if-else......Page 161
Schemat z podwójnym wywołaniem rekurencyjnym......Page 163
Podsumowanie......Page 165
Rozdział 6. Algorytmy sortowania......Page 167
)......Page 168
)......Page 169
Quicksort, algorytm klasy O(N log N)......Page 171
Heap Sort — sortowanie przez kopcowanie......Page 174
Sortowanie przez scalanie, algorytm klasy O(N log N)......Page 176
Sortowanie zewnętrzne......Page 178
Uwagi praktyczne......Page 181
Przeszukiwanie liniowe......Page 183
Przeszukiwanie binarne......Page 184
Transformacja kluczowa (hashing)......Page 185
W poszukiwaniu funkcji H......Page 187
Najbardziej znane funkcje H......Page 188
Powrót do źródeł......Page 190
Jeszcze raz tablice!......Page 191
Próbkowanie liniowe......Page 192
Podwójne kluczowanie......Page 193
Podsumowanie metod transformacji kluczowej......Page 195
Algorytm typu brute-force......Page 197
Nowe algorytmy poszukiwań......Page 199
Algorytm K-M-P......Page 200
Algorytm Boyera i Moore’a......Page 203
Algorytm Rabina i Karpa......Page 205
Rozdział 9. Zaawansowane techniki programowania......Page 209
Programowanie typu „dziel i zwyciężaj”......Page 210
Odszukiwanie minimum i maksimum w tablicy liczb......Page 211
N......Page 213
Mnożenie liczb całkowitych......Page 216
Algorytmy „żarłoczne”, czyli przekąsić coś nadszedł już czas......Page 217
Problem plecakowy, czyli niełatwe jest życie turysty piechura......Page 218
Wydawanie reszty, czyli „A nie ma pan drobnych?” w praktyce......Page 220
Programowanie dynamiczne......Page 221
Równania z wieloma zmiennymi......Page 223
Najdłuższa wspólna podsekwencja......Page 225
Inne techniki programowania......Page 227
Uwagi bibliograficzne......Page 230
Rozdział 10. Elementy algorytmiki grafów......Page 231
Definicje i pojęcia podstawowe......Page 232
Cykle w grafach......Page 234
Reprezentacja tablicowa......Page 237
Słowniki węzłów......Page 239
Kompozycja grafów......Page 240
Graf do potęgi......Page 241
Algorytm Roya-Warshalla......Page 242
Algorytm Floyda-Warshalla......Page 245
Algorytm Dijkstry......Page 248
Drzewo rozpinające minimalne......Page 249
Algorytm Kruskala......Page 250
Przeszukiwanie grafów......Page 251
Strategia „w głąb” (przeszukiwanie zstępujące)......Page 252
Strategia „wszerz”......Page 253
Problem właściwego doboru......Page 255
Zadania......Page 259
Rozdział 11. Algorytmy numeryczne......Page 261
Poszukiwanie miejsc zerowych funkcji......Page 262
Iteracyjne obliczanie wartości funkcji......Page 263
Interpolacja funkcji metodą Lagrange’a......Page 264
Różniczkowanie funkcji......Page 265
Całkowanie funkcji metodą Simpsona......Page 267
Rozwiązywanie układów równań liniowych metodą Gaussa......Page 268
Uwagi końcowe......Page 271
Rozdział 12. Czy komputery mogą myśleć?......Page 273
Przegląd obszarów zainteresowań sztucznej inteligencji (SI)......Page 274
Systemy eksperckie......Page 275
Sieci neuronowe......Page 276
Reprezentacja problemów......Page 278
Gry dwuosobowe i drzewa gier......Page 279
Algorytm mini-max......Page 280
Rozdział 13. Kodowanie i kompresja danych......Page 285
Kodowanie symetryczne......Page 287
Kodowanie asymetryczne......Page 288
Metody prymitywne......Page 293
Techniki kompresji danych......Page 295
Kompresja za pomocą modelowania matematycznego......Page 297
Kompresja metodą RLE......Page 298
Kompresja danych metodą Huffmana......Page 299
Kodowanie LZW......Page 303
Idea kodowania słownikowego na przykładach......Page 304
Opis formatu GIF......Page 306
Teksty zadań......Page 309
Rozwiązania......Page 311
Pierwszy program......Page 315
Procedury......Page 316
Funkcje......Page 317
Operacje logiczne......Page 318
Wskaźniki i zmienne dynamiczne......Page 319
Typy złożone......Page 320
Rekordy......Page 321
Iteracje......Page 322
Operacje na plikach w C++......Page 323
Programowanie obiektowe w C++......Page 324
Terminologia......Page 325
Obiekty na przykładzie......Page 326
Składowe statyczne klas......Page 328
Dziedziczenie własności......Page 329
Kod warunkowy w C++......Page 331
System dziesiętny i kilka definicji......Page 333
System dwójkowy......Page 334
Operacje arytmetyczne na liczbach dwójkowych......Page 335
Operacje logiczne na liczbach dwójkowych......Page 336
System szesnastkowy......Page 337
Zmienne w pamięci komputera......Page 338
Kodowanie znaków......Page 339
Zawartość archiwum ZIP na ftp......Page 341
GNU C Compiler......Page 342
Microsoft Visual Studio Community......Page 344
Kompilacja i uruchamianie programów w C++......Page 345
GCC......Page 346
Microsoft Visual Studio......Page 347
Dev-C++......Page 352
Literatura......Page 355
Spis tabel......Page 357
Spis ilustracji......Page 359
Skorowidz......Page 365