Spis treści

Podstawy algorytmów z przykładami w C++ -- spis treści

O Autorach (9)

Przedmowa (11)

Rozdział 1. Algorytmy - wydajność, analiza i rząd (17)

• 1.1. Algorytmy (18)
  
• 1.2. Znaczenie opracowywania wydajnych algorytmów (25)
  
  • 1.2.1. Wyszukiwanie sekwencyjne a wyszukiwanie binarne (26)
  • 1.2.2. Ciąg Fibonacciego (28)
• 1.3. Analiza algorytmów (33)
  
  • 1.3.1. Analiza złożoności (33)
  • 1.3.2. Zastosowanie teorii (41)
  • 1.3.3. Analiza poprawności (42)
• 1.4. Rząd (42)
  
  • 1.4.1. Intuicyjne wprowadzenie do problematyki rzędu (43)
  • 1.4.2. Formalne wprowadzenie do problematyki rzędu (45)
  • 1.4.3. Wykorzystanie granic do określenia rzędu (56)
• 1.5. Zarys dalszej treści książki (59)
  
• Ćwiczenia (60)

Rozdział 2. Dziel i zwyciężaj (65)

• 2.1. Wyszukiwanie binarne (66)
  
• 2.2. Sortowanie przez scalanie (71)
  
• 2.3. Podejście typu dziel i zwyciężaj (77)
  
• 2.4. Sortowanie szybkie (sortowanie przez podstawienie podziałów) (78)
  
• 2.5. Algorytm Strassena mnożenia macierzy (85)
  
• 2.6. Arytmetyka wielkich liczb całkowitych (90)
  
  • 2.6.1. Reprezentacja wielkich liczb całkowitych: dodawanie i inne operacje wykonywane w czasie liniowym (91)
  • 2.6.2. Mnożenie wielkich liczb całkowitych (91)
• 2.7. Określanie wartości progowych (97)
  
• 2.8. Przeciwwskazania do używania podejścia dziel i zwyciężaj (101)
  
• Ćwiczenia (103)

Rozdział 3. Programowanie dynamiczne (111)

• 3.1. Współczynnik dwumianowy (112)
  
• 3.2. Algorytm Floyda określania najkrótszej drogi w grafie (117)
  
• 3.3. Programowanie dynamiczne a problemy optymalizacyjne (125)
  
• 3.4. Łańcuchowe mnożenie macierzy (127)
  
• 3.5. Optymalne drzewa wyszukiwania binarnego (136)
  
• 3.6. Problem komiwojażera (145)
  
• Ćwiczenia (152)

Rozdział 4. Podejście zachłanne (157)

• 4.1. Minimalne drzewo rozpinające (161)
  
  • 4.1.1. Algorytm Prima (163)
  • 4.1.2. Algorytm Kruskala (169)
  • 4.1.3. Porównanie algorytmu Prima z algorytmem Kruskala (173)
  • 4.1.4. Dyskusja końcowa (173)
• 4.2. Algorytm Dijkstry najkrótszych dróg z jednego źródła (174)
  
• 4.3. Szeregowanie (177)
  
  • 4.3.1. Minimalizacja całkowitego czasu w systemie (178)
  • 4.3.2. Szeregowanie z terminami granicznymi (180)
• 4.4. Kod Huffmana (188)
  
  • 4.4.1. Kody prefiksowe (189)
  • 4.4.2. Algorytm Huffmana (190)
• 4.5. Podejście zachłanne a programowanie dynamiczne: problem plecakowy (194)
  
  • 4.5.1. Podejście zachłanne do problemu plecakowego 0-1 (195)
  • 4.5.2. Podejście zachłanne do ułamkowego problemu plecakowego (196)
  • 4.5.3. Podejście programowania dynamicznego do problemu plecakowego 0-1 (197)
  • 4.5.4. Poprawiona wersja algorytmu programowania dynamicznego dla problemu plecakowego 0-1 (197)
• Ćwiczenia (201)

Rozdział 5. Algorytmy z powrotami (207)

• 5.1. Techniki algorytmów z powrotami (208)
  
• 5.2. Problem n-królowych (215)
  
• 5.3. Zastosowanie algorytmu Monte Carlo do oszacowania wydajności algorytmu z powrotami (219)
  
• 5.4. Problem sumy podzbiorów (223)
  
• 5.5. Kolorowanie grafu (228)
  
