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 vtah

e. Podobná otázka jako z 5.6.2014 3f

f. Byl dán jazyk rekurzivní a co-RE. Jaký je jejich vztah