Zaawansowane algorytmy i struktury danych

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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