Algorytmy, struktury danych i techniki programowania. Wydanie V

• Wprowadzenie do algorytmiki
• Tylko niezbędna teoria
• Gotowe rozwiązania w C++

Oto kolejne wydanie sprawdzonej, cenionej przez programistów, wykładowców oraz studentów książki, będącej podstawowym podręcznikiem do nauki algorytmiki. Jej autor zapozna Cię z elementarnymi zagadnieniami z tej dziedziny oraz wyjaśni, skąd bierze się tak szybki postęp w tej dyscyplinie nauki. Poznasz podstawowe struktury danych używane do rozwiązywania problemów algorytmicznych oraz nauczysz się je projektować w C++ z użyciem technik obiektowych i klas parametryzowanych.

Podczas dalszej lektury poznasz takie pojęcia, jak rekurencja, analiza złożoności oraz algorytmy sortowania i przeszukiwania czy algorytmy numeryczne. Opanujesz metody optymalizacji algorytmów, sposoby kodowania i kompresji danych oraz elementy algorytmiki grafów. Przedstawione tu algorytmy są zilustrowane gotowymi kodami źródłowymi w C++ , co ułatwia zrozumienie poznawanych zagadnień. Przejrzysta forma, praktyczne przykłady oraz przystępny język sprawiają, że książka pozwala szybko i bez trudu opanować zarówno algorytmy, jak i struktury danych oraz najlepsze techniki programowania.

• Historia algorytmiki
• Struktury danych i ich implementacja
• Wprowadzenie do bibliotek STL, czyli algorytmy i struktury danych dla „leniuchów”
• Analiza złożoności algorytmów
• Wykorzystanie rekurencji i optymalizacja algorytmów
• Algorytmy sortowania i przeszukiwania
• Przeszukiwanie tekstów
• Zaawansowane techniki programowania
• Wykorzystanie grafów
• Algorytmy numeryczne
• Wprowadzenie do sztucznej inteligencji
• Kodowanie i kompresja danych
• Błyskawiczny kurs C++ z uwzględnieniem programowania obiektowego
• Poradnik kompilacji i uruchamiania programów konsolowych oraz graficznych w darmowych środowiskach IDE (GCC/Dev-C++, Microsoft Visual C++ z pakietu Visual Studio).

Szybko i bezboleśnie opanuj wszystkie zagadnienia algorytmiki.

Spis treści:

Przedmowa (9)

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

Rozdział 1. Zanim wystartujemy (17)

• Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych (19)
• Jak to się niedawno odbyło, czyli o tym, kto "wymyślił" metodologię programowania (23)
• Proces koncepcji programów (24)
• Poziomy abstrakcji opisu i wybór języka (25)
• Poprawność algorytmów (26)
• Zadania (28)
• Rozwiązania i wskazówki do zadań (28)

Rozdział 2. Rekurencja (31)

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

Rozdział 3. Typy i struktury danych (55)

• Typy podstawowe i złożone (56)
• Tablice (57)
• Ciągi znaków i napisy w C++ (58)
• Typy złożone (60)
  • Struktury i wprowadzenie pojęcia referencji (60)
  • Klasy i programowanie obiektowe (62)
• Abstrakcyjne struktury danych (63)
  • Listy jednokierunkowe (64)
  • Tablicowa implementacja list (84)
  • Stos (89)
  • Kolejki FIFO (93)
  • Sterty i kolejki priorytetowe (96)
  • Drzewa i ich reprezentacje (101)
  • Zbiory (113)
• STL, czyli struktury danych dla leniuchów (115)
  • Klasyczne kontenery sekwencyjne (116)
  • Adaptery (nakładki na inne kontenery) (120)
  • Kontenery asocjacyjne (121)
  • Algorytmy w STL (122)
  • Dalsze materiały na temat STL (123)
• Zadania (123)
• Rozwiązania zadań (124)

Rozdział 4. Analiza złożoności algorytmów (125)

• Definicje i przykłady (126)
  • Jeszcze raz funkcja silnia (129)
  • Zerowanie fragmentu tablicy (133)
  • Wpadamy w pułapkę (134)
  • Różne typy złożoności obliczeniowej (136)
