Státnice - Informatika - Složitost

Z ωικι.matfyz.cz
Verze z 24. 10. 2012, 15:01, kterou vytvořil 77.48.63.197 (diskuse) (Reverting spam.)

Přejít na: navigace, hledání

Tento souhrn slouží pro přípravu k magisterským státnicím pro obory Teoretická informatika a Diskrétní modely a algoritmy. Detailní informace o předmětu hledej na stránkách Složitost I a Složitost II.

Rozsah látky

Seznam oficiálních státnicových otázek pro studijní obory Teoretická informatika a 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 Softwarové systémy a Matematická lingvistika mají okruhy Složitost a Vyčíslitelnost do spojeny do jednoho a rozsah otázek pro složitost se liší.

Zdroje obecně

Většina je pokryta přednáškami Složitost I a II, některá témata je však třeba dohledat jinde (klidně po internetu, na wikipedii, v Majerechovi, v zahraničních skriptech...). Pozor, Čepkovy slajdy jsou více než stručné.

Vřele doporučuji strávit jedno odpoledne v knihovně s knížkou od Arory a Baraka Computational Complexity: A Modern Approach. Velmi názorně pomůže získat dobrou intuici u téměř všech okruhů a rigorózní důkazy se tam člověk venkoncem také dočte.

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 $ n + \lceil n/r \rceil + 6 \lceil t/r \rceil $ ($ r \in \mathbb{N} $)
    • postup: nový stroj stlačí r políček původní pásky na jedno -- nejdřív okopíruje a přejede na začátek ($ n + \lceil n/r \rceil $ 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í $ t(n) \in \omega(n) $. 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 $ t(n) \in \omega(n) $), 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 $ \forall \epsilon > 0 $ existuje k-páskový DTS M' s časovou složitostí $ (1+\epsilon)\cdot n $ přijímající L.

Blumova věta o zrychlení

see wen:Blum's speedup theorem

Nechť $ r(n) $ je rekurzivní funkce. Potom existuje rekurzivní jazyk $ L $ takový, že pro každý DTS $ M_i $ rozpoznávající $ L $ v prostoru $ S_i(n) $ existuje DTS $ M_j $, rozpoznávající $ L $ v prostoru $ S_j(n) $, kde $ r(S_j(n)) \leq S_i(n) $ 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.

iam fan of Mr Ata ur Rehman and also of the Free and Open Source Softwares. i appreciate his woredrful efforts for the promotion of FOSS movemnet.I took training of koha 2.2.8 in july, 2008 from him, and implement the same in NUST CAE.Mr ata ur rehman is an assett to LIS and its community.wishes him all success in his future endeaures.

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 $ L \notin DTIME(T(n)) $.

