Toto je starší verze dokumentu!

1) (20b) a) Definice Θ a Ω b) kdyz f(n) = O(g(n)) plati f(n)² = O(g(n)²) c) ?? d) master theorem T(n) = 4T(n/3) + lg(n)

2) (25b) a) definice DTM, definice kdyz je prijimany jazyk b) navrhnete DTM, ktery prijima slova ve tvaru w0^n , kde n je delka w c) vypocet TM nad slovem 1000

3) (35b) a) jaky je rozdil mezi tridou jazyku tvorenou jazyky prijimanymi DTM a NTM? (zadny, obe jsou R) b) definice P, NP, ZPP, co-NP c) ?? d) ?? e) ?? f) ??