"Algorytmy i struktury danych"

Spis treści

Przedmowa do nowego wydania 10

Przedmowa do pierwszego wydania 12

1 Podstawowe zasady analizy algorytmów 16

1.1. Złożoność obliczeniowa 16

1.2. Równania rekurencyjne 23

1.3. Funkcje tworzące 24

1.4. Poprawność semantyczna 25

1.5. Podstawowe struktury danych 27

1.5.1. Lista 28

1.5.2. Zbiór 30

1.5.3. Graf 31

1.5.4. Notacja funkcyjna dla atrybutów obiektów 36

1.5.5. Drzewo 36

1.6. Eliminacja rekursji 39

1.7. Koszt zamortyzowany operacji w strukturze danych 41

1.8. Metody układania algorytmów 43

1.8.1. Metoda „dziel i zwyciężaj” 43

1.8.2. Programowanie dynamiczne 43

1.8.3. Metoda zachłanna 44

Zadania 45

1.8.4. Inne metody 45

2 Sortowanie 52

2.1. Selectionsort – sortowanie przez selekcję 53

2.2. Insertionsort – sortowanie przez wstawianie 54

2.3. Quicksort – sortowanie szybkie 55

2.4. Dolne ograniczenie na złożoność problemu sortowania 65

2.5. Sortowanie pozycyjne 69

2.6. Kolejki priorytetowe i algorytm heapsort 73

2.7.. Drzewa turniejowe i zadania selekcji 80

2.8. Szybkie algorytmy wyznaczania k-tego największego elementu w ciągu 85

2.9. Scalanie ciągów uporządkowanych 88

2.10. Sortowanie zewnętrzne 91

2.10.1. Scalanie wielofazowe z 4 plikami 92

2.10.2. Scalanie wielofazowe z 3 plikami 93

Zadania 97

3 Słowniki 101

3.1. Implementacja listowa nieuporządkowana 102

3.2. Implementacja listowa uporządkowana 102

3.3. Drzewa poszukiwań binarnych 107

3.3.1. Drzewa AVL 115

3.3.2. Samoorganizujące się drzewa BST 119

3.4. Mieszanie 122

3.4.1. Wybór funkcji mieszającej 123

3.4.2. Struktury danych stosowane do rozwiązywania problemu kolizji 123

3.5. Wyszukiwanie pozycyjne 128

3.5.1. Drzewa RST 128

3.5.2. Drzewa TRIE 131

3.5.3. Drzewa PATRICIA 133

3.6. Wyszukiwanie zewnętrzne 136

3.6.1. Pliki nieuporządkowane 136

3.6.2. Pliki z funkcją mieszającą 137

3.6.3. Sekwencyjne pliki indeksowane 137

3.6.5. B-drzewo jako wielopoziomowy indeks gęsty 137

3.6.4. B-drzewo jako wielopoziomowy indeks rzadki 138

Zadania 140

4 Złożone struktury danych dla zbiorów elementów 144

4.1. Problem sumowania zbiorów rozłącznych 144

4.1.1. Implementacja listowa 145

4.1.2. Implementacja drzewowa 149

4.2. Złączalne kolejki priorytetowe 156

Zadania 163

5 Algorytmy tekstowe 165

5.1. Problem wyszukiwania wzorca 166

5.1.1. Algorytm N („naiwny”) 166

5.1.2. Algorytm KMP (Knutha-Morrisa-Pratta) 167

5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera 170

5.1.4. Algorytm GS′ (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców) 172

5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga) 173

5.1.6. Algorytm KR (Karpa-Rabina) 175

5.1.7. Algorytm BM (Boyera-Moore‘a) 176

5.1.8. Algorytm FP (Fishera-Patersona) 179

5.2. Drzewa sufiksowe i grafy podsłów 181

5.2.1. Niezwarta reprezentacja drzewa sufiksowego 181

5.2.2. Tworzenie drzewa sufiksowego 183

5.2.3. Tworzenie grafu podsłów 188

5.3. Inne algorytmy tekstowe 192

5.3.1. Obliczanie najdłuższego wspólnego podsłowa 193

5.3.2. Obliczanie najdłuższego wspólnego podciągu 193

5.3.3. Wyszukiwanie słów podwójnych 193

5.3.4. Wyszukiwanie słów symetrycznych 197

5.3.5. Równoważność cykliczna 197

5.3.6. Algorytm Huffmana 198

5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu 200

5.3.8. Jednoznaczne kodowanie 202

Zadania 203

5.3.9. Liczenie liczby podsłów 203

6 Algorytmy równoległe 208

6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych 210

6.2. Sortowanie równoległe 224

Zadania 227

7 Algorytmy grafowe 230

7.1. Spójne składowe 232

7.2. Dwuspójne składowe 235

7.3. Silnie spójne składowe i silna orientacja 242

7.4. Cykle Eulera 248

7.5. 5-kolorowanie grafów planarnych 251

7.6. Najkrótsze ścieżki i minimalne drzewo rozpinające 256

Zadania 258

8 Algorytmy geometryczne 261

8.1. Elementarne algorytmy geometryczne 262

8.2. Problem przynależności 263

8.3. Wypukła otoczka 266

8.4. Metoda zamiatania 274

8.4.1. Najmniej odległa para punktów 275

8.4.2. Pary przecinających się odcinków 278

Zadania 284

Bibliografia 286

Skorowidz 288