Algorytmy, struktury danych i techniki programowania. Wydanie IV

Podstawowy podręcznik do nauki algorytmiki

Przystępne wprowadzenie do algorytmiki
Bez zbędnej teorii
Gotowe rozwiązania w C++


Oto kolejne wydanie sprawdzonej i cenionej przez programistów, wykładowców oraz studentów książki, będącej podstawowym podręcznikiem do nauki algorytmiki. W pierwszej kolejności autor zapozna Cię z elementarnymi zagadnieniami z tej dziedziny oraz wyjaśni, skąd bierze się tak szybki postęp w tej dyscyplinie nauki. Podczas dalszej lektury poznasz takie pojęcia, jak rekurencja, analiza złożoności oraz algorytmy sortowania i przeszukiwania czy algorytmy numeryczne. Szybko opanujesz metody optymalizacji algorytmów, sposoby kodowania i kompresji danych oraz elementy algorytmiki grafów. Przedstawione w książce algorytmy zilustrowane zostały przykładowymi kodami źródłowymi w C++ , ułatwiającymi zrozumienie poznawanych zagadnień. Przejrzysta forma, praktyczne przykłady oraz przystępny język sprawiają, że książka ta pozwala szybko, a także bezboleśnie opanować zarówno algorytmy, jak i struktury danych oraz najlepsze techniki programowania.

Historia algorytmiki
Wykorzystanie rekurencji
Analiza złożoności algorytmów
Algorytmy sortowania
Algorytmy przeszukiwania
Przeszukiwanie tekstów
Struktury danych i ich implementacja
Optymalizacja algorytmów
Zaawansowane techniki programowania
Wykorzystanie grafów
Wprowadzenie do sztucznej inteligencji
Kodowanie i kompresja danych
Algorytmy numeryczne
Poradnik kompilacji i uruchamiania programów (GCC, DevC++, Microsoft Visual C++ Express Edition).

Szybko i bezboleśnie opanuj wszystkie zagadnienia algorytmiki!

Spis treści Przedmowa (9)
Rozdział 1. Zanim wystartujemy (17)

• Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych (18)
• Jak to się niedawno odbyło, czyli o tym, kto "wymyślił" metodologię programowania (21)
  
• Proces koncepcji programów (22)
• Poziomy abstrakcji opisu i wybór języka (23)
• Poprawność algorytmów (24)

Rozdział 2. Rekurencja (27)

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

Rozdział 3. Analiza złożoności algorytmów (49)

• Definicje i przykłady (50)
• Jeszcze raz funkcja silnia (53)
• Zerowanie fragmentu tablicy (57)
• Wpadamy w pułapkę (58)
• Różne typy złożoności obliczeniowej (59)
• Nowe zadanie: uprościć obliczenia! (61)
• Analiza programów rekurencyjnych (62)
• Terminologia i definicje (62)
• Ilustracja metody na przykładzie (63)
• Rozkład logarytmiczny (64)
• Zamiana dziedziny równania rekurencyjnego (66)
• Funkcja Ackermanna, czyli coś dla smakoszy (66)
• Złożoność obliczeniowa to nie religia! (68)
• Techniki optymalizacji programów (68)
• Zadania (69)
• Rozwiązania i wskazówki do zadań (70)

Rozdział 4. Algorytmy sortowania (73)

• Sortowanie przez wstawianie, algorytm klasy O(N2) (74)
• Sortowanie bąbelkowe, algorytm klasy O(N2) (75)
• Quicksort, algorytm klasy O(N log N) (77)
• Heap Sort - sortowanie przez kopcowanie (80)
• Scalanie zbiorów posortowanych (82)
• Sortowanie przez scalanie (83)
• Sortowanie zewnętrzne (84)
• Uwagi praktyczne (87)

Rozdział 5. Typy i struktury danych (89)

• Typy podstawowe i złożone (89)
• Ciągi znaków i napisy w C++ (90)
• Abstrakcyjne struktury danych (92)
• Listy jednokierunkowe (93)
• Tablicowa implementacja list (115)
• Stos (119)
• Kolejki FIFO (123)
• Sterty i kolejki priorytetowe (125)
• Drzewa i ich reprezentacje (131)
• Zbiory (143)
• Zadania (145)
• Rozwiązania zadań (146)

Rozdział 6. Derekursywacja i optymalizacja algorytmów (147)

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

Rozdział 7. Algorytmy przeszukiwania (165)

• Przeszukiwanie liniowe (165)
• Przeszukiwanie binarne (166)
• Transformacja kluczowa (hashing) (167)
• W poszukiwaniu funkcji H (169)
• Najbardziej znane funkcje H (169)
• Obsługa konfliktów dostępu (171)
• Powrót do źródeł (172)
• Jeszcze raz tablice! (173)
• Próbkowanie liniowe (173)
• Podwójne kluczowanie (175)
• Zastosowania transformacji kluczowej (176)
• Podsumowanie metod transformacji kluczowej (176)

Rozdział 8. Przeszukiwanie tekstów (179)

