Státnice - Informatika - Složitost: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Pseudopolynomiální algoritmy)
(FifLiGCzSHYALd)
Řádka 1: Řádka 1:
''Tento souhrn slouží pro přípravu k magisterským [[Státnice|státnicím]] pro obory [[Státnice - Informatika - I1: Teoretická informatika|Teoretická informatika]] a [[Státnice - Informatika - I4: Diskrétní modely a algoritmy|Diskrétní modely a algoritmy]]. Detailní informace o předmětu hledej na stránkách [[Složitost I]] a [[Složitost II]].''
+
Fraklny I think that's absolutely good stuff.
 
+
== Rozsah látky ==
+
Seznam [http://www.mff.cuni.cz/studium/bcmgr/ok/i3b4.htm oficiálních] státnicových otázek pro studijní obory [[Státnice - Informatika - I1: Teoretická informatika|Teoretická informatika]] a [[Státnice - Informatika - I4: Diskrétní modely a algoritmy|Diskrétní modely a algoritmy]]:
+
: Věty o zrychlení a o mezerách, věty o hierarchii tříd složitosti, konstruovatelné funkce, vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem, Savitchova věta. Úplné problémy pro třídy NP, PSPACE, polynomiální hierarchie, pseudopolynomiální algoritmy. Dolní odhady pro uspořádání (rozhodovací stromy). Aproximační algoritmy a schémata. Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus. Pravděpodobnostní algoritmy.
+
 
+
Studijní obory [[Státnice - Informatika - I2: Softwarové systémy|Softwarové systémy]] a [[Státnice - Informatika - I3: Matematická lingvistika|Matematická lingvistika]] mají okruhy [[Státnice - Informatika - Složitost (obory Matematická lingvistika a Softwarové systémy)|Složitost]] a [[Státnice - Informatika - Vyčíslitelnost|Vyčíslitelnost]] do spojeny do jednoho a rozsah otázek pro složitost se liší.
+
 
+
== Věty o zrychlení a o mezerách ==
+
=== Věta o lineárním zrychlení ===
+
:''see [[Složitost II#Věta o lineárním zrychlení]] (asi i [[wen:Linear speedup theorem]])''
+
 
+
* DTS s alespoň dvěma páskami se na vstupu délky n dá zrychlit z t kroků na <math>n + \lceil n/r \rceil + 6 \lceil t/r \rceil</math> (<math>r \in \mathbb{N}</math>)
+
** postup: nový stroj stlačí ''r'' políček původní pásky na jedno -- nejdřív okopíruje a přejede na začátek (<math>n + \lceil n/r \rceil</math> kroků), pak simuluje v šesti krocích ''r'' kroků původního stroje: nejdřív načte tři svoje políčka (3r políček původního stroje; trvá 4 kroky nového [vlevo,vpravo,vpravo,vlevo]), pak zjistí, jak budou vypadat po ''r'' krocích (jen ve vnitřním stavu), a nakonec to zapíše (další max 2 kroky, za ''r'' kroků starého se stihnou změnit nejvýše dvě políčka nového stroje)
+
* Je-li L jazyk přijímaný k-páskovým DTS M (k>=2) a s časovou složitostí <math>t(n) \in \omega(n)</math>. Potom pro každé kladné c existuje k-páskový M' s časovou složitostí c*t(n) přijímající L.
+
** Vezmeme r > 12/c, uděláme M' jako výše, doba jeho běhu nad vstupem délky n se dá pro r>2 shora odhadnout výrazem (c/2)*t(n)+(6/r)*t(n) (z <math>t(n) \in \omega(n)</math>), což z r>12/c dává omezení doby běhu c*t(n) pro skoro všechna n. Konečný počet výjimek se ošetří konečným automatem.
+
* Nechť je L jazyk přijímaný k-páskovým DTS M s časovou složitostí t(n) = c*n. Dále ať k>=2 a c>1. Pak <math>\forall \epsilon > 0</math> existuje k-páskový DTS M' s časovou složitostí <math>(1+\epsilon)\cdot n</math> přijímající L.
+
 
+
=== Blumova věta o zrychlení ===
+
:''see [[wen:Blum's speedup theorem]]''
+
 
+
Nechť <math>r(n)</math> je rekurzivní funkce. Potom existuje rekurzivní jazyk <math>L</math> takový, že pro každý DTS <math>M_i</math> rozpoznávající <math>L</math> v prostoru <math>S_i(n)</math> existuje DTS <math>M_j</math>, rozpoznávající <math>L</math> v prostoru <math>S_j(n)</math>, kde <math>r(S_j(n)) \leq S_i(n)</math> skoro všude.
+
 
+
(Tj. existují rekurzivní jazyky, jejichž rozpoznávání lze stále zrychlovat. Věta existuje i ve verzi pro časovou složitost. Věta ukazuje že když zkoumáme složitost a nepředpokládáme konstruovatelnost, můžeme dostat divnosti.)
+
 
+
:Důkaz je ve Strojilovi na stranách 24-25.
+
 
+
=== Borodinova věta mezerách ===
+
:''see [[wen:Gap theorem]]''
+
 
+
Nechť <math>g(n) \geq n</math> je rekurzivní funkce. Potom existuje rostoucí rekurzivní funkce S(n) taková, že DSPACE( S(n) ) = DSPACE( g(S(n)) )
+
 
+
(Pokud nepředpokládáme konstruovatelnost, dostáváme divnosti -- viz věty o hierarchii, které říkají že když se přidá na prostoru, dostaneme větší třídu jazyků.)
+
 
+
== Věty o hierarchii tříd složitosti ==
+
:''see [[Složitost II#Základní třídy složitosti]], [[wen:Complexity class]]''
+
 
+
=== Otevřenost časové hierarchie shora ===
+
Nechť T je rekurzivní funkce (tj. existuje TS, který ji vyčísluje). Potom existuje rekurzivní jazyk L takový, že <math>L \notin DTIME(T(n))</math>.
+
 
+
Důkaz přes jazyk <math>L = \{ x_i : M_i \mbox{ nepřijímá } x_i \mbox{ v čase } T(|x_i|) \} \ </math>, (máme očíslované řetězce i Turingovy stroje). Přítomnost v L se dá otestovat pomocí TS co si odsimuluje T(|x|) kroků příslušného stroje, L je tedy rekurzivní.
+
 
+
Pokud by platilo <math>L \in DTIME(T(n))</math>, tak by existoval TS M, který rozpozná L v čase T(n). Ten stroj má nějaké číslo i. (Tj. <math>M=M_i</math>.). Pak platí jedno z:
+
# <math>x_i \in L</math>, tj. stroj M přijme <math>x_i</math> v čase <math>T(|x_i|)</math> (protože ho poznává). Zároveň ale z stroj <math>M_i</math> <math>x_i</math> v čase <math>T(|x_i|)</math> nepřijímá (z definice L). Máme spor, protože M a <math>M_i</math> je ten samý.
+
# <math>x_i \notin L</math>, takže ho M (rozpoznávač L) v daném čase nepřijme, ale <math>M_i</math> (ten z definice L) ho v daném čase přijmout musí, tj. taky spor.
+
:(tj. vyzkoušíme, co řekne <math>M_i</math> na jemu příslušející řetězec <math>x_i</math>)
+
 
+
Proto <math>L \notin DTIME(T(n))</math>.
+
 
+
=== Otevřenost prostorové hierarchie shora ===
+
Nechť S je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že <math>L \notin DSPACE(S(n))</math>.
+
 
+
Důkaz je analogický jako u časové hierarchie, vyrobí se jazyk <math>L = \{ x_i : M_i \mbox{ nepřijímá } x_i \mbox { v prostoru } S(|x_i|) \}</math>. Rozdíl je jen v simulaci <math>M_i</math>, který se navíc může na svém omezeném prostoru zacyklit, což se ale dá detekovat, neb tam má omezený počet konfigurací.
+
 
+
=== Věty o časové a prostorové hierarchii ===
+
==== O prostorové hierarchii ====
+
Nechť <math>S_1: \mathbb N \to \mathbb N</math> a <math>S_2: \mathbb N \to \mathbb N</math> jsou funkce takové, že <math>S_2 \in \omega(S_1)</math> a <math>S_2</math> je prostorově konstruovatelná. Potom existuje jazyk L takový, že <math>L \in DSPACE(S_2) \setminus DSPACE(S_1)</math>.
+
 
+
To s omegou znamená že <math>S_2</math> není omezená <math>S_1</math> (ani když se přenásobí libovolnou konstantou), celá pointa věty je, že v takto větším prostoru se dají poznat nějaké další jazyky.
+
 
+
==== O časové hierarchii ====
+
 
+
Nechť <math>T_1: \mathbb N \to \mathbb N</math> a <math>T_2: \mathbb N \to \mathbb N</math> jsou funkce takové, že <math>T_2 \in \omega(T_1 \cdot \log T_1)</math> a <math>T_2</math> je časově konstruovatelná. Potom existuje jazyk L takový, že <math>L \in DTIME(T_2) \setminus DTIME(T_1)</math>.
+
 
+
== Konstruovatelné funkce ==
+
:''see also [[Složitost II#Konstruovatelnost funkcí|Složitost II]]''
+
 
+
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je ''rekurzivní'' pokud existuje DTS M takový, že pro vstup 1<sup>n</sup> vydá výstup 1<sup>f(n)</sup>.
+
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je ''vyčíslitelná v čase O(f)'' pokud f je rekurzivní a &exist; c &ge; 1 takové, že příslušný DTS udělá nejvýše cf(n) kroků než vydá 1<sup>f(n)</sup>.
+
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je ''vyčíslitelná v prostoru O(f)'' pokud f je rekurzivní a &exist; c &ge; 1 takové, že příslušný DTS použije při práci prostor nejvýše cf(n).
+
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je ''časově konstruovatelná'' pokud existuje DTS M takový, že pro každý vstup délky n zastaví po právě f(n) krocích (předpokládáme, že f(n) &ge; n + 1).
+
* Funkce <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> je ''prostorově konstruovatelná'' pokud existuje DTS M takový, že pro každý vstup délky n zastaví s právě f(n) páskovými symboly neprázdnými, přičemž žádný jiný prostor na pracovních páskách nebyl v průběhu výpočtu použit.
+
 
+
'''Lemma:''' Nechť <math>f_1+f_2</math> a <math>f_2</math> jsou časově konstruovatelné funkce, dále nechť <math>\exists \varepsilon>0, \exists n_0</math> takové, že <math>\forall n>n_0 : f_1(n) \geq \varepsilon \cdot f_2(n) + (1+\varepsilon)n</math>. Pak <math>f_1</math> je časově konstruovatelná.
+
: Podobně jako v důkazu věty o lineárním zrychlení zrychlíme výpočet trvající <math>f_1(n)+f_2(n)</math> kroků, aby trval přesně <math>f_1(n)</math> kroků...
+
 
+
'''Věta:''' Nechť <math>f:\mathbb N \to \mathbb N</math>, taková, že existuje <math>\varepsilon > 0</math> a <math>n_0</math>, že <math>\forall n \geq n_0: f(n) \geq (1+\varepsilon)n</math>. Pak je f časově konstruovatelná právě tehdy, když je vyčíslitelná v čase O(f).
+
:Je-li f časově konstruovatelná, pak máme stroj který běží v čase f(n). Můžeme mu přidat pásku, na kterou bude psát po dobu svého běhu jedničky, čímž f vyčíslí.
+
:Naopak, označíme-li g(n) přesný čas stroje M, který funkci f počítá v čase O(f(n)). (Tedy g(n) < c*f(n) pro skoro všechna n a nějaké c.) Potom g je časem TS M, f + g je časem TS, který "po dopočítání M ještě spočítá počet jedniček na pásce". Funkce g je časově konstruovatelná díky stroji M. Z toho (a z lemmatu výše) plyne časová konstruovatelnost f.
+
 
+
'''Věta:''' Funkce f je prostorově konstruovatelná právě tehdy, když je vyčíslitelná v prostoru O(f).
+
:Doprava nám stačí upravit stroj který f prostorově konstruuje tak, aby při zabrání nového políčka zapsal na novou pásku jedničku.
+
:Nechť M je k-páskový deterministický Turingův stroj vyčíslující f(n) v prostoru c*f(n). Podle věty o lineární kompresi zkonstruujeme k-páskový stroj M', který vyčísluje f(n) v prostoru přesně f(n). Uvědomte si, že M' vyčísluje f(n), tedy musí pracovat v prostoru alespoň f(n). Stroj M' dále převedeme podle věty o redukci počtu pásek na jednopáskový stroj M'', který již dokazuje prostorovou konstruovatelnost funkce f.
+
 
+
;Věta o lineární prostorové kompresi
+
:Je-li L jazyk přijímaný k-páskovým DTS M v prostoru S(n), pak pro každé přirozené číslo r existuje k-páskový DTS M', který přijímá L v prostoru <math>\lceil S(n)/r \rceil</math>
+
 
+
;Věta o redukci počtu pásek pro prostorovou složitost
+
:Je-li L jazyk příjímaný k-páskovým DTS M v prostoru S(n), pak existuje jednopáskový DTS M', který přijímá L v prostoru S(n).
+
 
+
'''Důsledek:''' Každá časově konstruovatelná funkce je také prostorově konstruovatelná.
+
: Funkce f je časově konstruovatelná, tedy je vyčíslitelná v čase O(f), tím spíše je vyčíslitelná v prostoru O(f) a z věty výše je tedy i prostorově konstruovatelná.
+
 
+
== Vztahy mezi časovými a prostorovými mírami a determinismem a nedeterminismem ==
+
DSPACE(S(n)), DTIME(T(n)), NSPACE(S(n)), NTIME(S(n)) -- třídy jazyků (ne)deterministické časové/prostorové složitosti T(n)/S(n).
+
 
+
Triviální vztahy
+
* <math>\forall F_1(n) \leq F_2(n) \Rightarrow XXX(F_1(n)) \subseteq XXX(F2(n))</math>, kde XXX je něco z [DN](SPACE|TIME)
+
 
+
=== Věta o vztazích mezi třídami složitosti ===
+
# <math>DTIME (f(n)) \subseteq NTIME(f(n))</math><br/><math>DSPACE (f(n)) \subseteq NSPACE(f(n))</math>
+
#* triviálně platí
+
# <math>DTIME(f(n)) \subseteq DSPACE(f(n))</math>
+
#* z vět o lineární kompresi a redukci počtu pásek
+
#* (IMHO si stačí uvědomit, že prostor je vždy omezen spotřebovaným časem)
+
# <math>NTIME(f(n)) \subseteq DSPACE(f(n))</math>
+
#* postupně generujeme f(n)-tice možných průchodů (v každém kroku max r možností, r=max|{přechodová funkce}|) jako graf průchodu výpočtem a výpočet simulujeme DTS podle toho -- simulace potřebuje DSPACE(f(n)) (třeba podle předchozího bodu), uloženi f(n)-tice potřebuje <math>log_2(r) * f(n)</math> místa, tj. taky DSPACE(f(n)), a tenhle prostor se dá použivat pro jednotlivé simulace stejný. Celkem tedy <math>DSPACE(f(n))</math>.
+
# <math>L \in DSPACE(f(n))</math> a <math>f(n) \geq log_2(n)</math>, pak <math>L \in DTIME(C_L^{f(n)})</math>, kde C<sub>L</sub> je konstanta závislá na jazyku L
+
#* Nechť M je jednopáskový stroj poznávající L v prostoru f(n). Počet jeho konfigurací je omezen <math>s \cdot (n+1) \cdot (f(n)+1) \cdot t^{f(n)} \leq d^{f(n)}</math>, pro vhodné <math>d</math> (<math>s</math> je počet stavů, <math>t</math> je počet páskových symbolů, člen (n+1) asi? pro pozici hlavy na vstupní pásce).
+
#*Zkonstruujeme M', který simuluje M a nejvýše po <math>d^{f(n)}</math> krocích se zastaví. (Potřebujeme předpoklad časové konstruovatelnosti funkce f.)
+
# <math>L \in NSPACE(f(n))</math> a <math>f(n) \geq log_2(n)</math>, pak <math>L \in DTIME(C_L^{f(n)})</math>, kde C<sub>L</sub> je konstanta závislá na jazyku L
+
#* Počet konfigurací opět omezen nějakým <math>d^{f(n)}</math>. Vygenerujeme graf, vrcholy=stavy (tj. omezené), hrana=přechod jedním krokem (konstanta*|stavy|, protože přechodová funkce je konečná). Pak se graf projde a zjistí, jestli tam je přijímací výpočet.
+
# <math>L \in NTIME(f(n))</math>, pak <math>L \in DTIME(C_L^{f(n)})</math>, kde C<sub>L</sub> je konstanta závislá na jazyku L
+
#* Nechť M je k-páskový NTS, který poznává L v čase f(n). Počet jeho konfigurací je omezen <math>s \cdot (f(n)+1)^k \cdot t^{k \cdot f(n)} \leq d^{f(n)}</math> pro vhodné <math>d</math> (<math>s</math> je počet stavů, <math>t</math> páskových symbolů).
+
#* Zkontruujeme DTS M', který vygeneruje seznam všech konfigurací dosažitelných z počáteční konfigurace, což lze provést v kradratickém čase vzhledem k délce výsledného seznamu. Tato délka je omezena součinem počtu konfigurací a délky zápisu jedné konfigurace. Tedy <math>l \leq d^{f(n)} \cdot (k \cdot f(n) + 1 + k \cdot \log f(n)) \leq c^{f(n)}</math>. M' je pak schopný poznat jestli je dosažitelná nějaká přijímající konfigurace, počet jeho kroků je omezen <math>c^{2 f(n)}</math>.
+
 
+
== Savitchova věta ==
+
:''see [[wen:Savitch's theorem]]''
+
 
+
Nechť <math>S:\mathbb{N} \rightarrow \mathbb{N}</math> je prostorově konstruovatelná funkce taková, že <math>S(n) \geq log_2(n)</math>. Potom <math>NSPACE(S(n)) \subseteq DSPACE(S^2(n))</math>.
+
 
+
:Pokud NTS M přijímá jazyk L v prostoru S(n), pak existuje konstanta <math>C_L</math> taková, že M má nejvýše <math>C_L^{S(n)}</math> konfigurací. Počet kroků přijímajícího výpočtu pak bude nanejvýš <math>C_L^{S(n)} = 2^{S(n) \log C_L}</math>.
+
:Pak definujeme proceduru <math>TEST(I_1, I_2, i)</math>, která zkoumá, jestli se ze stavu <math>I_1</math> dá přejít do stavu <math>I_2</math> za maximálně <math>2^i</math> kroků. (Dělá to rekurzivně -- pro i=0 ověří jestli jsou stavy shodné nebo existují přímý přechod a vrátí výsledek, jinak pro každý stav <math>I_x</math> pouští <math>TEST(I_1, I_x, i-1)</math> a <math>TEST(I_x, I_2, i-1)</math> a zkoumá jejich výsledek.)
+
:Jedna kopie procedury TEST si musí pamatovat tři konfigurace (jedna konfigurace potřebuje stav, pozici vstupní a výstupní hlavy, a obsah pracovní pásky, to vše O(S(n)) a parametr i (ten se taky vejde do O(S(n)), viz max počet kroků výpočtu).
+
:Simulace probíhá tak, že pro všechny přijímací stavy <math>I_j</math> voláme proceduru <math>TEST(I_0, I_j, mS(n))</math> (<math>I_0</math> je počáteční konfigurace) a pokud aspoň jednou odpoví ''true'', vstup přijmeme.
+
:Pracovní páska pak funguje jako zásobník parametrů procedury TEST, která se zahloubí nanejvýš O(S(n)), takže se celý výpočet vejde do prostoru <math>O(S^2(n))</math>
+
 
+
== Úplné problémy pro třídy NP, PSPACE ==
+
:''see [[wen:NP-complete]], [[wen:PSPACE-complete]]''
+
 
+
* NP-C problém: Kachličky, SAT; 3-SAT, 3-Color, Klika, NM, VP; VP, HK, TSP; VP, SP
+
* PSPACE-complete problém: kvantifikovaná boolovská proměnná (důkaz podobný důkazu Savichovy věty).
+
* dále typicky hry (zoběcněný [[wen: Hex (board game)]])
+
 
+
=== Příklady NP-C===
+
Pochopitelnější důkazy jsou uvedené v Majerechových skriptách (ke stažení ve [[Studnice vědomostí|studnici]]).
+
 
+
Lidsky vysvětlený důkaz Cook-Levinovy věty ("Existuje NP-úplný problém") je [[KACHL|zde]]. 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.
+
 
+
Důkaz KACHL < SAT je také v Majerechových skriptách.
+
 
+
* SAT < 3-SAT
+
: Za každou klauzuli s jiným počtem literálů než 3 dáme množinu klauzulí, která dává ekvivalentní podformuli. Vezměme klauzuli c<sub>i</sub>:
+
:# <math> c_i = (x) </math>, pak <math>
+
  c_i' := (x \vee y_1 \vee y_2)
+
  \wedge (x \vee y_1 \vee \bar y_2)
+
  \wedge (x \vee \bar y_1 \vee y_2)
+
  \wedge (x \vee \bar y_1 \vee \bar y_2)
+
</math>
+
:# <math> c_i = (x_1 \vee x_2) </math>, pak <math>
+
  c_i' := (x_1 \vee x_2 \vee y)
+
  \wedge (x_1 \vee x_2 \vee \bar y)
+
</math>
+
:# <math> c_i = (x_1 \vee \dotsb \vee x_k) </math> pro <math>k>3</math>, pak <math>
+
  c_i' :=  (x_1 \vee x_2 \vee y_1)
+
  \wedge (\bar y_1 \vee x_3 \vee y_2) \wedge \dotsb
+
  \wedge (\bar y_{i-2} \vee x_i \vee y_{i-1}) \wedge \dotsb
+
  \wedge (\bar y_{k-3} \vee x_{k-1} \vee x_k)
+
</math>
+
 
+
 
+
* SAT < Klika
+
: Graf nad všemi literály formule (opakované literály se budou opakovat i v grafu), hrana mezi každými dvěma literály z různých klauzulí, pokud s nejedná o vzájemnou negaci (x a -x). Hledáme kliku o velikosti jako je počet klauzulí, ta pak pro každou klauzuli určuje splňující literál.
+
 
+
* SAT < NM
+
: Nezávislé množiny odpovídají právě klikám v komplementárním grafu.
+
 
+
* SAT < VP
+
: Doplňky vrcholových pokrytí odpovídají právě nezávislým množinám. Důkaz snadno sporem, hrana porušující nezávislost není v doplňku pokryta a naopak.
+
 
+
== Polynomiální hierarchie ==
+
:''see [[Složitost II#Polynomiální hierarchie|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í <math>P(C) \subseteq NP(C) \subseteq PSPACE(C)</math>.
+
 
+
;Polynomiální hierarchie
+
:Máme <math>\Sigma_0 = P</math>, <math>\Sigma_{i+1} = NP(\Sigma_i)</math>
+
 
+
# <math>\Sigma_0 = P</math>
+
# <math>\Sigma_1 = NP(P) = NP</math>
+
# <math>\Sigma_2 = NP(NP)</math>
+
 
+
Celá hierarchie je <math>PH = \bigcup_{i=0}^\infty {\Sigma_i}</math>.
+
 
+
=== PH je v PSPACE ===
+
;Věta: <math>PH \subseteq PSPACE</math>
+
 
+
Dokazuje se indukcí podle i
+
# i = 0; <math>\Sigma_0 = P \subseteq PSPACE</math>
+
# předpokládáme, že tvrzení platí pro i (IP), chceme ukázat, že <math>\Sigma_{i+1} \subseteq PSPACE</math>
+
#: <math>\Sigma_{i+1} = NP(\Sigma_i) \subseteq^{IP} NP(PSPACE) \subseteq^* PSPACE(PSPACE)</math>
+
#: * -- co poznám v NP, poznám v i PSPACE, a orákulum mám stejné
+
#: <math>PSPACE(PSPACE) \subseteq PSPACE</math>
+
#: místo orákula může stroj kolikrát chce pouštět DTS, co si bude vedle psát ve svém polynomiálním prostoru
+
 
+
{{TODO|&Pi;<sub>k</sub>, &Delta;<sub>k</sub>, další vzájemné vztahy, alternující kvatifikátory, kolaps PH}}
+
 
+
== Pseudopolynomiální algoritmy ==
+
:''see [[wen:Pseudo-polynomial time]]''
+
* Nechť je dán rozhodovací problém (úloha, jejímž výstupem je ANO/NE) &pi; 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í &pi; se nazývá ''pseudopolynomiální'', pokud je jeho čas. slož. omezena polynomem v proměnných kód(I) a max(I).
+
* Pokud je &pi; tž. forall ''I'': max(I)&le;p(kód(I)) potom ''pseudopolynomiální''=''polynomiá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'')
+
** &pi;<sub>p</sub> omezení na podproblém &pi; tž. platí max(I)&le;p(kód(I)). Pokud &pi;<sub>p</sub> NPÚ, tak &pi; S-NPÚ
+
** Klika, TSP je S-NPÚ
+
 
+
{{TODO|S-NPÚ patří do tohoto požadavku taky!}}
+
 
+
== 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á <math>n!</math> listů (tolik je možných uspořádání množiny s <math>n</math> 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ň <math>\log_2(n!)</math>. (Úplný binární strom s <math>k</math> listy má výšku <math>\log_2 k</math>, 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ž <math>O(\log_2(n!)) = O(n\ \log n)</math>.
+
 
+
Podle Stirlingovy formule:
+
:<math>n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}</math> (to je ona)
+
:<math>O(\log_2 n!) = O(\log_2{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}) = O(n \log n)</math> (Logaritmus odmocniny bude asymptoticky <math>O(\log n)</math>, <math>(n/e)^n</math> bude <math>O(n \log n)</math>, a požere to.)
+
 
+
*Pro mne snazší odhad: n<sup>n</sup> &ge; n! &ge; n<sup>n/2</sup>
+
*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<sup>2</sup>] umim tridit
+
 
+
== Aproximační algoritmy a schémata ==
+
 
+
Pozri tiež [[Státnice - Aproximační algoritmy a schémata]]
+
 
+
:''see [[wen:Approximation algorithm]], kus na straně 12 z [http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/slozitost.sxw]''
+
 
+
*'''Předpoklady''': Každé řešení má nezápornou hodnotu.
+
 
+
*'''Značení''': <math>n</math> velikost zadání, C* hodnota ''optimálního'' řešení, C hodnota ''aproximovaného'' řešení
+
 
+
=== Definice ===
+
*'''Poměrová chyba''': <math>\rho(n) \geq max\left\{ \frac{C^*}{C}, \frac{C}{C^*} \right\}</math>
+
*'''Relativní chyba''': <math>\epsilon(n) \geq \frac{|C-C^*|}{C^*}</math>
+
**Pozn.: Pokud jsou <math>\rho(n),\epsilon(n)</math> konstanty, tak se obyčejně parametr <math>n</math> vynechává.
+
 
+
*'''Aproximační schéma (AS)''' pro optimalizační úlohu je aproximační alg., který pro vstup délky <math>n</math> a číslo <math>\epsilon>0</math> najde řešení s ''relativní chybou'' <math>\epsilon</math>. Může být exponenciální vzhledem k <math>n</math> i <math>1/\epsilon</math>.
+
 
+
*'''Polynomiální AS''': AS, které je polynomiální vzhledem k <math>n</math>.
+
 
+
*'''Úplně Polynomiální AS (ÚPAS)''': PAS, které je polynomiální i k <math>1/\epsilon</math>.
+
 
+
===Fakta===
+
* <math>\rho(n) \geq 1</math>
+
* <math>\epsilon(n) \geq \rho(n) - 1</math>
+
 
+
===Příklady===
+
 
+
====Vrcholové pokrytí====
+
*&rho;=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'''<nowiki>:</nowiki> 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|&le;|C*| (optimální řešení musí pokrýt i hrany z F).
+
:|C|=2*|F| a |F|&le;|C*| potom |C|&le;2*|C*|
+
 
+
 
+
==== ÚPAS pro součet podmnožiny ====
+
*Je dána konečná podmnožina množ. přirozených čísel A s prvky x<sub>i</sub>, hodnota součtu ''t'' a aproximační parametr 0<&epsilon;<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 &delta; znamená, že pro každý odstraněný prvek ''y'' existuje v prořezaném seznamu L<nowiki>'</nowiki> prvek ''z'' splňující<nowiki>:</nowiki> (1-&delta;)y &le; z &le; y. Zachovává uspořádání.
+
*Algoritmus řešení:
+
'''APPROX_SP(A,t,&epsilon;)''':<br>
+
L<sub>0</sub>=(0)
+
'''for''' i = 1 '''to''' n '''do'''
+
  L<sub>i</sub>=MERGE(L<sub>i-1</sub>, L<sub>i-1</sub>+x<sub>i</sub>) //vytvoří nový a slitím původního a součtu původního
+
  L<sub>i</sub>=PRUNE(L<sub>i</sub>, &epsilon;/''n'') //prořeže
+
  L<sub>i</sub>=CROP(L<sub>i</sub>, ''t'') //odstraní prvky větší než ''t''
+
'''end'''
+
'''return''' L<sub>n</sub> //vrátí řešení
+
*Prořezávání s parametrem &epsilon;/''n'' zajišťuje nepřekročení výsledné meze chyby &epsilon;, která se může kumulativně zvětšovat v každé iteraci. 
+
*Časová složitost algoritmu je <math>O\left(\frac{n^2\cdot log~t}{\epsilon}\right)</math>.
+
 
+
'''Obchodní cestující''':
+
*Pro TSP na úplném grafu s troj. nerovností (&Delta;TSP) ex. aprox. algoritmus s poměrovou chybou &rho;=2.
+
**Pro &Delta;TSP platí: <math>\forall u,v,w\in V: c(u,v)\leq c(u,w)+c(w,v)</math>. Je to vůbec NP-těžké? ANO: Lze řešit HK pomocí &Delta;TSP následujícím způsobem: Graf se doplní na K<sub>|V|</sub> a váhy se definují <math>c(e)=1\mbox{ pokud }e\in E</math>, <math>c(e)=2\mbox{ pokud }e\notin E</math>. Potom řešení hledá &Delta;TSP pro k=|V|.
+
**Řešení problému &Delta;TSP:
+
#Nalezení min. kostry (např. Primův alg. - staví se na jedna komponenta postupným připojováním vrcholů) &rarr; kostra T
+
#Zvolí se vrchol ''u'' a ''preorder'' (pořadí prvního navštívení vrcholu) se očíslují vrcholy pomocí DFS(T,u) &rarr; pořadí vrcholů dané očíslováním.
+
#Výsledná HK je určena očíslováním z kroku 2.
+
:'''DK'''<nowiki>:</nowiki> Ať H* je opt. HK a T je minimální kostra, potom c(T)&le;c(H*).
+
:W je úplná procházka po T (viz krok 2.), potom c(W)=2*c(T)&le;c(H*).
+
:Z W se vyrobí H nahrazováním cest délek &ge;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)&le;c(W).
+
:Platí c(H)&le;c(W)=2*c(T)&le;c(H*) potom &rho;&le;2.
+
*Ať &rho;&ge;1 je konstanta. Pokud P&ne;NP, potom neexistuje polynomiální aproximační algoritmus řešící obecný TSP s poměrovou chybou &rho;.
+
** Pokud by existoval, umí řešit HK (ten je NPÚ). Graf se doplní na K<sub>|V|</sub> a váhy hran se definují:
+
:<math>
+
c(e) =
+
\begin{cases}
+
  1,  & \mbox{pokud }e\in E \\
+
  \rho\cdot n+1, & \mbox{pokud }e\notin E
+
\end{cases}
+
</math>
+
:Nyní algoritmus buď vydá HK délky ''n'' (&rarr;Odpověď na HK v původním grafu je ANO), nebo vydá HK délky >&rho;&middot;''n'' (&rarr;Odpověď na HK v původním grafu je NE).
+
 
+
== Metody tvorby algoritmů ==
+
=== Rozděl a panuj ===
+
[[wen:Divide and conquer algorithm]]
+
 
+
# '''Rozděl''' &ndash; podúlohy stejného typu &hellip; D(n)
+
# '''Vyřeš''' &ndash; analogicky řeš (pod)úlohy &hellip; T(n)
+
# '''Sjednoť''' &ndash; z řešení podúloh vytvoř řešení původní úlohy &hellip; S(n)
+
 
+
T(n)=D(n)+a*T(n/c)+S(n) pro n>n<sub>0</sub>
+
 
+
T(n)=&Theta;(1) jinak
+
 
+
Master theorem, kuchařka
+
Př.: Merge-sort T(n)=2T(n/2) + O(n) &hellip; O(n*log(n))
+
K-ty prvek T(n)=c*n/5+T(n/5)+(n-1)+T(7/10) &hellip; O(n)
+
 
+
=== Dynamické programování ===
+
Viz [[wen:Dynamic programming]], [http://kam.mff.cuni.cz/~kuba/vyuka/textiky/matrix_mul.ps Násobení matic] od Jakuba Černého nebo dynamické programování podle [http://ksp.mff.cuni.cz/tasks/19/cook5.html kuchařky KSP].
+
 
+
Věta o dynamickém programování: papír ''Dynamické programování'' od Jiřího Vyskočila na [http://ladislav.strojil.cz/school.php?sub=3 strojilovych stránkách].
+
 
+
Využití:
+
# <nowiki>"překrývání podproblému"</nowiki> (problém lze rozdělit na podproblémy, jejichž řešení se využívá opakovaně).
+
# <nowiki>"optimální podstruktury"</nowiki> (optimální řešení lze zkonstruovat z optimálních řešení podproblémů).
+
 
+
Příklady použití:
+
* Násobení matic
+
* Problém batohu
+
* [[wcs:Problém_obchodního_cestujícího|Problém obchodního cestujícího]]
+
* Floyd-Warshallův algoritmus nejkratší cesty
+
* &hellip;
+
 
+
=== Hladový algoritmus ===
+
[[wen:Greedy algorithm]]
+
 
+
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'' &amp; ''A'' subset ''B'' potom ''A'' in ''I'').
+
# ''I'' má ''výměnnou vlastnost'' (pokud ''A'',''B'' in ''I'' tž. |''A''|&lt;|''B''| potom existuje ''x'' in ''B''-''A'': ''A''+{''x''} in ''I'').
+
 
+
(Pozn. Pro ''vážený matroid'' se doplňuje funkce ''w: S->R<sub>0</sub><sup>+</sup>'' 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:
+
 
+
# &Theta;(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&ndash;3 -> Greedy(M,w) vrací optimální množinu.
+
 
+
Pr.: Minimalní kostra grafu
+
 
+
== Pravděpodobnostní algoritmy ==
+
{{TODO}}
+
 
+
 
+
== Materiály ==
+
* [[TIN063_Skripta_Ladislava_Strojila|Skripta Ladislava Strojila]]
+
* Slajdy z přednášek a další materiály na [http://mff.modry.cz/slozitost/ mff.modry.cz]
+
* [http://www.cs.berkeley.edu/~vazirani/algorithms.html Algorithms] &ndash; Dasgupta S., Papadimitriou C.H., Vazirani U.V., Berkeley
+
* [http://www.cs.princeton.edu/theory/complexity/ Complexity Theory: A Modern Approach (draft)] &ndash; Arora S., Barak B., Princeton
+
 
+
[[Category: Státnice Informatika Mgr.]]
+

Verze z 2. 7. 2011, 02:26

Fraklny I think that's absolutely good stuff.