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

{{TOC float}}

''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)''
==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

{{TODO|Strassen}}

====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>

===Metody řešení rekurentních rovnic===

====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 d )\,\!</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 d )\,\!</math>

====Algoritmus (Hledání mediánu v lin. čase)====

Vstupem je (neuspořádáná) posloupnost <math> n\,\!</math> (navzájem různých) čísel. Výstup je <math> \lfloor\frac{n}{2}\rfloor\,\!</math>-té nejmenší číslo z nich. Složitost budeme měřit ''počtem porovnání''.

Algoritmus za použití techniky rozděl a panuj, hledá obecně <math> k\,\!</math>-té nejmenší číslo:  
# Vybrat pivota a rozdělit posloupnost pomocí <math> n-1\,\!</math> porovnání na 3 oddíly: čísla menší než pivot (<math> a\,\!</math> prvků), pivota samotného a čísla větší než pivot (<math> n-a-1\,\!</math> prvků). 
#  
## Pokud je <math> a + 1 < k\,\!</math>, hledám rekurzivně <math> k-a+1\,\!</math>-tý prvek v <math> n-a-1\,\!</math> prvcích 
## Pokud je <math> a + 1 = k\,\!</math>, vracím pivot 
## Pokud je <math> a + 1 > k\,\!</math>, hledám rekurzivně <math> k\,\!</math>-tý prvek v <math> a\,\!</math> prvcích   Rekurzivní vzorec <math> T(n) = T(n-1) + (n-1)\,\!</math> v nejhorším případě, což dává <math> \Theta(n^2)\,\!</math>.

Vylepšení, garantující dobrý výběr pivota:  
# Rozdělit posloupnost na pětice (poslední může být neúplná) 
# V každé pětici najít medián 
# Rekurzivně najít medián těchto mediánů 
# Použít ho jako pivot pro dělení celé posloupnosti, protože je větší než alespoň 3 prvky z alespoň <math> 1/2\,\!</math> pětic (až na zakrouhlení), je větší než alespoň <math> 1/2 \cdot 3/5 = 3/10\,\!</math> prvků (a také menší než alespoň <math> 3/10\,\!</math> prvků) 
# Z toho mám vždy zaručeno, že zahodím alespoň <math> 3/10\,\!</math> prvků pro následující krok.  Vzorec potom vychází: <math> T(n) = c\cdot\frac{n}{5} + T(\frac{n}{5}) + (n-1) + T(\frac{7}{10}n)\,\!</math> a podle kuchařky verze 2 nebo substituční metodou se dá vyčíslit jako <math> T(n) = \Theta(n)\,\!</math>.

==Dynamické programování==
{{TODO|}}

==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 pokud <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}}