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.

Pomimo, że pierwsze wydanie tej książki ukazało się w roku 1996, to nie straciła ona nic ze swoich walorów i nadal jest doskonałym wprowadzeniem w tę problematykę. Zawiera przegląd głównych zagadnień algorytmicznych. Korzystając z niej, Czytelnik pozna metody tworzenia i analizy algorytmów i struktur danych. Dzięki nim nie tylko będzie rozumiał zasady działania algorytmów zaimplementowanych w dostępnych bibliotekach algorytmów i struktur danych, ale także będzie samemu potrafił projektować wydajne algorytmy dla problemów pojawiających się w praktyce programistycznej.

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.

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.

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 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.1. 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 / 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 / 172
5.1.6. Algorytm KR / 174
5.1.7. Algorytm BM / 175
5.1.8. Algorytm FP / 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

Informacje o bezpieczeństwie produktu Informacje o producencie