====== Řešení příkladů ze zkoušek TAL ====== Disclaimer: Nejlíp se vždy na učím na příkladech. Takže místo biflování skript řeším příklady ze zkoušky jako přípravu na státnice. Odpovědi nejsou matematicky přesné, ale psané tak abych si je zapamatoval. --- //[[me@destil.cz|David Vávra (Destil)]] 2012/05/20 15:00// ===== Složitosti ===== ==== Co to znamená f(n) = O(g(n)) ==== Existuje kladná konstanta c, kde platí že f(n) ≤ c g(n) od nějakého přirozeného čísla n. ==== Definice Ω(g(n)). ==== Existuje kladná konstanta c, kde platí že f(n) ≥ c g(n) od nějakého přirozeného čísla n. ==== Co platí pro f(n) = Θ(g(n))? ==== Existují kladné konstanty c1 a c2, kde platí že c1 g(n) ≤ f(n) ≤ c2 g(n) od nějakého přirozeného čísla n. ==== Mame f(n) = 2n^(log n) + (log n)^n + 10n + 5, najdete nejmensi nejjednodussi a nejkrasnejsi g(n) takove, ze f(n) = O(g(n)) ==== g(n) = n^n ==== Je dána fce f(n) = n log^3 n + n^2 + ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = Θ(g(n)) ==== g(n) = n^2 ==== Prozkoumej T(n) = 2 T(n/2) + 1. Příklad na Master Theorem. ==== * n^(log_2(2)) = n * 1 = O(n) * prvni pripad => T(n)=Θ(n) ==== T(n) = 3T(n/4) + n^2 ==== * n^2 = Ω(n^(log_4(3)) * treti pripad => T(n) = Θ(n^2) ==== Zjisti složitost, co to dělá a dokaž správnost: ==== Give(m,n,s) s = 0; i = 1; while i <= n j = 1; while j <= m s = s + j*n; j = j + 1; end; i = i + 1; end; Output s O(n^2) //Nevím co alg. dělá// ===== Turingův stroj ====== ==== Co je to Turingův stroj a co to znamená, když přijímá jazyk L? ==== Turingův stroj je teoretický model počítače. Obsahuje: * Množinu stavů, počáteční stav a koncové stavy * Abecedu vstupních symbolů, výstupních symbolů a prázdný symbol (na pásce) * Přechodovou funkci, která mapuje stav a vstup na změnu stavu, výstup a posun pásky doleva nebo doprava TS přijímá jazyk L, pokus se úspěšně zastaví na každém slově z jazyka. ==== Nadefinujte nedeterministicky Turinguv stroj. ==== Stejná definice jako v minulé otázce ale přechodová funkce může obsahovat více přechodů pro daný vstup a stav. ==== Rozdíl mezi tím, když TM nějaký jazyk přijímá a když jej rozhoduje. ==== * Když TM jazyk přijímá tak každé slovo musí schválit. * Když TM jazyk rozhoduje tak každé slovo musí schválit nebo zamítnout, ale nezacyklit se. ==== Jaky je vztah mezi tridami jazyku rozpoznavanymi deterministickym a nedeterministickym Turingovym strojem? ==== Nedeterministický TS lze vždy převést na deterministický. Proto jazyk rozpoznávaný DTS je podmnožinout jazyka rozpoznávaného NTS. ==== Je dán jazyk L, jehož slova mají tvar: {0|1}* - libovolná posloupnost 0 a 1, kde ale musí být víc jedniček. Napiš TM, který rozhoduje tento jazyk. Stačí slovní popis nebo klidně i přechody. Napiš jeden netriviální stav jako přechodovou funkci.==== * Hledám 1 * Když najdu přepíšu na x, vracím se na začátek pásky a hledám 0 * Když nenajdu reject * Hledám 0 * Když najdu přepíšu na x, vrátím se na začátek pásky a hledám 1 * Když nenajdu accept Přechodová funkce pro úplně první stav q1 (hledání jedničky): * q1, 0 -> q1, 0, R * q1, 1 -> q2, x, R * q1, x -> q1, x, R * q1, blank -> reject ==== Vytvorte nedeterministicky Turinguv stroj, ktery prijima slova {w#w|w je {0,1}^*} (dve slova za sebou oddelene #). ==== [[https://docs.google.com/open?id=14SalVad6X1itN_KUIN6zLuEqPYqYNHdoBBRHBHTs8PZi8MyySW3ogyFtu3wo|Dobré vysvětlení TS, slide 17]] ===== NP ===== ==== Co je to třída NP a napiš jeden rozhodovací problém, který do ní nepatří. ==== Rozhodovací problém leží v NP pokud existuje nedeterministický Turingův stroj, který jí vyřeší a pracuje v polynomiálním čase. Ověření správného výsledku musí být v polynomiálním čase. Nepatří např. Existuje minimální kostra grafu menší než k? ==== Jaký je vztah mezi jazyky ROZHODOVANÝMI deterministickým TM a jazyky rozhodovanými nedeterministikým TM. ==== Rozhodování těchto jazyků je ve třídě P resp. NP. ==== Definovat třídu NPC ==== Problém je v NPC, pokud je v NP a zároveň na něj jdou polynomiálně převést všechny NP problémy. ==== 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. ==== Při redukci musíme dokázat, že: * existuje algoritmus, kterým převedeme libovolnou instanci prvního problému na druhý * 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 ==== * 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 ==== Kterýkoli NP problém, třeba obchodní cestující. ==== 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 ==== 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. * 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~~