Projektowanie i analiza algorytmów
Autorzy: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
Data wydania: 2003
Stron: 488
Tłumaczenie: Wojciech Derechowski
ISBN: 83-7197-770-0
Format: B5
Oprawa: twarda
Stan: bardzo dobry jak nowa

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.

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