MIMINF:Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 28: | Linia 28: | ||
** transformacyjna konstrukcja algorytmu | ** transformacyjna konstrukcja algorytmu | ||
* Sortowanie: | * Sortowanie: | ||
** sortowanie przez porównania (sortowanie przez wstawianie - InsertionSort, sortowanie szybkie - QuickSort, sortowanie przez scalanie - 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 | ** sortowanie kopcowe - ''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 słowniki: | * Wyszukiwanie i słowniki: | ||
** wyszukiwanie liniowe i binarne | ** wyszukiwanie liniowe i binarne | ||
** drzewa | ** drzewa wyszukiwań binarnych, zrównoważone drzewa wyszukiwań binarnych (AVL, drzewa czerwono-czarne, drzewa typu ''splay'') | ||
** haszowanie (funkcje haszujące, haszowanie uniwersalne, metody rozwiązywania kolizji, haszowanie doskonałe) | ** haszowanie (funkcje haszujące, haszowanie uniwersalne, metody rozwiązywania kolizji, haszowanie doskonałe) | ||
** B-drzewa | ** B-drzewa | ||
*Kolejki priorytetowe: | *Kolejki priorytetowe: | ||
**złączalne kolejki priorytetowe | **złączalne kolejki priorytetowe (kopce dwumianowe i Fibonacciego) | ||
**algorytm Dijkstry | **algorytm Dijkstry | ||
*Problem "Find-Union" i jego zastosowania | *Problem "Find-Union" i jego zastosowania | ||
| Linia 51: | Linia 50: | ||
** problemy ścieżkowe | ** problemy ścieżkowe | ||
** minimalne drzewo rozpinające | ** minimalne drzewo rozpinające | ||
** najliczniejsze skojarzenia w grafach dwudzielnych | |||
* Wyszukiwanie wzorca w tekstach: | * Wyszukiwanie wzorca w tekstach: | ||
** prefikso-sufiksy | ** prefikso-sufiksy | ||
Wersja z 13:12, 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
- sortowanie kopcowe - HeapSort
- sortowanie pozycyjne
- złożoność problemu sortowania
- Selekcja:
- algorytm Hoare'a
- algorytm magicznych piątek
- Wyszukiwanie i słowniki:
- wyszukiwanie liniowe i binarne
- drzewa wyszukiwań binarnych, zrównoważone drzewa wyszukiwań 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 (kopce dwumianowe i Fibonacciego)
- 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
- najliczniejsze skojarzenia w grafach dwudzielnych
- 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.
