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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 63: Linia 63:
 
== Moduły ==
 
== Moduły ==
  
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 5| Zaawansowane algorytmy grafowe I: Najkrótsze ścieżki]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 5|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 5|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 5| Zaawansowane algorytmy grafowe I: Najkrótsze ścieżki]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 5|Ć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]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 6|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 6| Zaawansowane algorytmy grafowe II: Najkrótsze ścieżki]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 6|Ć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]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 7|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 7| Zaawansowane algorytmy grafowe III: Skojarzenia w grafach dwudzielnych]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 7|Ć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]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 8|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 8| Zaawansowane algorytmy grafowe IV: Skojarzenia w grafach dowolnych]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 8|Ć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]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 9|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 9| Zaawansowane algorytmy grafowe V: Maksymalny przepływ I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 9|Ć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]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 10|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 10| Zaawansowane algorytmy grafowe VI: Maksymalny przepływ II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 10|Ćwiczenia]])
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 1| Zaawansowane algorytmy tekstowe I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 1|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 1|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 1| Zaawansowane algorytmy tekstowe I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 1|Ćwiczenia]])
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 2| Zaawansowane algorytmy tekstowe II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 2|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 2|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 2| Zaawansowane algorytmy tekstowe II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 2|Ćwiczenia]])
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 3| Zaawansowane algorytmy tekstowe III]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 3|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 3|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 3| Zaawansowane algorytmy tekstowe III]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 3|Ćwiczenia]])
 
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 11| Algorytmy geometryczne I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 11|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 11|Laboratoria]])
 
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 11| Algorytmy geometryczne I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 11|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 11|Laboratoria]])
 
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 12| Algorytmy geometryczne II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 12|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 12|Laboratoria]])
 
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 12| Algorytmy geometryczne II]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 12|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 12|Laboratoria]])
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 13| Algorytmy równoległe I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 13|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 13|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 13| Algorytmy równoległe I]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 13|Ć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/Laboratoria 14|Laboratoria]])
+
* [[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 4| Wielomiany i FFT]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 4|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 4|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 4| Wielomiany i FFT]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 4|Ćwiczenia]])
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 15| Algorytmy randomizowane]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 15|Ćwiczenia]], [[Zaawansowane_algorytmy_i_struktury_danych/Laboratoria 15|Laboratoria]])
+
* [[Zaawansowane_algorytmy_i_struktury_danych/Wykład 15| Algorytmy randomizowane]] ([[Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia 15|Ćwiczenia]])

Wersja z 10:06, 29 wrz 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