navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m01tal:zkouska-2010-06-07 [2010/06/23 17:33] founemi2 |
courses:a4m01tal:zkouska-2010-06-07 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 5: | Řádek 5: | ||
| 1) | 1) | ||
| a) Co platí pro f(n) = Theta(g(n))? | a) Co platí pro f(n) = Theta(g(n))? | ||
| - | |||
| b) Je dána fce f(n) = n log^3 n + n^2 + ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = theta(g(n)) | b) Je dána fce f(n) = n log^3 n + n^2 + ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = theta(g(n)) | ||
| - | |||
| c) Prozkoumej T(n) = 2 T(n/2) + 1. Příklad na Master Theorem. | c) Prozkoumej T(n) = 2 T(n/2) + 1. Příklad na Master Theorem. | ||
| 2) Je dán algoritmus | 2) Je dán algoritmus | ||
| - | Give(m,n,s) | + | Give(m,n,s) |
| - | + | s = 0; i = 1; | |
| - | s = 0; i = 1; | + | while i <= n |
| - | + | j = 1; | |
| - | while i <= n | + | while j <= m |
| - | + | s = s + j*n; | |
| - | j = 1; | + | j = j + 1; |
| - | + | end; | |
| - | while j <= m | + | i = i + 1; |
| - | + | end; | |
| - | s = s + j*n; | + | Output s |
| - | + | ||
| - | j = j + 1; | + | |
| - | + | ||
| - | end; | + | |
| - | + | ||
| - | i = i + 1; | + | |
| - | + | ||
| - | end; | + | |
| - | + | ||
| - | Output s | + | |
| a) časová složitost | a) časová složitost | ||
| - | |||
| b) najdi obecný zápis funkce s | b) najdi obecný zápis funkce s | ||
| - | |||
| c) dokaž správnost b) | c) dokaž správnost b) | ||
| 3) | 3) | ||
| a) Co je to Turingův stroj a co to znamená, když přijímá jazyk L? | a) Co je to Turingův stroj a co to znamená, když přijímá jazyk L? | ||
| - | |||
| b) Rozdíl mezi tím, když TM nějaký jazyk přijímá a když jej rozhoduje. | b) Rozdíl mezi tím, když TM nějaký jazyk přijímá a když jej rozhoduje. | ||
| - | |||
| c) Je dán jazyk L, jehož slova mají tvar: {0|1}* - libovolná posloupnost 0 a 1, kde ale musí být víc jedniček. | c) Je dán jazyk L, jehož slova mají tvar: {0|1}* - libovolná posloupnost 0 a 1, kde ale musí být víc jedniček. | ||
| - | |||
| Napiš TM, který rozhoduje tento jazyk. Stačí slovní popis nebo klidně i přechody. | Napiš TM, který rozhoduje tento jazyk. Stačí slovní popis nebo klidně i přechody. | ||
| - | |||
| {{:courses:a4m01tal:tm.jpg|}} | {{:courses:a4m01tal:tm.jpg|}} | ||
| - | |||
| d) Napiš jeden netriviální stav z c) jako přechodovou funkci. | d) Napiš jeden netriviální stav z c) jako přechodovou funkci. | ||
| 4) | 4) | ||
| a) Co je to třída NP a napiš jeden rozhodovací problém, který do ní nepatří. | a) Co je to třída NP a napiš jeden rozhodovací problém, který do ní nepatří. | ||
| - | |||
| b) Patří randomizovaný quick sort do RP nebo ZPP? Co je to RP a ZPP? | b) Patří randomizovaný quick sort do RP nebo ZPP? Co je to RP a ZPP? | ||
| - | |||
| c) Popiš postup pro důkaz toho, že je něco NP úplné. Popiš redukci atd. Můžeš buďto všeobecně a nebo na příkladu nějakého převodu. | c) Popiš postup pro důkaz toho, že je něco NP úplné. Popiš redukci atd. Můžeš buďto všeobecně a nebo na příkladu nějakého převodu. | ||
| - | |||
| d) Co jsou to rekurzivní a rekurzivně spočetné jazyky. | d) Co jsou to rekurzivní a rekurzivně spočetné jazyky. | ||
| - | |||
| e) Příklad rekurzivního jazyku, který není rekurzivně spočetný. | e) Příklad rekurzivního jazyku, který není rekurzivně spočetný. | ||
