{{TOC float}}

{{Sources| Tohle je poněkud obšírnější výcuc ke státnicovým okruhům ze složitosti pro obory Státnice_-_Informatika_-_I3:_Matematická_lingvistika a Státnice_-_Informatika_-_I2:_Softwarové_systémy, pocházející ze zápisků z předmětu Složitost I -- User: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 $D\,\!$ jako pro čísla $a_1,\dots,a_n\,\!$ je velikost dat $|D|=\sum_{i=1}^n \lceil \log a_i \rceil\,\!$.

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 $f:\mathbb{N}\to\mathbb{N}\,\!$ taková, že $f(|D|)\,\!$ udává počet kroků daného algoritmu, pokud je spuštěn na datech $D\,\!$.

Definice (Asymptotická složitost)

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

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

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

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

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

:$\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)\,\!$

Funkce $f(n)\,\!$ je asymptoticky ostře menší než $g(n)\,\!$ ($f(n)\,\!$ je $o(g(n))\,\!$, když

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

Funkce $f(n)\,\!$ je asymptoticky ostře větší než $g(n)\,\!$ ($f(n)\,\!$ je $w(g(n))\,\!$, když

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

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

*Pasáž knihy Jakuba Černého - 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

• QUICKSORT

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

• $T(n)\,\!$ budiž doba zpracování úlohy velikosti $n\,\!$, za předpokladu, že $T(n)=\Theta(1)\,\!$ pro $n\leq n_0\,\!$.

• $D(n)\,\!$ budiž doba na rozdělení úlohy velikosti $n\,\!$ na $a\,\!$ podúloh stejné velikosti $\frac{n}{c}\,\!$.

• $S(n)\,\!$ budiž doba na sjednocení řešení podúloh velikosti $\frac{n}{c}\,\!$ na jednu úlohu velikosti $n\,\!$. Dostávám rovnici

:$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}\,\!$

Poznámka

Při řešení rekurentních rovnic:

• Zanedbávám celočíselnost ($\frac{n}{2}\,\!$ místo $\lceil\frac{n}{2}\rceil\,\!$ a $\lfloor\frac{n}{2}\rfloor\,\!$)

• 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ť $a\geq 1, c>1,d\geq 0\in\mathbb{R}\,\!$ a nechť $T:\mathbb{N}\to\mathbb{N}\,\!$ je neklesající funkce taková, že $\forall n\,\!$ tvaru $c^k\,\!$ platí

:$T(n)=aT(\frac{n}{c}) + \Theta(n^d)\,\!$

Potom

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

2. Je-li $\log_c a = d\,\!$, pak $T(n)\,\!$ je $\Theta( n^d \log_c n )\,\!$

Věta (Master Theorem, varianta 2)

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

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

Nechť je číslo $x\,\!$ řešením rovnice $\sum_{i=1}^k a_i^x = 1\,\!$. Potom

1. Je-li $x \neq d\,\!$ (tedy $\sum_{i=1}^k a_i^d \neq 1\,\!$), pak $T(n)\,\!$ je $\Theta( n^{\max\{x, d\}} )\,\!$

2. Je-li $x = d\,\!$ (tedy $\sum_{i=1}^k a_i^d = 1\,\!$), pak $T(n)\,\!$ je $\Theta( n^d \log n )\,\!$

Dynamické programování

{{Sources|Převzato z vypracovaných otázek V. Bedecse --

User:Tuetschek 10:34, 30 Aug 2010 (CEST)}} {{zkazky|

• Dynamické programování (2012, Dvořák) - U dynamickýho programování jsem nějak sesmolil princip fungování a napsal jsem tam jeden konkrétní algoritmus (z grafiky - matchování vrcholů dvou mnohoúhelníků), na kterym jsem ukazoval, jak to funguje. To bylo OK, ale tahal ze mě pořád nějakej obecnej princip, jak to funguje. V rámci toho jsem ještě za pochodu vymýšlel algoritmus na batoh (to se mi vůbec nedělalo dobře, když vedle mě seděl a čekal na výsledek). Na konec jsme se teda asi dobrali toho, co chtěl slyšet - že se řešení konstruuje z menších podúloh stylem zdola nahoru (narozdíl od rozděl&panuj, kde to je v zásadě shora dolů).

}} 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: :$f(0) = 1, f(1) = 1$

:$f(n+2) = f(n+1) + f(n)$

Výpočet třeba 4. čísla by pak byl $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$. Vidíme, že jsme $f(2)$ počítali dvakrát, $f(1)$ třikrát a $f(0)$ 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 $f(0)$ a $f(1)$ spočteme $f(2)$, pak s jeho pomoci $f(3)$ nakonec $f(4)$ 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 sekci o NP-úplnosti.

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

Hladové algoritmy

Motivace

Problém 1

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

Problém 2

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

Problém 3

Je dána množina $S=\{1,\dots,n\}\,\!$ úkolů. Ke každému úkolu je dán čas jeho zahájení $s_i\,\!$ ukončení $f_i\,\!$, $s_i\leq f_i\,\!$. Úkoly $i\,\!$ a $j\,\!$ jsou kompatibilní, pokud se intervaly

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: \̲[̲s_i,f_i)\,\!

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: \̲[̲s_j,f_j)\,\!

Matroid

Definice (Matroid)

Matroid je uspořádaná dvojice $M=(S,I)\,\!$, splňující:

• $S\,\!$ je konečná neprázdná množina (*prvky matroidu * $M\,\!$)

• $I\,\!$ je neprázdná množina podmnožin $S\,\!$ (nezávislé podmnožiny), která má

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

2. výměnnou vlastnost: $A,B\in I \wedge |A|<|B|\quad \Rightarrow\quad \exists x\in B\backslash A: A\cup\{x\}\in I\,\!$.

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ť $A, B\in I\,\!$ maximální, $|A|<|B|\,\!$, pak $A\cup\{x\}\in I, x\notin A\,\!$, což je spor.

Definice (Vážený matroid)

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

:$A\subseteq S \Rightarrow w(A)=\sum_{x\in A}w(x)\,\!$

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) -- $M_G = (S, I)\,\!$, kde $S = E\,\!$ a pro $A\subseteq E\,\!$ platí $A\in I\,\!$, pokud hrany z $A\,\!$ 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 $A,B\subseteq E, |A|<|B|\,\!$. Pak lesy z $A, B\,\!$ mají $n-a > n-b\,\!$ stromů (vč. izolovaných vrcholů). V $B\,\!$ musí být strom, který se dotýká $\geq 2\,\!$ různých stromů z $A\,\!$. Ten obsahuje hranu, která není v žádném stromě $A\,\!$ a netvoří cyklus a tak ji můžu k $A\,\!$ přidat.

Váhovou funkci převedu na hledání maxim: $w(e) = c - d(e)\,\!$, kde $c\,\!$ 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 $n-1\,\!$ hran, takže půjde o kostru a její $w\,\!$ 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 $N_t(C) = |\{i\in C| d_i\leq t\}|\,\!$, udávající počet úkolů z množiny $C\,\!$ se lhůtou do času $t\,\!$. Pak množina $C\,\!$ je nezávislá, právě když $\forall t\in\{1,\dots,n\}: N_t(C)\leq t\,\!$.

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

Hladový algoritmus na váženém matroidu

Algoritmus (Greedy)

Mám zadaný matroid $M=(S,I)\,\!$, kde $S = \{x_1,\dots,x_n\}\,\!$ a $w:S\to\mathbb{R}^+\,\!$. Potom

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

2. pro každé $x_i\,\!$ zkoušej: je-li $A\cup\{x_i\}\in I\,\!$, tak $A:=A\cup\{x_i\}\,\!$

3. vrať $A\,\!$ jako maximální nezávislou množinu

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

Důkaz

• Vyhození prvků, které samy o sobě nejsou nezávislé množiny, nic nezkazí (z dědičné vlastnosti).

• První vybrané $x_i\,\!$ 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 $B\,\!$ ho doplníme, vzniklé $\{x_i\}\cup (B\backslash \{ x_j\})\,\!$ musí být také maximální).