• Nowe zadanie: uprościć obliczenia! (137)
• Analiza programów rekurencyjnych (138)
  • Terminologia i definicje (138)
  • Ilustracja metody na przykładzie (140)
  • Rozkład logarytmiczny (140)
  • Zamiana dziedziny równania rekurencyjnego (142)
  • Funkcja Ackermanna, czyli coś dla smakoszy (143)
• Złożoność obliczeniowa to nie religia! (144)
• Techniki optymalizacji programów (144)
• Zadania (145)
• Rozwiązania i wskazówki do zadań (146)

Rozdział 5. Derekursywacja i optymalizacja algorytmów (149)

• Jak pracuje kompilator? (150)
• Odrobina formalizmu nie zaszkodzi! (151)
• Kilka przykładów derekursywacji algorytmów (153)
• Derekursywacja z wykorzystaniem stosu (156)
  • Eliminacja zmiennych lokalnych (156)
• Metoda funkcji przeciwnych (158)
• Klasyczne schematy derekursywacji (160)
  • Schemat typu while (160)
  • Schemat typu if-else (161)
  • Schemat z podwójnym wywołaniem rekurencyjnym (163)
• Podsumowanie (165)

Rozdział 6. Algorytmy sortowania (167)

• Sortowanie przez wstawianie, algorytm klasy O(N²) (168)
• Sortowanie bąbelkowe, algorytm klasy O(N²) (169)
• Quicksort, algorytm klasy O(N log N) (171)
• Heap Sort - sortowanie przez kopcowanie (174)
• Scalanie zbiorów posortowanych (176)
• Sortowanie przez scalanie, algorytm klasy O(N log N) (176)
• Sortowanie zewnętrzne (178)
• Uwagi praktyczne (181)

Rozdział 7. Algorytmy przeszukiwania (183)

• Przeszukiwanie liniowe (183)
• Przeszukiwanie binarne (184)
• Transformacja kluczowa (hashing) (185)
  • W poszukiwaniu funkcji H (187)
  • Najbardziej znane funkcje H (188)
  • Obsługa konfliktów dostępu (190)
  • Powrót do źródeł (190)
  • Jeszcze raz tablice! (191)
  • Próbkowanie liniowe (192)
  • Podwójne kluczowanie (193)
  • Zastosowania transformacji kluczowej (195)
  • Podsumowanie metod transformacji kluczowej (195)

Rozdział 8. Przeszukiwanie tekstów (197)

• Algorytm typu brute-force (197)
• Nowe algorytmy poszukiwań (199)
  • Algorytm K-M-P (200)
  • Algorytm Boyera i Moore'a (203)
  • Algorytm Rabina i Karpa (205)

Rozdział 9. Zaawansowane techniki programowania (209)

