MIMINF:Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 19: | Linia 19: | ||
* Podstawowe zasady analizy algorytmów: | * Podstawowe zasady analizy algorytmów: | ||
** poprawność | ** poprawność | ||
** złożoność obliczeniowa algorytmu (pesymistyczna, | ** złożoność obliczeniowa algorytmu (czasowa i pamieciowa, pesymistyczna i oczekiwana, koszt zamortyzowany) | ||
** | ** złożoność problemu algorytmicznego a złożoność algorytmu - dolne granice, metody analizy złożoności | ||
* | * Metody projektowania wydajnych algorytmów: | ||
**metoda ''dziel i zwyciężaj'' | ** metoda ''dziel i zwyciężaj'' | ||
** | ** algorytmy zachłanne | ||
**pogramowanie dynamiczne | ** pogramowanie dynamiczne | ||
**transformacyjna konstrukcja algorytmu | ** przeszukiwanie z nawrotami i metoda podziału i ograniczeń | ||
** transformacyjna konstrukcja algorytmu | |||
* Sortowanie: | * Sortowanie: | ||
** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort) | ** sortowanie przez porównania (sortowanie przez wstawianie - InsertionSort, sortowanie szybkie - QuickSort, sortowanie przez scalanie - MergeSort) | ||
** proste kolejki priorytetowe: kopce binarne | ** proste kolejki priorytetowe: kopce binarne | ||
**HeapSort | ** HeapSort | ||
** sortowanie pozycyjne | ** sortowanie pozycyjne | ||
** złożoność problemu sortowania | ** złożoność problemu sortowania | ||
| Linia 36: | Linia 36: | ||
** algorytm Hoare'a | ** algorytm Hoare'a | ||
** algorytm ''magicznych piątek'' | ** algorytm ''magicznych piątek'' | ||
* Wyszukiwanie i | *Podstawowe abstrakcyjne struktury danych i metody ich implementacji: lista, kolejka, stos, zbiór, drzewo, graf | ||
* Wyszukiwanie i słowniki: | |||
** wyszukiwanie liniowe i binarne | ** wyszukiwanie liniowe i binarne | ||
** | ** drzewa poszukiwań binarnych, zrównoważone drzewa poszukiwań binarnych (AVL, drzewa czerwono-czarne, drzewa typu ''splay'' | ||
** haszowanie (funkcje haszujące, haszowanie uniwersalne, metody rozwiązywania kolizji, haszowanie doskonałe) | |||
** B-drzewa | ** B-drzewa | ||
* | *Kolejki priorytetowe: | ||
** | **złączalne kolejki priorytetowe | ||
** | **algorytm Dijkstry | ||
* Algorytmy grafowe: | *Problem "Find-Union" i jego zastosowania | ||
** | *Algorytmy grafowe: | ||
** problemy ścieżkowe | **komputerowe reprezentacje grafów | ||
**metody przeszukiwania grafów i ich zastosowania - najkrótsze ścieżki, spójność, dwuspójność, silna spójność, sortowanie topologiczne | |||
** problemy ścieżkowe | |||
** minimalne drzewo rozpinające | ** minimalne drzewo rozpinające | ||
* Wyszukiwanie wzorca w tekstach: | * Wyszukiwanie wzorca w tekstach: | ||
| Linia 57: | Linia 57: | ||
**tablice sufiksowe | **tablice sufiksowe | ||
**drzewa sufiksowe | **drzewa sufiksowe | ||
=== Literatura === | === Literatura === | ||
# ''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. | ||
# ''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. | ||
Wersja z 13:08, 17 paź 2006
Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin) + laboratorium (30 godzin)
Opis
Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych.
Sylabus
Autorzy
- Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
- Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
Wymagania wstępne
- Wstęp do programowania
- Matematyka dyskretna
- Podstawy matematyki
- Analiza matematyczna 1
- Geometria z algebrą liniową
Zawartość
- Podstawowe zasady analizy algorytmów:
- poprawność
- złożoność obliczeniowa algorytmu (czasowa i pamieciowa, pesymistyczna i oczekiwana, koszt zamortyzowany)
- złożoność problemu algorytmicznego a złożoność algorytmu - dolne granice, metody analizy złożoności
- Metody projektowania wydajnych algorytmów:
- metoda dziel i zwyciężaj
- algorytmy zachłanne
- pogramowanie dynamiczne
- przeszukiwanie z nawrotami i metoda podziału i ograniczeń
- transformacyjna konstrukcja algorytmu
- Sortowanie:
- sortowanie przez porównania (sortowanie przez wstawianie - InsertionSort, sortowanie szybkie - QuickSort, sortowanie przez scalanie - MergeSort)
- proste kolejki priorytetowe: kopce binarne
- HeapSort
- sortowanie pozycyjne
- złożoność problemu sortowania
- Selekcja:
- algorytm Hoare'a
- algorytm magicznych piątek
- Podstawowe abstrakcyjne struktury danych i metody ich implementacji: lista, kolejka, stos, zbiór, drzewo, graf
- Wyszukiwanie i słowniki:
- wyszukiwanie liniowe i binarne
- drzewa poszukiwań binarnych, zrównoważone drzewa poszukiwań binarnych (AVL, drzewa czerwono-czarne, drzewa typu splay
- haszowanie (funkcje haszujące, haszowanie uniwersalne, metody rozwiązywania kolizji, haszowanie doskonałe)
- B-drzewa
- Kolejki priorytetowe:
- złączalne kolejki priorytetowe
- algorytm Dijkstry
- Problem "Find-Union" i jego zastosowania
- Algorytmy grafowe:
- komputerowe reprezentacje grafów
- metody przeszukiwania grafów i ich zastosowania - najkrótsze ścieżki, spójność, dwuspójność, silna spójność, sortowanie topologiczne
- problemy ścieżkowe
- minimalne drzewo rozpinające
- Wyszukiwanie wzorca w tekstach:
- prefikso-sufiksy
- algorytm Knutha-Morisa-Pratta
- Tekstowe struktury danych:
- tablice sufiksowe
- drzewa sufiksowe
Literatura
- Algorytmy i struktury danych, L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
- Wprowadzenie do algorytmów, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
