====== 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ů. ======

[[https://fel.cvut.cz/en/education/bk/predmety/46/95/p4695106.html|BE4M01TAL]] [[https://moodle.fel.cvut.cz/course/view.php?id=5851|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.