Syntax highlighting of Archiv/Státnice - Metody tvorby algoritmů

{{TOC float}}

{{Sources|
''Tohle je poněkud obšírnější výcuc ke [[Státnice|státnicovým okruhům]] ze [[Státnice_-_Informatika_-_Složitost_(obory_Matematická_lingvistika_a_Softwarové_systémy)|složitosti]] pro obory [[Státnice_-_Informatika_-_I3:_Matematická_lingvistika|Matematická lingvistika]] a [[Státnice_-_Informatika_-_I2:_Softwarové_systémy|Softwarové systémy]], pocházející ze zápisků z předmětu [[Složitost I]] -- [[User:Tuetschek|Tuetschek]] 22:44, 16 Aug 2010 (CEST)''
}}

==Popis složitosti algoritmů==

====Definice (Velikost dat, krok algoritmu)====

''Velikost dat'' je obvykle počet bitů, potřebných k jejich zapsání, např. data <math> D\,\!</math> jako pro čísla <math> a_1,\dots,a_n\,\!</math> je velikost dat <math> |D|=\sum_{i=1}^n \lceil \log a_i \rceil\,\!</math>.

''Krok algoritmu'' je jedna operace daného abstraktního stroje (např. Turingův stroj, stroj RAM), zjednodušeně jde o nějakou operaci, proveditelnou v konstantním čase (např. aritmetické operace, porovnání hodnot, přiřazení -- pro jednoduché číselné typy).

====Definice (Časová složitost)====

''Časová složitost'' je funkce <math> f:\mathbb{N}\to\mathbb{N}\,\!</math> taková, že <math> f(|D|)\,\!</math> udává počet kroků daného algoritmu, pokud je spuštěn na datech <math> D\,\!</math>.

====Definice (Asymptotická složitost)====

Řekneme, že funkce <math> f(n)\,\!</math> je ''asymptoticky menší nebo rovna'' než <math> g(n)\,\!</math>, značíme <math> f(n)\,\!</math> je <math> O(g(n))\,\!</math>, právě tehdy, když

:<math>\exists c>0 \exists n_0 \forall n>n_0: 0 \leq f(n) \leq c \cdot g(n)\,\!</math>

Funkce <math> f(n)\,\!</math> je ''asymptoticky větší nebo rovna'' než <math> g(n)\,\!</math>, značíme <math> f(n)\,\!</math> je <math> \Omega(g(n))\,\!</math>, právě tehdy, když

:<math>\exists c>0 \exists n_0 \forall n>n_0: 0 \leq c \cdot g(n) \leq f(n)\,\!</math>

Funkce <math> f(n)\,\!</math> je ''asymptoticky stejná'' jako <math> g(n)\,\!</math>, značíme <math> f(n)\,\!</math> je <math> \Theta(g(n))\,\!</math>, právě tehdy, když

:<math>\exists c_1,c_2>0 \exists n_0 \forall n>n_0: 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)\,\!</math>

