Výpočtová zložitosť
(sylaby štátnic magisterského štúdia informatiky - plná verzia)
- Turingove stroje, základné zložitostné triedy a vzťahy medzi nimi
(Savitchova veta, simulácie a hierarchie).
- Gap Theorem a Veta o zrýchľovaní.
- NP-úplnosť, Cook-Levinova veta a niektoré ďalšie (aj pre prax
dôležité) NP-úplné problémy.
- Vzťah NP-úplných a NP-optimalizačných problémov.
- Aproximačné algoritmy pre NP-optimalizačné problémy;
neaproximovateľnosť.
- Pravdepodobnostné algoritmy (Veta o vylepšovaní, BPP vs.
PSPACE).
- Kolmogorovská zložitosť (základné pojmy a vlastnosti, nestlačiteľnosť).