2- AIN-106   "Teória zložitosti"
Skúška bude tak, ako je to v AIS, teda v piatok 27.8. o 9:00 v miestnosti VIII.
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
- PavolHromkovič: Theoretical Computer Science-An Introduction to Automata, Computability, Complexity, Algorithmics, Randomization Communication, and Cryptography
priebeh/sylaby
niečo na precvičenie
19 marec 2010