• 5.6. Problem cyklu Hamiltona (232)
  
• 5.7. Problem plecakowy 0-1 (235)
  
  • 5.7.1. Algorytm z powrotami dla problemu plecakowego 0-1 (235)
  • 5.7.2. Porównanie algorytmu programowania dynamicznego z algorytmem z powrotami do rozwiązywania problemu plecakowego 0-1 (244)
• Ćwiczenia (245)

Rozdział 6. Metoda podziału i ograniczeń (251)

• 6.1. Ilustracja metody podziału i ograniczeń dla problemu plecakowego 0-1 (253)
  
  • 6.1.1. Przeszukiwanie wszerz z przycinaniem metodą podziału i ograniczeń (253)
  • 6.1.2. Przeszukiwanie typu najpierw najlepszy z przycinaniem metodą podziału i ograniczeń (258)
• 6.2. Problem komiwojażera (264)
  
• 6.3. Wnioskowanie abdukcyjne (diagnozowanie) (272)
  
• Ćwiczenia (281)

Rozdział 7. Wprowadzenie do złożoności obliczeniowej: problem sortowania (285)

• 7.1. Złożoność obliczeniowa (286)
  
• 7.2. Sortowanie przez wstawianie i sortowanie przez wybieranie (288)
  
• 7.3. Dolne ograniczenia dla algorytmów usuwających co najwyżej jedną inwersję dla jednej operacji porównania (294)
  
• 7.4. Przypomnienie algorytmu sortowania przez scalanie (297)
  
• 7.5. Przypomnienie algorytmu szybkiego sortowania (303)
  
• 7.6. Sortowanie stogowe (305)
  
  • 7.6.1. Stogi i podstawowe na nich operacje (305)
  • 7.6.2. Implementacja algorytmu sortowania stogowego (309)
• 7.7. Zestawienie algorytmów sortowania przez scalanie, sortowania szybkiego i sortowania stogowego (316)
  
• 7.8. Dolne ograniczenia dla algorytmów sortujących wyłącznie na podstawie operacji porównania kluczy (317)
  
  • 7.8.1. Drzewa decyzyjne dla algorytmów sortujących (317)
  • 7.8.2. Dolne ograniczenia dla najgorszego przypadku (320)
  • 7.8.3. Dolne ograniczenia dla średniego przypadku (323)
• 7.9. Sortowanie przez podział (sortowanie pozycyjne) (328)
  
• Ćwiczenia (332)

Rozdział 8. Więcej o złożoności obliczeniowej: problem przeszukiwania (339)

• 8.1. Dolne ograniczenia dla przeszukiwania wyłącznie na podstawie porównywania wartości kluczy (340)
  
  • 8.1.1. Dolne ograniczenia dla najgorszego przypadku (343)
  • 8.1.2. Dolne ograniczenia dla średniego przypadku (345)
• 8.2. Przeszukiwanie przez interpolację (351)
  
• 8.3. Przeszukiwanie w drzewach (354)
  
  • 8.3.1. Drzewa wyszukiwania binarnego (355)
  • 8.3.2. B-drzewa (360)
• 8.4. Mieszanie (361)
  
• 8.5. Problem wyboru: wprowadzenie metody dyskusji z adwersarzem (367)
  
  • 8.5.1. Znajdowanie największego klucza (367)
  • 8.5.2. Znajdowanie zarówno najmniejszego, jak i największego klucza (369)
  • 8.5.3. Znajdowanie drugiego największego klucza (376)
  • 8.5.4. Znajdowanie k-tego najmniejszego klucza (381)
  • 8.5.5. Algorytm probabilistyczny dla problemu wyboru (390)
• Ćwiczenia (395)

Rozdział 9. Złożoność obliczeniowa i trudność problemów: wprowadzenie do teorii o zbiorze NP (401)

• 9.1. Trudność (402)
  
• 9.2. Ponowne omówienie zagadnienia rozmiaru danych wejściowych (404)
  
• 9.3. Trzy główne kategorie problemów (409)
  
  • 9.3.1. Problemy, dla których wynaleziono algorytmy wielomianowe (409)
  • 9.3.2. Problemy, których trudność została udowodniona (410)
  • 9.3.3. Problemy, których trudność nie została udowodniona, jednak nie udało się znaleźć rozwiązujących je algorytmów wielomianowych (411)
