Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m →Autorzy |
|||
| Linia 18: | Linia 18: | ||
=== Zawartość === | === Zawartość === | ||
* Podstawowe zasady analizy algorytmów | * Podstawowe zasady analizy algorytmów: | ||
** poprawność | ** poprawność | ||
** złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana) | ** złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana) | ||
**koszt zamortyzowany: metoda potencjału | **koszt zamortyzowany: metoda potencjału | ||
* Podstawowe techniki i struktury | * Podstawowe techniki i struktury: | ||
**metoda dziel i zwyciężaj | **metoda ''dziel i zwyciężaj'' | ||
**metoda zachłanna | **metoda zachłanna | ||
**pogramowanie dynamiczne | **pogramowanie dynamiczne | ||
**transformacyjna konstrukcja algorytmu | **transformacyjna konstrukcja algorytmu | ||
**elementarne struktury danych: stosy, kolejki, listy | **elementarne struktury danych: stosy, kolejki, listy | ||
* Sortowanie | * Sortowanie: | ||
** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort) | ** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort) | ||
** proste kolejki priorytetowe: kopce binarne | ** proste kolejki priorytetowe: kopce binarne | ||
| Linia 34: | Linia 34: | ||
** sortowanie pozycyjne | ** sortowanie pozycyjne | ||
** złożoność problemu sortowania | ** złożoność problemu sortowania | ||
* Selekcja | * Selekcja: | ||
** algorytm Hoare'a | ** algorytm Hoare'a | ||
** algorytm ''magicznych piątek'' | ** algorytm ''magicznych piątek'' | ||
* Wyszukiwanie i proste słowniki | * Wyszukiwanie i proste słowniki: | ||
** wyszukiwanie liniowe i binarne | ** wyszukiwanie liniowe i binarne | ||
** prosty słownik: drzewa poszukiwań binarnych | ** prosty słownik: drzewa poszukiwań binarnych | ||
** haszowanie | ** haszowanie | ||
* Efektywne implementacje słownika | * Efektywne implementacje słownika: | ||
** drzewa AVL | ** drzewa AVL | ||
** drzewa typu ''splay'' | ** drzewa typu ''splay'' | ||
** B-drzewa | ** B-drzewa | ||
* Złożone struktury danych | * Złożone struktury danych: | ||
** wzmocnione kolejki priorytetowe: kolejki dwumianowe, kopce Fibonacciego | ** wzmocnione kolejki priorytetowe: kolejki dwumianowe, kopce Fibonacciego | ||
** efektywne sumowanie zbiorów rozłącznych | ** efektywne sumowanie zbiorów rozłącznych | ||
* Algorytmy grafowe | * Algorytmy grafowe: | ||
** DFS i jego zastosowania | ** DFS i jego zastosowania | ||
** problemy ścieżkowe -- Algorytm Dijkstry | ** problemy ścieżkowe -- Algorytm Dijkstry | ||
** minimalne drzewo rozpinające | ** minimalne drzewo rozpinające | ||
* Wyszukiwanie wzorca w tekstach | * Wyszukiwanie wzorca w tekstach: | ||
** prefikso-sufiksy | ** prefikso-sufiksy | ||
** algorytm Knutha-Morisa-Pratta | ** algorytm Knutha-Morisa-Pratta | ||
*Tekstowe struktury danych | *Tekstowe struktury danych: | ||
**tablice sufiksowe | **tablice sufiksowe | ||
**drzewa sufiksowe | **drzewa sufiksowe | ||
* NP-zupełność | * NP-zupełność: | ||
** klasa NP | ** klasa NP | ||
** problemy NP-trudne i NP-zupełne | ** problemy NP-trudne i NP-zupełne | ||
Wersja z 11:41, 27 wrz 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
- Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
- Adam Malinowski — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
- Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
- Tomasz Waleń — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
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: 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
Moduły
- Wstęp: poprawność i złożoność algorytmu (Ćwiczenia)
- Wstęp: podstawowe techniki algorytmiczne i struktury danych (Ćwiczenia)
- Sortowanie przez porównania: BubleSort, SelectionSort i InsertionSort (Ćwiczenia)
- Sortowanie przez porównania: MergeSort, HeapSort i QuickSort (Ćwiczenia)
- Sortowanie: dolna granica, sortowanie pozycyjne (Ćwiczenia)
- Selekcja (Ćwiczenia)
- Wyszukiwanie (Ćwiczenia)
- Słowniki (Ćwiczenia)
- Kolejki priorytetowe (Ćwiczenia)
- Find-Union (Ćwiczenia)
- Algorytmy grafowe - najkrótsze ścieżki (Ćwiczenia)
- Algorytmy grafowe - przeszukiwanie grafów (Ćwiczenia)
- Algorytmy tekstowe I (Ćwiczenia)
- Algorytmy tekstowe II (Ćwiczenia)
- NP-zupełność (Ćwiczenia)
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.
