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:01] grepfruit |
courses:a4m01tal:zkouska-2010-06-14 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 13: | Řádek 13: | ||
| 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)) | ||
