Zaawansowane algorytmy i struktury danych: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 45: | Linia 45: | ||
** technika zamiatania. | ** technika zamiatania. | ||
* Algorytmy teorio liczbowe | * 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. | * 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. | |||
=== Bibliografia === | === Bibliografia === | ||
# ''Wprowadzenie do algorytmów'', Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004. | # ''Wprowadzenie do algorytmów'', Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004. | ||
# ''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. | ||
Wersja z 20:19, 8 cze 2006
Sylabus
Autorzy
- Piotr Sankowski
- Krzysztof Diks
Wymagania wstępne
- Algorytmy i struktury danych
- Analiza matematyczna
- Algebra liniowa z geometrią analityczną
Zawartość
- Kolejki priorytetowe:
- kopce dwumianowe,
- kopce Fibonacziego.
- 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 dwudzuelnych -- algorytm Hopcrofta-Karpa,
- algorytm Edmondsa.
- 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.
Bibliografia
- Wprowadzenie do algorytmów, Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
- Algorytmy i struktury danych, L. Banachowski., K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
