{{TOC float}}

{{Sources| Tohle je poněkud obšírnější výcuc ke ze pro obory a , pocházející ze zápisků z předmětu Složitost I -- 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:

  1. rozděl -- rozdělí úlohu na několik podúloh stejného typu, ale menší velikosti

  2. vyřeš -- vyřeší podúlohy a to buď přímo pro dostatečně malé, nebo rekurzivně pro větší

  3. sjednoť -- sjednotí řešení podúloh do řešení původní úlohy

Aplikace

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

  1. Uhodnu asymptoticky správné řešení

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

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

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

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

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

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 (subproblémy jsou závislé narozdíl od Rozděl a panuj).

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:

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

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 .

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á

  1. dědičnou vlastnost: <math> B\in I \wedge A\subseteq B\quad \Rightarrow\quad A\in I\,\!</math>,

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

  1. <math> A:=\emptyset\,\!</math>, setřiď a přeznač <math> S\,\!</math> sestupně podle vah

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

  3. 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:

  1. <math> A:=\emptyset\,\!</math>, <math> f_0:= 0, j:= 0\,\!</math>

  2. setřiď úkoly podle <math> f_i\,\!</math> vzestupně a přeznač

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

  4. 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}}