POLECAMY
Koszyk
Algorytmy i struktury danych
Wydawca:
Format:
epub, mobi, ibuk
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.
| Rok wydania | 2018 |
|---|---|
| Liczba stron | 292 |
| Kategoria | Bazy danych |
| Wydawca | Wydawnictwo Naukowe PWN |
| ISBN-13 | 978-83-01-20148-7 |
| Numer wydania | 1 |
| Język publikacji | polski |
| Informacja o sprzedawcy | ePWN sp. z o.o. |
Ciekawe propozycje
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.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 |
KUP NA PREZENT
Algorytmy i struktury danych
35,40 zł
Uzupełnij informacje na temat odbiorcy.
Produkt został pomyślnie dodany do koszyka.
Nieudana próba zakupu produktu. Spróbuj jeszcze raz.
Wypożyczaj w abonamencie!
Już od 2,66 zł za ebooka
