Toto je starší verze dokumentu!


Termín 5.6.2012

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.
courses/a4m01tal/zkouska-2012-06-05.1338973754.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)
Nahoru
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0