MIMINF:Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
|||
| Linia 11: | Linia 11: | ||
=== Wymagania wstępne === | === Wymagania wstępne === | ||
* Wstęp do programowania | * Wstęp do programowania | ||
* Matematyka dyskretna | * Matematyka dyskretna | ||
* | * Podstawy matematyki | ||
* Analiza matematyczna 1 | |||
* Geometria z algebrą liniową | |||
=== Zawartość === | === Zawartość === | ||
Wersja z 12:50, 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 (pesymistyczna, oczekiwana)
- koszt zamortyzowany: metoda potencjału
- Podstawowe techniki i struktury:
- metoda dziel i zwyciężaj
- metoda zachłanna
- pogramowanie dynamiczne
- transformacyjna konstrukcja algorytmu
- elementarne struktury danych: stosy, kolejki, listy
- Sortowanie:
- sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
- proste kolejki priorytetowe: kopce binarne
- HeapSort
- sortowanie pozycyjne
- złożoność problemu sortowania
- Selekcja:
- algorytm Hoare'a
- algorytm magicznych piątek
- Wyszukiwanie i proste słowniki:
- wyszukiwanie liniowe i binarne
- prosty słownik: drzewa poszukiwań binarnych
- haszowanie
- Efektywne implementacje słownika:
- drzewa AVL
- drzewa typu splay
- B-drzewa
- Złożone struktury danych:
- wzmocnione kolejki priorytetowe: kolejki dwumianowe, kopce Fibonacciego
- efektywne sumowanie zbiorów rozłącznych
- Algorytmy grafowe:
- DFS i jego zastosowania
- problemy ścieżkowe -- Algorytm Dijkstry
- minimalne drzewo rozpinające
- Wyszukiwanie wzorca w tekstach:
- prefikso-sufiksy
- algorytm Knutha-Morisa-Pratta
- Tekstowe struktury danych:
- tablice sufiksowe
- drzewa sufiksowe
- NP-zupełność:
- klasa NP
- problemy NP-trudne i NP-zupełne
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.
