Nadobudnúť základné znalosti z teórie zložitosti. Dôraz na typ a význam otázok, ktoré si kladieme a spôsoby, ktoré sa pri ich riešení používajú.

• Problémy a algoritmy. Základné výpočtové modely a miery zložitosti.
• Metódy tvorby (efektívnych) algoritmov
• Zložitostné triedy, ich základné charakteristiky a hierarchie.
• Redukcia a úplnosť v zložitostných triedach. NP-úplné problémy.

• 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