Zaawansowane algorytmy i struktury danych: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Linia 18: Linia 18:


=== Zawartość ===
=== Zawartość ===
* Zaawansowane algorytmy tekstowe (3)
* Zaawansowane algorytmy tekstowe
** struktury danych dla tekstów - tablice i drzewa sufiksowe, grafy podsłów,
** struktury danych dla tekstów - tablice i drzewa sufiksowe, grafy podsłów
** regularności w tesktach - okresowość, symetrie, powtórzenia,
** regularności w tesktach - okresowość, symetrie, powtórzenia
** algorytmy z błędami,
** algorytmy z błędami
** algorytm Aho-Corasica.
** algorytm Aho-Corasica
 
* Wielomiany i FFT
* Wielomiany i FFT (1)
** mnożenie wielomianów
** mnożenie wielomianów,
** dzielenie wielomianów
** dzielenie wielomianów,
** obliczanie wartości
** obliczanie wartości,
** interpolacja
** interpolacja.
 
* Zaawansowane algorytmy grafowe
* Zaawansowane algorytmy grafowe
** Problemy ścieżkowe (2)
** Problemy ścieżkowe
*** algorytm Bellmana-Forda,
*** algorytm Bellmana-Forda
*** problemy ścieżkowe i mnożenie macierzy,
*** problemy ścieżkowe i mnożenie macierzy
*** algorytm Floyda-Warshalla,
*** algorytm Floyda-Warshalla
*** algorytm Johnsona.
*** algorytm Johnsona
** Skojarzenia (1)
** Skojarzenia
*** skojarzenia w grafach dwudzielnych - algorytmy Hopcrofta-Karpa,
*** skojarzenia w grafach dwudzielnych - algorytmy Hopcrofta-Karpa
** Maksymalny przepływ: (2)
** Maksymalny przepływ:
*** algorytm Forda-Fulkersona,
*** algorytm Forda-Fulkersona
*** algorytm Edmondsa-Karpa,
*** algorytm Edmondsa-Karpa
*** algorytm Dinica.
*** algorytm Dinica
 
* Algorytmy geometryczne
* Algorytmy geometryczne (2)
** przynależnoźć punktu do wielokąta
** przynależnoźć punktu do wielokąta,
** znajdowanie otoczki wypukłej
** znajdowanie otoczki wypukłej,
** technika zamiatania
** technika zamiatania.
* Algorytmy równoległe
 
** sieci sortujące
* Algorytmy równoległe (2)
** PRAM
** sieci sortujące,
* Randomizacja
** PRAM.
** algorytmy Monte Carlo i Las Vegas
 
** problem minimalnego przekroju
* Randomizacja: (2)
** lemat Zippela-Schwartza i jego zastosowania
** algorytmy Monte Carlo i Las Vegas,
** problem minimalnego przekroju,
** lemat Zippela-Schwartza i jego zastosowania.


=== Literatura ===
=== Literatura ===

Wersja z 11:11, 7 lip 2006

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
    • 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 minimalnego przekroju
    • lemat Zippela-Schwartza i jego zastosowania

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. Text algorithms, W. Rytter, M. Crochemore, Oxford University Press, 1994.

Moduły

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych&oldid=3055”