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) Co platí pro f(n) = Theta(g(n))?
 b) Je dána fce f(n) = n log^3 n + n^2 + ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = theta(g(n))
 c) Prozkoumej T(n) = 2 T(n/2) + 1. Příklad na Master Theorem.

2)

a) Co je to Turingův stroj a co to znamená, když přijímá jazyk L?
b) Rozdíl mezi tím, když TM nějaký jazyk přijímá a když jej rozhoduje.
c) Je dán jazyk L, jehož slova mají tvar: {0|1}* - libovolná posloupnost 0 a 1, kde ale musí být víc jedniček.
   Napiš TM, který rozhoduje tento jazyk. Stačí slovní popis nebo klidně i přechody.
d) Napiš jeden netriviální stav jako přechodovou funkci.

3)

a) Co je to třída NP a napiš jeden rozhodovací problém, který do ní nepatří.
b) Popiš postup pro důkaz toho, že je něco NP úplné. Popiš redukci atd. Můžeš buďto všeobecně a nebo na příkladu nějakého převodu.
c) Co jsou to rekurzivní a rekurzivně spočetné jazyky.
d) Vztah mezi NP, rekurzivnými a rekurzivně spočtenými.