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 |
|