Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m01tal:zkouska-2015-06-08 [2015/06/10 17:05]
dothang
+++ courses:a4m01tal:zkouska-2015-06-08 [2025/01/03 18:28] (aktuální)
@@ Řádek 1: / Řádek 1: @@
 ===== Zkouška 8.6.2015 =====
 ===1.===
-a. definovat malé o a omegu a vztah mezi nimi
+a. definovat malé o a omegu a vztah mezi nimi \\
+b. \\
-b.
+c. Master theorem t(n) = 4T(n/3) + n^2*logn \\
-c. Master theorem t(n) = 4T(n/3) + n^2*logn
 ===2.===
-a. definovat deterministicý Turingův stroj, vysvětlit krok Turingova stroje
+a. definovat deterministicý Turingův stroj, vysvětlit krok Turingova stroje \\
+b. vytoviřit DTM, který realizuje  pro |w| <= 2 -> w a pro |w| > 2 -> w^R1^(k-2), kde w^R je revers slova w a k je délka slova w \\
-b. vytoviřit DTM, který realizuje  pro |w| <= 2 -> w a pro |w| > 2 -> w^R1^(k-2), kde w^R je revers slova w a k je délka slova w
+c. ukázat výpočet na w = 100 \\
-c. ukázat výpočet na w = 100
 ===3.===
-a. Co znamená že je jazyk/úloha P, NP, NPC, co-NP
+a. Co znamená že je jazyk/úloha P, NP, NPC, co-NP \\
+b. Pro každou třídu výše uvedenou říct zdali je/není algoritmus -> ověření zdali daný graf jde obarvit k-barvami. \\
-b. Pro každou třídu výše uvedenou říct zdali je/není algoritmus -> ověření zdali daný graf jde obarvit k-barvami.
+c. Definovat paměťovou složitost Turingkova stroje \\
+d. PSPACE a NSPACE, jejich vztah \\
-c. Definovat paměťovou složitost Turingkova stroje
+e. Podobná otázka jako z 5.6.2014 3f \\
+f. Byl dán jazyk rekurzivní a co-RE. Jaký je jejich vztah \\
-d. PSPACE a NSPACE, jejich vtah
-e. Podobná otázka jako z 5.6.2014 3f
-f. Byl dán jazyk rekurzivní a co-RE. Jaký je jejich vztah

courses/a4m01tal/zkouska-2015-06-08.1433948707.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru