navigation
hledat
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:30] destil |
statnice:spolecne:reseni_prikladu_ze_zkousek_tal [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 105: | Řádek 105: | ||
| * výsledná formule 3-SAT problému je konjunkce těch s ≤3 literály s těmi transformovanými | * výsledná formule 3-SAT problému je konjunkce těch s ≤3 literály s těmi transformovanými | ||
| * 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í. | * 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í | ||
| - | ==== Co jsou to rekurzivní a rekurzivně spočetné jazyky. ==== | + | ==== Definuje NP-hard a uveď příklad, který není NP-complete ==== |
| - | * Rekurzivní jazyk, pokud existuje TS, který se na každém vstupu zastaví a jazyk rozhodne ANO/NE. | + | Problém je NP-hard, pokud existuje polynomiální redukce z NP-complete problému, ale nevíme jestli je také v NP. |
| - | * Rekurzivně spočetný jazyk, pokud existuje TS, které se zastaví na každé ANO instanci. Na NE instanci se může zacyklit. | + | |
| + | Např. halting problem není NP-complete. Ptá se na to "jestli program na daný vstup doběhne". Lze převést ze SATu pro ANO instance, ale pro NE instance je nerozhodnutelný. | ||
| - | ==== Vztah mezi NP, rekurzivnými a rekurzivně spočtenými. ==== | ||
| - | ==== U <| V (redukce) a vite, ze V je rekurzivne spocetny, co muzete rict o U (nadefinujte i redukci (trojuhelnicek)) ==== | ||
| ==== Definujte PSPACE a NPSPACE ==== | ==== 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 ==== | ==== 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 ==== | + | |
| + | ==== Vztah mezi P, NP, PSPACE, NPSPACE, EXP ==== | ||
| + | P ⊆ NP ⊆ (PSPACE=NPSPACE) ⊆ EXP | ||
| ==== Definujte tridu jazyku RP a ZPP ==== | ==== 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 ==== | ==== Reknete priklad jazyka patriciho do RP ==== | ||
| - | ==== Vyjmenovat dvě úlohy patřící do NPC, dvě úlohy patřící no NP ==== | + | 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é. |
| - | ==== 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 ==== | + | |
| - | ==== 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 ==== | + | |
| + | |||
| + | ==== 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. | ||
| + | * Rekurzivně spočetný jazyk, pokud existuje TS, které se zastaví na každé ANO instanci. Na NE instanci se může zacyklit. | ||
| + | |||
| + | ==== U <| V (redukce) a vite, ze V je rekurzivne spocetny, co muzete rict o U (nadefinujte i redukci (trojuhelnicek)) ==== | ||
| + | Redukce znamená že se ANO instance budou shodovat. U bude tedy také rekurzivně spočetný. Jestli se na NE instancích zacyklí nebo ne (rekurzivní jazyk) neřešíme | ||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
