===== 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 a zduvodnete...

c) vypocet TM nad slovem 1000




===== 3) (35b) =====


a) jaky je rozdil mezi tridou jazyku tvorenou jazyky prijimanymi DTM a NTM? (zadny, obe jsou RE)

b) definice P, NP, ZPP, co-NP

c) ??

d) ??

e) ??

f) ??




~~DISCUSSION~~