Funkce <math> f(n)\,\!</math> je ''asymptoticky ostře menší'' než <math> g(n)\,\!</math> (<math> f(n)\,\!</math> je <math> o(g(n))\,\!</math>, když

:<math>\forall c>0 \exists n_0 \forall n>n_0: 0\leq f(n) < c\cdot g(n)\,\!</math>

Funkce <math> f(n)\,\!</math> je ''asymptoticky ostře větší'' než <math> g(n)\,\!</math> (<math> f(n)\,\!</math> je <math> w(g(n))\,\!</math>, když

:<math>\forall c>0 \exists n_0 \forall n>n_0: 0\leq c\cdot g(n) < f(n)\,\!</math>

====Poznámka====

Asymptotická složitost zkoumá chování algoritmů na velkých datech, zařazuje je podle toho do kategorií. Zanedbává multiplikativní a aditivní konstanty.

==Rozděl a panuj==

====Definice (Metoda rozděl a panuj)====

''Rozděl a panuj'' je metoda návrhu algoritmů (ne strukturované programování), která má 3 kroky:  
# ''rozděl'' -- rozdělí úlohu na několik podúloh stejného typu, ale menší velikosti 
# ''vyřeš'' -- vyřeší podúlohy a to buď přímo pro dostatečně malé, nebo rekurzivně pro větší 
# ''sjednoť'' -- sjednotí řešení podúloh do řešení původní úlohy

====Aplikace====
* [[Státnice - Třídění#Quicksort|QUICKSORT]]
* [[Státnice - Třídění#Pořadové statistiky (hledání mediánu)|Hledání mediánu]]
{{TODO|Strassen}}

===Analýza složitosti algoritmů rozděl a panuj===

====Poznámka (Vytvoření rekurentní rovnice)====

Pro časovou složitost algoritmů typu rozděl a panuj zpravidla dostávám nějakou rekurentní rovnici.  
* <math> T(n)\,\!</math> budiž doba zpracování úlohy velikosti <math> n\,\!</math>, za předpokladu, že <math> T(n)=\Theta(1)\,\!</math> pro <math> n\leq n_0\,\!</math>. 
* <math> D(n)\,\!</math> budiž doba na rozdělení úlohy velikosti <math> n\,\!</math> na <math> a\,\!</math> podúloh stejné velikosti <math> \frac{n}{c}\,\!</math>. 
* <math> S(n)\,\!</math> budiž doba na sjednocení řešení podúloh velikosti <math> \frac{n}{c}\,\!</math> na jednu úlohu velikosti <math> n\,\!</math>.  Dostávám rovnici

:<math>T(n)=\begin{cases} D(n)+aT(\frac{n}{c})+S(n) \quad\quad & n > n_0 \\ \Theta(1) & n \leq n_0 \end{cases}\,\!</math>

====Poznámka====

Při řešení rekurentních rovnic:  
* Zanedbávám celočíselnost (<math> \frac{n}{2}\,\!</math> místo <math> \lceil\frac{n}{2}\rceil\,\!</math> a <math> \lfloor\frac{n}{2}\rfloor\,\!</math>) 
* Nehledím na konkrétní hodnoty aditivních a multiplikativních konstant, asymptotické notace používám i v zadání rekurentních rovnic, i v jejich řešení.

====Věta (Substituční metoda)====

# Uhodnu asymptoticky správné řešení 
# Indukcí ověřím správnost (zvláště horní a dolní odhad)

====Věta (Metoda "kuchařka" (Master Theorem))====

Nechť <math> a\geq 1, c>1,d\geq 0\in\mathbb{R}\,\!</math> a nechť <math> T:\mathbb{N}\to\mathbb{N}\,\!</math> je neklesající funkce taková, že <math> \forall n\,\!</math> tvaru <math> c^k\,\!</math> platí

:<math>T(n)=aT(\frac{n}{c}) + \Theta(n^d)\,\!</math>

Potom  
# Je-li <math> \log_c a \neq d\,\!</math>, pak <math> T(n)\,\!</math> je <math> \Theta( n^{\max\{\log_c a, d\}} )\,\!</math> 
# Je-li <math> \log_c a = d\,\!</math>, pak <math> T(n)\,\!</math> je <math> \Theta( n^d \log_c n )\,\!</math>

====Věta (Master Theorem, varianta 2)====

Nechť <math> 0<a_i<1\,\!</math>, kde <math> i\in\{1,\dots,k\}\,\!</math>  a <math> d\geq 0\,\!</math> jsou reálná čísla a nechť <math> T:\mathbb{N}\to\mathbb{N}\,\!</math> splňuje rekurenci

:<math>T(n)=\sum_{i=1}^k T(a_i\cdot n) + \Theta(n^d)\,\!</math>

Nechť je číslo <math> x\,\!</math> řešením rovnice <math> \sum_{i=1}^k a_i^x = 1\,\!</math>. Potom  
# Je-li <math> x \neq d\,\!</math> (tedy <math> \sum_{i=1}^k a_i^d \neq 1\,\!</math>), pak <math> T(n)\,\!</math> je <math> \Theta( n^{\max\{x, d\}} )\,\!</math> 
# Je-li <math> x = d\,\!</math> (tedy <math> \sum_{i=1}^k a_i^d = 1\,\!</math>), pak <math> T(n)\,\!</math> je <math> \Theta( n^d \log n )\,\!</math>

==Dynamické programování==

{{Sources|Převzato z vypracovaných otázek V. Bedecse -- 
[[User:Tuetschek|Tuetschek]] 10:34, 30 Aug 2010 (CEST)}}

Dynamické programování je metoda řešení problemů, které v sobě obsahují 
překrývající se subproblémy. 

=== Příklad ===
Typickým příkladem je výpočet fibonaciho čísla. Fib. posloupnost je definována 
jako: 
:<math>f(0) = 1, f(1) = 1 </math>
:<math>f(n+2) = f(n+1) + f(n)  </math>
 
Výpočet třeba 4. čísla by pak byl <math>f(4) = f(3) + f(2) = f(2) + f(1) + f(1) + f(0) = f(1) + f(0) + f(1) +f(1) +f(0) = 5</math>. Vidíme, že jsme <math>f(2)</math> počítali dvakrát, <math>f(1)</math> třikrát a <math>f(0)</math> dvakrát. Ve větším měřítku toto zbytečně počítání vede k exponenciální složitosti algoritmu. Lepší cestou je počítat "od spodu", kdy pomoci <math>f(0)</math> a <math>f(1)</math> spočteme <math>f(2)</math>, pak s jeho pomoci <math>f(3)</math>  nakonec <math>f(4)</math> s lineární složitosti. 

V dynamickém programování se například vytvoří mapa Fibonacciho čísel a jejich hodnot. Před tím, než začnu počítat hodnotu nějakého Fibonacciho čísla, se podívám do mapy. 

=== Nutné podmínky ===

V dynamickém programování využíváme: 
# ''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ů. 

=== Postupy ===

Obvykle se používá jeden ze dvou přístupů k dynamickému programování: 
* ''Top-down'' - problém se rekurzivně dělí na podproblémy a po jejich vyřešení se zapamatují výsledky, které se použijí při případném opětovném řešení daného podproblému. 
* ''Bottom-up'' - nejdříve se spočítají všechny možné podproblémy (viz příklad s Fibonacciho posloupnosti), které se potom skládají do řešení větších problémů. Tento přístup je výhodnější z hlediska počtu volání funkci a místa na zásobníků, ale ne vždy musí být zřejmě, které všechny subproblémy je třeba předem spočítat.

=== Použití ===
 
''Problém batohu'' -- máme věci různé váhy a batoh určité nosnosti. Které věci máme dát do batohu, abychom jej co nejlépe zaplnili (jednorozměrná varianta problému batohu)? Speciální případ je součet podmnožiny (SP). Algoritmus je popsán v [[Státnice_-_NP-úplnost#P.C5.99.C3.ADklad|sekci o NP-úplnosti]].

''Uzávorkování součinu matic'' tak, aby počet skalárních součinů byl co nejmenší. Dělá se pomocí 2 čtvercových matic (<math>M</math> a <math>K</math>) řádu rovného počtu násobených matic, kde pracujeme jen nad diagonálou. Hodnota na <math>M_{ij}</math> udává minimální počet skalárních součinů při nejlepším uzávorkování matic <math>i</math> až <math>j</math>, hodnota <math>K_{ij}</math> určuje matici, která rozděluje závorkování na dvě podmnožiny matic. Hodnotu <math>M_{ij}</math> lze zkonstruovat ze všech <math>M_{ik}</math> a <math>M_{kj}</math> pro <math>i<k<j</math>.

==Hladové algoritmy==

===Motivace===

====Problém 1====

Dán souvislý neorientovaný graf <math> G=(V,E)\,\!</math> a funkce <math> d:E\to\mathbb{R}^+\,\!</math>, udávající délky hran. Najděte minimální kostru grafu <math> G\,\!</math>, tj. kostru <math> G'=(V,E')\,\!</math> tak, že <math> \sum_{e\in E'} d(e)\,\!</math> je minimální.

====Problém 2====

Je dána množina <math> S=\{1,\dots,n\}\,\!</math> úkolů jednotkové délky. Ke každému úkolu je dána lhůta dokončení <math> d_i\in\mathbb{N}\,\!</math> a pokuta <math> w_i\in\mathbb{N}\,\!</math>, kterou je úkol <math> i\,\!</math> penalizován, není-li hotov do své lhůty. Najděte rozvrh (permutaci úkolů od času <math> 0\,\!</math> do času <math> n\,\!</math>), který minimalizuje celkovou pokutu.

====Problém 3====

Je dána množina <math> S=\{1,\dots,n\}\,\!</math> úkolů. Ke každému úkolu je dán čas jeho zahájení <math> s_i\,\!</math> ukončení <math> f_i\,\!</math>, <math> s_i\leq f_i\,\!</math>. Úkoly <math> i\,\!</math> a <math> j\,\!</math> jsou kompatibilní, pokud se intervaly <math> [s_i,f_i)\,\!</math> a <math> [s_j,f_j)\,\!</math> nepřekrývají. Najděte co největší množinu (po dvou) kompatibilních úkolů.

===Matroid===

====Definice (Matroid)====

''Matroid'' je uspořádaná dvojice <math> M=(S,I)\,\!</math>, splňující:  
* <math> S\,\!</math> je konečná neprázdná množina (''prvky matroidu '' <math> M\,\!</math>) 
* <math> I\,\!</math> je neprázdná množina podmnožin <math> S\,\!</math> (''nezávislé podmnožiny''), která má  
# ''dědičnou vlastnost'': <math> B\in I \wedge A\subseteq B\quad \Rightarrow\quad A\in I\,\!</math>, 
# ''výměnnou vlastnost'': <math> A,B\in I \wedge |A|<|B|\quad \Rightarrow\quad \exists x\in B\backslash A: A\cup\{x\}\in I\,\!</math>.

====Věta (O velikosti maximálních nezávislých podmnožin)====

Všechny ''maximální'' (maximální vzhledem k inkluzi) nezávislé podmnožiny v matroidu mají stejnou velikost.

====Důkaz====

Z výměnné vlastnosti, nechť <math> A, B\in I\,\!</math> maximální, <math> |A|<|B|\,\!</math>, pak <math> A\cup\{x\}\in I, x\notin A\,\!</math>, což je spor.

====Definice (Vážený matroid)====

Matroid <math> M=(S,I)\,\!</math> je ''vážený'', pokud je dána funkce <math> w:S\to\mathbb{R}^+\,\!</math> a její rozšíření na podmnožiny množiny <math> S\,\!</math> je definováno předpisem:

:<math>A\in S \Rightarrow w(A)=\sum_{x\in A}w(x)\,\!</math>

====Problém 1 a 2 -- zobecněný====

Pro daný vážený matroid nalezněte nezávislou podmnožinu s co největší vahou (''optimální množinu''). Protože váhy jsou kladné, vždy se bude jednat o maximální nez. množinu.

Problém 1 je spec. případ tohoto, protože můžeme uvažovat ''grafový matroid'' (nad hranami) -- <math> M_G = (S, I)\,\!</math>, kde <math> S = E\,\!</math> a pro <math> A\subseteq E\,\!</math> platí <math> A\in I\,\!</math>, pokud hrany z <math> A\,\!</math> netvoří cyklus (tj. indukovaný podgraf tvoří les). 

Dědičná vlastnost této struktury je zřejmá, výměnnost se dá dokázat následovně: mějme <math> A,B\subseteq E, |A|<|B|\,\!</math>. Pak lesy z <math> A, B\,\!</math> mají <math> n-a > n-b\,\!</math> stromů (vč. izolovaných vrcholů). V <math> B\,\!</math> musí být strom, který se dotýká <math> \geq 2\,\!</math> různých stromů z <math> A\,\!</math>. Ten obsahuje hranu, která není v žádném stromě <math> A\,\!</math> a netvoří cyklus a tak ji můžu k <math> A\,\!</math> přidat. 

Váhovou funkci převedu na hledání maxim: <math> w(e) = c - d(e)\,\!</math>, kde <math> c\,\!</math> je dost velká konstanta, aby všechny váhy byly kladné. Algoritmus pak najde max. množinu, kde hrany netvoří cyklus. Implicitně bude mít <math> n-1\,\!</math> hran, takže půjde o kostru a její <math> w\,\!</math> bude maximální, tedy původní váha minimální.

Pro problém 2 zavedeme pojem ''kanonického rozvrhu'' -- takového rozvrhu, kde jsou všechny ''včasné'' úkoly rozvrženy před všemi ''zpožděnými'' a uspořádány podle neklesající lhůty dokončení (tohle na celkové pokutě nic nezmění a máme bijekci mezi množinou včasných úkolů a kanonickými rozvrhy).

Optimální množinu pak lze hledat jen nad kanonickými rozvrhy -- nezávislou množinou úkolů nazvu takovou, pro kterou existuje kanonický rozvrh tak, že žádný úkol v ní obsažený není zpožděný. Potom hledání max. nezávislé množiny při ohodnocení pokutami je hledání nejmenší pokuty (odeberu co nejvíc z možné celkové pokuty).

Pak zbývá dokázat, že takto vytvořená struktura je matroid. Dědičná vlastnost je triviální -- vyhodím-li něco z nezávislé množiny, nechám v rozvrhu mezery a bude platit stále. Pro výměnnou vlastnost zavedu pomocnou funkci <math> N_t(C) = |\{i\in C| d_i\leq t\}|\,\!</math>, udávající počet úkolů z množiny <math> C\,\!</math> se lhůtou do času <math> t\,\!</math>. Pak množina <math> C\,\!</math> je nezávislá, právě když <math> \forall t\in\{1,\dots,n\}: N_t(C)\leq t\,\!</math>.

Pak máme-li 2 nezávislé <math> A\,\!</math>, <math> B\,\!</math>, <math> |B|>|A|\,\!</math>, označíme <math> k\,\!</math> největší okamžik takový, že <math> N_k(B)\leq N_k(A)\,\!</math>, tj. od <math> k+1\,\!</math> dál platí <math> N_t(A) < N_t(B)\,\!</math>. To skutečně nastane, protože <math> |B| = N_n(B) > N_n(A) = |A|\,\!</math>. Pak určitě v <math> B\,\!</math> je ostře víc úkolů s <math> d_i = k+1\,\!</math> než v <math> A\,\!</math>, tj. <math> \exists x\in B\backslash A\,\!</math> se lhůtou <math> k+1\,\!</math>. <math> A \cup \{x\}\,\!</math> je nezávislá, protože <math> N_t(A\cup\{x\}) = N_t(A)\,\!</math> pro <math> t\leq k\,\!</math> a <math> N_t(A\cup\{x\}) \leq N_t(B)\,\!</math> pro <math> t\geq k+1\,\!</math>.

===Hladový algoritmus na váženém matroidu===

====Algoritmus (Greedy)====

Mám zadaný matroid <math> M=(S,I)\,\!</math>, kde <math> S = \{x_1,\dots,x_n\}\,\!</math> a <math> w:S\to\mathbb{R}^+\,\!</math>. Potom  
# <math> A:=\emptyset\,\!</math>, setřiď a přeznač <math> S\,\!</math> sestupně podle vah 
# pro každé <math> x_i\,\!</math> zkoušej: je-li <math> A\cup\{x_i\}\in I\,\!</math>, tak <math> A:=A\cup\{x_i\}\,\!</math> 
# vrať <math> A\,\!</math> jako maximální nezávislou množinu

Pokud přidám nějaké <math> x_i\,\!</math>, nikdy nezruším nezávislost množiny; s už přidanými prvky se nic nestane. Časová složitost je <math> \Theta(n\log n)\,\!</math> na setřídění podle vah, testování nezávislosti množiny závisí na typu matriodu (<math> f(n)\,\!</math>), takže celkem něco jako <math> \Theta(n\log n + n\cdot f(n))\,\!</math>.

====Důkaz====

* Vyhození prvků, které samy o sobě nejsou nezávislé množiny, nic nezkazí (z dědičné vlastnosti). 
* První vybrané <math> x_i\,\!</math> je "legální" (nezablokuje mi cestu), protože mezi max. nez. množinami určitě existuje taková, která jím mohla vzniknout (z výměnné vlastnosti -- vezmeme první prvek, který je sám o sobě nez. mn. a s pomocí nějaké max. nez. množiny <math> B\,\!</math> ho doplníme, vzniklé <math> \{x_i\}\cup (B\backslash \{ x_j\})\,\!</math> musí být také maximální). 
* Nalezení optimální množiny obsahující pevné (první vybrané) <math> x_i\,\!</math> v <math> M=(S,I)\,\!</math> je ekvivalentní nalezení optimální množiny v <math> M' = (S', I')\,\!</math>, kde <math> S' = \{ y \in S | \{ x_i,y\}\in I\}\,\!</math> a <math> I' = \{ B\subset S\backslash \{x_i\} | B\cup \{x_i\} \in I\}\,\!</math> (je-li <math> S'\,\!</math> neprázdná, je to matroid, vlastnosti se přenesou z původního; pokud je <math> S'\,\!</math> prázdná, tak algoritmus končí) a tedy když vyberu <math> x_i\,\!</math>, nezatarasím si cestu k optimu -- stačí ukázat, že <math> A\cup\{x\}\,\!</math> je optimální v <math> M\,\!</math> právě když <math> A\,\!</math> je optimální v <math> M'\,\!</math>. 
* Takže když budu vybírat (indukcí opakovaně) <math> x_i\,\!</math> podle váhy, dojdu k optimální množině.

====Algoritmus (Hladový algoritmus na problém 3)====

Máme <math> S=\{1,\dots,n\}\,\!</math> množinu úkolů s časy startů <math> s_i\,\!</math> a konců <math> f_i\,\!</math>. Provedeme:  
# <math> A:=\emptyset\,\!</math>, <math> f_0:= 0, j:= 0\,\!</math> 
# setřiď úkoly podle <math> f_i\,\!</math> vzestupně a přeznač 
# pro každé <math> i\,\!</math> zkoušej: je-li <math> s_i \geq f_j\,\!</math>, pak <math> A:=A\cup\{i\}\,\!</math> a <math> j:=i\,\!</math> 
# vrať <math> A\,\!</math> jako max. množinu nekryjících se úkolů

Složitost je <math> n\log n\,\!</math> na setřídění, zbytek už lineární. Sice to funguje, ale tahle struktura NENÍ matroid -- nesplňuje výměnnou vlastnost. Algoritmus má ale stejný důkaz jako předchozí na matroidech (legálnost hladového výběru -- existuje max. množina obsahující prvek <math> 1\,\!</math> -- a existenci optimální množiny -- převod na "menší" zadání).

{{Statnice I3}}