• Nalezení optimální množiny obsahující pevné (první vybrané) $x_i\,\!$ v $M=(S,I)\,\!$ je ekvivalentní nalezení optimální množiny v $M' = (S', I')\,\!$, kde $S' = \{ y \in S | \{ x_i,y\}\in I\}\,\!$ a $I' = \{ B\subset S\backslash \{x_i\} | B\cup \{x_i\} \in I\}\,\!$ (je-li $S'\,\!$ neprázdná, je to matroid, vlastnosti se přenesou z původního; pokud je $S'\,\!$ prázdná, tak algoritmus končí) a tedy když vyberu $x_i\,\!$, nezatarasím si cestu k optimu -- stačí ukázat, že $A\cup\{x\}\,\!$ je optimální v $M\,\!$ právě když $A\,\!$ je optimální v $M'\,\!$.

• Takže když budu vybírat (indukcí opakovaně) $x_i\,\!$ podle váhy, dojdu k optimální množině.

Algoritmus (Hladový algoritmus na problém 3)

Máme $S=\{1,\dots,n\}\,\!$ množinu úkolů s časy startů $s_i\,\!$ a konců $f_i\,\!$. Provedeme:

1. $A:=\emptyset\,\!$, $f_0:= 0, j:= 0\,\!$

2. setřiď úkoly podle $f_i\,\!$ vzestupně a přeznač

3. pro každé $i\,\!$ zkoušej: je-li $s_i \geq f_j\,\!$, pak $A:=A\cup\{i\}\,\!$ a $j:=i\,\!$

4. vrať $A\,\!$ jako max. množinu nekryjících se úkolů

Složitost je $n\log n\,\!$ 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 $1\,\!$ -- a existenci optimální množiny -- převod na "menší" zadání).

{{Statnice I3}}