navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m01tal:zkouska-2011-06-16 [2011/06/17 18:17] andelmi2 vytvořeno |
courses:a4m01tal:zkouska-2011-06-16 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 11: | Řádek 11: | ||
| 1) | 1) | ||
| - | a) Co platí pro f(n) = Theta(g(n))? | + | a) Definuj f(n) = Omega(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) = lg(n!) + (lg n)^4 + n^2 ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = Omega(g(n)) |
| - | c) Prozkoumej T(n) = 2 T(n/2) + 1. Příklad na Master Theorem. | + | c) Řeš T(n) = 7 T(n/9) + nlogn |
| 2) | 2) | ||
| - | a) Co je to Turingův stroj a co to znamená, když přijímá jazyk L? | + | a) Definuj nedeterministický TM. Definuj, co znamená, že tento TM přijímá jazyk L. |
| - | b) Rozdíl mezi tím, když TM nějaký jazyk přijímá a když jej rozhoduje. | + | b) TM přijímající L={w0w | w je binární} Nejprve slovně popiš, pak tabulky nebo přechodový diagram (body jsou i za zprávný popis stroje, klidně i poloviční počet bodů z příkladu) |
| - | 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) Napiš výpočet přijetí slova 11011 |
| - | Napiš TM, který rozhoduje tento jazyk. Stačí slovní popis nebo klidně i přechody. | + | |
| - | d) Napiš jeden netriviální stav jako přechodovou funkci. | + | |
| 3) | 3) | ||
| - | a) Co je to třída NP a napiš jeden rozhodovací problém, který do ní nepatří. | + | a) Definuj jazyky RP a ZPP. Příklad jazyka RP. |
| - | b) 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. | + | b) Jaký je vztah mezi jazyky ROZHODOVANÝMI deterministickým TM a jazyky rozhodovanými nedeterministikým TM. |
| - | c) Co jsou to rekurzivní a rekurzivně spočetné jazyky. | + | c) Třída co-RE je doplněk jazyka RE. Co platí pro třídy R, RE, co-RE a třídu úplně všech jazyků VS. Napiš všechny inkluze, které platí. Pokud jsou některé tyto inkluze ostré, uveď příklad jazyka patřícího do jedné třídy a nepatřícího do druhé. |
| - | d) Vztah mezi NP, rekurzivnými a rekurzivně spočtenými. | + | Možná ještě nějaké body, už si nepvzpomínám |
