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-05 [2012/06/06 11:09] rychtluk vytvořeno |
courses:a4m01tal:zkouska-2012-06-05 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| ====== Termín 5.6.2012 ====== | ====== Termín 5.6.2012 ====== | ||
| - | 1) | + | Bylo na to 90 minut. Demlová mi u ústní říkala, že to asi přehnala, že měla dát víc času - že si spousta lidí stěžovalo, že to nestíhali. |
| - | a) Definujte theta a velke O | + | |
| + | 1) (20b) | ||
| + | a) Definujte f(n) = theta(g(n)) a f(n) = omikron(g(n)) | ||
| 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) | 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 | c) Pokud plati f(n) nalezi theta g(n), plati pak 2 ^ f(n) nalezi theta 2 ^ g(n) ? Zduvodnete | ||
| - | d) master theorem | + | d) master theorem T(n) = 2*T(n/2) + lg(n) |
| + | |||
| + | 2) (25b) | ||
| + | a) Definujte DTM a definujte co to znamena, ze TM prijma/rozhoduje (5b) | ||
| + | b) Vytvorte TM tabulkou/grafem pro slovo w = {0, 1}*, kde TM prijme slovo, ve kterem je vice 0 nez 1 (15b) | ||
| + | c) Demonstrace prijmuti slova w = 10100 (chtela videt stav TM v kazdem kroku) (5b) | ||
| + | |||
| + | 3) (35b) | ||
| + | a) Definujte NP a P. | ||
| + | b) Definujte paměťovou složitost Turingova stroje. | ||
| + | c) Definujte ZPP + možná ještě něco. | ||
| + | d) Definujte co-NP + jaký je vztah co-NP a ZPP. | ||
| + | e) Zadány úlohy U, V, W. Platí U <| V <| W (<| je polynomiální redukce). U je 2-barevnost, W je existence hamiltonovské kružnice, V se neví. Napište nejsilnější tvrzení, které platí pro úlohu V a zdůvodněte. | ||
| + | f) Popište vzájemné vztahy R (rekurzivní jazyky), co-R (doplňkové jazyky k R), RE, co-RE, VS (množina všech jazyků) a zdůvodněte. (10b) | ||
| - | 2) | + | ~~DISCUSSION~~ |
| - | 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. | ||
