Ř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. — David Vávra (Destil) 2012/05/20 15:00

Existuje kladná konstanta c, kde platí že f(n) ≤ c g(n) od nějakého přirozeného čísla n.

Existuje kladná konstanta c, kde platí že f(n) ≥ c g(n) od nějakého přirozeného čísla 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.

g(n) = n^n

g(n) = n^2

• n^(log_2(2)) = n
• 1 = O(n)
• prvni pripad ⇒ T(n)=Θ(n)

• n^2 = Ω(n^(log_4(3))
• treti pripad ⇒ T(n) = Θ(n^2)

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 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.

Stejná definice jako v minulé otázce ale přechodová funkce může obsahovat více přechodů pro daný vstup a stav.

• 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.

Nedeterministický TS lze vždy převést na deterministický. Proto jazyk rozpoznávaný DTS je podmnožinout jazyka rozpoznávaného NTS.

• 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

Dobré vysvětlení TS, slide 17

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?

Rozhodování těchto jazyků je ve třídě P resp. NP.

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.

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í.

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í

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ý.

• 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

Kterýkoli NP problém, třeba obchodní cestující.

P ⊆ NP ⊆ (PSPACE=NPSPACE) ⊆ EXP

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.

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é.

• 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.

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