a. definovat malé o a omegu a vztah mezi nimi
b.
c. Master theorem t(n) = 4T(n/3) + n^2*logn

a. definovat deterministicý Turingův stroj, vysvětlit krok Turingova stroje
b. vytoviřit DTM, který realizuje pro |w| ⇐ 2 → w a pro |w| > 2 → w^R1^(k-2), kde w^R je revers slova w a k je délka slova w
c. ukázat výpočet na w = 100

a. Co znamená že je jazyk/úloha P, NP, NPC, co-NP
b. Pro každou třídu výše uvedenou říct zdali je/není algoritmus → ověření zdali daný graf jde obarvit k-barvami.
c. Definovat paměťovou složitost Turingkova stroje
d. PSPACE a NSPACE, jejich vztah
e. Podobná otázka jako z 5.6.2014 3f
f. Byl dán jazyk rekurzivní a co-RE. Jaký je jejich vztah