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