Státnice - Informatika - Složitost (obory Matematická lingvistika a Softwarové systémy)

Toto je souhrn zkušebních okruhů k magisterským státnicím ze složitosti pro obory Softwarové systémy a Matematická lingvistika.

Rozsah látky

Pro obory Softwarové systémy a Matematická lingvistika je látka složitosti a vyčíslitelnosti spojena do jednoho okruhu. Oficiální výčet otázek je následující:

Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus. Dolní odhady pro složitost třídění (rozhodovací stromy). Amortizovaná složitost. Úplné problémy pro třídu NP, Cook-Levinova věta. Pseudopolynomiální algoritmy, silná NP-úplnost. Aproximační algoritmy a schémata. Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti. Algoritmicky nerozhodnutelné problémy (halting problem). Věty o rekurzi a jejich aplikace: příklady, Riceova věta.

Metody tvorby algoritmů

Rozděl a panuj

wen:Divide and conquer algorithm

1. Rozděl – podúlohy stejného typu … D(n)
2. Vyřeš – analogicky řeš (pod)úlohy … T(n)
3. Sjednoť – z řešení podúloh vytvoř řešení původní úlohy … S(n)

T(n)=D(n)+a*T(n/c)+S(n) pro n>n₀

T(n)=Θ(1) jinak

Master theorem, kuchařka Př.: Merge-sort T(n)=2T(n/2) + O(n) … O(n*log(n)) K-ty prvek T(n)=c*n/5+T(n/5)+(n-1)+T(7/10) … O(n)

Dynamické programování

Viz wen:Dynamic programming, Násobení matic od Jakuba Černého nebo dynamické programování podle kuchařky KSP.

Věta o dynamickém programování: papír Dynamické programování od Jiřího Vyskočila na strojilovych stránkách.

Využití:

1. "překrývání podproblému" (problém lze rozdělit na podproblémy, jejichž řešení se využívá opakovaně).
2. "optimální podstruktury" (optimální řešení lze zkonstruovat z optimálních řešení podproblémů).

Pozn.: Na hladovy algoritmus staci mat iba optimalne podstruktury.

Moznosti pristupu:

• Top-down - Klasicka rekurzia (kuchařka KSP: fibonacci s rekurziou a odpamatavanim).
• Bottom-up - Najprv riesim podproblemy, skladam do celkoveho riesenia (kuchařka KSP: fibonacci bez rekurzie).

V oboch pripadoch si mozem odpamatavat medzivysledky, prave ich znovupouzitie zlepsuje zlozitost algoritmu vid kuchařka KSP.

Příklady použití:

• Násobení matic
• Problém batohu
• Problém obchodního cestujícího
• Floyd-Warshallův algoritmus nejkratší cesty
• …

Hladový algoritmus

wen:Greedy algorithm

Matroid je usp. dvojice M=(S,I) sjňující podmínky:

1. S je neprázdná množ. prvků.
2. I je neprázdná množina podmnožin množiny S (nezávislých podmnožin - význam podle kontextu konkrétního matroidu) taková, že má dědičnou vlastnost (B in I & A subset B potom A in I).
3. I má výměnnou vlastnost (pokud A,B in I tž. |A|<|B| potom existuje x in B-A: A+{x} in I).

(Pozn. Pro vážený matroid se doplňuje funkce w: S->R₀⁺ pro podmnožiny S suma přes prvky.)

Všechny max. nezávislých množiny mají stejnou velikost.

Greedy(M,w):
0. A={}
1. Setřiď S sestupně
2. foreach x in S do //seřazené podle vah
     if A+{x} in I then //test na nezávislost!
       A=A+{x} //rozšíření
3. return A

Složitost:

1. Θ(n*log(n))
2. n*test na nezávislost (zde jsme ignorovali složitost rozšiřování A, asi snazší než test na nezávislost)

• Lemma 1: x in S tž. {x} not in I, potom neex. A in I tž. x in A.
• Lemma 2: S setříděný dle vah do nerost. posl. a x je první v S tž {x} in I. Potom existuje optimální A sub S tž. x in A.
• Lemma 3: x z lemma 2. pak pro matroid M je nalezení optima ekvivalentní hledání optima pro M' tž. S'={y in S; {x,y} in I} a I'={B subeq S-{x}; B+{x} in I} (kontrakce prvkem x).

Pozn.: Lemma 1–3 -> Greedy(M,w) vrací optimální množinu.

Pr.: Minimalní kostra grafu

Dolní odhady pro uspořádání (rozhodovací stromy)

