Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m Poprawki edytorskie |
|||
| Linia 16: | Linia 16: | ||
=== Zawartość === | === Zawartość === | ||
* Podstawowe zasady analizy algorytmów | * Podstawowe zasady analizy algorytmów | ||
** poprawność | ** poprawność | ||
** złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, koszt zamortyzowany) | ** złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, koszt zamortyzowany) | ||
** złożoność problemu algorytmicznego | ** złożoność problemu algorytmicznego | ||
* Sortowanie | * Sortowanie | ||
** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort) | ** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort) | ||
** HeapSort i kopce binarne | ** HeapSort i kopce binarne | ||
** złożoność problemu sortowania | ** złożoność problemu sortowania | ||
** sortowanie pozycyjne | ** sortowanie pozycyjne | ||
* Selekcja | * Selekcja | ||
** algorytm Hoare'a | ** algorytm Hoare'a | ||
** algorytm ''magicznych piątek'' | ** algorytm ''magicznych piątek'' | ||
* Wyszukiwanie | * Wyszukiwanie | ||
** liniowe | ** liniowe | ||
** binarne | ** binarne | ||
** drzewa poszukiwań binarnych | ** drzewa poszukiwań binarnych | ||
** haszowanie | ** haszowanie | ||
* Złożone struktury danych | * Złożone struktury danych | ||
** słowniki i ich implementacje - zrównoważone drzewa poszukiwań binarnych, drzewa typu ''splay'', B-drzewa | ** słowniki i ich implementacje - zrównoważone drzewa poszukiwań binarnych, drzewa typu ''splay'', B-drzewa | ||
** kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego | ** kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego | ||
** sumowanie zbiorów rozłącznych | ** sumowanie zbiorów rozłącznych | ||
* Algorytmy grafowe | * Algorytmy grafowe | ||
** DFS i jego zastosowania | ** DFS i jego zastosowania | ||
** problemy ścieżkowe -- Algorytm Dijkstry | ** problemy ścieżkowe -- Algorytm Dijkstry | ||
** minimalne drzewo rozpinające | ** minimalne drzewo rozpinające | ||
* Algorytmy tekstowe | * Algorytmy tekstowe | ||
** wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora | ** wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora | ||
** kompresja | ** kompresja tekstów | ||
* NP-zupełność | * NP-zupełność | ||
** | ** klasa NP | ||
** | ** problemy NP-trudne i NP-zupełne | ||
=== Moduły=== | === Moduły=== | ||
Wersja z 07:22, 7 lip 2006
Forma zajęć
Wykład (30 godzin) + laboratorium (30 godzin)
Opis
Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych.
Sylabus
Autorzy
- Wojciech Rytter,
- Krzysztof Diks
Wymagania wstępne
- Wstęp do programowania
- Metody programowania
- Matematyka dyskretna
- Logika i teoria mnogości
Zawartość
- Podstawowe zasady analizy algorytmów
- poprawność
- złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, koszt zamortyzowany)
- złożoność problemu algorytmicznego
- Sortowanie
- sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
- HeapSort i kopce binarne
- złożoność problemu sortowania
- sortowanie pozycyjne
- Selekcja
- algorytm Hoare'a
- algorytm magicznych piątek
- Wyszukiwanie
- liniowe
- binarne
- drzewa poszukiwań binarnych
- haszowanie
- Złożone struktury danych
- słowniki i ich implementacje - zrównoważone drzewa poszukiwań binarnych, drzewa typu splay, B-drzewa
- kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego
- sumowanie zbiorów rozłącznych
- Algorytmy grafowe
- DFS i jego zastosowania
- problemy ścieżkowe -- Algorytm Dijkstry
- minimalne drzewo rozpinające
- Algorytmy tekstowe
- wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora
- kompresja tekstów
- NP-zupełność
- klasa NP
- problemy NP-trudne i NP-zupełne
Moduły
Literatura
- Wprowadzenie do algorytmów, Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
- Algorytmy i struktury danych, L. Banachowski., K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