Důkaz přes jazyk $ L = \{ x_i : M_i \mbox{ nepřijímá } x_i \mbox{ v čase } T(|x_i|) \} \ $, (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 $ L \in DTIME(T(n)) $, tak by existoval TS M, který rozpozná L v čase T(n). Ten stroj má nějaké číslo i. (Tj. $ M=M_i $.). Pak platí jedno z:

  1. $ x_i \in L $, tj. stroj M přijme $ x_i $ v čase $ T(|x_i|) $ (protože ho poznává). Zároveň ale z stroj $ M_i $ $ x_i $ v čase $ T(|x_i|) $ nepřijímá (z definice L). Máme spor, protože M a $ M_i $ je ten samý.
  2. $ x_i \notin L $, takže ho M (rozpoznávač L) v daném čase nepřijme, ale $ M_i $ (ten z definice L) ho v daném čase přijmout musí, tj. taky spor.
(tj. vyzkoušíme, co řekne $ M_i $ na jemu příslušející řetězec $ x_i $)

Proto $ L \notin DTIME(T(n)) $.

Otevřenost prostorové hierarchie shora

Nechť S je rekurzivní funkce. Potom existuje rekurzivní jazyk L takový, že $ L \notin DSPACE(S(n)) $.

Důkaz je analogický jako u časové hierarchie, vyrobí se jazyk $ L = \{ x_i : M_i \mbox{ nepřijímá } x_i \mbox { v prostoru } S(|x_i|) \} $. Rozdíl je jen v simulaci $ M_i $, 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ť $ S_1: \mathbb N \to \mathbb N $ a $ S_2: \mathbb N \to \mathbb N $ jsou funkce takové, že $ S_2 \in \omega(S_1) $ a $ S_2 $ je prostorově konstruovatelná. Potom existuje jazyk L takový, že $ L \in DSPACE(S_2) \setminus DSPACE(S_1) $.

To s omegou znamená že $ S_2 $ není omezená $ S_1 $ (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ť $ T_1: \mathbb N \to \mathbb N $ a $ T_2: \mathbb N \to \mathbb N $ jsou funkce takové, že $ T_2 \in \omega(T_1 \cdot \log T_1) $ a $ T_2 $ je časově konstruovatelná. Potom existuje jazyk L takový, že $ L \in DTIME(T_2) \setminus DTIME(T_1) $.

Konstruovatelné funkce

see also Složitost II
  • Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je rekurzivní pokud existuje DTS M takový, že pro vstup 1n vydá výstup 1f(n).
  • Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je vyčíslitelná v čase O(f) pokud f je rekurzivní a ∃ c ≥ 1 takové, že příslušný DTS udělá nejvýše cf(n) kroků než vydá 1f(n).
  • Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je vyčíslitelná v prostoru O(f) pokud f je rekurzivní a ∃ c ≥ 1 takové, že příslušný DTS použije při práci prostor nejvýše cf(n).
  • Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ 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) ≥ n + 1).
  • Funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ 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ť $ f_1+f_2 $ a $ f_2 $ jsou časově konstruovatelné funkce, dále nechť $ \exists \varepsilon>0, \exists n_0 $ takové, že $ \forall n>n_0 : f_1(n) \geq \varepsilon \cdot f_2(n) + (1+\varepsilon)n $. Pak $ f_1 $ je časově konstruovatelná.

Podobně jako v důkazu věty o lineárním zrychlení zrychlíme výpočet trvající $ f_1(n)+f_2(n) $ kroků, aby trval přesně $ f_1(n) $ kroků...

Věta: Nechť $ f:\mathbb N \to \mathbb N $, taková, že existuje $ \varepsilon > 0 $ a $ n_0 $, že $ \forall n \geq n_0: f(n) \geq (1+\varepsilon)n $. 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 $ \lceil S(n)/r \rceil $
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

  • $ \forall F_1(n) \leq F_2(n) \Rightarrow XXX(F_1(n)) \subseteq XXX(F2(n)) $, kde XXX je něco z [DN](SPACE|TIME)

