2- AIN-106 Teória zložitosti
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
■ J. Hromkovič:
Theoretical Computer Science-An Introduction to Automata, Computability,
Complexity, Algorithmics, Randomization Communication, and Cryptography
priebeh/sylaby
■
úvod
■
rozdeľuj a panuj najblizsie body 1 najblizsie body 2
■
dynamické programovanie a greedy metóda
■
metódy založené na prehľadávaní stavového priestoru
■
výpočtové modely a vzťahy medzi nimi
■
zložitostné triedy a vzťahy medzi nimi