| Odporúčaný ročník: | 2. |
| Semester: | zimný |
| Rozsah: | P3 |
| Hodnotenie: | 0/100 |
| Počet kreditov: | 4 |
| Vyučujúci: | prednáša doc. RNDr. Dana Pardubská CSc. |
| www stránka: |
Priblížiť a na príkladoch demonštrovať základné techniky pri riešení ťažkých výpočtových úloh.
- exaktné algoritmy
- aproximácia
- problémy aproximovateľné s konštantným faktorom (APX)
- problémy aproximovateľné s ľubovoľnou presnosťou (PTAS, FPTAS)
- randomizácia
- Las Vegas vs. Monte Carlo
- techniky návrhu pravdepodobnostných algoritmov
- derandomizácia
- heuristické metódy
G. Ausiello, P.Crescenzi, V.Kann, A.Marchetti-Spacamela, M.Protasi: Complexity and Approximation Springer, 1999
J. Hromkovič: Algorithmics for Hard Problems; Springer Verlag 2001, ISBN 3-540-66860-8
J. Hromkovič: Theoretical Computer Science – An Introduction to Automata, Computability, Complexity, Algorithnics, Randomization, Communication and Cryptography
J. Hromkovič: Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms, Springer 2005
R. Motwani, P.Raghavan: Randomized Algorithms Cambridge University Press, 1995
Ch. H. Papadimitriou: Computational Complexity, Addison-Wesley Publishing Company, 1994, ISBN 0-201-53082-1
elektronické poznámky na stránke