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

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


* [[ZASD Moduł 1| Kolejki priorytetowe I]] ([[ZASD Ćwiczenia 1|Ćwiczenia]])
* [[ZASD Moduł 1| Zaawansowane algorytmy tekstowe I]] ([[ZASD Ćwiczenia 1|Ćwiczenia]])
* [[ZASD Moduł 2| Kolejki priorytetowe II]] ([[ZASD Ćwiczenia 2|Ćwiczenia]])
* [[ZASD Moduł 2| Zaawansowane algorytmy tekstowe II]] ([[ZASD Ćwiczenia 2|Ćwiczenia]])
* [[ZASD Moduł 3| Wielomiany i FFT]] ([[ZASD Ćwiczenia 3|Ćwiczenia]])
* [[ZASD Moduł 3| Zaawansowane algorytmy tekstowe III]] ([[ZASD Ćwiczenia 3|Ćwiczenia]])
* [[ZASD Moduł 4| Algorytmy macierzowe]] ([[ZASD Ćwiczenia 4|Ćwiczenia]])
* [[ZASD Moduł 4| Wielomiany i FFT]] ([[ZASD Ćwiczenia 4|Ćwiczenia]])
* [[ZASD Moduł 5| Najkrótsze ścieżki I]] ([[ZASD Ćwiczenia 5|Ćwiczenia]])
* [[ZASD Moduł 5| Zaawansowane algorytmy grafowe I: Najkrótsze ścieżki]] ([[ZASD Ćwiczenia 5|Ćwiczenia]])
* [[ZASD Moduł 6| Najkrótsze ścieżki II]] ([[ZASD Ćwiczenia 6|Ćwiczenia]])
* [[ZASD Moduł 6| Zaawansowane algorytmy grafowe II: Najkrótsze ścieżki]] ([[ZASD Ćwiczenia 6|Ćwiczenia]])
* [[ZASD Moduł 7| Skojarzenia w grafach dwudzielnych]] ([[ZASD Ćwiczenia 7|Ćwiczenia]])
* [[ZASD Moduł 7| Zaawansowane algorytmy grafowe III: Skojarzenia w grafach dwudzielnych]] ([[ZASD Ćwiczenia 7|Ćwiczenia]])
* [[ZASD Moduł 8| Ważone skojarzenia w grafach dwudzielnych]] ([[ZASD Ćwiczenia 8|Ćwiczenia]])
* [[ZASD Moduł 8| Zaawansowane algorytmy grafowe IV: Maksymalny przepływ]] ([[ZASD Ćwiczenia 8|Ćwiczenia]])
* [[ZASD Moduł 9| Przepływy I]] ([[ZASD Ćwiczenia 9|Ćwiczenia]])
* [[ZASD Moduł 9| Zaawansowane algorytmy grafowe V: Maksymalny przepływ]] ([[ZASD Ćwiczenia 9|Ćwiczenia]])
* [[ZASD Moduł 10| Przepływy II]] ([[ZASD Ćwiczenia 10|Ćwiczenia]])
* [[ZASD Moduł 10| Algorytmy geometryczne I]] ([[ZASD Ćwiczenia 10|Ćwiczenia]])
* [[ZASD Moduł 11| Algorytmy geometryczne]] ([[ZASD Ćwiczenia 11|Ćwiczenia]])
* [[ZASD Moduł 11| Algorytmy geometryczne II]] ([[ZASD Ćwiczenia 11|Ćwiczenia]])
* [[ZASD Moduł 12| Algorytmy teorioliczbowe]] ([[ZASD Ćwiczenia 12|Ćwiczenia]])
* [[ZASD Moduł 12| Algorytmy równoległe I]] ([[ZASD Ćwiczenia 12|Ćwiczenia]])
* [[ZASD Moduł 13| Algorytmy aproksymacyjne]] ([[ZASD Ćwiczenia 13|Ćwiczenia]])
* [[ZASD Moduł 13| Algorytmy równoległe II]] ([[ZASD Ćwiczenia 13|Ćwiczenia]])
* [[ZASD Moduł 14| Algorytmy randomizowane]] ([[ZASD Ćwiczenia 14|Ćwiczenia]])
* [[ZASD Moduł 14| Algorytmy randomizowane I]] ([[ZASD Ćwiczenia 14|Ćwiczenia]])
* [[ZASD Moduł 15| Algorytmy randomizowane II]] ([[ZASD Ćwiczenia 15|Ćwiczenia]])


== Literatura uzupełniająca ==
== Literatura uzupełniająca ==
''opcjonalnie''
''opcjonalnie''

Wersja z 22:25, 17 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ść

  • 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 (1)
      • skojarzenia w grafach dwudzielnych - algorytmy Hopcrofta-Karpa,
    • 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=2221”