| Datum | Téma |
|---|
Pokračování přednášky TIN060 Algoritmy a datové struktury I
Algoritmy Aho-Corasicková, Knuth-Morris-Pratt, volitelně Rabin-Karp
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
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)
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
Konvexní obal
Voronoi diagram a Delanauy triangulace (algoritmus Fortune)
Polynomiální transformace a redukce mezi rozhodovacími problémy
nedeterministické algoritmy, třídy P a NP
NP-úplnost
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
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
A. Koubková, J. Pavelka : Úvod do teoretické informatiky, Matfyzpress 1999
Aho, Hopcroft, Ullman : The design and analysis of computer algorithms, Addison-Wesley 1976
T. Cormen, Ch. Leiserson, R. Rivest, C. Stein : Introduction to Algorithms (2nd Edition), McGraw-Hill 2001
L. Kučera : Kombinatorické algoritmy, SNTL Praha 1983
L. Kučera, J. Nešetřil : Algebraické metody diskretní matematiky, SNTL Praha 1989