Algorytmy i struktury danych WNT

Autor: L. Banachowski, K. Diks, W. Rytter

ISBN: 83-204-3224-3

Ilość stron: 290

Data wydania: 2006 (wydanie piąte)

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 "Algorytmy i struktury danych" 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.

Rozdziały:

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.6. Eliminacja rekursji
1.7. Koszt zamortyzowany operacji w strukturze danych
1.8. Metody układania algorytmów
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
Zadania

3. Słowniki

3.1. Implementacja listowa nieuporządkowana
3.2. Implementacja listowa uporządkowana
3.3. Drzewa poszukiwań binarnych
3.4. Mieszanie
3.5. Wyszukiwanie pozycyjne
3.6. Wyszukiwanie zewnętrzne
Zadania

4. Złożone struktury danych dla zbiorów elementów

4.1. Problem sumowania rozłącznych zbiorów
4.2. Złączalne kolejki priorytetowe
Zadania

5. Algorytmy tekstowe

5.1. Problem wyszukiwania wzorca
5.2. Drzewa sufiksowe i grafy podsłów
5.3. Inne algorytmy tekstowe
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
Zadania