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.
Obsah
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
- Rozděl – podúlohy stejného typu … D(n)
- Vyřeš – analogicky řeš (pod)úlohy … T(n)
- 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>n0
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í:
- "překrývání podproblému" (problém lze rozdělit na podproblémy, jejichž řešení se využívá opakovaně).
- "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
Matroid je usp. dvojice M=(S,I) sjňující podmínky:
- S je neprázdná množ. prvků.
- 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).
- 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->R0+ 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:
- Θ(n*log(n))
- 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)
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: nn ≥ 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,x2] 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=&ci
- kj=xj nebo -xj
- ci=(k) potom ci=(k|y|z)&(k|y|-z)&(k|-y|z)&(k|-y|-z)
- ci=(k1|k2) potom ci=(k1|k2|y)&(-y|k1|k2)
- ci=(k1|k2|k3) potom ci=(k1|k2|k3)
- ci=(k1|k2|...|km|...|kn-1|kn) potom ci=(k1|k2|y1)&...&(-ym-2|km|ym-1)&...&(-yn-3|kn-1|kn)
- 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 xi a -xi (pro každou proměnou 1 hrana)
- klazule: ci 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
- 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
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) $
- $ \Sigma_0 = P $
- $ \Sigma_1 = NP(P) = NP $
- $ \Sigma_2 = NP(NP) $
Celá hierarchie je $ PH = \bigcup_{i=0}^\infty {\Sigma_i} $.
Pseudopolynomiální algoritmy
- 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 xi, 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:
- 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)=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