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

===2.===

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 \\

===3.===

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 \\