Zaawansowane algorytmy i struktury danych

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-Fulkersona,
  • 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

1. Wprowadzenie do algorytmów, Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
2. Algorytmy i struktury danych, L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
3. 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