Badanie algorytmów leży w samym sercu nauk komputerowych. W ostatnich latach dokonano znaczących postępów w tej dziedzinie. Opracowano m.in. wiele efektywniejszych algorytmów (szybkie przekształcenie Fouriera), odkryto także istnienie pewnych naturalnych zadań, dla których wszystkie algorytmy są nieefektywne. Wyniki te powodują wzrost zainteresowania badaniami algorytmów, co przyczynia się do intensywnego rozwoju tej dziedziny wiedzy.

Książka jest podręcznikiem wstępnego kursu projektowania i analizy algorytmów. Autorzy położyli nacisk raczej na prezentacji najważniejszych idei i przystępności wykładu, niż na szczegółach realizacji i sztuczkach programistycznych. Autorzy przedstawiają na ogół nieformalne, intuicyjne objaśnienia zamiast długich i pracochłonnych dowodów. Książka nie wymaga żadnego szczególnego przygotowania z zakresu matematyki, czy języków programowania. Pożądana jest jednak pewna dojrzałość w stosowaniu pojęć matematycznych, ogólne obycie w językach programowania wysokiego poziomu, takich jak FORTRAN lub ALGOL, a także podstawowa znajomość algebry liniowej.

W książce omówiono m.in.:

• Podstawowe pojęcia i modele (w tym maszynę Turniga)
• Najważniejsze struktury danych, rekurencję, programowanie dynamiczne
• Algorytmy sortowania, operacje na zbiorach, drzewach i grafach
• Szybkie przekształcenie Fouriera z zastosowaniami
• Algorytmy arytmetyczne, operacje na wielomianach
• Algorytmy dopasowania wzorców
• Problemy NP-zupełne
• Dolne ograniczenia złożoności obliczeniowej

Ważnym uzupełnieniem treści książki są ćwiczenia o zróżnicowanych poziomach trudności. "Projektowanie i analiza algorytmów" to doskonały podręcznik dla studentów informatyki i kierunków pokrewnych, a także wspaniała pomoc dla osób prowadzących wykłady i ćwiczenia na tych kierunkach.

Projektowanie i analiza algorytmów -- spis treści

Przedmowa (7)

1. Modele obliczania 11

• 1.1 Algorytmy i ich złożoność (11)
  
• 1.2 Maszyny o dostępie swobodnym 14
  
• 1.3 Złożoność obliczeniowa programów RAM 20
  
• 1.4 Model z zapamiętanym programem 23
  
• 1.5 Abstrakcje RAM 28
  
• 1.6 Pierwotny model obliczania: maszyna Turinga 34
  
• 1.7 Związek pomiędzy maszyną Turinga i modelem RAM (39)
  
• 1.8 Pidgin ALGOL - język wysokiego poziomu (41)

2. Projektowanie efektywnych algorytmów 51

• 2.1 Struktury danych: listy, kolejki i stosy 52
  
• 2.2 Reprezentacje zbioru 56
  
• 2.3 Grafy 57
  
• 2.4 Drzewa (60)
  
• 2.5 Rekurencja (63)
  
• 2.6 Dziel i zwyciężaj 67
  
• 2.7 Zrównoważenie (73)
  
• 2.8 Programowanie dynamiczne 74
  
• 2.9 Zakończenie (77)

3. Sortowanie i statystyka pozycyjna 85

• 3.1 Problem sortowania 86
  
• 3.2 Sortowanie pozycyjne (87)
  
• 3.3 Sortowanie przez porównania (95)
  
• 3.4 Heapsort - algorytm sortowania przez O(n log n) porównań (96)
  
• 3.5 Quicksort - algorytm sortowania w czasie oczekiwanym O(n log n) 101
  
• 3.6 Statystyka pozycyjna 106
  
• 3.7 Czas oczekiwany dla statystyki pozycyjnej 108

4. Struktury danych dla zadań operujących na zbiorach 117

• 4.1 Operacje pierwotne na zbiorach 117
  
• 4.2 Haszowanie (120)
  
• 4.3 Poszukiwanie binarne (122)
  
• 4.4 Drzewa poszukiwań binarnych (124)
  
• 4.5 Optymalne drzewa poszukiwań binarnych 128
  
• 4.6 Prosty algorytm sumy zbiorów rozłącznych (132)
  
• 4.7 Struktury drzew dla problemu UNION-FIND 136
  
• 4.8 Zastosowania i rozszerzenia algorytmu UNION-FIND 146
  
• 4.9 Schematy z drzewami zrównoważonymi 152
  
• 4.10 Słowniki i kolejki priorytetowe 155
  
• 4.11 Kopce złączane (159)
  
