Třídy složitosti úloh/jazyků vzhledem k časové složitosti jejich řešení a paměťové složitosti včetně nerozhodnutelných úloh/jazyků.

BE4M01TAL Webové stránky předmětu

• Asymptotický růst funkcí, časová a prostorová složitost algoritmů. Správnost algoritmů – varianta a invariant.
• Deterministické Turingovy stroje, vícestopé Turingovy stroje a nedeterministické Turingovy stroje.
• Rozhodovací problémy a jazyky. Třídy složitosti P, NP, co-NP. Redukce a polynomiální redukce, třída NPC. Cookova věta. Heuristiky a aproximační algoritmy pro řešení NP-úplných problémů.
• Třídy založené na paměťové složitosti: PSPACE a NPSPACE. Savitchova věta.
• Randomizované algoritmy. Randomizované Turingovy stroje. Třídy založené na randomizaci: RP, ZPP, co-RP.
• Rozhodnutelnost a nerozhodnutelnost. Rekurzivní a rekurzivně vyčíslitelné jazyky. Diagonální jazyk. Univerzální jazyk a univerzální Turingův stroj.