====== Termín 26.5.2011 ======

Čas na vypracování 1 hodinka (dá se to stihnout)

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.

Ústní probíhá tak, že s Vámi projde písemku a pak zadá nějaký příklad (vlastně úplně cokoliv) na jeho vypracování máte mraky času, protože se během té doby  věnuje jiným kolegům.

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.

~~DISCUSSION~~