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