Algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m →Moduły |
|||
| Linia 55: | Linia 55: | ||
* [[ASD Moduł 4| Kolejki priorytetowe]] ([[ASD Ćwiczenia 4|Ćwiczenia]]) | * [[ASD Moduł 4| Kolejki priorytetowe]] ([[ASD Ćwiczenia 4|Ćwiczenia]]) | ||
* [[ASD Moduł 5| Struktury danych dla zbiorów rozłącznych]] ([[ASD Ćwiczenia 5|Ćwiczenia]]) | * [[ASD Moduł 5| Struktury danych dla zbiorów rozłącznych]] ([[ASD Ćwiczenia 5|Ćwiczenia]]) | ||
* [[ASD Moduł 6| ???]] ([[ASD Ćwiczenia 6|Ćwiczenia]]) | |||
* [[ASD Moduł 7| ???]] ([[ASD Ćwiczenia 7|Ćwiczenia]]) | |||
* [[ASD Moduł 8| ???]] ([[ASD Ćwiczenia 8|Ćwiczenia]]) | |||
* [[ASD Moduł 9| ???]] ([[ASD Ćwiczenia 9|Ćwiczenia]]) | |||
* [[ASD Moduł 10| ???]] ([[ASD Ćwiczenia 10|Ćwiczenia]]) | |||
* [[ASD Moduł 11| ???]] ([[ASD Ćwiczenia 11|Ćwiczenia]]) | |||
* [[ASD Moduł 12| ???]] ([[ASD Ćwiczenia 12|Ćwiczenia]]) | |||
* [[ASD Moduł 13| ???]] ([[ASD Ćwiczenia 13|Ćwiczenia]]) | |||
* [[ASD Moduł 14| ???]] ([[ASD Ćwiczenia 14|Ćwiczenia]]) | |||
* [[ASD Moduł 15| ???]] ([[ASD Ćwiczenia 15|Ćwiczenia]]) | |||
=== Literatura === | === Literatura === | ||
# ''Wprowadzenie do algorytmów'', Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004. | # ''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. | # ''Algorytmy i struktury danych'', L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006. | ||
Wersja z 14:57, 12 lip 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
- Sortowanie
- sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
- HeapSort i kopce binarne
- złożoność problemu sortowania
- sortowanie pozycyjne
- Selekcja
- algorytm Hoare'a
- algorytm magicznych piątek
- Wyszukiwanie
- liniowe
- binarne
- drzewa poszukiwań binarnych
- haszowanie
- Złożone struktury danych
- słowniki i ich implementacje - zrównoważone drzewa poszukiwań binarnych, drzewa typu splay, B-drzewa
- kolejki priorytetowe - 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
- Algorytmy tekstowe
- wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora
- kompresja tekstów
- NP-zupełność
- klasa NP
- problemy NP-trudne i NP-zupełne
Moduły
- Wstęp (Ćwiczenia)
- ??? (Ćwiczenia)
- Słowniki (Ćwiczenia)
- Kolejki priorytetowe (Ćwiczenia)
- Struktury danych dla zbiorów rozłącznych (Ćwiczenia)
- ??? (Ćwiczenia)
- ??? (Ćwiczenia)
- ??? (Ćwiczenia)
- ??? (Ćwiczenia)
- ??? (Ćwiczenia)
- ??? (Ćwiczenia)
- ??? (Ćwiczenia)
- ??? (Ćwiczenia)
- ??? (Ćwiczenia)
- ??? (Ć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.