• Programowanie typu "dziel i zwyciężaj" (210)
  • Odszukiwanie minimum i maksimum w tablicy liczb (211)
  • Mnożenie macierzy o rozmiarze N(N (213)
  • Mnożenie liczb całkowitych (216)
  • Inne znane algorytmy "dziel i zwyciężaj" (217)
• Algorytmy "żarłoczne", czyli przekąsić coś nadszedł już czas... (217)
  • Problem plecakowy, czyli niełatwe jest życie turysty piechura (218)
  • Wydawanie reszty, czyli "A nie ma pan drobnych?" w praktyce (220)
• Programowanie dynamiczne (221)
  • Ciąg Fibonacciego (223)
  • Równania z wieloma zmiennymi (223)
  • Najdłuższa wspólna podsekwencja (225)
• Inne techniki programowania (227)
• Uwagi bibliograficzne (230)

Rozdział 10. Elementy algorytmiki grafów (231)

• Definicje i pojęcia podstawowe (232)
• Cykle w grafach (234)
• Sposoby reprezentacji grafów (237)
  • Reprezentacja tablicowa (237)
  • Słowniki węzłów (239)
  • Listy kontra zbiory (240)
• Podstawowe operacje na grafach (240)
  • Suma grafów (240)
  • Kompozycja grafów (240)
  • Graf do potęgi (241)
• Algorytm Roya-Warshalla (242)
• Algorytm Floyda-Warshalla (245)
• Algorytm Dijkstry (248)
• Algorytm Bellmana-Forda (249)
• Drzewo rozpinające minimalne (249)
  • Algorytm Kruskala (250)
  • Algorytm Prima (251)
• Przeszukiwanie grafów (251)
  • Strategia "w głąb" (przeszukiwanie zstępujące) (252)
  • Strategia "wszerz" (253)
  • Inne strategie przeszukiwania (255)
• Problem właściwego doboru (255)
• Podsumowanie (259)
• Zadania (259)

Rozdział 11. Algorytmy numeryczne (261)

• Poszukiwanie miejsc zerowych funkcji (261)
• Iteracyjne obliczanie wartości funkcji (263)
• Interpolacja funkcji metodą Lagrange'a (264)
• Różniczkowanie funkcji (265)
• Całkowanie funkcji metodą Simpsona (267)
• Rozwiązywanie układów równań liniowych metodą Gaussa (268)
• Uwagi końcowe (271)

Rozdział 12. Czy komputery mogą myśleć? (273)

• Przegląd obszarów zainteresowań sztucznej inteligencji (SI) (274)
  • Systemy eksperckie (275)
  • Sieci neuronowe (276)
• Reprezentacja problemów (278)
• Gry dwuosobowe i drzewa gier (279)
• Algorytm mini-max (280)

Rozdział 13. Kodowanie i kompresja danych (285)

• Kodowanie danych i arytmetyka dużych liczb (287)
  • Kodowanie symetryczne (287)
  • Kodowanie asymetryczne (288)
  • Metody prymitywne (293)
  • Łamanie szyfrów (295)
• Techniki kompresji danych (295)
  • Kompresja za pomocą modelowania matematycznego (297)
  • Kompresja metodą RLE (298)
  • Kompresja danych metodą Huffmana (299)
  • Kodowanie LZW (303)
  • Idea kodowania słownikowego na przykładach (304)
  • Opis formatu GIF (306)

Rozdział 14. Zadania różne (309)

• Teksty zadań (309)
• Rozwiązania (311)

Dodatek A. Poznaj C++ w pięć minut! (315)

• Elementy języka C++ na przykładach (315)
  • Pierwszy program (315)
  • Dyrektywa #include (316)
• Podprogramy (316)
  • Procedury (316)
  • Funkcje (317)
• Operacje arytmetyczne (318)
  • Operacje logiczne (318)
  • Wskaźniki i zmienne dynamiczne (319)
• Referencje (320)
• Typy złożone (320)
  • Tablice (321)
  • Rekordy (321)
  • Instrukcja switch (322)
• Iteracje (322)
• Struktury rekurencyjne (323)
• Parametry programu main() (323)
• Operacje na plikach w C++ (323)
• Programowanie obiektowe w C++ (324)
  • Terminologia (325)
  • Obiekty na przykładzie (326)
  • Składowe statyczne klas (328)
  • Metody stałe klas (329)
  • Dziedziczenie własności (329)
• Kod warunkowy w C++ (331)

Dodatek B. Systemy obliczeniowe w pigułce (333)

• System dziesiętny i kilka definicji (333)
• System dwójkowy (334)
  • Operacje arytmetyczne na liczbach dwójkowych (335)
  • Operacje logiczne na liczbach dwójkowych (336)
• System ósemkowy (337)
• System szesnastkowy (337)
• Zmienne w pamięci komputera (338)
• Kodowanie znaków (339[x1])

Dodatek C. Kompilowanie programów przykładowych (341)

• Zawartość archiwum ZIP na ftp (341)
• Darmowe kompilatory C++ (342)
  • GNU C Compiler (342)
  • Microsoft Visual Studio Community (344)
  • Dev-C++ (Orwell) (345)
• Kompilacja i uruchamianie programów w C++ (345)
  • GCC (346)
  • Microsoft Visual Studio (347)
  • Dev-C++ (352)

Literatura (355)

Spis tabel (357)

Spis ilustracji (359)