Č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