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)

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

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) ??