2- AIN-106   "Teória zložitosti"

podmienky absolvovania predmetu

Hodnotenie predmetu pozostáva z troch častí: 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