statnice:spolecne:reseni_prikladu_ze_zkousek_tal [OI-Wiki]

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== Ř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~~
statnice/spolecne/reseni_prikladu_ze_zkousek_tal.txt · Poslední úprava: 2025/01/03 18:29 (upraveno mimo DokuWiki)
Nahoru