ALGORYTMY STRUKTURY DANYCH I TECHNIKI PROGRAMOWANIA WRÓBLEWSKI P. Księgarnia

Algorytmy, struktury danych i techniki programowania

Poznaj najważniejsze algorytmy i techniki programistyczne
Naucz się skutecznie wykorzystywać typy i struktury danych
Dowiedz się, jak w praktyce zastosować zdobytą wiedzę

Algorytmika to dziedzina, która w ciągu ostatnich kilkudziesięciu lat dostarczyła wielu efektywnych narzędzi wspomagających rozwiązywanie różnorodnych zagadnień za pomocą komputera. Dla niektórych stanowi swego rodzaju książkę kucharską, do której sięgają jedynie po wybrane przepisy, a dla innych - pole do rozwinięcia umiejętności skutecznego rozwiązywania problemów i szkołę niestandardowego myślenia. Niezależnie od podejścia jest to dziedzina, z którą wypada się zapoznać, jeśli ma się ambicję zostać zawodowym programistą lub po prostu być osobą nowoczesną i wszechstronnie wykształconą.

Ten przewodnik prezentuje szerokie spektrum zagadnień algorytmicznych, najważniejsze informacje na temat struktur danych, technik rekurencyjnych i złożonych metod algorytmicznych.

Teoria jest tu poparta przykładowymi programami napisanymi w języku C++, łatwymi do analizy i skompilowania z wykorzystaniem standardowych narzędzi. Autor nie poprzestaje na suchym kodzie, lecz stara się przedstawić praktyczne zastosowanie opisywanych rozwiązań. Podręcznik przyda się zarówno osobom niemającym solidnych podstaw teoretycznych, jak i specjalistom, którzy zawodowo zajmują się programowaniem. Nowe wydanie zostało gruntownie odświeżone i poprawione, a listingi dostosowane do wymagań najnowszych kompilatorów. Książka zawiera opis zasad kompilacji dla środowiska Visual Studio 2017 i kilku wybranych środowisk używających GNU C++ (Dev-C++ i Cygwin).

Historia algorytmiki
Mechanizm rekurencji
Systemy liczbowe i kodowanie
Typy i struktury danych
Analiza złożoności algorytmów
Derekursywacja algorytmów
Optymalizacja algorytmów
Algorytmy sortowania i wyszukiwania
Elementy algorytmiki grafów
Sztuczna inteligencja
Szyfrowanie i kompresja danych
Biblioteka STL

Przedmowa 9
Uwagi do wydania VI 9
Co odróżnia tę książkę od innych podręczników? 10
Dlaczego C++? 11
Jak należy czytać tę książkę? 11
Co zostało opisane w tej książce? 12
Programy przykładowe 14
Konwencje typograficzne i oznaczenia 15

Rozdział 1. Zanim wystartujemy 17

Czym powinien się charakteryzować algorytm? 18
Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych 20
- 1804 - 20
- 1830 i później - 21
- 1890 - 21
- lata 30. XX w. - 21
- lata 40. XX w. - 22
- okres powojenny - 22
- 1969 - 23
- teraz - 23
Jak to się niedawno odbyło, czyli o tym, kto "wymyślił" metodologię programowania 24
Proces koncepcji programów 25
Poziomy abstrakcji opisu i wybór języka 26
Modelowanie działania algorytmów (maszyna Turinga) 28
Poprawność algorytmów 29
Zadania 31
Rozwiązania i wskazówki do zadań 31

Rozdział 2. Rekurencja 33

Definicja rekurencji 33
Ilustracja pojęcia rekurencji 35
Jak wykonują się programy rekurencyjne? 36
Niebezpieczeństwa rekurencji 38
Ciąg Fibonacciego 38
Stack overflow! 40
Pułapek ciąg dalszy 42
Stąd do wieczności 43
Definicja poprawna, ale... 43
Typy programów rekurencyjnych 45
Myślenie rekurencyjne 46
Przykład 1. Spirala 47
Przykład 2. Kwadraty "parzyste" 48
Uwagi praktyczne na temat technik rekurencyjnych 50
Zadania 51
Rozwiązania i wskazówki do zadań 53

Rozdział 3. Systemy obliczeniowe i podstawy kodowania 59

