Zaawansowane algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania (→Moduły) |
(→Moduły) |
||
| Linia 63: | Linia 63: | ||
== Moduły == | == Moduły == | ||
| + | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 1| Zaawansowane algorytmy tekstowe I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 1|Ćwiczenia]]) | ||
| + | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 2| Zaawansowane algorytmy tekstowe II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 2|Ćwiczenia]]) | ||
| + | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 3| Zaawansowane algorytmy tekstowe III]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 3|Ćwiczenia]]) | ||
| + | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 4| Wielomiany i FFT]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 4|Ćwiczenia]]) | ||
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 5| Zaawansowane algorytmy grafowe I: Najkrótsze ścieżki]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 5|Ćwiczenia]]) | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 5| Zaawansowane algorytmy grafowe I: Najkrótsze ścieżki]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 5|Ćwiczenia]]) | ||
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 6| Zaawansowane algorytmy grafowe II: Najkrótsze ścieżki]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 6|Ćwiczenia]]) | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 6| Zaawansowane algorytmy grafowe II: Najkrótsze ścieżki]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 6|Ćwiczenia]]) | ||
| Linia 69: | Linia 73: | ||
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 9| Zaawansowane algorytmy grafowe V: Maksymalny przepływ I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 9|Ćwiczenia]]) | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 9| Zaawansowane algorytmy grafowe V: Maksymalny przepływ I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 9|Ćwiczenia]]) | ||
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 10| Zaawansowane algorytmy grafowe VI: Maksymalny przepływ II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 10|Ćwiczenia]]) | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 10| Zaawansowane algorytmy grafowe VI: Maksymalny przepływ II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 10|Ćwiczenia]]) | ||
| − | |||
| − | |||
| − | |||
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 11| Algorytmy geometryczne I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 11|Ćwiczenia]]) | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 11| Algorytmy geometryczne I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 11|Ćwiczenia]]) | ||
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 12| Algorytmy geometryczne II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 12|Ćwiczenia]]) | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 12| Algorytmy geometryczne II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 12|Ćwiczenia]]) | ||
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 13| Algorytmy równoległe I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 13|Ćwiczenia]]) | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 13| Algorytmy równoległe I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 13|Ćwiczenia]]) | ||
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 14| Algorytmy równoległe II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 14|Ćwiczenia]]) | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 14| Algorytmy równoległe II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 14|Ćwiczenia]]) | ||
| − | |||
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 15| Algorytmy randomizowane]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 15|Ćwiczenia]]) | * [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 15| Algorytmy randomizowane]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 15|Ćwiczenia]]) | ||
Wersja z 15:41, 30 wrz 2006
Forma zajęć
Wykład (30 godzin) + laboratorium (30 godzin)
Opis
Projektowanie i analiza algorytmów. Przegląd zaawansowanych algorytmów i struktur danych. Wprowadzenie do zaawansowanych technik projektowania algorytmów.
Sylabus
Autorzy
- Krzysztof Diks
- Wojciech Rytter
- Piotr Sankowski
Wymagania wstępne
- Algorytmy i struktury danych
- Analiza matematyczna
- Algebra liniowa z geometrią analityczną
Zawartość
- Zaawansowane algorytmy grafowe
- Problemy ścieżkowe
- algorytm Bellmana-Forda
- problemy ścieżkowe i mnożenie macierzy
- algorytm Floyda-Warshalla
- algorytm Johnsona
- Skojarzenia
- skojarzenia w grafach dwudzielnych - algorytmy Hopcrofta-Karpa
- skojarzenia w grafach dowolnych - algorytm Edmondsa
- Maksymalny przepływ:
- algorytm Forda-Fulkersona
- algorytm Edmondsa-Karpa
- algorytm Dinica
- Problemy ścieżkowe
- Zaawansowane algorytmy tekstowe
- algorytm Boyera Moore'a
- Wyszukiwanie wzorca w pamięci stałej
- regularności w tesktach - symetrie, powtórzenia
- Algorytmy geometryczne
- przynależnoźć punktu do wielokąta
- znajdowanie otoczki wypukłej
- technika zamiatania i problem najmniej odległej pary punktów
- Algorytmy równoległe
- Abstrakcyjny model PRAM
- sumy prefiksowe i sortowanie na PRAMie
- algorytm jednoczesnych podstawień
- równoległa kontrakcja drzew
- Wielomiany i FFT
- mnożenie wielomianów
- dzielenie wielomianów
- obliczanie wartości
- interpolacja
- Randomizacja
- algorytmy Monte Carlo i Las Vegas
- problem maksymalnego przekroju
- problem długiej ścieżki
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.
- Randomized Algorithms, R. Motwani, P. Raghavan, Cambridge University Press, 1995.
- Jewels of stringology, W. Rytter, M. Crochemore, World Scientific, 2003.
Moduły
- Zaawansowane algorytmy tekstowe I (Ćwiczenia)
- Zaawansowane algorytmy tekstowe II (Ćwiczenia)
- Zaawansowane algorytmy tekstowe III (Ćwiczenia)
- Wielomiany i FFT (Ćwiczenia)
- Zaawansowane algorytmy grafowe I: Najkrótsze ścieżki (Ćwiczenia)
- Zaawansowane algorytmy grafowe II: Najkrótsze ścieżki (Ćwiczenia)
- Zaawansowane algorytmy grafowe III: Skojarzenia w grafach dwudzielnych (Ćwiczenia)
- Zaawansowane algorytmy grafowe IV: Skojarzenia w grafach dowolnych (Ćwiczenia)
- Zaawansowane algorytmy grafowe V: Maksymalny przepływ I (Ćwiczenia)
- Zaawansowane algorytmy grafowe VI: Maksymalny przepływ II (Ćwiczenia)
- Algorytmy geometryczne I (Ćwiczenia)
- Algorytmy geometryczne II (Ćwiczenia)
- Algorytmy równoległe I (Ćwiczenia)
- Algorytmy równoległe II (Ćwiczenia)
- Algorytmy randomizowane (Ćwiczenia)
