Spis treści
Przedmowa
I
XIII
Podstawy Wprowadzenie
3
1
Rola algorytmów w obliczeniach 5 1.1 Algorytmy 5 1.2 Algorytmy jako technologia 11
2
Zaczynamy 16 2.1 Sortowanie przez wstawianie 16 2.2 Analiza algorytmów 24 2.3 Projektowanie algorytmów 31
3
Rz˛edy wielkości funkcji 46 3.1 Notacje O, i ‚ 47 3.2 Notacja asymptotyczna: definicje formalne 50 3.3 Standardowe notacje i typowe funkcje 59
4
Metoda „dziel i zwyci˛eżaj" 71 4.1 Mnożenie macierzy kwadratowych 75 4.2 Algorytm Strassena mnożenia macierzy 79 4.3 Metoda podstawiania 84 4.4 Metoda drzewa rekursji 89 4.5 Metoda rekurencji uniwersalnej 95 4.6 Dowód ciagłej ˛ wersji twierdzenia o rekurencji uniwersalnej 4.7 Rekurencje Akry-Bazziego 108
? ? 5
?
100
Analiza probabilistyczna i algorytmy randomizowane 119 5.1 Problem zatrudnienia sekretarki 119 5.2 Zmienne losowe wskaźnikowe 122 5.3 Algorytmy randomizowane 127 5.4 Analiza probabilistyczna i dalsze zastosowania zmiennych losowych wskaźnikowych 132