Opis
Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych. Doskonalenie praktycznych umiejętnosci w projektowaniu i programowaniu poprawnych i wydajnych algorytmow oraz w posługiwaniu się gotowymi bibliotekami 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
- L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, Wydawnictwa Naukowo - Techniczne, 2006.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, Wydawnictwa Naukowo - Techniczne, 2004.
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.