Algorytmy struktury danych i techniki programowania
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).
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(N2) (168)
- Sortowanie bąbelkowe, algorytm klasy O(N2) (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)
Skorowidz (365)
376 stron, oprawa miękka
