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

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

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

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

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

  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: 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
  1. ci=(k) potom ci=(k|y|z)&(k|y|-z)&(k|-y|z)&(k|-y|-z)
  2. ci=(k1|k2) potom ci=(k1|k2|y)&(-y|k1|k2)
  3. ci=(k1|k2|k3) potom ci=(k1|k2|k3)
  4. 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
  1. proměnné: množina hran mezi xi a -xi (pro každou proměnou 1 hrana)
  2. klazule: ci 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 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:
  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