====== 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, klidně i poloviční počet bodů z příkladu)
  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) Třída co-RE je doplněk jazyka RE. Co platí pro třídy R, RE, co-RE a třídu úplně všech jazyků VS. Napiš všechny inkluze, které platí. Pokud jsou některé tyto inkluze ostré, uveď příklad jazyka patřícího do jedné třídy a nepatřícího do druhé.
     Možná ještě nějaké body, už si nepvzpomínám



~~DISCUSSION~~