Zaawansowane algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 18: | Linia 18: | ||
=== Zawartość === | === Zawartość === | ||
* Wielomiany i FFT | * Wielomiany i FFT: | ||
** mnożenie wielomianów, | ** mnożenie wielomianów, | ||
** dzielenie wielomianów, | ** dzielenie wielomianów, | ||
** obliczanie | ** obliczanie wartości, | ||
** | ** interpolacja. | ||
* | * Złożoność problemów macierzowych: | ||
** szybkie mnożenie macierzy, | ** szybkie mnożenie macierzy, | ||
** rozwiązywanie układów równań i liczenie odwrotności macierzy. | ** rozwiązywanie układów równań i liczenie odwrotności macierzy. | ||
* Problemy ścieżkowe | * Problemy ścieżkowe: | ||
** algorytm Bellmana-Forda, | ** algorytm Bellmana-Forda, | ||
** problemy ścieżkowe i mnożenie macierzy, | ** problemy ścieżkowe i mnożenie macierzy, | ||
| Linia 34: | Linia 34: | ||
** algorytm Johnsona. | ** algorytm Johnsona. | ||
* Skojarzenia | * Skojarzenia: | ||
** skojarzenia w grafach dwudzielnych -- algorytm Hopcrofta-Karpa, | ** skojarzenia w grafach dwudzielnych -- algorytm Hopcrofta-Karpa, | ||
** skojarzenia w grafach dowolnych -- algorytm Edmondsa | ** skojarzenia w grafach dowolnych -- algorytm Edmondsa | ||
| Linia 49: | Linia 49: | ||
** technika zamiatania. | ** technika zamiatania. | ||
* Algorytmy równoległe | * Algorytmy równoległe: | ||
** sieci sortujące | ** sieci sortujące | ||
** PRAM | ** PRAM | ||
* Generowanie i zliczanie obiektów kombinatorycznych | * Generowanie i zliczanie obiektów kombinatorycznych: | ||
** Klasa #P i problemy #P-zupełne | ** Klasa #P i problemy #P-zupełne | ||
** Gnerowanie permutacji i podzbiorów | ** Gnerowanie permutacji i podzbiorów | ||
| Linia 62: | Linia 62: | ||
** problem minimalnego przekroju, | ** problem minimalnego przekroju, | ||
** lemat Zippela-Schwartza i zastosowania. | ** lemat Zippela-Schwartza i zastosowania. | ||
* Algorytmy dynamiczne: | |||
** dynamiczne drzewa, | |||
** dynamiczne spójność grafu. | |||
=== Literatura === | === Literatura === | ||
Wersja z 16:26, 13 cze 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ść
- Wielomiany i FFT:
- mnożenie wielomianów,
- dzielenie wielomianów,
- obliczanie wartości,
- interpolacja.
- Złożoność problemów macierzowych:
- szybkie mnożenie macierzy,
- rozwiązywanie układów równań i liczenie odwrotności macierzy.
- Problemy ścieżkowe:
- algorytm Bellmana-Forda,
- problemy ścieżkowe i mnożenie macierzy,
- algorytm Floyda-Warshalla,
- algorytm Johnsona.
- Skojarzenia:
- skojarzenia w grafach dwudzielnych -- algorytm Hopcrofta-Karpa,
- skojarzenia w grafach dowolnych -- algorytm Edmondsa
- ważone skojarzenia w grafach dwudzielnych.
- Największy przepływ:
- algorytm Forda-Fulckersona,
- algorytm Edmondsa-Karpa,
- algorytm Dintiz'a.
- Algorytmy geometryczne:
- przynależnoźć punktu do wielokąta,
- znajdowanie otoczki wypukłej,
- technika zamiatania.
- Algorytmy równoległe:
- sieci sortujące
- PRAM
- Generowanie i zliczanie obiektów kombinatorycznych:
- Klasa #P i problemy #P-zupełne
- Gnerowanie permutacji i podzbiorów
- Zliczanie drzew, cykli Eulera, doskonałych skojarzeń
- Randomizacja:
- algorytmy Monte Carlo i Las Vegas,
- problem minimalnego przekroju,
- lemat Zippela-Schwartza i zastosowania.
- Algorytmy dynamiczne:
- dynamiczne drzewa,
- dynamiczne spójność grafu.
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.
Moduły
- Kolejki priorytetowe I (Ćwiczenia)
- Kolejki priorytetowe II (Ćwiczenia)
- Wielomiany i FFT (Ćwiczenia)
- Algorytmy macierzowe (Ćwiczenia)
- Najkrótsze ścieżki I (Ćwiczenia)
- Najkrótsze ścieżki II (Ćwiczenia)
- Skojarzenia w grafach dwudzielnych (Ćwiczenia)
- Ważone skojarzenia w grafach dwudzielnych (Ćwiczenia)
- Przepływy I (Ćwiczenia)
- Przepływy II (Ćwiczenia)
- Algorytmy geometryczne (Ćwiczenia)
- Algorytmy teorioliczbowe (Ćwiczenia)
- Algorytmy aproksymacyjne (Ćwiczenia)
- Algorytmy randomizowane (Ćwiczenia)
Literatura uzupełniająca
opcjonalnie