System dziesiętny i kilka definicji 60
System dwójkowy 60
Operacje arytmetyczne na liczbach dwójkowych 61
Operacje logiczne na liczbach dwójkowych 62
Kod BCD 64
System ósemkowy 65
System szesnastkowy 65
Kodowanie liczb ze znakiem 65
Kod znak-moduł (ZM) 66
Kod U2 (system uzupełnienia dwójkowego) 66
Zmienne w pamięci komputera 67
Kodowanie znaków 68
Kodowanie obrazów 70
Mapy bitowe na przykładzie formatu BMP 71

Rozdział 4. Typy i struktury danych 75

Typy podstawowe i złożone 76
Tablice 77
Ciągi znaków i napisy w C++ 78
Typy złożone 80
Struktury i wprowadzenie pojęcia referencji 80
Klasy i programowanie obiektowe 83
Abstrakcyjne struktury danych 83
Listy jednokierunkowe 85
Tablicowa implementacja list 106
Stos 111
Kolejki FIFO 116
Sterty i kolejki priorytetowe 119
Drzewa i ich reprezentacje 125
Zbiory 138
STL, czyli struktury danych dla leniuchów 140
Klasyczne kontenery sekwencyjne 141
Adaptery (nakładki na inne kontenery) 147
Kontenery asocjacyjne 148
Algorytmy w STL 151
Dalsze materiały na temat STL 152
Zadania 152
Rozwiązania zadań 153

Rozdział 5. Analiza złożoności algorytmów 155

Definicje i przykłady 156
Jeszcze raz funkcja silnia 160
Zerowanie fragmentu tablicy 163
Wpadamy w pułapkę 165
Różne typy złożoności obliczeniowej 166
Nowe zadanie: uprościć obliczenia! 168
Analiza programów rekurencyjnych 169
Terminologia i definicje 169
Ilustracja metody na przykładzie 170
Rozkład logarytmiczny 171
Przeszukiwanie binarne... tym razem bez matematyki wyższej! 173
Zamiana dziedziny równania rekurencyjnego 174
Funkcja Ackermanna, czyli coś dla smakoszy 174
Złożoność obliczeniowa to nie religia! 176
Techniki optymalizacji programów 176
Zadania 177
Rozwiązania i wskazówki do zadań 178

Rozdział 6. Derekursywacja i optymalizacja algorytmów 181

Jak pracuje kompilator? 182
Odrobina formalizmu nie zaszkodzi! 184
Kilka przykładów derekursywacji algorytmów 185
Derekursywacja z wykorzystaniem stosu 188
Eliminacja zmiennych lokalnych 188
Metoda funkcji przeciwnych 190
Klasyczne schematy derekursywacji 192
Schemat typu while 193
Schemat typu if-else 194
Schemat z podwójnym wywołaniem rekurencyjnym 196
Podsumowanie 198

Rozdział 7. Algorytmy sortowania 199

Sortowanie przez wstawianie, algorytm klasy O(N2) 200
Sortowanie bąbelkowe, algorytm klasy O(N2) 201
Sortowanie szybkie (Quicksort) - algorytm klasy O(N log N) 203
Heapsort - sortowanie przez kopcowanie 206
Scalanie zbiorów posortowanych 209
Sortowanie przez scalanie, algorytm klasy O(N log N) 209
Sortowanie zewnętrzne 211
Uwagi praktyczne 214

Rozdział 8. Algorytmy przeszukiwania 217

Przeszukiwanie liniowe 217
Przeszukiwanie binarne 218
Transformacja kluczowa (hashing) 220
W poszukiwaniu funkcji H 221
Najbardziej znane funkcje H 222
Obsługa konfliktów dostępu 224
Powrót do źródeł 225
Jeszcze raz tablice! 226
Próbkowanie liniowe 226
Podwójne kluczowanie 228
Zastosowania transformacji kluczowej 229
Podsumowanie metod transformacji kluczowej 230

Rozdział 9. Przeszukiwanie tekstów 233

Algorytm typu brute force 233
Nowe algorytmy poszukiwań 235
Algorytm KMP 236
Algorytm Boyera-Moore'a 240
Algorytm Rabina-Karpa 242

Rozdział 10. Zaawansowane techniki programowania 245

