Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 16: | Linia 16: | ||
=== Zawartość === | === Zawartość === | ||
* Podstawowe zasady analizy algorytmów | * Podstawowe zasady analizy algorytmów (1) | ||
** 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 (3) | ||
** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort), | ** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort), | ||
** HeapSort | ** HeapSort i kopce binarne, | ||
** złożoność problemu sortowania, | ** złożoność problemu sortowania, | ||
** sortowanie pozycyjne. | ** sortowanie pozycyjne. | ||
* Selekcja | * Selekcja (1) | ||
** algorytm Hoare'a, | ** algorytm Hoare'a, | ||
** algorytm ''magicznych piątek''. | ** algorytm ''magicznych piątek''. | ||
* Wyszukiwanie | * Wyszukiwanie (2) | ||
** liniowe, | ** liniowe, | ||
** binarne, | ** binarne, | ||
** drzewa poszukiwań binarnych, | ** drzewa poszukiwań binarnych, | ||
** haszowanie. | ** haszowanie. | ||
* | * Złożone struktury danych (3) | ||
* Algorytmy grafowe | ** słowniki i ich implementacje - zrównoważone drzewa poszukiwań bibarnych, drzewa typu ''splay'', B-drzewa, | ||
** kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego, | |||
** sumowanie zbiorów rozłącznych. | |||
* Algorytmy grafowe (2) | |||
** 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 (2) | ||
** 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 tekstów. | ** kompresja tekstów. | ||
Wersja z 11:04, 16 cze 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 (1)
- poprawność,
- złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, koszt zamortyzowany),
- złożoność problemu algorytmicznego.
- Sortowanie (3)
- sortowanie przez porównania (InsertionSort, QuickSort, MergeSort),
- HeapSort i kopce binarne,
- złożoność problemu sortowania,
- sortowanie pozycyjne.
- Selekcja (1)
- algorytm Hoare'a,
- algorytm magicznych piątek.
- Wyszukiwanie (2)
- liniowe,
- binarne,
- drzewa poszukiwań binarnych,
- haszowanie.
- Złożone struktury danych (3)
- słowniki i ich implementacje - zrównoważone drzewa poszukiwań bibarnych, drzewa typu splay, B-drzewa,
- kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego,
- sumowanie zbiorów rozłącznych.
- Algorytmy grafowe (2)
- DFS i jego zastosowania,
- problemy ścieżkowe -- Algorytm Dijkstry,
- minimalne drzewo rozpinające.
- Algorytmy tekstowe (2)
- wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora,
- kompresja tekstów.
- NP-zupełność (1)
- Klasa NP
- Problemy NP-trudne i NP-zupełne
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.
