Rozdíly

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

--- statnice:spolecne:reseni_prikladu_ze_zkousek_tal [2012/05/21 17:59]
destil
+++ statnice:spolecne:reseni_prikladu_ze_zkousek_tal [2025/01/03 18:29] (aktuální)
@@ Řádek 119: / Řádek 119: @@
 ==== Definujte PSPACE a NPSPACE ====
+  * PSPACE - existuje deterministický TS, který pracuje s polynomiální paměťovou složitostí
+  * NPSPACE - existuje nedeterministický TS, který pracuje s polynomiální paměťovou složitostí
+Podle Sawitchovy věty PSPACE=NPSPACE
 ==== Reknete priklad jazyka patriciho do NPSPACE ====
-==== Vztah mezi P, NP, PSPACE, NPSPACE ====
+Kterýkoli NP problém, třeba obchodní cestující.
-==== Vztah mezi rekurzivne spocetnymi jazyky a NPSPACE ====
-==== Třída EXP je třída všech jazyků přijímaných TS v exponenciálním čase (nebo něco v tom smyslu), určit vztah mezi EXP, NPSPACE, NP, co-NP ====
+==== Vztah mezi P, NP, PSPACE, NPSPACE, EXP ====
+P ⊆ NP ⊆ (PSPACE=NPSPACE) ⊆ EXP
 ==== Definujte tridu jazyku RP a ZPP ====
+Jazyk patří do RP, pokud ho rozhoduje randomizovaný TS (TS s další náhodnou páskou) a ANO instance odhalí s pravděpodobností > 50%.
+Jazyk patří do ZPP, když rozhodne jazyk randomizovaným TS pro ANO i NE instance.
 ==== Reknete priklad jazyka patriciho do RP ====
-==== 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 ====
+Rabin-Millerův test přijímá složená čísla s pravděpodobností 75% a pro žádné prvočíslo neprohlásí, že je složené.
 ==== Co jsou to rekurzivní a rekurzivně spočetné jazyky. ====
   * Rekurzivní jazyk, pokud existuje TS, který se na každém vstupu zastaví a jazyk rozhodne ANO/NE.

statnice/spolecne/reseni_prikladu_ze_zkousek_tal.1337615995.txt.gz · Poslední úprava: 2025/01/03 18:25 (upraveno mimo DokuWiki)

Nahoru