Toto je starší verze dokumentu!
1)
a) Definujte theta a velke O 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
2)
a) Definujte DTM a definujte co to znamena, ze TM prijma/rozhoduje b) Vytvorte TM tabulkou/grafem pro slovo w = {0, 1}*, kde TM prijme slovo, ve kterem je vice 0 nez 1 c) Demonstrace prijmuti slova w = 10100 (chtela videt stav TM v kazdem kroku)
3)
a) Definujte NP a P b) c) d) e) f) Definujte R, coR, RE, coRE, VS (mnozina vsech jazyku) a jejich vzajemne vztahy a zduvodnete.