Toto je starší verze dokumentu!

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) Neco jako: vztah mezi deterministickym a nedeterministickym turingem?

4)

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