Termín 5.6.2012

Bylo na to 90 minut. Demlová mi u ústní říkala, že to asi přehnala, že měla dát víc času - že si spousta lidí stěžovalo, že to nestíhali.

1) (20b)

a) Definujte f(n) = theta(g(n)) a f(n) = omikron(g(n))
b) f(n) = sum od 1 do n k^2; g(n) = n^2 log n; dokazte zda f(n) nalezi theta g(n) a zda f(n) nalezi velke O g(n)
c) Pokud plati f(n) nalezi theta g(n), plati pak 2 ^ f(n) nalezi theta 2 ^ g(n) ? Zduvodnete
d) master theorem T(n) = 2*T(n/2) + lg(n)

2) (25b)

a) Definujte DTM a definujte co to znamena, ze TM prijma/rozhoduje  (5b)
b) Vytvorte TM tabulkou/grafem pro slovo w = {0, 1}*, kde TM prijme slovo, ve kterem je vice 0 nez 1  (15b)
c) Demonstrace prijmuti slova w = 10100 (chtela videt stav TM v kazdem kroku)  (5b)

3) (35b)

a) Definujte NP a P.
b) Definujte paměťovou složitost Turingova stroje.
c) Definujte ZPP + možná ještě něco.
d) Definujte co-NP + jaký je vztah co-NP a ZPP.
e) Zadány úlohy U, V, W. Platí  U <| V <| W (<| je polynomiální redukce). U je 2-barevnost, W je existence hamiltonovské kružnice, V se neví. Napište nejsilnější tvrzení, které platí pro úlohu V a zdůvodněte.
f) Popište vzájemné vztahy R (rekurzivní jazyky), co-R (doplňkové jazyky k R), RE, co-RE, VS (množina všech jazyků) a zdůvodněte.  (10b)