• 4.12 Kolejki konkatenowane (162)
  
• 4.13 Podział (164)
  
• 4.14 Podsumowanie rozdziału 169

5. Algorytmy na grafach 179

• 5.1 Drzewa rozpinające o minimalnym koszcie 179
  
• 5.2 Przeszukiwanie w głąb (183)
  
• 5.3 Dwuspójność 187
  
• 5.4 Przeszukiwanie w głąb grafu skierowanego 195
  
• 5.5 Spójność silna 197
  
• 5.6 Problemy znajdowania ścieżek (203)
  
• 5.7 Algorytm przechodniego domknięcia (207)
  
• 5.8 Algorytm najkrótszych ścieżek 208
  
• 5.9 Problemy ścieżek i mnożenie macierzy 210
  
• 5.10 Problemy jednego źródła 215
  
• 5.11 Dominatory w acyklicznym grafie skierowanym (218)

6. Mnożenie macierzy i pokrewne operacje 235

• 6.1 Podstawy 235
  
• 6.2 Algorytm Strassena mnożenia macierzy (239)
  
• 6.3 Odwracanie macierzy 241
  
• 6.4 Rozkład LUP 242
  
• 6.5 Zastosowania rozkładu LUP 250
  
• 6.6 Mnożenie macierzy zero-jedynkowych (252)

7. Szybkie przekształcenie Fouriera z zastosowaniami (263)

• 7.1 Dyskretna transformata Fouriera i transformata odwrotna (264)
  
• 7.2 Algorytm szybkiego przekształcenia Fouriera 268
  
• 7.3 FFT z operacjami na bitach 276
  
• 7.4 Iloczyny wielomianów (281)
  
• 7.5 Mnożenie liczb całkowitych według algorytm Schonhagego-Strassena 282

8. Arytmetyka na liczbach całkowitych i wielomianach (289)

• 8.1 Podobieństwo między liczbami całkowitymi i wielomianami 290
  
• 8.2 Mnożenie i dzielenie liczb całkowitych 291
  
• 8.3 Mnożenie i dzielenie wielomianów (298)
  
• 8.4 Arytmetyka modularna 300
  
• 8.5 Arytmetyka modularna na wielomianach i wartości wielomianów .304
  
• 8.6 Chińskie zliczanie reszt (306)
  
• 8.7 Chińskie zliczanie reszt i interpolacja wielomianów (310)
  
• 8.8 Największy wspólny dzielnik i algorytm Euklidesa (312)
  
• 8.9 Asympotycznie szybki algorytm GCD dla wielomianów (315)
  
• 8.10 Największy wspólny dzielnik liczb całkowitych 320
  
• 8.11 Chińskie zliczanie reszt - raz jeszcze (322)
  
• 8.12 Wielomiany rzadkie 323

9. Algorytmy dopasowania wzorców (329)

• 9.1 Automaty skończone i wyrażenia regularne (329)
  
• 9.2 Rozpoznawanie wzorców przez wyrażenia regularne (338)
  
• 9.3 Rozpoznawanie podnapisów 341
  
• 9.4 Dwukierunkowe deterministyczne automaty ze stosem (347)
  
• 9.5 Drzewa pozycji i identyfikatory podnapisowe 358

10. Problemy NP-zupełne 375

• 10.1 Niedeterministyczne maszyny Turinga 376
  
• 10.2 Klasy P i NP (383)
  
• 10.3 Języki i problemy 385
  
• 10.4 NP-zupełność problemu spełnialności (388)
  
• 10.5 Inne problemy NP-zupełne 395
  
• 10.6 Problemy o wielomianowej złożoności pamięciowej (406)

11. Problemy niełatwe na podstawie dowodu 417

• 11.1 Hierarchie złożoności 417
  
• 11.2 Hierarchia pamięciowa dla deterministycznych maszyn Turinga 418
  
• 11.3 Problem wymagający wykładniczego czasu i pamięci 421
  
• 11.4 Problem nieelementarny 430

12. Ograniczenia dolne liczby operacji arytmetycznych (439)

• 12.1 Ciała (439)
  
• 12.2 Kod liniowy - raz jeszcze (440)
  
• 12.3 Macierzowe formułowanie problemów (443)
  
• 12.4 Ograniczenie dolne liczby mnożeń zależne od liczby wierszy 443
  
• 12.5 Ograniczenie dolne liczby mnożeń zależne od liczby kolumn 445
  
• 12.6 Ograniczenie dolne liczby mnożeń zależne od liczby wierszy i kolumn 450
  
• 12.7 Nastawianie (452)

Bibliografia (463)

Indeks 477