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