• Algorytm typu brute-force (179)
• Nowe algorytmy poszukiwań (181)
• Algorytm K-M-P (182)
• Algorytm Boyera i Moore'a (185)
• Algorytm Rabina i Karpa (187)

Rozdział 9. Zaawansowane techniki programowania (191)

• Programowanie typu "dziel i zwyciężaj" (192)
• Odszukiwanie minimum i maksimum w tablicy liczb (193)
• Mnożenie macierzy o rozmiarze N(N (195)
• Mnożenie liczb całkowitych (197)
• Inne znane algorytmy "dziel i zwyciężaj" (198)
• Algorytmy "żarłoczne", czyli przekąsić coś nadszedł już czas... (199)
• Problem plecakowy, czyli niełatwe jest życie turysty piechura (200)
• Programowanie dynamiczne (202)
• Ciąg Fibonacciego (203)
• Równania z wieloma zmiennymi (204)
• Najdłuższa wspólna podsekwencja (205)
• Inne techniki programowania (208)
• Uwagi bibliograficzne (210)

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

• Definicje i pojęcia podstawowe (212)
• Cykle w grafach (214)
• Sposoby reprezentacji grafów (217)
• Reprezentacja tablicowa (217)
• Słowniki węzłów (218)
• Listy kontra zbiory (219)
• Podstawowe operacje na grafach (220)
• Suma grafów (220)
• Kompozycja grafów (220)
• Potęga grafu (220)
• Algorytm Roy-Warshalla (221)
• Algorytm Floyda-Warshalla (224)
• Algorytm Dijkstry (227)
• Algorytm Bellmana-Forda (228)
• Drzewo rozpinające minimalne (228)
• Algorytm Kruskala (229)
• Algorytm Prima (230)
• Przeszukiwanie grafów (230)
• Strategia "w głąb" (przeszukiwanie zstępujące) (231)
• Strategia "wszerz" (232)
• Inne strategie przeszukiwania (234)
• Problem właściwego doboru (235)
• Podsumowanie (239)
• Zadania (239)

Rozdział 11. Algorytmy numeryczne (241)

• Poszukiwanie miejsc zerowych funkcji (241)
• Iteracyjne obliczanie wartości funkcji (243)
• Interpolacja funkcji metodą Lagrange'a (244)
• Różniczkowanie funkcji (245)
• Całkowanie funkcji metodą Simpsona (247)
• Rozwiązywanie układów równań liniowych metodą Gaussa (248)
• Uwagi końcowe (251)

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

• Przegląd obszarów zainteresowań Sztucznej Inteligencji (254)
• Systemy eksperckie (255)
• Sieci neuronowe (256)
• Reprezentacja problemów (257)
• Ćwiczenie 1. (258)
• Gry dwuosobowe i drzewa gier (259)
• Algorytm mini-max (260)

Rozdział 13. Kodowanie i kompresja danych (265)

• Kodowanie danych i arytmetyka dużych liczb (267)
• Kodowanie symetryczne (267)
• Kodowanie asymetryczne (268)
• Metody prymitywne (274)
• Łamanie szyfrów (275)
• Techniki kompresji danych (275)
• Kompresja poprzez modelowanie matematyczne (277)
• Kompresja metodą RLE (278)
• Kompresja danych metodą Huffmana (279)
• Kodowanie LZW (283)
• Idea kodowania słownikowego na przykładach (284)
• Opis formatu GIF (286)

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

• Teksty zadań (289)
• Rozwiązania (291)

Dodatek A: Poznaj C++ w pięć minut! (295)

• Elementy języka C++ na przykładach (295)
• Pierwszy program (295)
• Dyrektywa #include (296)
• Podprogramy (296)
• Procedury (296)
• Funkcje (297)
• Operacje arytmetyczne (298)
• Operacje logiczne (298)
• Wskaźniki i zmienne dynamiczne (299)
• Referencje (300)
• Typy złożone (300)
• Tablice (300)
• Rekordy (301)
• Instrukcja switch (301)
• Iteracje (302)
• Struktury rekurencyjne (303)
• Parametry programu main() (303)
• Operacje na plikach w C++ (303)
• Programowanie obiektowe w C++ (304)
• Terminologia (304)
• Obiekty na przykładzie (305)
• Składowe statyczne klas (308)
• Metody stałe klas (308)
• Dziedziczenie własności (308)
• Kod warunkowy w C++ (311)

Dodatek B: Systemy obliczeniowe w pigułce (313)

• Kilka definicji (313)
• System dwójkowy (313)
• Operacje arytmetyczne na liczbach dwójkowych (315)
• Operacje logiczne na liczbach dwójkowych (315)
• System ósemkowy (317)
• System szesnastkowy (317)
• Zmienne w pamięci komputera (317)
• Kodowanie znaków (318)

Dodatek C: Kompilowanie programów przykładowych (321)

• Zawartość archiwum ZIP na ftp (321)
• Darmowe kompilatory C++ (321)
• Kompilacja i uruchamianie (322)
• GCC (322)
• Visual C++ Express Edition (323)
• Dev C++ (327)

Literatura (329)
Spis tabel (331)
Spis ilustracji (333)
Skorowidz (339)