• 9.4. Teoria o zbiorze NP (411)
  
  • 9.4.1. Zbiory P i NP (414)
  • 9.4.2. Problemy NP-zupełne (419)
  • 9.4.3. Problemy NP-trudne, NP-łatwe i NP-równoważne (431)
• 9.5. Sposoby rozwiązywania problemów NP-trudnych (435)
  
  • 9.5.1. Algorytm przybliżony dla problemu komiwojażera (436)
  • 9.5.2. Przybliżony algorytm dla problemu pakowania (441)
• Ćwiczenia (446)

Rozdział 10. Algorytmy teorii liczb (449)

• 10.1. Przegląd teorii liczb (450)
  
  • 10.1.1. Liczby złożone i liczby pierwsze (450)
  • 10.1.2. Największy wspólny dzielnik (451)
  • 10.1.3. Rozkładanie liczb całkowitych na czynniki pierwsze (455)
  • 10.1.4. Najmniejsza wspólna wielokrotność (457)
• 10.2. Wyznaczanie największego wspólnego dzielnika (457)
  
  • 10.2.1. Algorytm Euklidesa (458)
  • 10.2.2. Rozszerzenie algorytmu Euklidesa (462)
• 10.3. Przegląd arytmetyki modularnej (465)
  
  • 10.3.1. Teoria grup (465)
  • 10.3.2. Kongruencja modulo n (467)
  • 10.3.3. Podgrupy (473)
• (10.4. Rozwiązywanie modularnych równań liniowych 479)
  
• (10.5. Obliczanie modularnych potęg 485)
  
• 10.6. Znajdowanie wielkich liczb pierwszych (488)
  
  • 10.6.1. Szukanie liczby pierwszej (488)
  • (10.6.2. Sprawdzanie, czy dana liczba całkowita jest liczbą pierwszą 489)
• 10.7. System szyfrowania RSA z publicznym kluczem (508)
  
  • 10.7.1. Systemy szyfrowania z kluczem publicznym (508)
  • 10.7.2. System szyfrowania RSA (509)
• Ćwiczenia (512)

Rozdział 11. Wprowadzenie do algorytmów równoległych (517)

• 11.1. Architektury równoległe (521)
  
  • 11.1.1. Mechanizm sterowania (521)
  • 11.1.2. Organizacja przestrzeni adresowej (522)
  • 11.1.3. Sieci łączące (524)
• 11.2. Model PRAM (527)
  
  • 11.2.1. Projektowanie algorytmów dla modelu CREW PRAM (531)
  • 11.2.2. Projektowanie algorytmów dla modelu CRCW PRAM (538)
• Ćwiczenia (541)

Dodatek A Przegląd niezbędnej wiedzy matematycznej (543)

• A.1. Notacja (543)
  
• A.2. Funkcje (545)
  
• A.3. Indukcja matematyczna (546)
  
• A.4. Twierdzenia i lematy (553)
  
• A.5. Logarytmy (554)
  
  • A.5.1. Definicja i właściwości logarytmów (554)
  • A.5.2. Logarytm naturalny (557)
• A.6. Zbiory (559)
  
• A.7. Permutacje i kombinacje (560)
  
• A.8. Prawdopodobieństwo (563)
  
  • A.8.1. Losowość (569)
  • A.8.2. Wartość oczekiwana (573)
• Ćwiczenia (575)

Dodatek B Rozwiązywanie równań rekurencyjnych na potrzeby analizy algorytmów rekurencyjnych (581)

• B.1. Rozwiązywanie rekurencji za pomocą indukcji (581)
  
• B.2. Rozwiązywanie rekurencji z zastosowaniem równań charakterystycznych (585)
  
  • B.2.1. Homogeniczna rekurencja liniowa (585)
  • B.2.2. Niehomogeniczna rekurencja liniowa (594)
  • B.2.3. Zamiana zmiennej (przekształcenie dziedziny) (600)
• B.3. Rozwiązywanie rekurencji przez podstawianie (603)
  
• B.4. Rozszerzanie wyników dla n będącego potęgą dodatniej stałej b do wyników dla dowolnego n (605)
  
• B.5. Dowody twierdzeń (611)
  
• Ćwiczenia (614)

Dodatek C Struktury danych dla zbiorów rozłącznych (621)

Dodatek D Bibliografia (631)

Skorowidz (637)