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:57]
destil
+++ statnice:spolecne:reseni_prikladu_ze_zkousek_tal [2025/01/03 18:29] (aktuální)
@@ Řádek 106: / Řádek 106: @@
   * Při transformaci se přidává literálů-3 logických proměnných. Každá proměnná se přidává dvakrát. Při k klausulích to je 2*k*(s-3) nových proměnných. Převod je proto polynomiální.
 ==== Vyjmenovat dvě úlohy patřící do NPC, dvě úlohy patřící no NP ====
+NPC jsou podle definice také NP. Takže třeba:
+  * 3-SAT
+  * barvení grafu k-barvami
+  * subset sum problém (subset kde součet je 0)
+  * batoh
+  * obchodní cestující
 ==== Definuje NP-hard a uveď příklad, který není NP-complete ====
 Problém je NP-hard, pokud existuje polynomiální redukce z NP-complete problému, ale nevíme jestli je také v NP.
@@ Řádek 112: / Řá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.1337615874.txt.gz · Poslední úprava: 2025/01/03 18:25 (upraveno mimo DokuWiki)

Nahoru