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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Sank (dyskusja | edycje)
734 edycje
Diks (dyskusja | edycje)
538 edycji
Linia 18: Linia 18:


=== Zawartość ===
=== Zawartość ===
* Wielomiany i FFT:
* Złożone struktury danych (3)
** słowniki i ich implementacje - drzewa typu ''splay'', listy z przeskokami,
** kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego,
** sumowanie zbiorów rozłącznych.
 
* Zaawansowane algorytmy tekstowe (3)
** 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 (1)
** mnożenie wielomianów,
** mnożenie wielomianów,
** dzielenie wielomianów,
** dzielenie wielomianów,
Linia 24: Linia 35:
** interpolacja.
** interpolacja.


* Złożoność problemów macierzowych:
* Zaawansowane algorytmy grafowe
** szybkie mnożenie macierzy,
** Problemy ścieżkowe (2)
** rozwiązywanie układów równań i liczenie odwrotności macierzy.
*** algorytm Bellmana-Forda,
*** problemy ścieżkowe i mnożenie macierzy,
*** algorytm Floyda-Warshalla,
*** algorytm Johnsona.


* Problemy ścieżkowe:
** Skojarzenia (2)
** algorytm Bellmana-Forda,
*** skojarzenia w grafach dwudzielnych - algorytmy Hopcrofta-Karpa,
** problemy ścieżkowe i mnożenie macierzy,
*** ważone skojarzenia w grafach dwudzielnych.
** algorytm Floyda-Warshalla,
** algorytm Johnsona.


* Skojarzenia:
** Maksymalny przepływ: (2)
** skojarzenia w grafach dwudzielnych -- algorytm Hopcrofta-Karpa,
*** algorytm Forda-Fulkersona,
** skojarzenia w grafach dowolnych -- algorytm Edmondsa,
*** algorytm Edmondsa-Karpa,
** ważone skojarzenia w grafach dwudzielnych.
*** algorytm Dintiz'a.


* Największy przepływ:
* Algorytmy geometryczne (2)
** algorytm Forda-Fulkersona,
** algorytm Edmondsa-Karpa,
** algorytm Dintiz'a.
 
* Algorytmy geometryczne:
** 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:
* Algorytmy równoległe (2)
** sieci sortujące,
** sieci sortujące,
** PRAM.
** PRAM.


* Generowanie i zliczanie obiektów kombinatorycznych:
* Randomizacja: (2)
** klasa #P i problemy #P-zupełne,
** gnerowanie permutacji i podzbiorów,
** zliczanie drzew, cykli Eulera, doskonałych skojarzeń.
 
* Randomizacja:
** algorytmy Monte Carlo i Las Vegas,
** algorytmy Monte Carlo i Las Vegas,
** problem minimalnego przekroju,
** problem minimalnego przekroju,
** lemat Zippela-Schwartza i zastosowania.
** lemat Zippela-Schwartza i jego zastosowania.
 
* Algorytmy dynamiczne:
** dynamiczne drzewa,
** dynamiczne spójność grafu.


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

Wersja z 10:52, 16 cze 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ść

  • Złożone struktury danych (3)
    • słowniki i ich implementacje - drzewa typu splay, listy z przeskokami,
    • kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego,
    • sumowanie zbiorów rozłącznych.
  • Zaawansowane algorytmy tekstowe (3)
    • 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 (1)
    • mnożenie wielomianów,
    • dzielenie wielomianów,
    • obliczanie wartości,
    • interpolacja.
  • Zaawansowane algorytmy grafowe
    • Problemy ścieżkowe (2)
      • algorytm Bellmana-Forda,
      • problemy ścieżkowe i mnożenie macierzy,
      • algorytm Floyda-Warshalla,
      • algorytm Johnsona.
    • Skojarzenia (2)
      • skojarzenia w grafach dwudzielnych - algorytmy Hopcrofta-Karpa,
      • ważone skojarzenia w grafach dwudzielnych.
    • Maksymalny przepływ: (2)
      • algorytm Forda-Fulkersona,
      • algorytm Edmondsa-Karpa,
      • algorytm Dintiz'a.
  • Algorytmy geometryczne (2)
    • przynależnoźć punktu do wielokąta,
    • znajdowanie otoczki wypukłej,
    • technika zamiatania.
  • Algorytmy równoległe (2)
    • sieci sortujące,
    • PRAM.
  • Randomizacja: (2)
    • 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.

Moduły

Literatura uzupełniająca

opcjonalnie

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