Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 28: | Linia 28: | ||
* Sortowanie | * Sortowanie | ||
** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort) | ** sortowanie przez porównania (InsertionSort, QuickSort, MergeSort) | ||
** | ** proste kolejki priorytetowe: kopce binarne | ||
** złożoność problemu sortowania | **HeapSort | ||
** złożoność problemu sortowania <font color=red> *</font> | |||
** sortowanie pozycyjne | ** sortowanie pozycyjne | ||
* Selekcja | * Selekcja | ||
** algorytm Hoare'a | ** algorytm Hoare'a | ||
** algorytm ''magicznych piątek'' | ** algorytm ''magicznych piątek'' | ||
* Wyszukiwanie | * Wyszukiwanie i proste słowniki | ||
** liniowe i binarne | ** wyszukiwanie liniowe i binarne | ||
** drzewa poszukiwań binarnych | ** prosty słownik: drzewa poszukiwań binarnych | ||
** haszowanie | ** haszowanie | ||
* Złożone struktury danych <font color=red> *</font> | * Złożone struktury danych <font color=red> *</font> | ||
** słowniki | ** efektywne słowniki - zrównoważone drzewa poszukiwań binarnych, drzewa typu ''splay'', B-drzewa | ||
** kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego | ** kolejki priorytetowe z dodatkowymi operacjami - kolejki dwumianowe i kopce Fibonacciego | ||
** sumowanie zbiorów rozłącznych | ** sumowanie zbiorów rozłącznych | ||
* Algorytmy grafowe | * Algorytmy grafowe | ||
| Linia 46: | Linia 47: | ||
** problemy ścieżkowe -- Algorytm Dijkstry | ** problemy ścieżkowe -- Algorytm Dijkstry | ||
** minimalne drzewo rozpinające | ** minimalne drzewo rozpinające | ||
* | * wyszukiwanie wzorca w tekstach | ||
** prefikso-sufiksy | ** prefikso-sufiksy | ||
**algorytm Knutha-Morisa-Pratta | **algorytm Knutha-Morisa-Pratta | ||
Wersja z 09:02, 14 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
- Wojciech Rytter,
- Krzysztof Diks
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)
- złożoność problemu algorytmicznego
- 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
- złożoność problemu sortowania *
- sortowanie pozycyjne
- Selekcja
- algorytm Hoare'a
- algorytm magicznych piątek
- Wyszukiwanie i proste słowniki
- wyszukiwanie liniowe i binarne
- prosty słownik: drzewa poszukiwań binarnych
- haszowanie
- Złożone struktury danych *
- efektywne słowniki - zrównoważone drzewa poszukiwań binarnych, drzewa typu splay, B-drzewa
- kolejki priorytetowe z dodatkowymi operacjami - kolejki dwumianowe i kopce Fibonacciego
- 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: HeapSort, MergeSort 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 w głąb (Ćwiczenia)
- Algorytmy tekstowe I (Ćwiczenia)
- Algorytmy tekstowe II (Ćwiczenia)
- NP-zupełność (Ćwiczenia)
Literatura
- Wprowadzenie do algorytmów, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
- Algorytmy i struktury danych, L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
