# Algoritmy a datové struktury 2 ## Hledání v řetězci - značení - jehla $\iota$ - $J=|\iota|$ - seno $\sigma$ - $S=|\sigma|$ - abeceda $\Sigma$ - předpokládáme konečnost a malou konstantní velikost - slova/řetězce $\alpha,\beta,\gamma,\dots$ - znaky $a,b,c\dots$ - délka řetězce $|\alpha|$ - prázdný řetězec $\varepsilon$ - $|\varepsilon|=0$ - zřetězení $\alpha\beta$ - i-tý znak $\alpha[i]$ (počítáme od nuly) - podřetězec $\alpha[i:j]$ (od i-tého znaku do (j-1). znaku včetně) - prefix $\alpha[:j]=\alpha[0:j]$ - suffix $\alpha[i:]=\alpha[i:|\alpha|]$ - $\alpha[:]=\alpha$ - pozorování - prázdný řetězec je prefixem i suffixem jakéhokoliv řetězce - každý řetězec je prefixem i suffixem sebe sama - každý podřetězec se dá zapsat jako prefix nějakého suffixu nebo suffix nějakého prefixu - jak najít jehlu - můžeme hledat jehlu na každém indexu sena → $\Theta(J\cdot S)$ - můžeme po nenalezení přeskočit dál → nefunguje, viz seno "clanekokokosu", jehla "kokos" - postupně si vytváříme seno - df: stav algoritmu := nejdelší prefix jehly, který je suffixem sena - … - hledání více jehel v kupce sena – algoritmus Aho-Corasicková - automat = trie - stavy = prefixy jehel - dopředné hrany = přidání jednoho znaku na konec ($\alpha\to\alpha x$) - konce jehel (označíme v trii) - zpětné hrany – vedou z $\alpha$ do nejdelšího vlastního suffixu $\alpha$, který je stavem (tohle obvykle v trii nebývá) - zkratkové hrany – vedou z $\alpha$ do nejbližšího stavu dosažitelného po zpětných hranách, kde končí jehla - reprezentace automatu - stavy očíslujeme – kořen má číslo 0, ostatní vrcholy libovolná různá - pole Dopředu(stav, písmenko) – obsahuje další stav (podle dopředné hrany) - pole Slovo(stav) – končí v daném stavu slovo? - pole Zpět(stav) – číslo stavu, kam vede zpětná hrana (kromě kořene je vždy právě jedno) - pole Zkratka(stav) – číslo stavu, kam vede zkratková hrana - algoritmus - … - Robinův-Karpův algoritmus - hledání jedné jehly (?) - zahashuju si posloupnost $J$ znaků a porovnám s hashem jehly - postupně přehashovávám pro každý takový úsek sena (hashování v lineárním čase, přehashování v konstantním) - průměrná časová složitost $\Theta(J+S+JV+{SJ\over M})$ pro rovnoměrnou hashovací funkci - přesnější odhad nebude na zkoušce ## Toky v síti - graf - máme zdroj a spotřebič (vrcholy) - trubky (hrany) mají kapacitu (ohodnocení) - trubky jsou orientované - df: síť je čtveřice - orientovaný graf $(V,E)$ - BÚNO symetrický ($uv\in E\implies vu\in E$) - chybějící hrana má jakoby nulovou kapacitu - zdroj $z\in V$ - spotřebič $s\in V,\,s\neq z$ - kapacity $c:E\to\mathbb R_0^+$ - df: tok je funkce $f:E\in\mathbb R_0^+$ taková, že - $\forall e\in E:f(e)\leq c(e)$ - Kirchhoffův zákon (zákon zachování, tekutina se nám nikam neztrácí) … $\forall v\in V,\,v\neq z,s:f^\Delta(v)=0$ - df: pro $v\in V$ - přítok $f^+(v):=\sum_{uv\in E} f(uv)$ - odtok $f^-(v):=\sum_{vw\in E}f(vw)$ - přebytek $f^\Delta(v):=f^+(v)-f^-(v)$ - df: velikost toku $|f|:=f^\Delta(s)$ - pozorování: $f^\Delta(s)=-f^\Delta(z)$ - … - df: toku $f$ přiřadíme průtok $f^*$ - $f^*(uv):=f(uv)-f(vu)$ - pozorování - $f^*(uv)=-f^*(vu)$ - $f^*(uv)\leq c(uv)$ - $-c(vu)\leq f^*(uv)$ - $\forall v\neq z,s:\sum_{uv\in E}f^*(uv)=0$ - tzn. pro takové $v$ platí $\sum_{uv\in E}f^*(uv)=f^\Delta(v)$ - $r(uv):=c(uv)-f(uv)+f(vu)=c(uv)-f^*(uv)$ - lemma: pokud funkce $f^*:E\to\mathbb R$ splňuje tato pozorování, pak existuje tok $f$, jehož průtokem je $f^*$ - důkaz - $uv,vu\in E$ - BÚNO $f^*(uv)\geq 0$ - $f(uv):=f^*(uv)$ - $f(vu)=0$ - takže můžeme místo s toky počítat s průtoky, přičemž si to pak ekvivalentně převedeme na toky - df: k síti $(V,E,z,s,c)$ a toku $f$ v ní je síť rezerv $(V,E,z,s,r)$, kde $r=c-f^*$ - lemma: pro každý tok $f$ v síti $S$ a každý tok $g$ v síti $R(S,f)$ existuje tok $h$ v síti $S$ takový, že $|h|=|f|+|g|$ a $h$ lze najít v čase $O(m)$ - $m$ … počet hran - důkaz: $h^*:=f^*+g^*$ - $h^*(uv)=f^*(uv)+g^*(uv)$ - $g^*(uv)\leq r(uv)\leq c(uv)-f^*(uv)$ - … - df: tok $f$ je blokující $\equiv$ pro každou cestu $P$ ze $z$ do $s$ existuje $e\in P$ taková, že $f(e)=c(e)$ - df: síť $S$ je vrstevnatá (pročištěná) $\equiv$ každý vrchol i hrana leží na nějaké nejkratší cestě ze $z$ do $s$ - Dinicův algoritmus $O(n^2m)$ - $f\leftarrow$ všude nulový tok - opakujeme (tyto kroky tvoří jednu fázi) - $R\leftarrow$ síť rezerv vzhledem k $f$ - smažeme z $R$ nulové hrany - pročistíme $R$ - pokud $R=\emptyset$, skončíme - $g\leftarrow$ blokující tok v $R$ - vylepšíme $f$ pomocí $g$ - vrátíme $f$ - čištění sítě $O(m)$ - pomocí BFS ze $z$ rozdělíme graf na vrstvy - smažeme vrstvy za $s$ - smažeme hrany, které nevedou o vrstvu vpřed (tzn. ty, které vedou o vrstvu zpět a které vedou uvnitř vrstvy) - smažeme slepé uličky (pomocí fronty) - každý vrchol a každá hrana se účastní nejvýš jednou - blokující tok $O(nm)$ - $g\leftarrow 0$ (tok, který je všude nulový) - dokud existuje $P$ cesta ze $z$ do $s$ v $R$ - $\varepsilon\leftarrow\min_{e\in P}(r(e)-g(e))$ - $\forall e\in P: g(e)\leftarrow g(e)+\varepsilon$ a pokud $g(e)=r(e)$, hranu $e$ smažeme - dočistíme síť (kdykoliv smažu hranu, musím se zbavit slepých uliček) - vrátíme $g$ - složitost - krok cyklu (bez čistění) v $O(n)$, cyklus poběží nejvýše $m$-krát, protože pokaždé smažu alespoň jednu hranu - čištění sítě je za všechny iterace $O(m)$ - lemma: během každé fáze vzroste počet vrstev pročištěné sítě aspoň o jedna - důsledek: počet fází $\leq n$ - intuitivní důkaz (zablokovali jsme cesty dané délky) nefunguje – mezi fázemi nám mohly vzrůst rezervy - rezerva vzroste těm hranám, které vedou o vrstvu zpět - nahlédneme, že žádná cesta, která použije alespoň jednu zpětnou hranu nemůže být krátká - nově vzniklá cesta bude mít aspoň o 2 větší délku než nejkratší cesty - df: $f$ je vlna $\equiv$ - $\forall e\in E:f(e)\leq c(e)$ - $\forall v\neq z,s: f^\Delta(v)\geq 0$ - převedení přebytku - $f^\Delta(u)\gt 0$ - $r(uv)\gt 0$ - $\delta:=\min(f^\Delta(u),r(uv))$ - $f'(uv):=f(uv)+\delta$ - důsledky - $f$ zůstane vlnou - $f^\Delta(u)\mathrel{-}=\delta,\;f^\Delta(v)\mathrel{+}=\delta$ - $r(uv)\mathrel{-}=\delta,\;r(vu)\mathrel{+}=\delta$ - výška $h:V\to\mathbb N$ - Goldbergův algoritmus - $f(\_)\leftarrow0$ - $\forall zv\in E: f(zv)\leftarrow c(zv)$ - $h(\_)\leftarrow 0,\;h(z)\leftarrow n$ - dokud $\exists v\neq z,s:f^\Delta(v)\gt 0$ - pokud $\exists vw\in E:r(vw)\gt 0\land h(v)\gt h(w)$ - převedeme po $vw$ - jinak $h(v)\leftarrow h(v)+1$ - vlna: $f:E\to\mathbb R_0^+$ - $f\leq c,\,\forall v\neq z,s:f^\Delta(v)\geq 0$ - převedení po hraně $uv$ - když $f^\Delta(u)\gt 0,\,r(uv)\gt 0$ - $h(u)\gt h(v)$ - tak na hraně $uv$ zvýšíme o $\delta :=\min(r(uv),f^\Delta(u))$ - invariant A (základní) - $f$ je vlna - $\forall v: h(v)$ neklesá - $h(z)=n,\, h(s)=0$ - $\forall v\neq z:f^\Delta(v)\geq 0$ - invariant S (o spádu) - $\nexists uv\in E:r(uv)\gt 0\land h(u)\gt h(v)+1$ - na začátku platí - rozbít se to můžu zvednutím (to se nestane – místo toho se provede převedení) nebo převedením (ale to zvyšuje rezervu jenom do kopce – takže se to taky nemůže stát) - lemma K (korektnosti) - pokud se algoritmus zastaví, finální $f$ je maximální tok - důkaz - $f$ je tok - $f$ je maximální - kdyby nebyl maximální → podle FF existuje nenasycená cesta ze zdroje do spotřebiče - zdroj je ve výšce $n$, spotřebič ve výšce 0, délka cesty je maximálně $n-1$, tudíž tam bude hrana se spádem aspoň dva, která ale na nenasycené cestě nemůže existovat - invariant C (cesta do zdroje) - $\forall v:f^\Delta(v)\gt 0$ - $\exists P$ nenasycená cesta z $v$ do $z$ - důkaz - $A:=\set{t\in V\mid\exists\text{ nenasycená cesta }v\to t}$ - chceme ukázat $z\in A$ - $\sum_{a\in A}f^\Delta(a)=\underbrace{f(\overline A,A)}_{0}-\underbrace{f(A,\overline A)}_{\geq 0}$ - tudíž suma je nekladná - ale v sumě je aspoň jeden prvek kladný - takže tam musí být záporný člen – to je pouze zdroj - invariant V (o výšce) - $\forall v: h(v)\leq 2n$ - invariant C $\implies$ invariant V - uvažme první porušení – zvedáme $v\in V$ z výšky $2n$ - tehdy $f^\Delta(v)\gt 0\implies\exists P$ nenasycená cesta $v\to z$ - $z$ ve výšce $n$, $v$ ve výšce $2n$, umíme dostat spor podobně jako v důkazu lemmatu K - lemma Z (zvednutí) - počet zvednutí je nejvýš $2n^2$ - protože každý z $n$ vrcholů vystoupá nejvýše do výšky $2n$ (z invariantu V) - df: převedení je nasycené $\equiv$ vynuluje rezervu - pozorování: nenasycené převedení po hraně $uv$ vynuluje $f^\Delta(u)$ - lemma S („sytá“ převedení) - počet nasycených převedení $\leq n\cdot m$ - důkaz - uvažme hranu $uv$ - těsně po sytém převedení je $r(uv)=0$ a $uv$ vede z kopce - před dalším sytým převedení $r(uv)\gt 0$ - mezitím se muselo převést v protisměru … tedy $uv$ do kopce - tzn. posloupnost - syté převedení u→v - aspoň 2 zvednutí $v$ - převedení v→u - aspoň 2 zvednutí $u$ - až pak může přijít další syté převedení u→v - podle invariantu V toto max. $n$-krát - df: potenciál $\Phi:=\sum_{v\neq z,s:f^\Delta(v)\gt0}h(v)$ - $\Phi\geq 0$ - na počátku $\Phi=0$ - zvednutí: zvýší $\Phi$ o 1 - celkem $\leq 2n^2$ - sytá převedení po hraně $uv$: změní možná o $-h(u)$ a možná o $+h(v)$, takže se $\Phi$ zvýší nejvýš o $2n$ - celkem $\leq 2n^2m$ - nenasycená převedení po hraně $uv$: určitě změní o $-h(u)$ a možná o $+h(v)$, přičemž $h(u)=h(v)+1$, takže se $\Phi$ sníží aspoň o 1 - lemma N (nenasycená převedení) - počet nenasycených převedení $\in O(n^2m)$ - implementace - $S:=$ seznam vrcholů s přebytkem - údržba O(1) při změně přebytku - výběr v kroku 3 v algoritmu … v O(1) - $\forall v:K(v):=$ seznam hran s nenulovou rezervou, které z vrcholu $v$ vedou z kopce - převedení po $uv$ … O(1) - zvednutí $u$ … O(n) - rozbor složitosti - inicializace v čase $O(m)$ - čas celkem $O(2n^2\cdot n+nm\cdot 1+n^2m\cdot 1)=O(n^2m)$ - **vylepšení Goldbergova algoritmu** - lemma N' - v algoritmu s výběrem nejvyššího $v$ s $f^\Delta(v)\gt 0$ nastane $O(n^3)$ nenasycených převedení - důkaz - $H:=\max\set{h(x)\mid f^\Delta(v)\gt 0,\;v\neq z,s}$ - fáze končí změnou $H$ - zvýšení zvednutím - max. $2n^2$-krát - $H$ vždy roste o 1 - snížení aspoň o 1 - max. $2n^2$-krát (klesá právě tolikrát, kolikrát roste) - pozorování: během jedné fáze se každý vrchol účastní maximálně jednoho nenasyceného převedení - nenasycené převedení vynuluje přebytek - převádí se z kopce → nemůže se zvýšit jeho přebytek - tudíž během fáze je všech nenasycených převedení nejvýš $n$ - fází je $O(n^2)$, takže složitost algoritmus je $O(n^3)$ - odhad není optimální, lze ukázat $O(n^2\sqrt m)$ ## Rychlá Fourierova transformace - $P(x) := \sum_{j=0}^{n-1} p_jx^j$ - $\vec{p}=(p_0,p_1,\dots,p_{n-1})$ - $n$ … velikost polynomu - normalizace: $p_{n-1}\neq 0$ nebo $n=0$ - $(n-1)$ … stupeň polynomu - násobení polynomů - $R=P\cdot Q$ - … - konvoluce vektorů (získání koeficientu $r_t$) … $\Theta(n)$ - násobení vektorů (získání všech koeficientů $r_*$) … $\Theta(n^2)$ - rovnost polynomů – dvě možnosti - identita $P\equiv Q$ – stejné vektory koeficientů po normalizaci - rovnost funkcí – $\forall x:P(x)=Q(x)$ - identita $\implies$ rovnost funkcí … jednoduchá - identita $\impliedby$ rovnost funkcí … podle věty - věta: nechť $P,Q$ jsou polynomy stupně maximálně $d$ a $P(x_j)=Q(x_j)$ pro navzájem různá čísla $x_0,\dots,x_d$, potom $P\equiv Q$ - polynom stupně $d$ je určený $d+1$ body - lemma: pro polynom $P$ stupně $d\geq 0$ je počet $x$ takových, že $P(x)=0$ nejvýše $d$ - dk: - $R:=P-Q$ - $\forall j: R(x_j)=P(x_j)-Q(x_j)=0$ - stupeň $R\leq d$ - podle lemmatu $R\equiv 0$, takže $P\equiv Q$ - kdyby byl $d\geq 0$, tak by to byl spor s lemmatem, protože se $R(x)$ rovná nule v $d+1$ bodech → $d=-1$ → $R\equiv 0$ - graf polynomu - … - násobení polynomů a grafy - … - postřehy - násobením polynomů dostaneme polynom s dvojnásobným stupněm, takže řekneme, že u násobených polynomů je horních $\frac n2$ koeficientů nulových - teorie ke komplexním číslům - … - df: $\omega\in\mathbb C$ je primitivní $n$-tá odmocnina z 1 $\equiv\omega^n=1$ a $\omega^1,\dots,\omega^{n-1}\neq 1$ - pozorování: $\omega^j\neq\omega^k$ pro $0\leq j\lt k\lt n$ - kdyby $\omega^j=\omega^k$, pak $\underbrace{\omega^k\over\omega^j}_{\omega^{k-j}}=1$, což je spor - pozorování: pro sudé $n$ … $\omega^{n/2}=-1$ - protože kroužím od $1$ k $1$ - pro $|x|=1:x^{-1}=\overline x$ - pozorování: $\omega^2$ je primitivní $n/2$-tá odmocnina z 1 - algoritmus FFT - vstup - $n=2^k$ - $\omega$ … primitivní $n$-tá odmocnina z 1 - $(p_0,\dots,p_{n-1})$ … koeficienty polynomu - výstup - $(y_0,\dots,y_{n-1})$ … graf polynomu $P$ v bodech $(\omega^0,\dots,\omega^{n-1})$ - algoritmus - … - inverzní Fourierovu transformaci můžeme počítat jako tu dopřednou, jen vydělením $n$ - celé násobení polynomů umíme v čase $\Theta(n\log n)$ - $\Omega_{jk}=\omega^{jk}$ - lemma: $\Omega^{-1}=\frac 1n\cdot\overline{\Omega}$ - důkaz - poznámka k FFT – dá se implementovat nerekurzivně; lze nahlédnout, že tam vzniká permutace odpovídající seřazení binárních čísel pozpátku - věta: nechť $x\in\mathbb R^n$ a $y=\mathcal F(x)$; potom $y_j=\overline{y_{n-j}}$ pro všechna $j$ - tím pádem můžeme každý reálný vektor zapsat jako lineární kombinaci navzorkovaných sinů a kosinů ## Paralelní algoritmy - hradlo arity $k$ má $k$ vstupů a jeden výstup - počítá funkci $f:\Sigma^k\to\Sigma$ - $\Sigma$ … konečná abeceda, typicky $\set{0,1}$ - booleovská hradla - binární: AND, OR, XOR, $\leq$ (implikace), … (je jich 16) - unární: NOT (a „buffer“) - nulární, konstanty: 0, 1 - $\text{Majorita}(x, y, z)=(x\land y)\lor(x\land z)\lor(y\land z)$ - hradlová síť obsahuje - hradla - vstupní porty - výstupní porty - acyklické propojení - výpočet probíhá v taktech - 0. takt: ohodnotíme vstupní porty a konstanty - $(i+1).$ takt: ohodnotíme hradla a porty, jejichž vstupy byly ohodnoceny nejpozději v $i.$ taktu - tak dostáváme rozklad sítě na vrstvy, kde v $i$-té vrstvě jsou hradla a porty, které byly ohodnoceny v $i.$ taktu - čas = počet vrstev - prostor = počet hradel - nemohli bychom použít počet hradel v největší vrstvě, protože ne všechny hrany vedou o jednu vrstvu (někdy je potřeba, aby si hradlo pamatovalo svůj výsledek během několika taktů) - je nutné omezit počet vstupů a výstupů – jinak bychom mohli cokoliv počítat v konstantním čase - kombinační obvody … na obecné abecedě $\Sigma$ - booleovské obvody … $\Sigma=\set{0,1}$ - hradlová síť má pevnou velikost vstupu - tedy ekvivalent programu ve světě hradlových sítí by byla sada různých hradlových sítí pro různé velikosti vstupu - tedy výpočetní model je neuniformní - chceme tyto sítě efektivně generovat – ale stačí nám polynomiální čas - co se týče časové složitosti hradlových sítí – obvykle chceme polylogaritmickou složitost (tedy nějakou mocninu logaritmu) - $\text{OR}(x_1,\dots,x_n)$ - lze v lineárním čase – vždycky vezmeme výsledek a přiORujeme $x_i$ - nebo v logaritmickém čase – ORujeme po dvojicích - $\Theta(\log n)$ vrstev - $\Theta(n)$ hradel - binární sčítání - $z_i=x_i\oplus y_i\oplus c_i$ - kde $\oplus$ je XOR - $c_{i+1}=\text{Majorita}(x_i,y_i,c_i)$ - jednoduchá implementace má $\Theta(n)$ hladin a $\Theta(n)$ hradel – musíme čekat na přenosy ($c_i$) - jak předpovídat přenosy? - blok – souvislá posloupnost bitů - chování bloku – závislost $c_\text{out}$ na $c_{\text{in}}$ - fáze (ručního?) výpočtu - chování kanonických bloků - zahušťuji přenosy - finální XORy (jedna vrstva) - binární násobení - pomocí ANDu a bitového posunu v $O(1)$ dostaneme $n$ mezivýsledků, ty chceme sčítat - kdybychom sčítali po dvojicích, dostali bychom se na $O(\log^2n)$ - ale my ke sčítání použijeme kompresor – ze 3 sčítanců uděláme dva - v první vrstvě $n$ čísel, v druhé $\frac 23 n$ čísel, ve třetí $(\frac 23)^2 n$ čísel, …, v poslední 2 čísla, ty sečteme klasickou sčítačkou - kompresorových vrstev bude $O(\log n)$, hloubka kompresoru je $O(1)$ - závěrečná sčítačka bude $O(\log n)$ - takže celková složitost násobení bude $O(\log n)$ - v reálných počítačích se používá hradlová síť založena na Fourierově transformaci, protože má menší prostorovou složitost - komparátorová síť - má $n$ vstupů a $n$ výstupů - výstupem je setříděná posloupnost vstupních dat - mezi vrstvami se vždy převádí permutace vstupu – BÚNO výstupy se nevětví - bubble sort lze paralelizovat v $\Theta(n)$ vrstvách - df: posloupnost $x_0,\dots,x_{n-1}$ je - čistě bitonická $\equiv\exists k:x_0\lt x_1\lt \dots\lt x_k\gt \dots\gt x_{n-1}$ - bitonická $\equiv$ má čistě bitonickou rotaci - tedy $\exists l: x_l,x_{l+1},\dots,x_{l+n-1}$ (kde indexy jsou modulo $n$) je čistě bitonická - separátor $S_n$ - na vstupu bitonická posloupnost - na výstupu dvě poloviční bitonické posloupnosti, kde všechny prvky jedné jsou menší než všechny prvky druhé - princip - rozdělím vstup na poloviny - nainstaluju komparátory mezi $i$-tým prvkem v první polovině a $i$-tým prvkem v druhé polovině (takže vlastně $x_i$ a $x_{n/2+i}$) - prvky rozdělím na horu ($n/2$ největších prvků) a údolí ($n/2$ nejmenších prvků) - hora i údolí jsou souvislé - $x_k$ … prvek, kterým začíná hora - $x_{k+n/2}$ … prvek, kterým končí hora - $k$ je BÚNO menší než $n/2$ - jak fungují komparátory? - pro $i\lt k$ neprohazujeme - pro $i\geq k$ prohazujeme - levý výstup = rotace údolí - pravý výstup = rotace hory - bitonická třídička $B_n$ - na vstupu bitonická posloupnost - na výstupu rostoucí posloupnost - $\log n$ pater separátorů - na začátku jeden separátor délky $n$ - každý z výsledků pošleme do separátoru délky $n/2$ - nakonec dostaneme $n$ posloupností délky 1, které jsou vzájemně setříděné - čas $O(\log n)$ - prostor $O(n\log n)$ - slévačka $M_n$ - vstup: dvě monotónní rostoucí posloupnosti o $n$ prvcích - výstup: monotónní posloupnost o $2n$ prvcích - jednu z nich otočíme na klesající → dostaneme bitonickou posloupnost, proženeme ji $B_{2n}$ - třidička $S_n$ - na vstupu je $n$ prvků - na výstupu je monotónní rostoucí posloupnost $n$ prvků - budeme mít $\log n$ pater slévaček, každá má nejhůř $\log n$ pater, takže celkem $O(\log^2n)$ - prostorová složitost $O(n\log^2n)$ - pozorování: prostorová složitost komparátorové sítě může být nejhůř $n$-krát větší než časová složitost - pozorování: z dolního odhadu složitosti třídění plyne, že hloubka každé třídicí sítě je $\Omega(\log n)$ - dá se to $O(\log n)$, ale konstanta je obrovská - algoritmy odvozené od komparátorových sítí se velmi snadno vektorizují ## Dvojrozměrné úlohy - oplocení jabloní - nejlevější jabloň určitě bude součástí plotu - ukotvíme polopřímku v jabloni, otáčíme jí, než se dotkne další jabloně - tenhle postup opakujeme, nakonec dostaneme konvexní obal množiny $x_1,\dots,x_n\in\mathbb R^2$ - předpokládáme body v obecné poloze - budeme „zametat“ rovinu – rovinu přejíždíme přímkou, body na jedné straně jsme zpracovali, body na druhé budeme zpracovávat, bod na přímce právě zpracováváme - máme konvexní obal zpracovaných bodů - $H$ … horní obálka – stáčí se doprava - $D$ … dolní obálka – stáčí se doleva - přidáváme bod - pro obě obálky zkontrolujeme, zda do nich bod můžeme přidat, aniž bychom porušili konvexnost - jinak z dané obálky odstraňujeme body tak dlouho, dokud bod nepůjde napojit - časová složitost - třídění bodů podle $x$-ové souřadnice v $\Theta(n\log n)$ - odstraňování bodů v $O(n)$ … každý bod odstraníme nejvýše jednou - jak poznat, zda můžu napojit bod (neboli kam se křivka stáčí) – pomocí znaménka determinantu matice složené ze souřadnic posledních dvou vektorů - jak řešit body, které nejsou v obecné poloze? - představíme si pootočení soustavy souřadnic o $\varepsilon$ - tedy nebudeme třídit body zleva doprava, ale lexikograficky podle souřadnic (zleva doprava, shora dolů) - průsečíky $n$ úseček - průsečíků je $\Theta(n^2)$ - chceme složitost $O(\text{hezká funkce}(n+p))$ - $p$ … počet průsečíků - předpokládáme obecnou polohu úseček (v daném bodě se protínají právě dvě přímky, žádná z nich nekončí v průsečíku) - zametáme přímkou shora dolů - události: začátky, konce, průsečíky - v danou chvíli máme průřez $\equiv$ množina úseček proťatých zametací přímkou - průřez je seřazen zleva doprava - pozorování: těsně před zametením průsečíku sousedí protínající se úsečky v průřezu - kalendář událostí - algoritmus - … - reprezentace - … - celkem $O((n+p)\log n)$ čas - $O(n)$ paměť - umí se $O(n\log n+p)$ čas - Voroného diagram - místa a oblasti - oblast $o_i$ odpovídá místu $x_i$, je to část roviny, jejíž body jsou k místu $x_i$ blíže než k jinému místu - Voroného diagram je rozkladem roviny na mnohoúhelníkové oblasti, z nichž některé jsou otevřené do nekonečna - mezi nekonečnými paprsky se dá binárně vyhledávat, takže si to zjednodušíme na konečnou verzi - oblast je určena průnikem polorovin - lze zkonstruovat v čase $O(n\log n)$, ale algoritmus přeskočíme - lokalizace bodu - datová struktura pro rozklad roviny na oblasti – mnohoúhelníky - dotaz: do jaké oblasti patří zadaný bod? - přístup 1 - nařežeme rozklad roviny na vodorovné pásy podle vrcholů mnohoúhelníků - takže pro daný dotaz nejdříve binárně vyhledáváme, ve kterém pásu se bod nachází - a potom v pásu binárně vyhledáváme, mezi jaké dvě přímky se bod trefil - dotaz v $O(\log n)$ - paměť $O(n^2)$ - přístup 2 - použijeme algoritmus z průsečíků přímek - použijeme (semi)perzistentní datovou strukturu - pamatuje si historii - zápis → nová verze - dotaz: dostane verzi - umí se semiperzistentní BVS - $O(\log n)$ čas na operaci - $O(\log n)$ paměť na verzi - časová složitost algoritmu - $O(n)$ operací s průřezem → čas $O(n \log n)$ - $O(n)$ verzí → prostor $O(n\log n)$ - perzistence stromu kopírováním cest - AVL vyvažování taky funguje u perzistentního stromu - umí se i konstantní paměť na verzi ## Složitost algoritmů - rozhodovací problém $\equiv$ funkce $f:\set{0,1}^*\to\set{0,1}$ - problém existence párování velikosti $k$ - vstup: bipartitní graf a $k\in\mathbb N$ - df: problém A je převoditelný na problém B $\equiv\exists f:\set{0,1}^*\to\set{0,1}^*$ taková, že $\forall\alpha\in\set{0,1}^*:A(\alpha)=B(f(\alpha))$ a $f$ lze spočítat v čase polynomiálním v $|\alpha|$ - začíme $A\to B$ nebo $A\leq_P B$ - příklad - párování - dán bipartitní graf $G$ a $k\in\mathbb N$ - existuje párování velikosti aspoň $k$? - tok - dána síť $S$ a $t\in\mathbb N$ - existuje tok velikosti $\geq t$? - párování $\to$ tok - lemma - nechť $A\to B$, $B$ řešitelné v polynomiálním čase - potom $A$ je řešitelné v polynomiálním čase - princip - vstup pro $A$ $\xrightarrow{f}$ vstup pro B $\xrightarrow{\text{ALG}(B)}$ výstup - algoritmus pro $B$ je polynomiální, ale k délce vstupu pro $B$ (což je výstup $f$) - důkaz - … - vlastnosti relace převoditelnosti ($\to$) - $A\to A$ - $A\xrightarrow{f} B\land B\xrightarrow{g} C\implies A\xrightarrow{f\circ g} C$ - $\exists A,B:A\to B\land B\to A$ - $A$: vstup má sudou délku - $B$: vstup má lichou délku - není to antisymetrické - $\exists A,B:A\not\to B\land B\not\to A$ - $A$: konstantní 0 - $B$: konstantní 1 - částečné kvaziuspořádání ### SAT - splnitelnost booleovských formulí - vstup: formule v CNF - CNF … konjunkce klauzulí - klauzule … disjunkce literálů - literál … proměnná nebo její negace - výstup: $\exists$ dosazení za proměnné takové, že formule je pravdivá (= splňující ohodnocení) - 3-SAT: navíc každá klauzule obsahuje max. 3 literály - problém: nezávislá množina (NzMna) - … - pozor: převoditelnost z 3-SAT na SAT není identita - je potřeba zvalidovat vstup, jestli je 3-SAT – pro nevalidní vstupy chceme vrátit NE - zajímavější je převod SAT → 3-SAT - vyrábíme ekvisplnitelnou formuli - $(\alpha\lor\beta)\to(\alpha\lor\zeta)\land(\beta\lor\neg\zeta)$ - převod funguje i naopak (viz rezoluce) - jak rozštípnout dlouhou klauzuli délky $\ell$? - $\alpha$ nechť má délku 2 - $\beta$ nechť má délku $\ell-2$ - po přidání $\zeta$ dostanu konjunkci klauzulí délky 3 a $\ell-1$ - klauzuli délky $\ell-1$ štípu dál (pokud je moc dlouhá) - počet štípnutí je shora omezen délkou formule - v polynomiálním čase postupně rozštípeme všechny dlouhé klauzule při zachování splnitelnosti - 3-SAT → NzMna - … - NzMna → SAT - BÚNO $V(G)=[n]$ - $\forall i\in[n]:x_i=1\iff i\in$ NzMna - $\forall ij\in E:(\neg x_i\lor\neg x_j)$ - vytvoříme si tabulku pro nezávislou množinu - $y_{ij}=1\equiv$ vrchol $j$ je $i$-tým v NzMna - $i=1,\dots,k$ - $j=1,\dots,n$ - ve sloupci je maximálně 1 jednička - $\forall i,i',j:(\neg y_{ij}\lor\neg y_{i'j})$ - v řádku je právě jedna jednička - $\forall i,j,j':(\neg y_{ij}\lor\neg y_{ij'})$ - $\forall i:(y_{i1}\lor y_{i2}\lor\dots\lor y_{in})$ - propojíme klauzule - $\forall ij:(y_{ij}\implies x_j)\sim(\neg y_{ij}\lor x_j)$ - tedy umíme SAT ↔ 3-SAT → NzMna → SAT - nahlédneme NzMna ↔ Klika - 3,3-SAT … každá proměnná se vyskytuje v nejvýše třech klauzulích - převod 3,3-SAT → 3-SAT je opět identita s kontrolou syntaxe - 3-SAT → 3,3-SAT - nechť $x$ je proměnná s $k\gt 3$ výskyty - pro každý výskyt si pořídíme nové proměnné $x_1,\dots,x_k$ - ekvivalenci všech $x_i$ zajistíme řetězcem implikací - $x_1\implies x_2$ - $x_2\implies x_3$ - $\quad\vdots$ - $x_k\implies x_1$ - každá proměnná $x_i$ se tudíž vyskytne třikrát - 3,3-SAT* … navíc každý literál max. 2× - použijeme předchozí algoritmus pro všechny proměnné s $\geq 3$ výskyty - 3D-párování - vstup: konečné množiny $H,D,K$ + množina $T\subseteq H\times D\times K$ - výstup: $\exists T'\subseteq T$ taková, že každý prvek $H,D,K$ je v právě jedné trojici v $T'$ - ukážeme 3,3-SAT → 3D-párování - za cvičení 3D-párování → 3,3-SAT - 3,3-SAT → 3D-párování - gadget pro proměnnou - gadget pro klauzuli - zbude zvířátek: 2 × počet proměnných – počet klauzulí - přidáme tolik párů $k,d$ a pro ně trojice se všemi zvířátky - v Průvodci je chyba ### Třídy problémů - df: třída problémů P - $L\in \text P\equiv\exists A$ algoritmus $\exists p$ polynom takový, že $\forall x$ vstup platí, že $A(x)$ doběhne do $p(|x|)$ kroků $\land\;A(x)=L(x)$ - pozorování: $K\to L,\; L\in P\implies K\in P$ - df: třída problémů NP - $L\in \text{NP}\equiv\exists V\in P$ (verifikátor) $\exists g$ polynom (omezení délky certifikátů) $\forall x:L(x)=1\iff$ $\exists y$ (certifikát) $|y|\leq g(|x|)$ (krátký) $\land\;V(x,y)=1$ (schválený) - $\text P\subseteq\text{NP}$ (rovnost se neví) - df: $L$ je NP-těžký $\equiv\forall K\in\text{NP}:K\to L$ - df: $L$ je NP-úplný $\equiv L$ je NP-těžký $\land\;L\in\text{NP}$ - lemma: pokud $L\in P$ je NP-těžký, pak $\text P = \text{NP}$ - důkaz - nechť $K\in\text{NP}$ - $K\to L$ (díky NP-těžkosti) - $\implies K\in P$ … proto $\text{NP}\subseteq \text P$ - věta (Cook, Levin): SAT je NP-úplný - lemma: nechť $K,L\in\text{NP}$, $K\to L$, $K$ je NP-úplný, pak $L$ je NP-úplný - důkaz - nechť $M\in\text{NP}$ - pak $M\to K\to L$ - tedy $M\to L$ - NP-úplné problémy - logické - (CNF) SAT - 3-SAT - 3,3-SAT - obvodový SAT - grafové - nezávislá množina - klika - $k$-obarvitelnost (pro $k\geq 3$) - hamiltonovská cesta/kružnice - 3D-párování - číselné - součet podmnožiny - batoh - 2 loupežníci - nulajedničkové řešení soustavy lineárních rovnic (v $\mathbb Z$) - často se stává, že restrikcí polynomiálního problému dostaneme nepolynomiální - částečný důkaz Cookovy věty - ukážeme, že $L\in\text{NP}$ lze převést na obvodový SAT - obvodový SAT převedeme na SAT ### Co s NP-úplným problémem? - triky a přístupy - uvědomit si, že vstupy, pro něž problém potřebujeme řešit, jsou malé - zjistit, že naše vstupy jsou něčím speciální - např. v případě grafových problémů je náš graf vždycky strom nebo třeba bipartitní - může se stát, že algoritmus bude pro naše vstupy polynomiální - spokojíme se s řešením, které není optimální, ale je blízko optimu – použijeme aproximační algoritmus - typicky jsme schopni dokázat, jak daleko bude výsledek od optimálního řešení - použijeme heuristiku - o takových algoritmech typicky neumíme nic moc dokázat - vše dohromady - největší nezávislá množina ve stromu - lemma: Je-li $T$ strom a $\ell$ jeho list, pak aspoň jedna největší nezávislá množina obsahuje $\ell$. - důkaz - nechť $M$ je nějaká největší nezávislá množina - pokud $\ell\in M$, pak máme hotovo - pokud $\ell\notin M$, pak $\ell$ má souseda $s$ - pokud $s\notin M$, můžu $\ell$ přidat do $M$, což je spor, protože $M$ je největší - pokud $s\in M$, můžu z $M$ odebrat $s$ a přidat tam $\ell$, čímž zachovám velikost $\quad\square$ - hladový algoritmus - DFS(v): - nz(v) <- ANO - Pro s syny v: - DFS(s) - Pokud nz(s)=ANO: - nz(v) <- NE - složitost $O(n)$ - plánování přednášek - známe časový plán přednášek (jednotlivé intervaly) - zjišťujeme, kolik potřebujeme poslucháren - chceme intervalový graf omezit nejmenším počtem barviček - $V:=$ intervaly - $\set{u,v}\in E\equiv u\cap v\neq\emptyset$ - budeme zametat přímku bodem - předpokládejme, že intervaly nezačínají/nekončí stejně (obecná poloha) – z analýzy algoritmu vyplývá, že: - když začínají stejně, nezáleží na pořadí - když končí stejně, nezáleží na pořadí - když jeden začíná a druhý končí ve stejnou chvíli, pořadí zpracování vyplývá z rozhodnutí, jak s takovou situací nakládat (můžeme intervaly chápat jako uzavřené nebo jako otevřené) - udržujeme množinu volných barviček, postupně procházíme po přímce – pokud potkáme začátek intervalu, vezmeme barvičku (když není žádná volná přidáme novou), pokud potkáme konec intervalu, vrátíme barvičku - algoritmus barvení intervalového grafu minimálním počtem barev - setřídíme začátky i konce intervalů $[x_i,y_i]$ - b <- 0, V <- $\emptyset$ - procházíme začátky a konce: - $x_i:$ - pokud $V\neq\emptyset:b_i\leftarrow$ libovolný prvek odebraný z $V$ - jinak - $b\leftarrow b+1$ - $b_i\leftarrow b$ - $y_i:$ do $V$ přidáme $b_i$ - třídění v $O(n\log n)$ - průchod začátků a konců v $2n$ krocích - takže celkem $O(n\log n)$ - batoh - předměty $1,\dots,n$ - hmotnosti $h_1,\dots,h_n$ - ceny $c_1,\dots,c_n$ - nosnost batohu $H$ - chceme $I\subseteq\set{1,\dots,n}$ takovou, že $h(I)\leq H$, $c(I)$ je maximální - chceme algoritmus polynomiální v $n$, $C=\sum_i c_i$ - df: $A_k(c):=$ minimální hmotnost podmnožiny z $\set{1,\dots,k}$, která má cenu $c$ - může být $+\infty$, pokud taková podmnožina neexistuje - sestavujeme tabulku z hodnot $A_k(c)$, kde po řádcích roste $k$ a po sloupcích roste $c$ - v prvním sloupci $c=0$, v prvním řádku $k=0$ - v posledním sloupci $c=C$, v posledním řádku $k=n$ - $A_0(0)=0$ - $A_0(c)=+\infty$ pro $c\gt 0$ - $A_k(c)=\min(A_{k-1}(c),A_{k-1}(c-c_k)+h_k)$ - varianta s $A_{k-1}$ připadá v úvahu, jen pokud $c-c_k\geq 0$ - celou tabulku vyplníme v čase $O(nC)$ - maximální dosažielná cena $c^*:=\max\set{c\mid A_n(c)\leq H}$ - rekonstrukce optimální množiny - tak, že si u každého políčka tabulky pamatujeme maximální prvek dané podmnožiny - stačí projít konstrukci pozpátku (nejsou potřeba ukazatele, stačí jít zpátky odečtením ceny aktuálního maximálního prvku) - nebo se to dá udělat pomocí ukazatelů - problém batohu řešíme v čase $O(nC)$ … pseudopolynomiální - celý algoritmus lze otočit na počítání maximální ceny pro určitou hmotnost a počet předmětů, pak to bude $O(nH)$ - TSP (problém obchodního cestujícího) - v ohodnoceném grafu hledáme nejkratší hamiltonovskou kružnici (každý vrchol navštíví právě jednou) - omezení - úplný graf - délky hran splňují trojúhelníkovou nerovnost - aproximační algoritmy - máme množinu přípustných řešení, mezi nimi nějaké optimum - máme cenovou funkci $c$, která jednotlivá řešení ohodnocuje reálnými čísly - chceme přípustné řešení s minimální (někdy naopak maximální) cenou - aproximační poměr $\alpha$ - $c(\text{výstup})\leq\alpha\cdot\text{optimum}$ - … - 2-aproximace TSP s $\Delta$ nerovností - T <- min. kostra - obejdeme kostru, nachodíme 2T - akorát vrcholy navštěvujeme víckrát - takže přidáme zkratky - díky trojúhelníkové nerovnosti si tím neublížíme - zkratky … $\leq 2T$ - pozorování: $T\leq$ optimum - výstup $\leq 2T\leq 2$ opt. - umí se $1.5$-aproximace - dokážeme, že bez trojúhelníkové nerovnosti nelze obchodního cestujícího aproximovat - věta: pokud pro $t\geq 1$ existuje algoritmus $t$-aproximující TSP v úplných grafech bez trojúhelníkové nerovnosti v polynomiálním čase, pak P = NP - důkaz: $t$-aproximace $\implies$ polynomiální algoritmus pro hamiltonovskou kružnici $\implies$ P = NP - zadaný graf $G$ doplníme na $G'$ úplný graf s ohodnocením hran - hrana v $G$ → hrana v $G'$ délky 1 - nehrana v $G$ → hrana v $G'$ délky $c$ - původní hamiltonovské kružnice budou mít délku $n$ (počet vrcholů) - nové hamiltonovské kružnice budou mít délku $\geq n-1+c$ - potřeujeme $tn\lt n-1+c$ - $c\gt tn-n+1=(t-1)n+1$ - splníme $c=tn$ - batoh - umíme řešit v čase $O(nC)$, kde $C=\sum_ic_i,\;C\leq n\cdot c_\max$ - chceme menší $C$ - idea: $\set{0,\dots,c_\max}\to\set{0,\dots,M}$ - $\hat {c_i}:= c_i\cdot\frac M{c_\max}$ - chyba pro jeden předmět $\leq\frac{c_\max}M$ - chyba celkem $\leq\frac{c_\max\cdot n}M\overset{\text{chceme}}\leq\varepsilon\cdot c^*$ - po zahození předmětů s $h_i\gt H$ bude $c^*\geq c_\max$ - … - ceny můžeme zaokrouhlovat (dostaneme aproximaci), hmotnosti ne, protože by se nám to rozbilo - $(1-\varepsilon)$-aproximace batohu - odstraníme předměty s $h_i\gt H$ - $c_\max\leftarrow\max_ic_i$ - $M\leftarrow\lceil n/\varepsilon\rceil$ - … - analýza chyby - P … optimální řešení původní úlohy - Q … optimální přeškálované úlohy - chceme $c(Q)\geq(1-\varepsilon)\cdot c(P)$ - $\hat c(P)=\sum_{i\in P}\lfloor c_i\cdot \frac M{c_\max}\rfloor\geq\sum_{i\in P}(c_i\cdot\frac M{c_\max}-1)\geq$ - $\geq(\frac M{c_\max}\underbrace{\sum_{i\in P}c_i}_{c(P)})-n$ - $c(Q)=\sum_{i\in Q}c_i\geq\sum_{i\in Q}\hat{c_i}\cdot\frac{c_\max}M=\frac{c_\max}M\cdot\hat c(Q)\geq\frac{c_\max}M\cdot\hat c(P)$ - … - df: polynomiální aproximační schéma (PTAS) $\equiv$ algoritmus, který pro vstup velikosti $n$ a $\varepsilon\gt 0$ najde aproximaci s chybou $\leq\varepsilon$ v čase pro každé $\varepsilon$ polynomiálním - df: plně polynomiální aproximační schéma (FPTAS) … čas O(poly(n,1/$\varepsilon$))