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

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