Předmět Algoritmy a datové struktury II (NTIN061)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN061 - Algoritmy a datové struktury II, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Sylabus
Vyhledávání v textu: Algoritmy Aho-Corasicková, Knuth-Morris-Pratt, volitelně Rabin-Karp Toky v sítích: algoritmus zlepšující cesty (Ford-Fulkerson), algoritmus Dinicův a Goldbergův, volitelně hledání maximálního toku minimální ceny a párování v bipartitním grafu Algebraické algoritmy: Diskrétní Fourierova transformace, její motivace a aplikace, algoritmus FFT (Fast Fourier Transform) a jeho implementace obvodem "butterfly" volitelně příbuzné transformace (kosinová - komprese JPEG) Paralelní aritmetické algoritmy: třídící sítě (merge-sort nebo bitonic-sort) sčítání čísel - algoritmus carry look-ahead volitelně algoritmus Karatsuba-Ofman pro násobení čísel Základní geometrické algoritmy v rovině: Konvexní obal Voronoi diagram a Delanauy triangulace (algoritmus Fortune) Převoditelnost problémů a třídy časové složitosti: Polynomiální transformace a redukce mezi rozhodovacími problémy nedeterministické algoritmy, třídy P a NP NP-úplnost Aproximační algoritmy: použití aproximačních algoritmů, poměrová a relativní chyba jeden až dva příklady, např. knapsack, bin-packing, rozvrhování na paralelních strojích, včetně horního odhadu chyby Pravděpodobnostní algoritmy a kryptografie: algoritmy typu Monte Carlo (Rabin-Millerův test prvočíselnosti) šifrování s otevřeným klíčem (RSA šifra) volitelně DES a podobné algoritmy a další kryptografické protokoly Dynamické programování
Literatura
A.Koubková, J.Pavelka : Úvod do teoretické informatiky, Matfyzpress 1999 Aho, Hopcroft, Ullman : The design and analysis of computer algorithms, Addison-Wesley 1976T.Cormen, Ch.Leiserson, R. Rivest, C. Stein : Introduction to Algorithms (2nd Edition), McGraw-Hill 2001L.Kučera : Kombinatorické algoritmy, SNTL Praha 1983L.Kučera, J. Nešetřil : Algebraické metody diskretní matematiky, SNTL Praha 1989http://kam.mff.cuni.cz/~ludek
Garant
Mgr. Martin Mareš, Ph.D.RNDr. Jan Hric