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.
• Randomizacja.
• Algorytmy aproksymacyjne.