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 16:13] destil |
statnice:spolecne:reseni_prikladu_ze_zkousek_tal [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 93: | Řádek 93: | ||
| ==== Popiš postup pro důkaz toho, že je něco NP úplné. Popiš redukci atd. Můžeš buďto všeobecně a nebo na příkladu nějakého převodu. ==== | ==== Popiš postup pro důkaz toho, že je něco NP úplné. Popiš redukci atd. Můžeš buďto všeobecně a nebo na příkladu nějakého převodu. ==== | ||
| - | ==== Co jsou to rekurzivní a rekurzivně spočetné jazyky. ==== | + | Při redukci musíme dokázat, že: |
| - | ==== Vztah mezi NP, rekurzivnými a rekurzivně spočtenými. ==== | + | * existuje algoritmus, kterým převedeme libovolnou instanci prvního problému na druhý |
| - | ==== U <| V (redukce) a vite, ze V je rekurzivne spocetny, co muzete rict o U (nadefinujte i redukci (trojuhelnicek)) ==== | + | * původní a převedená instance má vždy stejné ohodnocení ANO/NE |
| + | * nové instance jsou tvořeny v polynomiálním čase | ||
| + | |||
| + | Příklad převodu SAT na 3-SAT: | ||
| + | * SAT je problém splnitelnosti formulí v CNF, 3-SAT je problém splnitelnosti formulí v CNF, které mají 3 literály v každé klausuli | ||
| + | * musíme nalézt algoritmus, kterým se převede obecná formule v CNF do 3-CNF: | ||
| + | * pro klausule s ≤3 literály nemusíme nic dělat | ||
| + | * pro klausule s >3 literály přidáme další logické proměnné a rozsekáme to do trojic. První trojice obsahuje první původní, druhou původní a novou 1. Druhá trojice obsahuje negaci nové 1, třetí původní, novou 2 atd. Poslední trojice obsahuje negaci nové 1, původní předposlední a původní poslední. Tyto proměnné mez klausulemi přenášejí informaci, jestli byla původní klausule už splněna. | ||
| + | * 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í. | ||
| + | ==== 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. | ||
| + | |||
| + | 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ý. | ||
| ==== 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~~ | ||
