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 12:01] zwick |
courses:a4m01tal:zkouska-2012-06-25 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 5: | Řádek 5: | ||
| 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) ?? | ||
| Řádek 18: | Řádek 18: | ||
| 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 | ||
| Řádek 28: | Řádek 28: | ||
| - | a) jaky je rozdil mezi tridou jazyku tvorenou jazyky prijimanymi DTM a NTM? (zadny, obe jsou R) | + | 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 | ||
