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.

 

Osoby które kupowały "Projektowanie i analiza algorytmów", wybierały także:

• Distributed Tracing in Practice. Instrumenting, Analyzing, and Debugging Microservices 249,17 zÅ‚, (29,90 zÅ‚ -88%)
• The Software Architect Elevator. Redefining the Architect's Role in the Digital Enterprise 213,57 zÅ‚, (29,90 zÅ‚ -86%)
• Software Engineering at Google. Lessons Learned from Programming Over Time 213,57 zÅ‚, (29,90 zÅ‚ -86%)
• Jenkins 2: Up and Running. Evolve Your Deployment Pipeline for Next Generation Automation 213,57 zÅ‚, (29,90 zÅ‚ -86%)
• Istio: Up and Running. Using a Service Mesh to Connect, Secure, Control, and Observe 186,88 zÅ‚, (29,90 zÅ‚ -84%)

• 
• 
• 
• 
• 

Spis treści

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