Věta o vztazích mezi třídami složitosti

  1. $ DTIME (f(n)) \subseteq NTIME(f(n)) $
    $ DSPACE (f(n)) \subseteq NSPACE(f(n)) $
    • triviálně platí
  2. $ DTIME(f(n)) \subseteq DSPACE(f(n)) $
    • 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)
  3. $ NTIME(f(n)) \subseteq DSPACE(f(n)) $
    • 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 $ log_2(r) * f(n) $ místa, tj. taky DSPACE(f(n)), a tenhle prostor se dá použivat pro jednotlivé simulace stejný. Celkem tedy $ DSPACE(f(n)) $.
  4. $ L \in DSPACE(f(n)) $ a $ f(n) \geq log_2(n) $, pak $ L \in DTIME(C_L^{f(n)}) $, kde CL 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 $ s \cdot (n+1) \cdot (f(n)+1) \cdot t^{f(n)} \leq d^{f(n)} $, pro vhodné $ d $ ($ s $ je počet stavů, $ t $ 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 $ d^{f(n)} $ krocích se zastaví. (Potřebujeme předpoklad časové konstruovatelnosti funkce f.)
  5. $ L \in NSPACE(f(n)) $ a $ f(n) \geq log_2(n) $, pak $ L \in DTIME(C_L^{f(n)}) $, kde CL je konstanta závislá na jazyku L
    • Počet konfigurací opět omezen nějakým $ d^{f(n)} $. 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.
  6. $ L \in NTIME(f(n)) $, pak $ L \in DTIME(C_L^{f(n)}) $, kde CL 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 $ s \cdot (f(n)+1)^k \cdot t^{k \cdot f(n)} \leq d^{f(n)} $ pro vhodné $ d $ ($ s $ je počet stavů, $ t $ 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 $ l \leq d^{f(n)} \cdot (k \cdot f(n) + 1 + k \cdot \log f(n)) \leq c^{f(n)} $. M' je pak schopný poznat jestli je dosažitelná nějaká přijímající konfigurace, počet jeho kroků je omezen $ c^{2 f(n)} $.

Savitchova věta

see wen:Savitch's theorem

Nechť $ S:\mathbb{N} \rightarrow \mathbb{N} $ je prostorově konstruovatelná funkce taková, že $ S(n) \geq log_2(n) $. Potom $ NSPACE(S(n)) \subseteq DSPACE(S^2(n)) $.

Pokud NTS M přijímá jazyk L v prostoru S(n), pak existuje konstanta $ C_L $ taková, že M má nejvýše $ C_L^{S(n)} $ konfigurací. Počet kroků přijímajícího výpočtu pak bude nanejvýš $ C_L^{S(n)} = 2^{S(n) \log C_L} $.
Pak definujeme proceduru $ TEST(I_1, I_2, i) $, která zkoumá, jestli se ze stavu $ I_1 $ dá přejít do stavu $ I_2 $ za maximálně $ 2^i $ 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 $ I_x $ pouští $ TEST(I_1, I_x, i-1) $ a $ TEST(I_x, I_2, i-1) $ 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 $ I_j $ voláme proceduru $ TEST(I_0, I_j, mS(n)) $ ($ I_0 $ 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 $ O(S^2(n)) $

Ú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 studnici).

Lidsky vysvětlený důkaz Cook-Levinovy věty ("Existuje NP-úplný problém") je 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 ci:
  1. $ c_i = (x) $, pak $ 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) $
  2. $ c_i = (x_1 \vee x_2) $, pak $ c_i' := (x_1 \vee x_2 \vee y) \wedge (x_1 \vee x_2 \vee \bar y) $
  3. $ c_i = (x_1 \vee \dotsb \vee x_k) $ pro $ k>3 $, pak $ 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) $


  • 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.
  • Klika < NM
Nezávislé množiny odpovídají právě klikám v komplementárním grafu.
  • NM < 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 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} $.

Pozor! Podle mj je treba znat i definici Pi a Delta, dobre je tusit i alespon nektere inkluze (viz obrazek na wikipedii).

PH je v PSPACE

Věta
$ PH \subseteq PSPACE $

Dokazuje se indukcí podle i

  1. i = 0; $ \Sigma_0 = P \subseteq PSPACE $
  2. předpokládáme, že tvrzení platí pro i (IP), chceme ukázat, že $ \Sigma_{i+1} \subseteq PSPACE $
    $ \Sigma_{i+1} = NP(\Sigma_i) \subseteq^{IP} NP(PSPACE) \subseteq^* PSPACE(PSPACE) $
    * -- co poznám v NP, poznám v i PSPACE, a orákulum mám stejné
    $ PSPACE(PSPACE) \subseteq PSPACE $
    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
Tato část je neúplná a potřebuje rozšířit. Πk, Δk, 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) π 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 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)
    • πp omezení na podproblém π tž. platí max(I)≤p(kód(I)). Pokud πp NPÚ, tak π S-NPÚ
    • Klika, TSP je S-NPÚ
Tato část je neúplná a potřebuje rozšířit. 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á $ 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! ≥ nn/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

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 [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 $.

Well done article that. I'll make sure to use it wisley.

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) $ (v nejhorsim pripade se kazdy prvek od predchoziho lisi o 1-e/n, tedy budou prvky tvorit geometrickou posloupnost (1-e/n)^i a t=(1-e/n)^|L_i| a tedy |L_i|=log_{1-e/n}t).

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

Metody tvorby algoritmů

The honesty of your psotnig is there for all to see

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ů).

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

TIeJya <a href="http://zkdmbnlxlecp.com/">zkdmbnlxlecp</a>

Materiály