2- AIN-106 "Teória zložitosti"
podmienky absolvovania predmetu
Hodnotenie predmetu pozostáva z troch častí:
- písomka počas semestra (30b)
- skúšková písomka (40b)
- ústna skúška (30b)
Podmienkou postupu na ústnu skúšku je získanie aspoň 35 bodov (kompromis medzi oznámenými 40 bodmi a želanými 40%) z oboch písomiek.
Každý sa môže prísť na písomku pozrieť, mohla som niečomu nerozumieť,..
výsledky 13.6.2011
kedy?
Streda 9:50-12:20, F2
o čom?
Problémy a algoritmy, metódy tvorby efektívnych algoritmov. Základné výpočtové modely a miery zložitosti. Zložitostné triedy, ich základné
charakteristiky a hierarchie. Redukcia a úplnosť v zložitostných
triedach. NP-úplné problémy.
literatúra
- A.V.Aho, J.E.Hopcroft, J. D.Ullman: The Design and Analysis of Computer Algorithms
- J.E.Hopcroft, J.D.Ullman: Formálne jazyky a automaty
- Horowitz, Sahni: Fundamentals of Computer Algorithms
- Papadimitriou: Computational Complexity
- Juraj Hromkovič: Theoretical Computer Science-An Introduction to Automata, Computability, Complexity, Algorithmics, Randomization Communication, and Cryptography
stránka k cvičeniam tu
priebeh/sylaby