Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 18: | Linia 18: | ||
* Podstawowe zasady analizy algorytmów: | * Podstawowe zasady analizy algorytmów: | ||
** poprawność, | ** poprawność, | ||
** złożoność obliczeniowa (pesymistyczna, oczekiwana), | ** złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, koszt zamortyzowany), | ||
** złożoność problemu algorytmicznego. | ** złożoność problemu algorytmicznego. | ||
* Sortowanie: | * Sortowanie: | ||
| Linia 27: | Linia 27: | ||
** minimum i maximum, | ** minimum i maximum, | ||
** algorytm Hoare'a, | ** algorytm Hoare'a, | ||
** algorytm magicznych piątek. | ** algorytm ''magicznych piątek''. | ||
* Wyszukiwanie: | * Wyszukiwanie: | ||
** liniowe, | ** liniowe, | ||
** binarne, | ** binarne, | ||
** drzewa | ** drzewa poszukiwań binarnych, | ||
** zrównoważone drzewa | ** zrównoważone drzewa poszukiwań binarnych, | ||
** B-drzewa, | ** B-drzewa, | ||
** haszowanie. | ** haszowanie. | ||
| Linia 40: | Linia 40: | ||
* Algorytmy grafowe: | * Algorytmy grafowe: | ||
** DFS i jego zastosowania, | ** DFS i jego zastosowania, | ||
** problemy ścieżkowe -- Algorytm Dijkstry, | ** problemy ścieżkowe -- Algorytm Dijkstry i jego implementacje, | ||
** | ** minimalne drzewo rozpinające. | ||
* Algorytmy tekstowe: | * Algorytmy tekstowe: | ||
** | ** wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora, | ||
** drzewa sufiksowe. | ** struktury danych dla tekstów - drzewa sufiksowe. | ||
* | * NP-zupełność i algorytmy aproksymacyjne | ||
** NP | ** Klasa NP i problemy NP-zupełne | ||
** | ** dowodzenie NP-zupełności | ||
** | ** algorytmy aproksymacyjne, schematy aproksymacyjne, nieaproksymowalność | ||
=== Literatura === | === Literatura === | ||
# ''Wprowadzenie do algorytmów'', Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004. | # ''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. | # ''Algorytmy i struktury danych'', L. Banachowski., K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006. | ||
Wersja z 15:46, 13 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:
- 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.
- Selekcja:
- minimum i maximum,
- algorytm Hoare'a,
- algorytm magicznych piątek.
- Wyszukiwanie:
- liniowe,
- binarne,
- drzewa poszukiwań binarnych,
- zrównoważone drzewa poszukiwań binarnych,
- B-drzewa,
- haszowanie.
- Złożone struktury danych:
- kolejki priorytetowe,
- struktury danych dla zbiorów rozłącznych.
- Algorytmy grafowe:
- DFS i jego zastosowania,
- problemy ścieżkowe -- Algorytm Dijkstry i jego implementacje,
- minimalne drzewo rozpinające.
- Algorytmy tekstowe:
- wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora,
- struktury danych dla tekstów - drzewa sufiksowe.
- NP-zupełność i algorytmy aproksymacyjne
- Klasa NP i problemy NP-zupełne
- dowodzenie NP-zupełności
- algorytmy aproksymacyjne, schematy aproksymacyjne, nieaproksymowalność
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.
