Toto je souhrn zkušebních okruhů k <Státnice> ze složitosti pro obory <Státnice%20-%20Informatika%20-%20I2:%20Softwarové%20systémy> a <Státnice%20-%20Informatika%20-%20I3:%20Matematická%20lingvistika>.

Rozsah látky

Pro obory <Státnice%20-%20Informatika%20-%20I2:%20Softwarové%20systémy> a <Státnice%20-%20Informatika%20-%20I3:%20Matematická%20lingvistika> 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.

[[Státnice - Metody tvorby algoritmů|Metody tvorby algoritmů]]

Rozděl a panuj

wen:Divide%20and%20conquer%20algorithm

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(nlog(n)) K-ty prvek T(n)=cn/5+T(n/5)+(n-1)+T(7/10) … O(n)

Dynamické programování

Viz wen:Dynamic%20programming, 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

• wcs:Problém_obchodního_cestujícího

• Floyd-Warshallův algoritmus nejkratší cesty

• …

Hladový algoritmus

wen:Greedy%20algorithm

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):

1. A={}

2. Setřiď S sestupně

3. foreach x in S do //seřazené podle vah if A+{x} in I then //test na nezávislost!

   *A*=*A*+{*x*} //rozšíření
   

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

[[Státnice - Odhady složitosti|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(nlog(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)

[[Státnice - NP-úplnost|Ú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 <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 <Studnice%20vědomostí>).

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

*SAT < 3-SAT

:c=&c_i :k_j=x_j nebo -x_j

#c_i=(k) potom c_i=(k|y|z)&(k|y|-z)&(k|-y|z)&(k|-y|-z) #c_i=(k₁|k₂) potom c_i=(k₁|k₂|y)&(-y|k₁|k₂)

#c_i=(k₁|k₂|k₃) potom c_i=(k₁|k₂|k₃) #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 #proměnné: množina hran mezi x_i a -x_i (pro každou proměnou 1 hrana)

#klazule: c_i obsahujíce n proměnných definuje úplný graf nad n vrcholy #spojí se příslušné vrcholy z bodu (1) s vrcholem z (2) //x s x resp. -x s -x

:User: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 #jako bod (2) u SAT<VP

#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 <Složitost%20II#Polynomiální%20hierarchie>, wen:Polynomial%20hierarchy

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%20time

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

[[Státnice - Aproximační algoritmy a schémata|Aproximační algoritmy a schémata]]

:see wen:Approximation%20algorithm, kus na straně 12 z http://urtax.ms.mff.cuni.cz/%7Enovap2am/poznamky/slozitost.sxw

*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,ε):<br>

L₀=(0) for i = 1 to n do

L_i=MERGE(L_i-1, L_i-1+x_i) //vytvoří nový a slitím původního a součtu původního L_i=PRUNE(L_i, ε/n) //prořeže

L_i=CROP(L_i, t) //odstraní prvky větší než t end

return L_n //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í

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 7: c(e)=1\̲m̲b̲o̲x̲{ pokud }e\in E

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 7: c(e)=2\̲m̲b̲o̲x̲{ pokud }e\noti…

#Nalezení min. kostry (např. Primův alg. - staví se na jedna komponenta postupným připojováním vrcholů) → kostra T #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.

#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)=2c(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)=2c(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

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

Category:%20Státnice%20Informatika%20Mgr.