1)

 a) Co to znamená f(n) = Omikron(g(n))
 b) Mame f(n) = 2n^(log n) + (log n)^n + 10n + 5, najdete nejmensi 
    nejjednodussi a nejkrasnejsi g(n) takove, ze f(n) = Omikron(g(n))
 c) T(n) = 3T(n/4) + n^2 - slozitost

2)

 a) Byl algoritmus zapsany v pseudokodu - napsat vystup
 b) Napiste slozitost toho algoritmu
 c) Co vlastne algoritmus dela? (Radil cisla)
 d) Dokazte ze dela to, co jste napsali, ze dela.

3)

 a) Nadefinujte nedeterministicky Turinguv stroj.
 b) Vytvorte nedeterministicky Turinguv stroj, ktery prijima slova {ww|w je {0,1}^*} (zkratka dve stejna slova za sebou)
 c) Popiste stavy (pouzijte prechodovou funkci), kterymi automat projde pri prijimani 101101
 d) Jaky je vztah mezi tridami jazyku rozpoznavanymi deterministickym a nedeterministickym Turingovym strojem?

4)

 a) Definujte PSPACE a NPSPACE
 b) Reknete priklad jazyka patriciho do NPSPACE
 c) Vztah mezi P, NP, PSPACE, NPSPACE
 d) Vztah mezi rekurzivne spocetnymi jazyky a NPSPACE
 e) Definujte tridu jazyku RP a ZPP
 f) Reknete priklad jazyka patriciho do RP
 g) U <| V (redukce) a vite, ze V je rekurzivne spocetny, co muzete rict o U (nadefinujte i redukci (trojuhelnicek))