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

• Piotr Sankowski
• Krzysztof Diks

Wymagania wstępne

• Algorytmy i struktury danych
• Analiza matematyczna
• Algebra liniowa z geometrią analityczną

Zawartość

• Kolejki priorytetowe:
  • kopce dwumianowe,
  • kopce Fibonacziego.

• Wielomiany i FFT
  • mnożenie wielomianów,
  • dzielenie wielomianów,
  • obliczanie wartośći,
  • interpolacja·

• Algorytmy macierzowe:
  • 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,
  • ważone skojarzenia w grafach dwudzielnych.

• Największy przepływ:
  • algorytm Forda-Fuckersona,
  • algorytm Edmondsa-Karpa,
  • algorytm Dintiz'a.

• Algorytmy geometryczne:
  • przynaleźnoźć punktu do wielokąta,
  • znajdowanie otoczki wypukłej,
  • technika zamiatania.

• Algorytmy teorio liczbowe:
  • najwiekszy wspólny dzielnik,
  • arytmetyka modularna,
  • rozwiązywanie liniowych równań modularnych,
  • chińskie twierdzenie o resztach,
  • system kryptograficzny z kluczem jawnym RSA.

• Algorytmy aproksymacyjne.
  • problem pokrycia wierzchołkowego,
  • problem komiwojażera.

• Randomizacja:
  • algorytmy Monte Carlo i Las Vegas,
  • problem minimalnego przecięcia,
  • lemat Zippela-Schwartza i zastosowania.

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