## Vyhledávání v textu - $ε$ = prázdný řetězec ### KMP - vyhledávací automat - stav - suffix prohledaného textu, který je nejdelším prefixem jehly - z každého stavu si připravíme hranu, která vede do nejbližšího validního stavu získaného zkracováním stavu od začátku - vyhledávání - pokud lze pokračovat dopředu, udělej to - jinak skákej dozadu, dokud nepůjde jít dopředu - pokud jsi stuck na ε, můžeš skočit o znak dál a zůstat na něm - konstrukce - připravíme si automat s prvním znakem ι - hledáme jehlu v jehle bez prvního znaku - z každého vrcholu vede hrana do aktuálního stavu v tomhle vyhledávání ### AC - automat jako u KMP ale - větví se - jsou označené vrcholy, kde končí nějaká jehla - zpětné hrany mohou vést úplně náhodně - vyhledávání jako u KMP - hlášení - v každém stavu musíme zjistit, jestli není na čase hlásit - buď jsme v koncovém stavu a zahlásíme - nebo zkoušíme skákat po zpětných hranách, jestli nenajdeme další koncový stav - přidáme zpětné hrany, které vedou na nejbližší koncový stav z každého vrcholu - konstrukce - nejdříve všechny dopředné hrany - pak procházíme graf po hladinách a sestrojujeme zpětné hrany jako u KMP - při nalezení zpětné hrany buď - je na konci zpětné hrany koncový stav, zkratka vede do něj - nebo vede zkratka tam, kam vede zkratka z konce zpětné hrany ### RabinKarp - pořídíme okénkový heš, posouváme okýnkem a pokud se shoduje s jehlou, kontrolujeme manuálně - heš: $H(x_1, ..., x_J) = (x_1P^{J-1} + ... + x_JP^0) \mod N$ - posunutí: $H(x_2, ..., x_{J+1}) = (P · H(x_1, ..., x_J) + x_{J+1} - x_1P^{J}) \mod N$ - $P^J$ se dá předpočítat ## Toky v sítích - síť - graf kapacit, má zdroj a stok $(V,E,c,z,s)$ - tok - funkce $f$, která přiřazuje hranám $f(uv) ≤ c(uv)$, v každém vrcholu kromě zdroje a stoku platí, že dovnitř teče právě tolik jako ven ($f^Δ(v) = 0$ pro všechna $v$ mimo $z,s$) - velikost toku $= f^+(s)$ - řez - rozdělení $V$ na $A$ a $B$, kdy $z ∈ A$, $s ∈ B$, $A ∩ B = Ø$, $A ∪ B = V$ - kapacita řezu - součet kapacit všech hran vedoucích mezi stranami řezu - řez toku → velikost toku - min. řez sítě → max. velikost toku - rezerva hrany $r(uv) = c(uv) - f(uv) + f(vu)$, $r(uv) ≠ 0 ⇒ uv$ je nenasycená ### Ford-Fulkerson - začínáme s nulovým tokem - hledáme cestu, kde všechny hrany mají $r(e) ≠ 0$ - zvýšíme na cestě tok o minimum z rezerv hran - vznikne řez, kde do $A$ vedou nenasycené hrany z $z$, tedy hrany na řezu jsou všechny nasycené a velikost našeho toku je rovna velikosti řezu - algoritmus doběhne pro celočíselné sítě, protože pokaždé se zvětší tok alespoň o 1 #### Největší párování - FF jde použít - tok v síti, zdroj → leva strana bip. grafu → prava strana bip. grafu → stok - kapacity 1 - FF doběhne v $𝓞(nm)$ ### Dinic - průtok = tok, kde nám nezáleží, kterým směrem něco teče - $f^*(uv) = f(uv) - f(vu)$ - $f^*(vu) = -f^*(uv)$ - $f^*(uv) ≤ c(uv)$ - platí Kirchhoff - díky výše uvedeným podmínkám můžeme převést průtok na tok - síť rezerv R má místo $c(e)$ $r(e)$ - alg - vytvoříme průtok $f$ nulový - opakuj - vytvoříme síť rezerv, nulové hrany smažeme - najdeme nejkratší cestu z $z$ do $s$ a rozdělíme graf na vrstvy - odstraníme všechny hrany, které vedou uvnitř vrstev nebo za $s$, rekurzivně pak hrany, které nikam nevedou - najdeme max. tok v pročištěné síti, z sítě odstraňujeme dál hrany, které jsme nasytili - vylepšíme $f$ o nový tok - síť rezerv vytvoříme v $𝓞(m)$ - nejkratší cesta a rozdělení na vrstvy je také v $𝓞(m)$ - čištění je v $𝓞(m)$ - hledání max. toku je v $𝓞(nm)$ - iterací je $n$ - v každém kroku se nejkratší cesta zvětší o 1 a délka nejdelší možné cesty je $n$ - složitost je $𝓞(n^2m)$ ### Goldberg - vlna - tok, kde akceptujeme přetlak ve vrcholech mimo $z,s$, ale ne podtlak! - alg - přiřadíme vrcholům výšku $∀u: h(u) ← 0$ - pro zdroj $z$ : $h(z) ← n$ - $f$ je vlna, vytvoříme přelak ze $z: ∀zv ∈ E: f(zv) = c(zv)$ - dokud je v nějakém vrcholu $u$ mimo $s,z$ přebytek - pokud existuje nějaká hrana $uv$, kde $h(u) > h(v)$ a $r(uv)$ > 0 - převedu přebytek – $f(uv) \mathbin{+\mathbin{=}} δ$, kde $δ = \min\{r(uv), f^Δ(u)\}$ - jinak $h(u)\mathbin{++}$ - invarianty a lemmata - základní A - $f$ je vlna - $h(z) = n, h(s) = 0$ - výšky neklesají - přebytky jsou nezáporné (plyne z vlny) - o spádu S - spád na hraně s kladnou rezervou $uv: h(u) - h(v) ≤ 1$ - pokud je na hraně rezerva, vždy nejdříve vyřešíme tu, než zvedneme vrchol, posílání v protisměru taky nejde - korektnost - je tok? kapacitní omezení platí i pro vlny, Kirchhoff - algoritmus se zastaví až když platí Kirchhoff - je maximální? kdyby nebyl, existuje nenasycená cesta, tedy cesta celá z kopce dolů na nejvýše $n-1$ hranách, což je spor s inv. S, musela by se pomocí $n-1$ jedniček snížit z $n$ na $0$ ## Algebraické algoritmy (aneb fakin efeftéčko) - reprezentace polynomu grafem - polynom stupně $n$ je plně určen $n+1$ body - polynom stupně $n$ má nejvýše $n$ kořenů: - je možné z něj vydělit součin nejvýše $n$ závorek formátu: $(x-α)$ - $P(x_j) = Q(x_j)$ pro $x_0...x_d$ - $R := P-Q, R(x_j) = P(x_j) - Q(x_j) = 0$ - $R ≡ 0$, protože je rovno nule v $d+1$ bodech - násobení polynomů pomocí grafu - polynomy → grafy → násobení v $Θ(n)$ → polynomy - pokus o rozděl a panuj - $P(x) = P_s(x^2) + xP_l(x^2)$ - pořád potřebujeme evaluovat polynomy poloviční velikosti v $n$ bodech - řekněme, že určíme $n$ bodů tak, že máme vždy $±x_0...±x_{n/2}$ - pak $x^2 = (-x)^2$ a $P(-x) = P_s(x^2) -xP_l(x^2)$ - stačí nám tedy jen evaluovat rekurenci jen pro prvních $n/2$ bodů - dále v rekurenci už ale pokračovat nemůžeme, protože tam nebude možné rozdělit $x$ symetricky - stejný pokus jako výše, akorát zvolíme $x_j = \sqrt[n]{1}^j$ (zaokrouhlíme $n$ na mocninu $2$ nahoru) - pak $x_j^2 = \sqrt[n/2]{1}^j$ - alg FFT($n=2^k$, $ω$, $p_0...p_{n-1}$) - a = FFT($n/2$, $ω^2$, $p_0,p_2...$) - b = FFT($n/2$, $ω^2$, $p_1,p_3...$) - pro $j$ od $0$ do $n/2-1$ - $x_j = a_j + ωb_j$ - pro $j$ od $n/2$ do $n-1$ - $x_j = a_j - ωb_j$ - DFT je lin. zobrazení vektoru $x_0...x_{n-1}$: $$ \begin{align*} y_j &= \sum_{i=0}^{n-1} x_iω^{ij}\\ &= \sum_{i=0}^{n-1} p_i(ω^j)^i\\ \end{align*} $$ - matice zobrazení $Ω$ je $$ \begin{pmatrix} 1 & 1 & 1 & 1 & ... \\ 1 & (ω^1)^1 & (ω^1)^2 & (ω^1)^3 & ... \\ 1 & (ω^2)^1 & (ω^2)^2 & (ω^2)^3 & ... \\ 1 & (ω^3)^1 & (ω^3)^2 & (ω^3)^3 & ... \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{pmatrix} $$ - $Ω · \overline Ω = n · E ⇒ Ω^{-1} = \frac 1n \overline Ω$ ## Paralelní algoritmy - hradlová síť - DAM (DAG, but mutligraf) - vstupy, hradla a výstupy - hradla mají aritu - všechno musí být korektně zapojené - přípojky do hradel jsou očíslované - sčítání - carry vyřešíme zvlášť pomocí $\log n$ stromečků, vyhodnocujeme, jestli je carry 0, 1 nebo < - násobení - vytvoříme si pro bity čísel $x_n...x_0$ a $y_n...y_0$ $n^2$ čísel: $$ (x_n \and y) \ll n, ... , (x_0 \and y) \ll 0 $$ - tyto čísla pak sečteme pomocí kompresorů - v konstantní hloubce udělají z tří čísel dvě jejichž součet je stejný jako původních 3 - první číslo reprezentuje součet všech tří bez carry $p = x \oplus y \oplus z$ - druhé číslo jsou všechny carry bity $q_{i+1} = maj(x_i, y_i, z_i)$ - kompresory zkompresují všechna čísla v $𝓞(\log_{2/3}n) = 𝓞(\log n)$ (zbývající dvě vezmeme třeba normální sčítačkou) - komparátorová síť - síť složená z vrstev komparátorů – dostanou dva vstupy a pokud jsou ve špatném pořadí, prohodí je - bitonické třídění - chceme mergesort, na ten potřebujeme slévací krabičky - slévací krabička je např. bitonická třídička - bitonická třídička lze složit ze separátorů, které umí rozložit bit. posloupnost na dvě, kde jedna je celá menší než druhá - separátor porovnává $x_i$ s $x_{n/2+i}$ - všechny lze porovnat paralelně - $\log n$ separátorů je třídička = slévací krabička (dvě posloupnosti slejeme tak, že druhou otočíme a bitonicky setřídíme), těch potřebujeme také $\log n$, celkem $𝓞(\log ^2 n)$ ## Geometrické algoritmy - konvexní obal - zametáme, stack horní a spodní, ze stacku odstraňujeme body, pokud zatáčíme na druhou stranu - každý bod jednou přidáme jednou odebereme $𝓞(n)$ - průsečíky úseček - zametáme, máme průřez a kalendář, na začátku jsou v kalendáři jen začátky a konce úseček - bereme z kalendáře - začátek: přidáme úsečku do průřezu a přidáme do kalendáře průsečíky všech nově sousedících úseček a odstraníme těch, které už nesousedí - konec: odebereme úsečku z průřezu a opět aktualizujeme průsečíky v kalendáři - průsečík: zahlásíme průsečík, prohodíme úsečky v průřezu, aktualizujeme kalendář - kalendář je halda, $𝓞(\log n)$ na operaci, průřez je strom, taky $𝓞(\log n)$ na operaci - z kalendáře odebereme jednou začátek, jednou konec každé úsečky a každý hlášený průsečík, po každém odebrání provedeme $𝓞(\log n)$ operací s DS, celá složitost je $𝓞((n+s) \log n)$, kde $s$ je výsledný počet průsečíků - Voroného diagram - zametáme přímkou, udržujeme pobřeží a kalendář - v kalendáři jsou všechna místa - odebíráme z kalendáře - pokud místo - přidáme parabolu, v pobřeží doprostřed tím rozdělíme už existující region, v diagramu začne vznikat úsečka rozdělující nové místo a místo původní paraboly - pokud kružnice - daná parabola zanikne, ve středu kružnice v diagramu vznikne bod zakončující úsečku krajních míst s prostředním a začne vznikat úsečka obou krajních míst mezi sebou - aktualizujeme kružnicové události - $𝓞(n \log n)$ ## Převody problémů ### Rozhodovací problémy - funkce $\{0,1\}^* → \{0,1\}$ ### Bipart. párování jako rozhodovací problém - $t$ jedniček – určíme si velikost slova - jedno slovo pro $n$ - jedno slovo pro $k$ (kolik chceme aby existovalo minimálně hran v párování) - $n^2$ bitů pro matici sousednosti ### Převody mezi problémy - problém $A$ je převoditelný na $B$ ($A → B$), pokud existuje polynomiální funkce, pro kterou platí, že $∀x: A(x) = B(f(x))$ - převoditelnost je tansitivní, reflexivní, ale ne nutně antisymetrická – kvaziuspořádání - klika ↔ nezávislá množina - negace hran bruh - SAT → 3-SAT - pro klauzule delší než 3 – nová proměnná $x$: - $(v_1 ∨ v_2 ∨ x), (¬x ∨ v_3...)$ - 3-SAT → 3,3-SAT - pokud se proměnná vyskytuje víc než 3×, vytvoříme novou proměnnou za každý výskyt a vytvoříme chain implikací: - $(x_1 ⇒ x_2), (x_2 ⇒ x_3), ..., (x_n ⇒ x_1)$ - 3-SAT → NzMna - každá klauzule trojúhélník, všechny $x$ spojeny hranou se všemi $\lnot x$ - NzMna → SAT - vrchol → proměnná - hrana → klauzule - vynucení počtu pomocí matice $X$ velikosti ${k×n}$, $X_{ij} = 1 ≡$ vrchol $j$ je $i$-tým vrcholem v NzMně - v každém sloupci nejvýše jedna 1 - v každém řádku právě jedna 1 - 3,3-SAT → 3D párování - gadget pro proměnnou – čtyři trojice, cyklus K,D,K,D, ke každé trojici připojeno jedno Z – nesmí se zároveň použít horizontální a vertikální Z - gadget pro klauzuli – dvojice K,D, připojena k trojici Zek, jedno z každé proměnné, horizontální pro $¬$, vertikální pro $¬¬$ - dostatek univerzálních K a D pro nevyužitá Z ## NP-úplnost - problém je v P, pokud je řešitelný poly. algoritmem - problém $L$ je v NP, pokud pro $K$ v P platí ekvivalence $∀x: L(x) = 1 ⟺ ∃y: K(x,y) = 1$ - $A→B ∧ B∈P ⇒ A∈P$ - proof by fucking obviousness - $A→B ∧ B∈\text{NP} ∧ \text{NP-complete}(A) ⇒ \text{NP-complete}(B)$ - dokazuji, že $B$ je NP-těžký, pokud $A$ je NP-těžký, pokud všechno můžu převést na A, můžu to pak převést i na B - SAT je NP-úplný – obvod-SAT je NP-úplný, protože je umíme reprezentovat v počítači, duh - obvod SAT → SAT – proměnné reprezentují splnitelnost vstupu nebo výstupu hradel, všechno se dá převést na AND a NOT ### klasické NP-úplné problémy - SAT, 3-SAT, 3,3-SAT, obvod-SAT - klika, NzMna, 3D-párování - batoh - zloději - Ax = 1 - Ham. kruž. - plnění kyblíků wahoo - TSP - barvení grafů - součet podmnožiny