2-INF-135 Pravdepodobnostné algoritmy
| Odporúčaný ročník: | 1. |
| Semester: | letný |
| Rozsah: | P3,C1 |
| Hodnotenie: | 20/80 |
| Počet kreditov: | 6 |
| Vyučujúci: | prednáša doc. RNDr. Dana Pardubská CSc. |
| www stránka: |
Cieľ:
Prednáška o použití náhodnosti v algoritmoch a protokoloch; náhodnosť umožňuje riešiť niektoré úlohy, ktoré sú bez jej použitia (prakticky) neriešiteľné alebo riešiteľné menej efektívne.
Sylabus:
- algoritmy využívajúce náhodné čísla a vlastnosti náhodných objektov ako jeden z prístupov k riešeniu algoritmicky ťažkých problémov
- techniky návrhnu pravdepodobnostných algoritmov, derandomizácia
- zložitostné triedy pravdepodobnostných výpočtov
Literatúra:
R. Motwani, P. Raghavan: Randomized algorithms. Cambridge University Press 1995, ISBN 0521474655
J. Hromkovič: Design And Analysis of Randomized Algorithms: Introduction to Design Paradigms, Springer-Verlag New York Inc 2005, ISBN-13: 9783540239499
Ch.H.Papadimitriou: Computational Complexity, Addison-Wesley Publishing Company, 1994, ISBN 0-201-53082-1