Zaawansowane algorytmy i struktury danych

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 dwudzuelnych -- algorytm Hopcrofta-Karpa,
  • algorytm Edmondsa.

• 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.

Bibliografia

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.

Moduły

• Kolejki priorytetowe - Kopce dwumianowe ( Ćwiczenia)