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-14 [2010/06/14 20:00] grepfruit created |
courses:a4m01tal:zkouska-2010-06-14 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 2: | Řádek 2: | ||
| a) Co to znamená f(n) = Omikron(g(n)) | a) Co to znamená f(n) = Omikron(g(n)) | ||
| b) Mame f(n) = 2n^(log n) + (log n)^n + 10n + 5, najdete nejmensi | b) Mame f(n) = 2n^(log n) + (log n)^n + 10n + 5, najdete nejmensi | ||
| - | nejjednodussi a nejkrasnejsi g(n) takove, ze f(n) = Omikron(g(n)) | + | nejjednodussi a nejkrasnejsi g(n) takove, ze f(n) = Omikron(g(n)) |
| c) T(n) = 3T(n/4) + n^2 - slozitost | c) T(n) = 3T(n/4) + n^2 - slozitost | ||
| 2) | 2) | ||
| a) Byl algoritmus zapsany v pseudokodu - napsat vystup | a) Byl algoritmus zapsany v pseudokodu - napsat vystup | ||
| - | b) Napiste slozitost | + | b) Napiste slozitost toho algoritmu |
| c) Co vlastne algoritmus dela? (Radil cisla) | c) Co vlastne algoritmus dela? (Radil cisla) | ||
| - | d) Dokazte ze dela to, jste napsali, ze dela. | + | d) Dokazte ze dela to, co jste napsali, ze dela. |
| 3) | 3) | ||
| a) Nadefinujte nedeterministicky Turinguv stroj. | a) Nadefinujte nedeterministicky Turinguv stroj. | ||
| b) Vytvorte nedeterministicky Turinguv stroj, ktery prijima slova {ww|w je {0,1}^*} (zkratka dve stejna slova za sebou) | b) Vytvorte nedeterministicky Turinguv stroj, ktery prijima slova {ww|w je {0,1}^*} (zkratka dve stejna slova za sebou) | ||
| c) Popiste stavy (pouzijte prechodovou funkci), kterymi automat projde pri prijimani 101101 | c) Popiste stavy (pouzijte prechodovou funkci), kterymi automat projde pri prijimani 101101 | ||
| - | d) Neco jako: vztah mezi deterministickym a nedeterministickym turingem? | + | d) Jaky je vztah mezi tridami jazyku rozpoznavanymi deterministickym a nedeterministickym Turingovym strojem? |
| 4) | 4) | ||
| - | a) Reknete priklad jazyka patriciho do RP | + | a) Definujte PSPACE a NPSPACE |
| - | b) Definujte tridu jazyku RP a ZPP | + | b) Reknete priklad jazyka patriciho do NPSPACE |
| - | c) Reknete priklad jazyka patriciho do NPSPACE | + | c) Vztah mezi P, NP, PSPACE, NPSPACE |
| - | d) Vztah mezi P, NP, PSPACE, NPSPACE | + | d) Vztah mezi rekurzivne spocetnymi jazyky a NPSPACE |
| - | e) Vztah mezi rekurzivne spocetnymi jazyky a NPSPACE | + | e) Definujte tridu jazyku RP a ZPP |
| - | f) | + | f) Reknete priklad jazyka patriciho do RP |
| g) U <| V (redukce) a vite, ze V je rekurzivne spocetny, co muzete rict o U (nadefinujte i redukci (trojuhelnicek)) | g) U <| V (redukce) a vite, ze V je rekurzivne spocetny, co muzete rict o U (nadefinujte i redukci (trojuhelnicek)) | ||
