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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Diks (dyskusja | edycje)
538 edycji
Sank (dyskusja | edycje)
734 edycje
 
(Nie pokazano 38 wersji utworzonych przez 5 użytkowników)
Linia 8: Linia 8:


=== Autorzy ===  
=== Autorzy ===  
* Krzysztof Diks
* Wojciech Rytter
* Piotr Sankowski
* Piotr Sankowski
* Krzysztof Diks


=== Wymagania wstępne ===
=== Wymagania wstępne ===
Linia 17: Linia 18:


=== Zawartość ===
=== Zawartość ===
* Kolejki priorytetowe:
* Zaawansowane algorytmy grafowe
** kopce dwumianowe,
** Problemy ścieżkowe
** kopce Fibonacziego.
*** 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
* Wielomiany i FFT
** mnożenie wielomianów,
** mnożenie wielomianów
** dzielenie wielomianów,
** dzielenie wielomianów
** obliczanie wartośći,
** obliczanie wartości
** interpolacja·
** interpolacja
 
* Randomizacja
* Algorytmy macierzowe:
** algorytmy Monte Carlo i Las Vegas
** szybkie mnożenie macierzy,
** problem maksymalnego przekroju
** rozwiązywanie układów równań i liczenie odwrotności macierzy.
** problem długiej ścieżki
 
* Problemy ścieżkowe:
** algorytm Bellmana-Forda,
** problemy ścieżkowe i mnożenie macierzy,
** algorytm Floyda-Warshalla,
** algorytm Johnsona.
 
* Skojarzenia
** skojarzenia w grafach dwudzielnych -- algorytm Hopcrofta-Karpa,
** ważone skojarzenia w grafach dwudzielnych.
 
* Największy przepływ:
** algorytm Forda-Fuckersona,
** algorytm Edmondsa-Karpa,
** algorytm Dintiz'a.
 
* Algorytmy geometryczne:
** przynaleźnoźć punktu do wielokąta,
** znajdowanie otoczki wypukłej,
** technika zamiatania.
 
* Algorytmy teorio liczbowe:
** najwiekszy wspólny dzielnik,
** arytmetyka modularna,
** rozwiązywanie liniowych równań modularnych,
** chińskie twierdzenie o resztach,
** system kryptograficzny z kluczem jawnym RSA.
 
* Algorytmy aproksymacyjne.
** problem pokrycia wierzchołkowego,
** problem komiwojażera.
 
* Randomizacja:
** algorytmy Monte Carlo i Las Vegas,
** problem minimalnego przecięcia,
** lemat Zippela-Schwartza i zastosowania.


=== Literatura ===
=== Literatura ===
Linia 71: Linia 59:
# ''Algorytmy i struktury danych'', L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
# ''Algorytmy i struktury danych'', L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
#  ''Randomized Algorithms'', R. Motwani, P. Raghavan, Cambridge University Press, 1995.
#  ''Randomized Algorithms'', R. Motwani, P. Raghavan, Cambridge University Press, 1995.
# ''Jewels of stringology'', W. Rytter, M. Crochemore, World Scientific, 2003.


== Moduły ==
== Moduły ==


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

Aktualna wersja na dzień 21:38, 3 paź 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 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

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