|
Przedmowa
Część I Podstawy
Wprowadzenie
1. Rola algorytmów w obliczeniach
1.1. Algorytmy
1.2. Algorytmy jako technologia
2. Zaczynamy
2.1. Sortowanie przez wstawianie
2.2. Analiza algorytmów
2.3. Projektowanie algorytmów
2.3.1. Metoda „dziel i zwyciężaj"
2.3.2. Analiza algorytmów typu „dziel i zwyciężaj"
3. Rzędy wielkości funkcji
3.1. Notacja asymptotyczna
3.2. Standardowe notacje i typowe funkcje
4. Rekurencje
4.1. Metoda podstawiania
4.2. Metoda drzewa rekursji
4.3. Metoda rekurencji uniwersalnej
4.4. Dowód twierdzenia o rekurencji uniwersalnej
4.4.l. Dowód dla dokładnych potęg
4.4.2. Podłogi i sufity
5. Analiza probabilistyczna i algorytmy randomizowane
5.1. Problem zatrudnienia sekretarki
5.2. Zmienne losowe wskaźnikowe
5.3. Algorytmy randomizowane
5.4. Analiza probabilistyczna i dalsze zastosowania zmiennych losowych wskaźnikowych
5.4.1. Paradoks dnia urodzin
5.4.2. Kule i urny
5.4.3. Ciągi „dobrej passy", czyli sukcesów
5.4.4. Problem on-line zatrudnienia sekretarki
Część II Sortowanie i statystyki pozycyjne
Wprowadzenie
6. Heapsort - sortowanie przez kopcowanie
6.1. Kopce
6.2. Przywracanie własności kopca
6.3. Budowanie kopca
6.4. Algorytm sortowania przez kopcowanie (heapsort)
6.5. Kolejki priorytetowe
7. Quicksort - sortowanie szybkie
7.1. Opis algorytmu
7.2. Czas działania algorytmu quicksort
7.3. Randomizowana wersja algorytmu quicksort
7.4. Analiza algorytmu quicksort
7.4.1. Analiza przypadku pesymistycznego
7.4.2. Analiza przypadku średniego
8. Sortowanie w czasie liniowym
8.1. Dolne ograniczenia dla problemu sortowania
8.2. Sortowanie przez zliczanie
8.3. Sortowanie pozycyjne
8.4. Sortowanie kubełkowe
9. Mediany i statystyki pozycyjne
9.1. Minimum i maksimum
9.2. Wybór w oczekiwanym czasie liniowym
9.3. Wybór w pesymistycznym czasie liniowym
Część III Struktury danych
Wprowadzenie
10. Elementarne struktury danych
10.1. Stosy i kolejki
10.2. Listy
10.3. Reprezentowanie struktur wskaźnikowych za pomocą tablic
10.4. Reprezentowanie drzew (ukorzenionych)
11. Tablice z haszowaniem
11.1. Tablice z adresowaniem bezpośrednim
11.2. Tablice z haszowaniem
11.3. Funkcje haszujące
11.3.1. Haszowanie modularne
11.3.2. Haszowanie przez mnożenie
11.3.3. Haszowanie uniwersalne
11.4. Adresowanie otwarte
11.5. Haszowanie doskonałe
12. Drzewa wyszukiwań binarnych
12.1. Co to jest drzewo wyszukiwań binarnych?
12.2. Wyszukiwanie w drzewie wyszukiwań binarnych
12.3. Wstawianie i usuwanie
12.4. Losowo skonstruowane drzewa wyszukiwań binarnych
13. Drzewa czerwono-czarne
13.1. Własności drzew czerwono-czarnych
13.2. Operacje rotacji
13.3. Operacja wstawiania
13.4. Operacja usuwania
14. Wzbogacanie struktur danych
14.1. Dynamiczne statystyki pozycyjne
14.2. Jak wzbogacać strukturę danych
14.3. Drzewa przedziałowe
Część IV Zaawansowane metody konstruowania i analizowania algorytmów
Wprowadzenie
15. Programowanie dynamiczne
15.1. Planowanie czynności na liniach montażowych
15.2. Mnożenie ciągu macierzy
15.3. Podstawy programowania dynamicznego
15.4. Najdłuższy wspólny podciąg
15.5. Optymalne drzewa wyszukiwań binarnych
16. Algorytmy zachłanne
16.1. Problem wyboru zajęć
16.2. Podstawy strategii zachłannej
16.3. Kody Huffmana
16.4. Teoretyczne podstawy strategii zachłannych
16.5. Problem szeregowania zadań
17. Analiza kosztu zamortyzowanego
17.1. Metoda kosztu sumarycznego
17.2. Metoda księgowania
17.3. Metoda potencjału
17.4. Tablice dynamiczne
17.4.1. Powiększanie tablicy
17.4.2. Powiększanie i zmniejszanie tablicy
Część V Złożone struktury danych
Wprowadzenie
18. B-drzewa
18.1. Definicja B-drzewa
18.2. Podstawowe operacje na B-drzewach
18.3. Usuwanie klucza z B-drzewa
19. Kopce dwumianowe
19.1. Drzewa i kopce dwumianowe
19.1.1. Drzewa dwumianowe
19.1.2. Kopce dwumianowe
19.2. Operacje na kopcach dwumianowych
20. Kopce Fibonacciego
20.1. Struktura kopców Fibonacciego
20.2. Operacje kopca złączalnego
20.3. Zmniejszanie wartości klucza i usuwanie węzła
20.4. Oszacowanie maksymalnego stopnia
21. Struktury danych dla zbiorów rozłącznych
21.1. Operacje na zbiorach rozłącznych
21.2. Listowa reprezentacja zbiorów rozłącznych
21.3. Lasy zbiorów rozłącznych
21.4. Analiza metody łączenia według rangi z kompresją ścieżki
Część VI Algorytmy grafowe
Wprowadzenie
22. Podstawowe algorytmy grafowe
22.1. Reprezentacja grafów
22.2. Przeszukiwanie wszerz
22.3. Przeszukiwanie w głąb
22.4. Sortowanie topologiczne
22.5. Silnie spójne składowe
23. Minimalne drzewa rozpinające
23.1. Rozrastanie się minimalnego drzewa rozpinającego
23.2. Algorytmy Kruskala i Prima
24. Najkrótsze ścieżki z jednym źródłem
24.1. Algorytm Bellmana-Forda
24.2. Najkrótsze ścieżki z jednym źródłem w acyklicznych grafach skierowanych
24.3. Algorytm Dijkstry
24.4. Ograniczenia różnicowe i najkrótsze ścieżki
24.5. Dowody własności najkrótszych ścieżek
25. Najkrótsze ścieżki między wszystkimi parami wierzchołków
25.1. Najkrótsze ścieżki i mnożenie macierzy
25.2. Algorytm Floyda-Warshalla
25.3. Algorytm Johnsona dla grafów rzadkich
26. Maksymalny przepływ
26.l. Sieci przepływowe
26.2. Metoda Forda-Fulkersona
26.3. Najliczniejsze skojarzenia w grafach dwudzielnych
26.4. Algorytmy typu „prześlij-przemianuj"
26.5. Algorytm „przemianuj i przesuń na początek"
Część VII Wybrane zagadnienia
Wprowadzenie
27. Sieci sortujące
27.1. Sieci porównujące
27.2. Zasada zero-jedynkowa
27.3. Bitoniczna sieć sortująca
27.4. Sieć scalająca
27.5. Sieć sortująca
28. Operacje na macierzach
28.1. Własności macierzy
28.2. Algorytm Strassena mnożenia macierzy
28.3. Rozwiązywanie układów równań liniowych
28.4. Odwracanie macierzy
28.5. Symetryczne macierze dodatnio określone i metoda najmniejszych kwadratów
29. Programowanie liniowe
29.1. Postać standardowa i uzupełnieniowa
29.2. Formułowanie problemów w postaci programów liniowych
29.3. Algorytm sympleks
29.4. Dualność
29.5. Początkowe bazowe rozwiązanie dopuszczalne
30. Wielomiany i FFT
30.1. Reprezentacja wielomianów
30.2. DFT i FFT
30.3. Efektywne implementacje FFT
31. Algorytmy teorioliczbowe
31.1. Podstawowe pojęcia teorii liczb
31.2. Największy wspólny dzielnik
31.3. Arytmetyka modularna
31.4. Rozwiązywanie modularnych równań liniowych
31.5. Chińskie twierdzenie o resztach
31.6. Potęgi elementu
31.7. System kryptograficzny z kluczem publicznym RSA
31.8. Sprawdzanie, czy dana liczba jest pierwsza
31.9. Rozkład na czynniki
32. Wyszukiwanie wzorca
32.1. Algorytm „naiwny" wyszukiwania wzorca
32.2. Algorytm Rabina-Karpa
32.3. Wyszukiwanie wzorca z wykorzystaniem automatów skończonych
32.4. Algorytm Knutha-Morrisa-Pratta
33. Geometria obliczeniowa
33.1. Własności odcinków
33.2. Sprawdzanie, czy jakakolwiek para odcinków się przecina
33.3. Znajdowanie otoczki wypukłej
33.4. Znajdowanie pary najmniej odległych punktów
34. NP-zupełność
34.1. Czas wielomianowy
34.2. Weryfikacja w czasie wielomianowym
34.3. NP-zupełność i redukowalność
34.4. Dowodzenie NP-zupełności
34.5. Problemy NP-zupełne
34.5.1. Problem kliki
34.5.2. Problem pokrycia wierzchołkowego
34.5.3. Problem cyklu Hamiltona
34.5.4. Problem komiwojażera
34.5.5. Problem sumy podzbioru
35. Algorytmy aproksymacyjne
35.1. Problem pokrycia wierzchołkowego
35.2. Problem komiwojażera
35.2.1. Problem komiwojażera z nierównością trójkąta
35.2.2. Ogólny problem komiwojażera
35.3. Problem pokrycia zbioru
35.4. Randomizacja i programowanie liniowe
35.5. Problem sumy podzbioru
Część VIII Dodatek: Podstawy matematyczne
Wprowadzenie
A. Sumy
A.1 Wzory i własności dotyczące sum
A.2. Szacowanie sum
B. Zbiory i nie tylko
B.1. Zbiory
B.2. Relacje
B.3. Funkcje
B.4. Grafy
B.5. Drzewa
B.5.1. Drzewa wolne
B.5.2. Drzewa ukorzenione i uporządkowane
B.5.3. Drzewa binarne i pozycyjne
C. Zliczanie i prawdopodobieństwo
C.l. Zliczanie
C.2. Prawdopodobieństwo
C.3. Dyskretne zmienne losowe
C.4. Rozkłady: geometryczny i dwumianowy
C.5. Krańce rozkładu dwumianowego
Literatura
Skorowidz
|
Spis treści
Serie wydawnicze
