Spis Treści
|
|---|
| 1. Podstawowe zasady analizy algorytmów |
| 1.1. Złożoność obliczeniowa |
| 1.2. Równania rekurencyjne |
| 1.3. Funkcje tworzące |
| 1.4. Poprawność semantyczna |
| 1.5. Podstawowe struktury danych |
| 1.5.1. Lista |
| 1.5.2. Zbiór |
| 1.5.3. Graf |
| 1.5.4. Notacja funkcyjna dla atrybutów obiektów |
| 1.5.5. Drzewo |
| 1.6. Eliminacja rekursji |
| 1.7. Koszt zamortyzowany operacji w strukturze danych |
| 1.8. Metody układania algorytmów |
| 1.8.1. Metoda „dziel i zwyciężaj" |
| 1.8.2. Programowanie dynamiczne |
| 1.8.3. Metoda zachłanna |
| 1.8.4. Inne metody |
| Zadania |
|
|
| 2. Sortowanie |
| 2.1. Selectionsort - sortowanie przez selekcję |
| 2.2. Insertionsort - sortowanie przez wstawianie |
| 2.3. Quicksort - sortowanie szybkie |
| 2.4. Dolne ograniczenie na złożoność problemu sortowania |
| 2.5. Sortowanie pozycyjne |
| 2.6. Kolejki priorytetowe i algorytm heapsort |
| 2.7. Drzewa turniejowe i zadania selekcji |
| 2.8. Szybkie algorytmy wyznaczania k-tego największego elementu w ciągu |
| 2.9. Scalanie ciągów uporządkowanych |
| 2.10. Sortowanie zewnętrzne |
| 2.10.1. Scalanie wielofazowe z 4 plikami |
| 2.10.2. Scalanie wielofazowe z 3 plikami |
| Zadania |
|
|
| 3. Słowniki |
| 3.1. Implementacja listowa nieuporządkowana |
| 3.2. Implementacja listowa uporządkowana |
| 3.3. Drzewa poszukiwań binarnych |
| 3.3.1. Drzewa AVL |
| 3.3.2. Samoorganizujące się drzewa BST |
| 3.4. Mieszanie |
| 3.4.1. Wybór funkcji mieszającej |
| 3.4.2. Struktury danych stosowane do rozwiązywania problemu kolizji |
| 3.5. Wyszukiwanie pozycyjne |
| 3.5.1. Drzewa RST |
| 3.5.2. Drzewa TRIE |
| 3.5.3. Drzewa PATRICIA |
| 3.6. Wyszukiwanie zewnętrzne |
| 3.6.1. Pliki nieuporządkowane |
| 3.6.2. Pliki z funkcją mieszającą |
| 3.6.3. Sekwencyjne pliki indeksowane |
| 3.6.4. B-drzewo jako wielopoziomowy indeks rzadki |
| 3.6.5. B-drzewo jako wielopoziomowy indeks gęsty |
| Zadania |
|
|
| 4. Złożone struktury danych dla zbiorów elementów |
| 4.1. Problem sumowania rozłącznych zbiorów |
| 4.1.1. Implementacja listowa |
| 4.1.2. Implementacja drzewowa |
| 4.2. Załączalne kolejki priorytetowe |
| Zadania |
|
|
| 5. Algorytmy tekstowe |
| 5.1. Problem wyszukiwania wzorca |
| 5.1.1. Algorytm N („naiwny") |
| 5.1.2. Algorytm KMP (Knuthą-Morrisa-Pratta) |
| 5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera |
| 5.1.4. Algorytm GS' (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców) |
| 5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga) |
| 5.1.6. Algorytm KR (Karpa-Rabina) |
| 5.1.7. Algorytm BM (Boyera-Moore'a) |
| 5.1.8. Algorytm FP (Fishera-Patersona) |
| 5.2. Drzewa sufiksowe i grafy podsłów |
| 5.2.1. Niezwarta reprezentacja drzewa sufiksowego |
| 5.2.2. Tworzenie drzewa sufiksowego |
| 5.2.3. Tworzenie grafu podsłów |
| 5.3. Inne algorytmy tekstowe |
| 5.3.1. Obliczanie najdłuższego wspólnego podsłowa |
| 5.3.2. Obliczanie najdłuższego wspólnego podciągu |
| 5.3.3. Wyszukiwanie słów podwójnych |
| 5.3.4. Wyszukiwanie słów symetrycznych |
| 5.3.5. Równoważność cykliczna |
| 5.3.6. Algorytm Huffmana |
| 5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu |
| 5.3.8. Jednoznaczne kodowanie |
| 5.3.9. Liczenie liczby podsłów |
| Zadania |
| |
|
| 6. Algorytmy równoległe |
| 6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych |
| 6.2. Sortowanie równoległe |
| Zadania |
| |
| |
| 7. Algorytmy grafowe |
| 7.1. Spójne składowe |
| 7.2. Dwuspójne składowe |
| 7.3. Silnie spójne składowe i silna orientacja |
| 7.4. Cykle Eulera |
| 7.5. 5-kolorowanie grafów planarnych |
| 7.6. Najkrótsze ścieżki i minimalne drzewo rozpinające |
| Zadania |
|
|
| 8. Algorytmy geometryczne |
| 8.1. Elementarne algorytmy geometryczne |
| 8.2. Problem przynależności |
| 8.3. Wypukła otoczka |
| 8.4. Metoda zamiatania |
|
| 8.4.1. Najmniej odległa para punktów |
| 8.4.2. Pary przecinających się odcinków |
| Zadania |
|
| Bibliografia |
| Skorowidz |
|