Programowanie typu "dziel i zwyciężaj" 246
Odszukiwanie minimum i maksimum w tablicy liczb 247
Mnożenie macierzy o rozmiarze N(N 249
Mnożenie liczb całkowitych 252
Inne znane algorytmy "dziel i zwyciężaj" 253
Algorytmy "żarłoczne", czyli przekąsić coś nadszedł już czas... 253
Problem plecakowy, czyli niełatwe jest życie turysty piechura 254
Wydawanie reszty, czyli "A nie ma pan drobnych?" w praktyce 257
Programowanie dynamiczne 258
Ciąg Fibonacciego 259
Równania z wieloma zmiennymi 260
Najdłuższa wspólna podsekwencja 261
Inne techniki programowania 264
Uwagi bibliograficzne 266

Rozdział 11. Elementy algorytmiki grafów 269

Definicje i pojęcia podstawowe 270
Etykiety i wartości 271
Cykle w grafach 273
Sposoby reprezentacji grafów 276
Reprezentacja tablicowa 276
Słowniki węzłów 278
Listy kontra zbiory 279
Podstawowe operacje na grafach 279
Suma grafów 279
Kompozycja grafów 280
Graf do potęgi 280
Algorytm Roya-Warshalla 281
Algorytm Floyda-Warshalla 284
Algorytm Dijkstry 287
Algorytm Bellmana-Forda 289
Drzewo rozpinające minimalne 289
Algorytm Kruskala 290
Algorytm Prima 291
Przeszukiwanie grafów 291
Strategia "w głąb" (przeszukiwanie zstępujące) 292
Strategia "wszerz" 294
Inne strategie przeszukiwania 295
Problem właściwego doboru 296
Podsumowanie 300
Zadania 300

Rozdział 12. Algorytmy numeryczne 301

Poszukiwanie miejsc zerowych funkcji 301
Iteracyjne obliczanie wartości funkcji 303
Interpolacja funkcji metodą Lagrange'a 304
Różniczkowanie funkcji 305
Całkowanie funkcji metodą Simpsona 307
Rozwiązywanie układów równań liniowych metodą Gaussa 308
Biblioteka GSL (GNU Scientific Library) 311
Uwagi końcowe 311

Rozdział 13. Czy komputery mogą myśleć? 313

Przegląd obszarów zainteresowań sztucznej inteligencji (SI) 314
Systemy eksperckie 315
Sieci neuronowe 317
Reprezentacja problemów 318
Gry dwuosobowe i drzewa gier 320
Algorytm min-max 321

Rozdział 14. Kodowanie i kompresja danych 327

Kodowanie danych i arytmetyka dużych liczb 329
Metody prymitywne 329
Kodowanie symetryczne 331
Kodowanie asymetryczne 332
Łamanie kodów 338
Jakość klucza szyfrującego 338
Metody łamania szyfrów 339
Techniki kompresji danych 340
Kompresja za pomocą modelowania matematycznego 341
Kompresja metodą RLE 342
Kompresja danych metodą Huffmana 343
Kodowanie LZW 348
Rozdział 15. Zadania różne 355

Teksty zadań 355
Rozwiązania 357

Dodatek A. Poznaj C++ w pięć minut! 361

Elementy języka C++ na przykładach 361
Pierwszy program 361
Dyrektywa #include 362
Kod warunkowy w C++ 362
Operacje arytmetyczne i zmienne 363
Operacje logiczne 363
Wskaźniki i zmienne dynamiczne 364
Referencje 365
Typy proste i typy złożone 365
Podprogramy 367
Procedury 367
Funkcje 367
Instrukcja wyboru (switch) 368
Iteracje 369
Struktury rekurencyjne 369
Parametry programu main() 370
Operacje na plikach w C++ 370
Programowanie obiektowe w C++ 371
Terminologia 372
Obiekty na przykładzie 373
Składowe statyczne klas 376
Metody stałe klas 376
Dziedziczenie własności 376

Dodatek B. Kompilowanie programów przykładowych 381

Zawartość archiwum ZIP na FTP-ie 381
Darmowe kompilatory C++ 382
GCC (GNU Compiler Collection) 382
Microsoft Visual Studio Community 384
macOS 386
Dev-C++ (Orwell) 386
Kompilacja i uruchamianie programów w C++ 387
GCC 387
Microsoft Visual Studio 388
Dev-C++ 395
Cygwin 395
Literatura 397

Spis ilustracji 399
Spis tabel 404
Skorowidz 406

416 stron, Format: 158x235, oprawa miękka

Po otrzymaniu zamówienia poinformujemy,
czy wybrany tytuł polskojęzyczny lub anglojęzyczny jest aktualnie na półce księgarni.