Tytuł Algorytmy i struktury informacji Autorzy Lech Banachowski, Krzysztof Marian Diks, Wojciech Rytter Język polski Wydawnictwo Wydawnictwo Naukowe PWN ISBN 978-83-01-20148-7 Rok wydania 2018 Warszawa Wydanie 1 liczba stron 292 Format epub, mobi Spis treści Przedmowa do nowego wydania 9
Przedmowa do pierwszego wydania 11
1 Podstawowe zasady analizy algorytmów 15
1.1. Złożoność obliczeniowa 15
1.2. Równania rekurencyjne 22
1.3. Funkcje wytwarzające 23
1.4. Poprawność semantyczna 24
1.5. Podstawowe struktury informacji 26
1.5.1. Lista 27
1.5.2. Zbiór 29
1.5.3. Graf 30
1.5.4. Notacja funkcyjna dla atrybutów obiektów 35
1.5.5. Drzewo 35
1.6. Eliminacja rekursji 38
1.7. Koszt zamortyzowany operacji w strukturze informacji 40
1.8. Metody układania algorytmów 42
1.8.1. Metoda „dziel i zwyciężaj" 42
1.8.2. Programowanie dynamiczne 42
1.8.3. Metoda zachłanna 43
1.8.4. Inne metody 44
Zadania 44
2 Sortowanie 51
2.1. Selectionsort – sortowanie przez selekcję 52
2.2. Insertionsort – sortowanie poprzez wstawianie 53
2.3. Quicksort – sortowanie szybkie 54
2.4. Dolne ograniczenie na złożoność problemu sortowania 64
2.5. Sortowanie pozycyjne 68
2.6. Kolejki priorytetowe i algorytm heapsort 72
2.7.. Drzewa turniejowe i zadania selekcji 79
2.8. Prędkie algorytmy wyznaczania k-tego największego elementu w ciągu 84
2.9. Scalanie ciągów uporządkowanych 87
2.10. Sortowanie zewnętrzne 90
2.10.1. Scalanie wielofazowe z 4 plikami 91
2.10.2. Scalanie wielofazowe z 3 plikami 92
Zadania 96
3 Słowniki 100
3.1. Implementacja listowa nieuporządkowana 101
3.2. Implementacja listowa uporządkowana 101
3.3. Drzewa poszukiwań binarnych 106
3.3.1. Drzewa AVL 114
3.3.2. Samoorganizujące się drzewa BST 118
3.4. Miksowanie 121
3.4.1. Wybór funkcji mieszającej 122
3.4.2. Struktury informacji stosowane do rozwiązywania problemu kolizji 122
3.5. Wyszukiwanie pozycyjne 127
3.5.1. Drzewa RST 127
3.5.2. Drzewa TRIE 130
3.5.3. Drzewa PATRICIA 132
3.6. Wyszukiwanie zewnętrzne 135
3.6.1. Pliki nieuporządkowane 135
3.6.2. Pliki z funkcją mieszającą 136
3.6.3. Sekwencyjne pliki indeksowane 136
3.6.4. B-drzewo jako wielopoziomowy indeks rzadki 137
3.6.5. B-drzewo jako wielopoziomowy indeks gęsty 136
Zadania 139
4 Złożone struktury danych dla zbiorów składników 143
4.1. Problem sumowania zbiorów rozłącznych 143
4.1.1. Implementacja listowa 144
4.1.2. Implementacja drzewowa 148
4.2. Złączalne kolejki priorytetowe 155
Zadania 162
5 Algorytmy tekstowe 164
5.1. Problem wyszukiwania wzorca 165
5.1.1. Algorytm N („naiwny") 165
5.1.2. Algorytm KMP (Knutha-Morrisa-Pratta) 166
5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera 169
5.1.4. Algorytm GS′ (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców) 171
5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga) 172
5.1.6. Algorytm KR (Karpa-Rabina) 174
5.1.7. Algorytm BM (Boyera-Moore‘a) 175
5.1.8. Algorytm FP (Fishera-Patersona) 178
5.2. Drzewa sufiksowe i grafy podsłów 180
5.2.1. Niezwarta reprezentacja drzewa sufiksowego 180
5.2.2. Tworzenie drzewa sufiksowego 182
5.2.3. Tworzenie grafu podsłów 187
5.3. Inne algorytmy tekstowe 191
5.3.1. Obliczanie najdłuższego wspólnego podsłowa 192
5.3.2. Obliczanie najdłuższego wspólnego podciągu 192
5.3.3. Wyszukiwanie słów podwójnych 192
5.3.4. Wyszukiwanie słów symetrycznych 196
5.3.5. Równoważność cykliczna 196
5.3.6. Algorytm Huffmana 197
5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu 199
5.3.8. Jednoznaczne kodowanie 201
5.3.9. Liczenie liczby podsłów 202
Zadania 202
6 Algorytmy równoległe 207
6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych 209
6.2. Sortowanie równoległe 223
Zadania 226
7 Algorytmy grafowe 229
7.1. Spójne składowe 231
7.2. Dwuspójne składowe 234
7.3. Silnie spójne składowe i silna orientacja 241
7.4. Cykle Eulera 247
7.5. 5-kolorowanie grafów planarnych 250
7.6. Najkrótsze ścieżki i niepokaźne drzewo rozpinające 255
Zadania 257
8 Algorytmy geometryczne 260
8.1. Elementarne algorytmy geometryczne 261
8.2. Problem przynależności 262
8.3. Wypukła otoczka 265
8.4. Metoda zamiatania 273
8.4.1. Najmniej odległa para punktów 274
8.4.2. Pary przecinających się odcinków 277
Zadania 283
Bibliografia 285
Skorowidz 287
Przedmowa do pierwszego wydania 11
1 Podstawowe zasady analizy algorytmów 15
1.1. Złożoność obliczeniowa 15
1.2. Równania rekurencyjne 22
1.3. Funkcje wytwarzające 23
1.4. Poprawność semantyczna 24
1.5. Podstawowe struktury informacji 26
1.5.1. Lista 27
1.5.2. Zbiór 29
1.5.3. Graf 30
1.5.4. Notacja funkcyjna dla atrybutów obiektów 35
1.5.5. Drzewo 35
1.6. Eliminacja rekursji 38
1.7. Koszt zamortyzowany operacji w strukturze informacji 40
1.8. Metody układania algorytmów 42
1.8.1. Metoda „dziel i zwyciężaj" 42
1.8.2. Programowanie dynamiczne 42
1.8.3. Metoda zachłanna 43
1.8.4. Inne metody 44
Zadania 44
2 Sortowanie 51
2.1. Selectionsort – sortowanie przez selekcję 52
2.2. Insertionsort – sortowanie poprzez wstawianie 53
2.3. Quicksort – sortowanie szybkie 54
2.4. Dolne ograniczenie na złożoność problemu sortowania 64
2.5. Sortowanie pozycyjne 68
2.6. Kolejki priorytetowe i algorytm heapsort 72
2.7.. Drzewa turniejowe i zadania selekcji 79
2.8. Prędkie algorytmy wyznaczania k-tego największego elementu w ciągu 84
2.9. Scalanie ciągów uporządkowanych 87
2.10. Sortowanie zewnętrzne 90
2.10.1. Scalanie wielofazowe z 4 plikami 91
2.10.2. Scalanie wielofazowe z 3 plikami 92
Zadania 96
3 Słowniki 100
3.1. Implementacja listowa nieuporządkowana 101
3.2. Implementacja listowa uporządkowana 101
3.3. Drzewa poszukiwań binarnych 106
3.3.1. Drzewa AVL 114
3.3.2. Samoorganizujące się drzewa BST 118
3.4. Miksowanie 121
3.4.1. Wybór funkcji mieszającej 122
3.4.2. Struktury informacji stosowane do rozwiązywania problemu kolizji 122
3.5. Wyszukiwanie pozycyjne 127
3.5.1. Drzewa RST 127
3.5.2. Drzewa TRIE 130
3.5.3. Drzewa PATRICIA 132
3.6. Wyszukiwanie zewnętrzne 135
3.6.1. Pliki nieuporządkowane 135
3.6.2. Pliki z funkcją mieszającą 136
3.6.3. Sekwencyjne pliki indeksowane 136
3.6.4. B-drzewo jako wielopoziomowy indeks rzadki 137
3.6.5. B-drzewo jako wielopoziomowy indeks gęsty 136
Zadania 139
4 Złożone struktury danych dla zbiorów składników 143
4.1. Problem sumowania zbiorów rozłącznych 143
4.1.1. Implementacja listowa 144
4.1.2. Implementacja drzewowa 148
4.2. Złączalne kolejki priorytetowe 155
Zadania 162
5 Algorytmy tekstowe 164
5.1. Problem wyszukiwania wzorca 165
5.1.1. Algorytm N („naiwny") 165
5.1.2. Algorytm KMP (Knutha-Morrisa-Pratta) 166
5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera 169
5.1.4. Algorytm GS′ (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców) 171
5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga) 172
5.1.6. Algorytm KR (Karpa-Rabina) 174
5.1.7. Algorytm BM (Boyera-Moore‘a) 175
5.1.8. Algorytm FP (Fishera-Patersona) 178
5.2. Drzewa sufiksowe i grafy podsłów 180
5.2.1. Niezwarta reprezentacja drzewa sufiksowego 180
5.2.2. Tworzenie drzewa sufiksowego 182
5.2.3. Tworzenie grafu podsłów 187
5.3. Inne algorytmy tekstowe 191
5.3.1. Obliczanie najdłuższego wspólnego podsłowa 192
5.3.2. Obliczanie najdłuższego wspólnego podciągu 192
5.3.3. Wyszukiwanie słów podwójnych 192
5.3.4. Wyszukiwanie słów symetrycznych 196
5.3.5. Równoważność cykliczna 196
5.3.6. Algorytm Huffmana 197
5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu 199
5.3.8. Jednoznaczne kodowanie 201
5.3.9. Liczenie liczby podsłów 202
Zadania 202
6 Algorytmy równoległe 207
6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych 209
6.2. Sortowanie równoległe 223
Zadania 226
7 Algorytmy grafowe 229
7.1. Spójne składowe 231
7.2. Dwuspójne składowe 234
7.3. Silnie spójne składowe i silna orientacja 241
7.4. Cykle Eulera 247
7.5. 5-kolorowanie grafów planarnych 250
7.6. Najkrótsze ścieżki i niepokaźne drzewo rozpinające 255
Zadania 257
8 Algorytmy geometryczne 260
8.1. Elementarne algorytmy geometryczne 261
8.2. Problem przynależności 262
8.3. Wypukła otoczka 265
8.4. Metoda zamiatania 273
8.4.1. Najmniej odległa para punktów 274
8.4.2. Pary przecinających się odcinków 277
Zadania 283
Bibliografia 285
Skorowidz 287
