Personal tools

Zaawansowane algorytmy i struktury danych

From Studia Informatyczne

Spis treści

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ść

  • Zaawansowane algorytmy grafowe
    • Problemy ścieżkowe
      • algorytm Bellmana-Forda
      • problemy ścieżkowe i mnożenie macierzy
      • algorytm Floyda-Warshalla
      • algorytm Johnsona
    • Skojarzenia
      • skojarzenia w grafach dwudzielnych - algorytmy Hopcrofta-Karpa
      • skojarzenia w grafach dowolnych - algorytm Edmondsa
    • Maksymalny przepływ:
      • algorytm Forda-Fulkersona
      • algorytm Edmondsa-Karpa
      • algorytm Dinica
  • Zaawansowane algorytmy tekstowe
    • algorytm Boyera Moore'a
    • Wyszukiwanie wzorca w pamięci stałej
    • regularności w tesktach - symetrie, powtórzenia
  • Algorytmy geometryczne
    • przynależnoźć punktu do wielokąta
    • znajdowanie otoczki wypukłej
    • technika zamiatania i problem najmniej odległej pary punktów
  • Algorytmy równoległe
    • Abstrakcyjny model PRAM
    • sumy prefiksowe i sortowanie na PRAMie
    • algorytm jednoczesnych podstawień
    • równoległa kontrakcja drzew
  • Wielomiany i FFT
    • mnożenie wielomianów
    • dzielenie wielomianów
    • obliczanie wartości
    • interpolacja
  • Randomizacja
    • algorytmy Monte Carlo i Las Vegas
    • problem maksymalnego przekroju
    • problem długiej ścieżki

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.
  4. Jewels of stringology, W. Rytter, M. Crochemore, World Scientific, 2003.

Moduły