Termín 16.6.2011

Čas na vypracování 1 hodinka (nic moc času)

Chce všecko zdůvodnit a pečlivě popsat rovnou v té písemce. Není vůbec žádný prostor na doplnění pak při ústní.

V případě, že máte méně než 30b z testu tak moc nediskutuje a na ústní se ani nedostane.

Zadání:

1)

 a) Definuj f(n) = Omega(g(n))?
 b) Je dána fce f(n) = lg(n!) + (lg n)^4 + n^2 ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = Omega(g(n))
 c) Řeš T(n) = 7 T(n/9) + nlogn 

2)

a) Definuj nedeterministický TM. Definuj, co znamená, že tento TM přijímá jazyk L.
b) TM přijímající L={w0w | w je binární} Nejprve slovně popiš, pak tabulky nebo přechodový diagram (body jsou i za zprávný    popis stroje
c) Napiš výpočet přijetí slova 11011

3)

a) Definuj jazyky RP a ZPP. Příklad jazyka RP.
b) Jaký je vztah mezi jazyky ROZHODOVANÝMI deterministickým TM a jazyky rozhodovanými nedeterministikým TM.
c) Co jsou to rekurzivní a rekurzivně spočetné jazyky.
d) Vztah mezi NP, rekurzivnými a rekurzivně spočtenými.