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)