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

• Krzysztof Diks
• Wojciech Rytter
• Piotr Sankowski

Wymagania wstępne

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

Zawartość

• Zaawansowane algorytmy tekstowe
  • struktury danych dla tekstów - tablice i drzewa sufiksowe, grafy podsłów
  • regularności w tesktach - okresowość, symetrie, powtórzenia
  • algorytmy z błędami
  • algorytm Aho-Corasica
• Wielomiany i FFT
  • mnożenie wielomianów
  • dzielenie wielomianów
  • obliczanie wartości
  • interpolacja
• 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
• Algorytmy geometryczne
  • przynależnoźć punktu do wielokąta
  • znajdowanie otoczki wypukłej
  • technika zamiatania
• Algorytmy równoległe
  • sieci sortujące
  • PRAM
• 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

• Zaawansowane algorytmy tekstowe I (Ćwiczenia, Laboratoria)
• Zaawansowane algorytmy tekstowe II (Ćwiczenia, Laboratoria)
• Zaawansowane algorytmy tekstowe III (Ćwiczenia, Laboratoria)
• Zaawansowane algorytmy grafowe I: Najkrótsze ścieżki (Ćwiczenia, Laboratoria)
• Zaawansowane algorytmy grafowe II: Najkrótsze ścieżki (Ćwiczenia, Laboratoria)
• Zaawansowane algorytmy grafowe III: Skojarzenia w grafach dwudzielnych (Ćwiczenia, Laboratoria)
• Zaawansowane algorytmy grafowe IV: Skojarzenia w grafach dowolnych (Ćwiczenia, Laboratoria)
• Zaawansowane algorytmy grafowe V: Maksymalny przepływ I (Ćwiczenia, Laboratoria)
• Zaawansowane algorytmy grafowe VI: Maksymalny przepływ II (Ćwiczenia, Laboratoria)
• Algorytmy geometryczne I (Ćwiczenia, Laboratoria)
• Algorytmy geometryczne II (Ćwiczenia, Laboratoria)
• Algorytmy równoległe I (Ćwiczenia, Laboratoria)
• Wielomiany i FFT (Ćwiczenia, Laboratoria)
• Algorytmy równoległe II (Ćwiczenia, Laboratoria)
• Algorytmy randomizowane I (Ćwiczenia, Laboratoria)