podle http://ksvi.mff.cuni.cz/~topfer/ppt/Progr-10.pps

Třídíme-li s pomocí porovnávání, můžeme si výpočet znázornit binárním stromem. Začínáme v kořeni, v uzlech porovnáváme a větvíme, v listech máme setříděno. Pro každá vstupní data se výpočet někde odliší od ostatních, strom má $ n! $ listů (tolik je možných uspořádání množiny s $ n $ prvky.) Výška stromu je počet provedených porovnání při nejdelším výpočtu (v nejhorším případě) je alespoň $ \log_2(n!) $. (Úplný binární strom s $ k $ listy má výšku $ \log_2 k $, neúplný je vyšší.) Časová složitost třídícího algoritmu založeného na porovnávání proto nemůže být lepší než $ O(\log_2(n!)) = O(n\ \log n) $.

Podle Stirlingovy formule:

$ n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n} $ (to je ona)

$ O(\log_2 n!) = O(\log_2{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}) = O(n \log n) $ (Logaritmus odmocniny bude asymptoticky $ O(\log n) $, $ (n/e)^n $ bude $ O(n \log n) $, a požere to.)

• Pro mne snazší odhad: nⁿ ≥ n! ≥ (n/2)^n/2
• k-tý prvek nelze s porovnanim ziskat driv nez v O(n): musim mit alespon retizek s n-1 hranami.
• konvexni obal nelze lepe nez O(n*log(n)): pro [x,x²] umim tridit

Amortizovaná složitost

• typicky pro počítání realističtějčí časové složitosti operací nad datovými strukturami, zjišťujeme průměrný čas na 1 operaci při provádění posloupnosti N operací
• metody: 1)agregační (spočítá se nejhorší možný čas T(n) pro posloupnost n operací, amortizovaná cena 1 operace = T(n)/n), 2)účetní
• Triviální příklad s přičítáním jedničky k binárnímu čítači
• Příklad s dynamickým polem
• Fibonacciho haldy, (Invariant: Každý vrchol si drží jedno euro, co dostane od operace, co ho vytvořila)

Úplné problémy pro třídy NP, Cook - Levinova věta

see wen:NP-complete

Definice

• Co je NP těžký problém
• Co je NP úplný problém
• PSPACE uplnost
• Co je silně NP úplný problém

Cook - Levinova věta

Věta

Existuje NP-úplný problém

Lidsky vysvětlený důkaz Cook-Levinovy věty je zde pro problém KACHL. Původně je věta formulována pro problém SAT, ale snazší důkaz je pro KACHL a potom ukázat, že KACHL < SAT.

Myšlenka důkazu:

• Kachl je v NP (jistě jde verifikovat v polynomiálním čase)
• Kachl je NP těžký
  • Vezměme libovolný problém z NP, pak jeho nedeterministický turingáč řeší, jestli $ I \in L $ (zda řetězec $ I $ patří do jazyka $ L $, neboli zda jeho nedeterministický turingáč přijme daný vstup $ I $) v polynomiálním čase polynomu $ P $
  • Zkonstruujeme síť $ PxP $, zkonstruujeme vhodné kachličky (7 druhů) a obravení (barvy jsou z množiny $ ABECEDA \bigcup STAVY x ABECEDA \bigcup \lbrace q_l, q_r | q \in STAVY \rbrace $ tak, aby
    • Každý krok výpočtu kódoval jeden vykachličkovaný řádek
    • Každý řádek popisoval jeden krok výpočtu
• Tím jsme nalezli NP-úplný problém

Příklady NP-C

• NP-C problém: Kachličky, SAT; 3-SAT, 3-Color, Klika, NM, VP; VP, HK, TSP; VP, SP

Pochopitelnější důkazy jsou uvedené v Majerechových skriptách (ke stažení ve studnici).

Důkaz KACHL < SAT je také v Majerechových skriptách.

• SAT < 3-SAT

c=&c_i

k_j=x_j nebo -x_j

1. c_i=(k) potom c_i=(k|y|z)&(k|y|-z)&(k|-y|z)&(k|-y|-z)
2. c_i=(k₁|k₂) potom c_i=(k₁|k₂|y)&(-y|k₁|k₂)
3. c_i=(k₁|k₂|k₃) potom c_i=(k₁|k₂|k₃)
4. c_i=(k₁|k₂|...|k_m|...|k_n-1|k_n) potom c_i=(k₁|k₂|y₁)&...&(-y_m-2|k_m|y_m-1)&...&(-y_n-3|k_n-1|k_n)

• SAT<Klika

hrana = mezi každými dvěma proměnnými z různých klauzulí, pokud s nejedná o vzájemno negaci(x a -x).

• SAT<VP

1. proměnné: množina hran mezi x_i a -x_i (pro každou proměnou 1 hrana)
2. klazule: c_i obsahujíce n proměnných definuje úplný graf nad n vrcholy
3. spojí se příslušné vrcholy z bodu (1) s vrcholem z (2) //x s x resp. -x s -x

PetrC: Tomu nerozumím, ale znám lepší: nejprve se podívejte na SAT<NM, který vybere nezávislou množinu A. No a množina A'=V-A je VP. Takže algoritmem pro vrcholové pokrytí nalezneme A' a V-A' odpovídá ohodnocení proměnných v SAT. Důkaz viz slidy z přednášek pana Savického na FF UK.

• SAT<NM

1. jako bod (2) u SAT<VP
2. spojí se vrcholy, které se vzájemně vylučují //tj. x s -x

Priklad PSPACE uplneho problemu

• Koubek chtel u statnic neco s obecnou booleovskou formuli

Polynomiální hierarchie

see polynomiální hierarchie, wen:Polynomial hierarchy

NP(C) je třída jazyků, které v polynomiálním čase rozpozná NTS s orákulem detekujícím zda jeho vstup patří do nějakého jazyka z C.

NP(P) je potom třída jazyků, které v polynomiálním čase pozná NTS s orákulem na řešení problémů z P. NP(NP) řeší NTS s orákulem na řešení problémů z NP.

• Pozn: P(P)=P ... jasné (simuluji si sam vypocet orakula a zretezim), NP(NP)=? ... nevime! (nemuzem pouzit postup jako u P(P), vypocet simulace nema jednu vetev).

Pro každou množinu jazyků platí $ P(C) \subseteq NP(C) \subseteq PSPACE(C) $.

Polynomiální hierarchie

Máme $ \Sigma_0 = P $, $ \Sigma_{i+1} = NP(\Sigma_i) $

1. $ \Sigma_0 = P $
2. $ \Sigma_1 = NP(P) = NP $
3. $ \Sigma_2 = NP(NP) $

Celá hierarchie je $ PH = \bigcup_{i=0}^\infty {\Sigma_i} $.

Pseudopolynomiální algoritmy

see wen:Pseudo-polynomial time

• Nechť je dán rozhodovací problém (úloha, jejímž výstupem je ANO/NE) π a jeho instance I. Def:
  • kód(I) .. délka zápisu I v nějakém kódování (např. binárním)
  • max(I) .. velikost největšího čísla v I (ne jeho kódu)

• Alg. řešící π se nazývá pseudopolynomiální, pokud je jeho čas. slož. omezena polynomem v proměnných kód(I) a max(I).
• Pokud je π tž. forall I: max(I)≤p(kód(I)) potom pseudopolynomyální=polynomyální
• Problémy, pro které obě skupiny nesplývají se nazývají číselné. tj. neexistuje polynom p tž. viz výš
• Ne však každý číselný problém lze řešit pseudopolynomiálně (tzv. silně NP-uplné problémy)
  • π_p omezení na podproblém π tž. platí max(I)≤p(kód(I)). Pokud π_p NPÚ, tak π S-NPÚ
  • Klika, TSP je S-NPÚ

Aproximační algoritmy a schémata

see wen:Approximation algorithm, kus na straně 12 z [1]

• Předpoklady: Každé řešení má nezápornou hodnotu.

• Značení: $ n $ velikost zadání, C* hodnota optimálního řešení, C hodnota aproximovaného řešení

Definice

• Poměrová chyba: $ \rho(n) \geq max\left\{ \frac{C^*}{C}, \frac{C}{C^*} \right\} $
• Relativní chyba: $ \epsilon(n) \geq \frac{|C-C^*|}{C^*} $
  • Pozn.: Pokud jsou $ \rho(n),\epsilon(n) $ konstanty, tak se obyčejně parametr $ n $ vynechává.

• Aproximační schéma (AS) pro optimalizační úlohu je aproximační alg., který pro vstup délky $ n $ a číslo $ \epsilon>0 $ najde řešení s relativní chybou $ \epsilon $. Může být exponenciální vzhledem k $ n $ i $ 1/\epsilon $.

• Polynomiální AS: AS, které je polynomiální vzhledem k $ n $.

• Úplně Polynomiální AS (ÚPAS): PAS, které je polynomiální i k $ 1/\epsilon $.

Fakta

• $ \rho(n) \geq 1 $
• $ \epsilon(n) \leq \rho(n) - 1 $

Příklady

Vrcholové pokrytí

• ρ=2.
• Stačí v cyklu: Vždy vzít ze zbylých hran jednu. Oba její vrcholy přidat do pokrytí a odstranit ostatní incidentní hrany.

DK: Ať je F množina všech hran vybraných během algoritmu a C nalezené pokrytí. Platí: |C|=2*|F| (každá hrana má 2 vrcholy) a navíc |F|≤|C*| (optimální řešení musí pokrýt i hrany z F).

|C|=2*|F| a |F|≤|C*| potom |C|≤2*|C*|

ÚPAS pro součet podmnožiny

• Je dána konečná podmnožina množ. přirozených čísel A s prvky x_i, hodnota součtu t a aproximační parametr 0<ε<1.
• Součet L+x označuje seznam vzniklý ze seznamu L přičtením hodnoty x ke všem jeho položkám. Zachovává uspořádání.
• Prořezat seznam L s parametrem δ znamená, že pro každý odstraněný prvek y existuje v prořezaném seznamu L' prvek z splňující: (1-δ)y ≤ z ≤ y. Zachovává uspořádání.
• Algoritmus řešení:

APPROX_SP(A,t,ε):

L0=(0)
for i = 1 to n do
  Li=MERGE(Li-1, Li-1+xi) //vytvoří nový a slitím původního a součtu původního
  Li=PRUNE(Li, ε/n) //prořeže
  Li=CROP(Li, t) //odstraní prvky větší než t
end
return Ln //vrátí řešení

• Prořezávání s parametrem ε/n zajišťuje nepřekročení výsledné meze chyby ε, která se může kumulativně zvětšovat v každé iteraci.
• Časová složitost algoritmu je $ O\left(\frac{n^2\cdot log~t}{\epsilon}\right) $.

Obchodní cestující:

• Pro TSP na úplném grafu s troj. nerovností (ΔTSP) ex. aprox. algoritmus s poměrovou chybou ρ=2.
  • Pro ΔTSP platí: $ \forall u,v,w\in V: c(u,v)\leq c(u,w)+c(w,v) $. Je to vůbec NP-těžké? ANO: Lze řešit HK pomocí ΔTSP následujícím způsobem: Graf se doplní na K_|V| a váhy se definují $ c(e)=1\mbox{ pokud }e\in E $, $ c(e)=2\mbox{ pokud }e\notin E $. Potom řešení hledá ΔTSP pro k=|V|.
  • Řešení problému ΔTSP:

1. Nalezení min. kostry (např. Primův alg. - staví se na jedna komponenta postupným připojováním vrcholů) → kostra T
2. Zvolí se vrchol u a preorder (pořadí prvního navštívení vrcholu) se očíslují vrcholy pomocí DFS(T,u) → pořadí vrcholů dané očíslováním.
3. Výsledná HK je určena očíslováním z kroku 2.

DK: Ať H* je opt. HK a T je minimální kostra, potom c(T)≤c(H*).

W je úplná procházka po T (viz krok 2.), potom c(W)=2*c(T)≤c(H*).

Z W se vyrobí H nahrazováním cest délek ≥2 jednou hranou (vracení se v DFS průchodu a první dopředný krok). Jelikož zde platí trojúhelníková nerovnost, platí také: c(H)≤c(W).

Platí c(H)≤c(W)=2*c(T)≤c(H*) potom ρ≤2.

• Ať ρ≥1 je konstanta. Pokud P≠NP, potom neexistuje polynomiální aproximační algoritmus řešící obecný TSP s poměrovou chybou ρ.
  • Pokud by existoval, umí řešit HK (ten je NPÚ). Graf se doplní na K_|V| a váhy hran se definují:

$ c(e) = \begin{cases} 1, & \mbox{pokud }e\in E \\ \rho\cdot n+1, & \mbox{pokud }e\notin E \end{cases} $

Nyní algoritmus buď vydá HK délky n (→Odpověď na HK v původním grafu je ANO), nebo vydá HK délky >ρ·n (→Odpověď na HK v původním grafu je NE).

Materiály

• Skripta Ladislava Strojila
• Slajdy z přednášek a další materiály na mff.modry.cz
• Algorithms – Dasgupta S., Papadimitriou C.H., Vazirani U.V., Berkeley
• Complexity Theory: A Modern Approach (draft) – Arora S., Barak B., Princeton