Algorytmy i struktury danych

Jądrem informatyki jest algorytmika, a najważniejszym elementem procesu tworzenia dobrego programu komputerowego jest właściwy dobór algorytmów i struktur danych – szczególnie pod kątem ich wydajności. Algorytmy i struktury danych są tematem jednego z podstawowych przedmiotów wykładanych na każdych studiach informatycznych. Książka została sprawdzona dydaktyczne na zajęciach prowadzonych ze studentami informatyki Uniwersytetu Warszawskiego, jak też wielu innych uczelni informatycznych w kraju. Informacja o autorze/ redaktorze: Autorzy są informatykami o uznanym w świecie dorobku naukowym, edukacyjnym i popularyzatorskim. W latach osiemdziesiątych XX wieku tworzyli podwaliny algorytmiki w Uniwersytecie Warszawskim. Mają na swoim koncie wiele znakomitych prac algorytmicznych opublikowanych w najlepszych wydawnictwach naukowych poświęconych informatyce teoretycznej.

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 tworzące 23 1.4. Poprawność semantyczna 24 1.5. Podstawowe struktury danych 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 danych 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 przez 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. Szybkie 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. Mieszanie 121 3.4.1. Wybór funkcji mieszającej 122 3.4.2. Struktury danych 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 elementó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 minimalne 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