Algorytmy, struktury danych i techniki programowania. Wydanie VI (e-book)

Algorytmy, struktury danych i techniki programowania. Wydanie VI (e-book) - Opis

Algorytmy i struktury danych - szybko, łatwo, skutecznie!

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 (...) więcej 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

Jedyny podręcznik do algorytmiki, którego będziesz potrzebować!
Spis treści:

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

O autorze: Piotr Wróblewski —

autor książek z dziedziny informatyki. Z wydawnictwem Helion współpracuje od 1992 roku, czego efektem są liczne podręczniki programowania i obsługi komputerów; najpopularniejsze, ABC komputera i Algorytmy, struktury danych i techniki programowania, doczekały się wielu wydań i nieprzerwanie cieszą się zainteresowaniem czytelników. Ostatni z wymienionych tytułów ukazał się również za granicą. Pierwotnie ilustrowany kodem C++, został przygotowany także w wariantach z językami Java i Python.

Piotr Wróblewski jest absolwentem Politechniki Śląskiej i francuskiej uczelni inżynierskiej ENSSAT (w Lannion w Bretanii). Studia we Francji do dziś wspomina jako największą przygodę swojego życia. Po powrocie do Polski przez pewien czas zajmował się pisaniem oprogramowania na zamówienie i prowadzeniem szkoleń komputerowych. Główną część kariery zawodowej zajmuje mu praca w spółkach zagranicznych z branży telekomunikacyjnej, IT i konsultingu, głównie w charakterze kierownika projektów i product managera.

Już w trakcie pracy zawodowej ukończył studia z zarządzania i marketingu ... Master HEC w Szkole Biznesu Politechniki Warszawskiej. Od 2006 roku mieszka we Wrocławiu. W ostatnich latach specjalizuje się w bezpieczeństwie aplikacji (klasycznych i oferowanych w chmurze) i rozwijaniu produktów wspomagających cyberbezpieczeństwo.

Pełny profil zawodowy: https://www.linkedin.com/in/pwroblewski/. mniej