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
Diks (dyskusja | edycje)
538 edycji
Linia 17: Linia 17:


=== Zawartość ===
=== Zawartość ===
* Kolejki priorytetowe:
** kopce dwumianowe,
** kopce Fibonacziego.
* Wielomiany i FFT
* Wielomiany i FFT
** mnożenie wielomianów,
** mnożenie wielomianów,
Linia 27: Linia 23:
** interpolacja·
** interpolacja·


* Algorytmy macierzowe:
* Algorytmy macierzowe
** szybkie mnożenie macierzy,
** szybkie mnożenie macierzy,
** rozwiązywanie układów równań i liczenie odwrotności macierzy.
** rozwiązywanie układów równań i liczenie odwrotności macierzy.


* Problemy ścieżkowe:
* Problemy ścieżkowe
** algorytm Bellmana-Forda,
** algorytm Bellmana-Forda,
** problemy ścieżkowe i mnożenie macierzy,
** problemy ścieżkowe i mnożenie macierzy,
Linia 39: Linia 35:
* Skojarzenia
* Skojarzenia
** skojarzenia w grafach dwudzielnych -- algorytm Hopcrofta-Karpa,
** skojarzenia w grafach dwudzielnych -- algorytm Hopcrofta-Karpa,
** skojarzenia w grafach dowolnych -- algorytm Edmondsa
** ważone skojarzenia w grafach dwudzielnych.
** ważone skojarzenia w grafach dwudzielnych.


* Największy przepływ:
* Największy przepływ:
** algorytm Forda-Fuckersona,
** algorytm Forda-Fulckersona,
** algorytm Edmondsa-Karpa,
** algorytm Edmondsa-Karpa,
** algorytm Dintiz'a.
** algorytm Dintiz'a.


* Algorytmy geometryczne:
* 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 teorio liczbowe:
* Algorytmy równoległe
** najwiekszy wspólny dzielnik,
** sieci sortujące
** arytmetyka modularna,
** PRAM
** rozwiązywanie liniowych równań modularnych,
** chińskie twierdzenie o resztach,
** system kryptograficzny z kluczem jawnym RSA.


* Algorytmy aproksymacyjne.
* Generowanie i zliczanie obiektów kombinatorycznych
** problem pokrycia wierzchołkowego,
** Klasa #P i problemy #P-zupełne
** problem komiwojażera.
** Gnerowanie permutacji i podzbiorów
** Zliczanie drzew, cykli Eulera, doskonałych skojarzeń


* Randomizacja:
* Randomizacja:
** algorytmy Monte Carlo i Las Vegas,
** algorytmy Monte Carlo i Las Vegas,
** problem minimalnego przecięcia,
** problem minimalnego przekroju,
** lemat Zippela-Schwartza i zastosowania.
** lemat Zippela-Schwartza i zastosowania.


Wersja z 15:58, 13 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

  • Piotr Sankowski
  • Krzysztof Diks

Wymagania wstępne

  • Algorytmy i struktury danych
  • Analiza matematyczna
  • Algebra liniowa z geometrią analityczną

Zawartość

  • Wielomiany i FFT
    • mnożenie wielomianów,
    • dzielenie wielomianów,
    • obliczanie wartośći,
    • interpolacja·
  • Algorytmy macierzowe
    • szybkie mnożenie macierzy,
    • rozwiązywanie układów równań i liczenie odwrotności macierzy.
  • 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,
    • skojarzenia w grafach dowolnych -- algorytm Edmondsa
    • ważone skojarzenia w grafach dwudzielnych.
  • Największy przepływ:
    • algorytm Forda-Fulckersona,
    • algorytm Edmondsa-Karpa,
    • algorytm Dintiz'a.
  • Algorytmy geometryczne:
    • przynależnoźć punktu do wielokąta,
    • znajdowanie otoczki wypukłej,
    • technika zamiatania.
  • Algorytmy równoległe
    • sieci sortujące
    • PRAM
  • Generowanie i zliczanie obiektów kombinatorycznych
    • 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,
    • problem minimalnego przekroju,
    • lemat Zippela-Schwartza i 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=2015”