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.