Algorytmy i struktury danych

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 efektywności.
Książka 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. Dzięki nim będzie mógł projektować efektywne algorytmy dla problemów pojawiających się w jego praktyce programistycznej lub pracy badawczej.
Algorytmy i struktury danych są tematem jednego z podstawowych przedmiotów na każdych studiach informatycznych. Książka jest sprawdzona dydaktycznie. Powstała na podstawie skryptu o tym samym tytule i notatek do wykładów prowadzonych przez Autorów na Wydziale Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.

Spis treści

Przedmowa

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. Złączalne kolejki priorytetowe
Zadania

5. Algorytmy tekstowe

5.1. Problem wyszukiwania wzorca
5.1.1. Algorytm N („naiwny")
5.1.2. Algorytm KMP (Knutha-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