navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m01tal:zkouska-2012-06-25 [2012/06/26 11:59] zwick vytvořeno |
courses:a4m01tal:zkouska-2012-06-25 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | 1) (20b) | + | ===== 1) (20b) ===== |
| + | |||
| + | |||
| a) Definice Θ a Ω | a) Definice Θ a Ω | ||
| - | b) kdyz f(n) = O(g(n)) plati f(n)² = O(g(n)²) | + | |
| + | b) kdyz f(n) = O(g(n)), plati f(n)² = O(g(n)²) ? | ||
| c) ?? | c) ?? | ||
| + | |||
| d) master theorem T(n) = 4T(n/3) + lg(n) | d) master theorem T(n) = 4T(n/3) + lg(n) | ||
| - | 2) (25b) | + | |
| + | |||
| + | ===== 2) (25b) ===== | ||
| + | |||
| a) definice DTM, definice kdyz je prijimany jazyk | a) definice DTM, definice kdyz je prijimany jazyk | ||
| - | b) navrhnete DTM, ktery prijima slova ve tvaru w0^n , kde n je delka w | + | |
| + | b) navrhnete DTM, ktery prijima slova ve tvaru w0^n , kde n je delka w a zduvodnete... | ||
| c) vypocet TM nad slovem 1000 | 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) | + | |
| + | |||
| + | ===== 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 | b) definice P, NP, ZPP, co-NP | ||
| + | |||
| c) ?? | c) ?? | ||
| + | |||
| d) ?? | d) ?? | ||
| + | |||
| e) ?? | e) ?? | ||
| + | |||
| f) ?? | f) ?? | ||
| + | |||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
