Algoritmy a datové struktury 2

Při sepisování poznámek jsem hodně čerpala z Průvodce labyrintem algoritmů. Z knihy jsem přejala většinu značení a mnoho obrázků.

Prohledávání řetězců

Značení

Inkrementální algoritmus

Knuth-Morris-Pratt algoritmus

barbarossa

kmpkrok

Analýza složitosti

Lemma: Funkce $\text{KmpHledej}$ běží v čase $\Theta (S)$

Konstrukce automatu

Analýza složitosti

Aho-Corasicková

Automat

Aho-Corasick se zkratkovými hranami

Reprezentace

Algoritmus

ackrok

achledej

Analýza složitosti

Konstrukce automatu

ackonstrukce

Rabin–Karp

Hashovací funkce

$$ H(x_1, ..., x_J) = (x_1P^{J-1} + x_2P^{J-2}+...+x_{J-1}P^1+x_JP^0) \mod{N} $$$$ \begin{align*} H(x_2,...,x_{J+1})&=(x_2P^{J-1} + x_3P^{J-2}+...+x_JP^1+x_{J+1}P^0) \mod{N} \\ &= (P\cdot H(x_1,...,x_J) - x_1P^J + x_{J+1}) \mod{N} \end{align*} $$

Algoritmus Rabin-Karp

Analýza složitosti

Toky v sítích

Síť

Definice: Síť je uspořádaná pětice $(V, E, z, s, c)$, kde:

Tok

Definice: Tok v síti je funkce $f: E \rightarrow \R^{+}_0$, pro níž platí:

  1. Tok po každé hraně je omezen její kapacitou $\forall e \in E : f(e) \leq c(e)$.

  2. Kirchhoffův zákon: Do každého vrcholu přiteče stejně, jako z něj odteče („síť těsní”).

    Výjimku může tvořit pouze zdroj a spotřebič. Formálně:

$$ \forall v \in V \setminus \{z, s \} : \sum_{u:uv \in E} f(uv) = \sum_{u:vu \in E} f(vu) $$

tok

Lemma: $f^{\Delta}(z) = -f^{\Delta}(s)$

Ford-Fulkerson

ford-fulkerson

Konečnost

Analýza složitosti

Maximalita toku

rez_draw

$$ f^{\Delta}(A,B) = \sum_{v\in B}f^{\Delta}(v) = f^{\Delta}(s) = |f| $$

Lemma: pokud se Ford-Fulkersonův algoritmus zastaví, vydá maximální tok

Maximální párování

párování

Analýza složitosti

Dinicův algoritmus

Síť rezerv

Definice: každé hraně přiřadíme její průtok $f^*(uv) = f(uv)-f(vu)$ (tok tam mínus tok zpět)

  1. $f^*(uv) = - f^*(vu)$
  2. $f^*(uv) \leq c(uv)$
  3. $f^*(uv) \geq -c(vu)$ – plyne z předchozích dvou
  4. pro všechny vrcholy $v \neq z, s$ platí, že $\sum_{u:uv \in E}f^*(uv) = 0$
    • opět Kirchhoffův zákon – co přiteče hranami dovnitř, vyteče hranami na druhé straně ven
    • stejný vztah jako pro přebytek $f^{\Delta}(v)$ popsaný ve FF alg.
    • $f^*(uv) = -f^*(vu)$

Lemma P (o průtoku)

Lemma Z (o zlepšování toků)

Definice: Tok je blokující, jestliže na každé orientované cestě ze zdroje do spotřebiče existuje alespoň jedna hrana, na níž je tok roven kapacitě

Definice: Síť $S$ je vrstevnatá (pročištěná), pokud každý vrchol i hrana leží na nějaké nejkratší cestě ze $z$ do $s$

vrstvy

dinic

dinic_vrstvy

cisteni

blokující tok

Analýza složitosti

Goldbergův algoritmus

Vlna

Definice: Funkce $f : E \rightarrow \R^⁺_0$ je vlna v síti $(V,E,z,s,c)$, splňuje-li obě následující podmínky

  1. $\forall{e} \in E:f(e) \leq c(e)$ – vlna nepřekročí kapacity hran
  2. $\forall{v} \in V \setminus \{z,s\} : f^{\Delta}(v) \geq 0$ – přebytek ve vrcholu je nezáporný
    • mohou mít přebytky, ale nesmí mít deficity

Převedení vlny po hraně $uv$

Definice: převedení je nasycené, když vynuluje rezervu hrany

Algoritmus

Goldbergův algoritmus

Poznámky k implementaci

Analýza složitosti

Invariant A (základní)

  1. $f$ je vlna
  2. $\forall v: h(v)$ neklesá
  3. $h(z) = n$ a $h(s) = 0$
  4. $\forall v \ne z: f^{\Delta}(v) \ge 0$

Invariant S (o spádu)

Lemma K (o korektnosti)

Důkaz

Invariant C (o cestě do zdroje)

Důkaz

Invariant H (o výšce)

Invariant Z (o zvednutí)

Lemma Sp (o sytých převedeních)

Důkaz

Lemma Np (o nenasycených převedeních)

Definice: potenciál $\phi := \sum\limits_{\substack{v \in z,s \\ f^{\Delta}(v > 0)}} h(v)$ – součet výšek vrcholů s přebytkem

  1. $\phi \ge 0$
  2. na počátku $\phi = 0$
  3. zvednutí
    • zvýší $\phi$ přesně o 1
    • stane se nejvýše $2n^2$-krát
  4. Sp
    • mohlo se stát, že $v$ mělo předtím nulový přebytek, ale nyní jsme ho zvětšili, tedy jeho výška bude započítána do $\phi$
    • mohlo se stát, že $u$ mělo předtím nenulový přebytek, ale nyní jsme ho vynulovali, tedy jeho výška zmizí z $\phi$
      • $\phi$ se zvýšil nejvýše o $2n$
      • všechna nasycená převedení zvýší potenciál maximálně o $2n^2m$
  5. Np
    • určitě se vynuluje přebytek $u$, jeho výška z $\phi$ určitě zmizí
    • možná se z nulového přebytku $v$ stane nenulový, tedy jeho výška bude započítána do $\phi$
      • $\phi$ se snížil alespoň o 1

Vylepšení Goldbergova algoritmu

Lemma Np’

Důkaz

Rychlá Fourierova transformace

Polynomy

$$ P(x) := \sum^{n-1}_{j=0}p_jx^j $$

Rovnost polynomů

Věta: Nechť $P$, $Q$ jsou polynomy stupně max. $d$ a $P(x_j) = Q(x_j)$ pro navzájem různá čísla $x_0$ až $x_d$. Potom $P=Q$.

Lemma: Pro polynom $P$ stupně $d \ge 0$, počet kořenů je nejvýše $d$

Důkaz věty: $R:= P-Q$

Násobení

$$ \begin{align*} R &= P\cdot Q \\\\ R(x) &= (\sum^{n-1}_{j=0}p_jx^j)\cdot (\sum^{n-1}_{k=0}q_kx^k) \\ &= \sum^{n-1}_{j, k=0}p_j \cdot q_k \cdot x^{j+k} \\ &= \sum^{2n-2}_{t=0}( x^t \cdot (\sum^t_{j = 0}p_j \cdot q_{t-j}) ) \end{align*} $$

Graf polynomu

(Chybné) rychlé vyhodnocování

$$ P(x) = (p_0x^0+p_2x^2+\dots+p_{n-2}x^{n-2})+(p_1x^1+p_3x^3+\dots+p_{n-1}x^{n-1}) $$$$ P(x) = (p_0x^0+p_2x^2+\dots+p_{n-2}x^{n-2})+x\cdot(p_1x^0+p_3x^2+\dots+p_{n-1}x^{n-2}) $$$$ P(x)=P_s(x^2)+x\cdot P_l(x^2) $$$$ P(-x)=P_s(x^2)-x\cdot P_l(x^2)_s $$

Intermezzo o komplexních číslech

Algebraický tvar

Goniometrický tvar

Exponenciální tvar

Odmocniny z jedničky

Definice: $\omega \in \C$ je primitivní $n$-tá odmocnina z 1 tehdy, když $\omega = 1$ a $\omega ^1$ až $\omega ^{n-1} \ne 1$

FFT

FFT

$$ \mathcal{F}(\vec{v})_k = (\Omega \cdot \vec{v})_k = \sum_{j=0}^{n-1}\vec{v}_j \cdot \omega^{j \cdot k} $$$$ \Omega = \begin{pmatrix} 1 & 1 & 1 & ... & 1 \\ 1 & \omega^1 & \omega^2 & \ldots & \omega^{n-1} \\ 1 & \omega^2 & \omega^4 & \ldots & \omega^{n - 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{n-2} & \ldots & \omega^1 \end{pmatrix} $$

Inverzní FFT

$$ \mathcal{F}^{-1}(\vec{v})_k = \frac{1}{n}\sum^{n-1}_{j=0}\vec{v}_j\cdot \omega^{(n-j)\cdot k} $$$$ \begin{align*} \Omega = \begin{pmatrix} 1 & 1 & 1 & ... & 1 \\ 1 & \omega^1 & \omega^2 & \ldots & \omega^{n-1} \\ 1 & \omega^1 & \omega^4 & \ldots & \omega^{n - 2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{n-2} & \ldots & \omega^1 \end{pmatrix} && \bar{\Omega} = \begin{pmatrix} 1 & 1 & 1 & ... & 1 \\ 1 & \omega^{n-1} & \omega^{n-2} & \ldots & \omega^1 \\ 1 & \omega^{n-2} & \omega^{n-4} & \ldots & \omega^{2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^1 & \omega^2 & \ldots & \omega^{n-1} \end{pmatrix} \end{align*} $$ $$ \begin{align} (\Omega \cdot \bar{\Omega})_{jk}=\sum_l \Omega_{jl} \cdot \bar{\Omega}_{lk} = \sum_l \omega^{jl - kl} = \sum_l (\omega^{j-k})^l = \frac{(w^n)^{j-k}-1}{w^{j-k}-1} \end{align} $$

Vzorkování periodických funkcí

Věta: Nechť $\vec{x} \in \R^n$ a $\vec{y} = \mathcal{F}(\vec{x})$. Potom $\vec{y}_j = \overline{\vec{y}_{n-j}}$ pro všechna $j$

Paralelní algoritmy

Hradlo

Boolovská hradla

Hradlové sítě

Majorita

majorita

Složení hradlových sítí

Průběh výpočtu

vrstvy majority

Posloupnosti hradlových sítí

obecný ORrychlejší obecný or

Sčítání

![Paralelní sčítačka](/images/paralelní sčítačka.png)

Násobení

Násobení

Kompresor

Binární kompresor

Třídění

Komparátorová síť

Bubble sort

![Paralelní bubble sort](/images/paralelní bubble sort.png)

Bitonické třídění

Definice: Posloupnost $x_0,\dots,x_{n-1}$ je čistě bitonická, pokud ji můžeme rozdělit na nějaké pozici $k$ na rostoucí posloupnost $x_0,\dots,x_k$ a klesající posloupnost $x_k,\dots,x_{n-1}$.

Definice: Posloupnost je bitonická, jestliže ji lze získat rotací nějaké čistě bitonické posloupnosti

Separátor

Separátor S₈

Důkaz správnosti

Důkaz funkčnosti separátoru

Bitonická třídička

Bitonická slévačka

Třídící síť

Geometrické algoritmy

Konvexní obal

Konvexní obal pro malé počty bodů

Algoritmus Konvexní obal

Orientace úhlu

$$ \begin{align*} \mathbf{u} = \begin{pmatrix} x_1 \quad y_1 \end{pmatrix} \quad \mathbf{v} = \begin{pmatrix} x_2 \quad y_2 \end{pmatrix} \\ \\ M = \begin{pmatrix} \mathbf{u} \\ \mathbf{v} \end{pmatrix} = \begin{pmatrix} x_1 \quad y_1 \\ x_2 \quad y_2 \end{pmatrix} \\ \\ \det(M) = x_1y_2-x_2y_2 \end{align*} $$

Determinanty různých znamének v rovině

Analýza složitosti

Průsečíky úseček

Průřez a události v kalendáři

Algoritmus průsečíky úseček

Reprezentace

Analýza složitosti

Voroného diagramy

Voroného diagram

Lokalizace bodu

Oblasti rozřezané na pásy

Analýza složitosti

Předvýpočet

Persistentní vyhledávací stromy

Persistentní AVL strom

Těžké problémy

Rozhodovací problém

Bipartitní párování

Převádění

Definice: Jsou-li $A$, $B$ rozhodovací problémy, říkáme, že $A$ lze převést na $B$ (značíme $A \rightarrow B$) právě tehdy, když existuje funkce $f: \{0, 1 \}^* \rightarrow \{0, 1 \}^*$ taková, že pro všechna $x \in \{0, 1 \}^*$ platí $A(x) = B(f(x))$, a navíc lze funkci $f$ spočítat v čase polynomiálním vzhledem k $|x|$. Funkci $f$ říkáme převod nebo také redukce.

Lemma: Nechť $A \rightarrow B$ a $B$ je řešitelné v polynomiálním čase, pak $A$ je řešitelné v polynomiálním čase

Převoditelnost jako relace

SAT

CNF

$$ (x \or y \or z) \and (\neg x \or y \or z) \and (x \or \neg y \or \neg z) \and (x \or y \or \neg z) $$

3-SAT

SAT $\rightarrow$ 3-SAT

$$ (\alpha \or \beta) \rightarrow (\alpha \or \chi) \and (\beta \or \neg \chi) $$

3,3-SAT

3-SAT $\rightarrow$ 3,3-SAT

Nezávislá množina

3-SAT $\rightarrow$ NzMna

$$ (x \or y \or z) \and (x \or \neg y \or \neg z) \and (\neg x \or \neg y \or p) $$

Nezávislá množina

NzMna $\rightarrow$ SAT

tabulka pro NzMna

Klika

Klika v grafu a nezávislá množina v jeho hranovém doplňku

3D-párování

3D-párování

3,3-SAT $\rightarrow$ 3D-párování

Gadget pro proměnnou

Gadget pro proměnnou

Gadget pro klauzuli

Gadget pro klauzuli

Zapojení gadgetů pro proměnné do gadgetů pro klauzule (mandatory hákáče included)

Složitostní třídy

Třída P

Definice: Problém $L$ leží v $\text{P}$ tehdy, když existuje nějaký algoritmus $A$ a polynom $f$, přičemž pro každý vstup $x$ algoritmus $A$ doběhne v čase nejvýše $f(|x|)$ a vydá výsledek $A(x)=L(x)$

Třída NP

Definice: $\text{NP}$ je třída rozhodovacích problémů, v níž problém $L$ leží tehdy, když existuje nějaký problém $K \in \text{P}$ a polynom $g$, přičemž pro každý vstup $x$ je $L(x) = 1$ právě tehdy, když pro nějaký řetězec $y$ délky nejvýše $g(|x|)$ platí $K(x,y) = 1$

Třídy problémů NP

NP certifikáty

NP-hard

Definice: Problém $L$ je $\text{NP}$-těžký tehdy, když každý problém $K \in \text{NP}$, lze převést na $L$

NP-complete

Definice: Problém $L$ je $\text{NP}$-úplný tehdy, když je $\text{NP}$-těžký a navíc $L\in\text{NP}$

Lemma: pokud $L \in \text{P}$ je $\text{NP}$-těžký, pak $\text{P}=\text{NP}$

Cook-Levinova věta

Věta: SAT je $\text{NP}$-úplný

Lemma: Nechť $L$ je problém ležící v $P$. Potom existuje polynom $p$ a algoritmus, který pro každé $n$ sestrojí v čase $p(n)$ hradlovou síť $B_n$ s $n$ vstupy a jedním výstupem, která řeší $L$.

Úprava definice NP: Budeme chtít, aby nápověda $y$ měla pevnou velikost závislou pouze na velikosti vstupu: $|y| = g(|x|)$ (napísto předchozího $|y| \le g(|x|)$)

NP-úplnost obvodového SATu

Obvodový SAT $\rightarrow$ 3,SAT

NOT

hradlo NOT v CNF

AND

hradlo AND v CNF

Co s NP-úplným problémem?

  1. malé vstupy
    • stačí problém umlátit vhodně ořezaným exponenciálním algoritmem
  2. speciální vstupy
    • na stromech – většinou lineární
    • na bipartitních grafech – většinou bude existovat polynomiální algoritmus (často odvozený od toků v sítích)
  3. aproximační algoritmy – existuje docela dobrá aproximace v polynomiálním čase
    • umíme vždy dobře říct, jak daleko je aproximace od optima
  4. heuristické přístupy – v některých případech bude výsledek fajn, jindy fakt mizerný
    • neumíme říct, jak daleko je výsledek od optima
  5. kombinace
    • heuristické řešení může rozdělit problém na malé podproblémy, které řeší optimálně v exponenciálním čase
    • aproximační algoritmus si může zkusit pomoct heuristikou pro nalezení potenciálně lepšího řešení

Největší nezávislá množina ve stromu

Lemma: Je-li $T$ strom (funguje i pro lesy :evergreen_tree::deciduous_tree:) a $l$ jeho list, pak alespoň 1 největší nezávislá množina obsahuje $l$

Algoritmus

Nezávislá množi na ve stromu

Barvení intervalového grafu

Obarvený intervalový graf

Intervalový graf:

Algoritmus

barvení intervalového grafu

Problém batohu s malými čísly

Definice: $A_k(c) := $ minimum z hmotností těch podmnožin velikosti $k$, které jejichž cena je právě $c$

Aproximační algoritmy

TSP – Problém obchodního cestujícího

2-aproximace

kostra TSP se zkratkami

Pozorování: $T \le \text{OPT}$ – když z nejkratší hamiltonovské kružnice smažeme hranu, získáme minimální kostru

Nutnost trojúhelníkové nerovnosti

Věta: TSP nejde bez trojúhelníkové nerovnosti aproximovat (jinak by platilo $\text{P}=\text{NP}$)

Problém batohu s velkými čísly

Aproximační algoritmus pro problém batohu

Analýza složitosti

Analýza chyby

$$ \hat{c}(P) = \sum_{i\in P}\hat{c}_i =\sum_{i\in P}\left\lfloor c_i \cdot \frac{M}{c_{max}} \right\rfloor \ge \sum_{i \in P} \left(c_i \cdot \frac{M}{c_{max}} - 1 \right) \ge \left(\sum_{i \in P} c_i \cdot \frac{M}{c_{max}} \right) - n = c(P) \cdot \frac{M}{c_{max}} - n \\ \hat{c}(P) \ge c(P) \cdot \frac{M}{c_{max}} - n $$$$ c(Q) = \sum_{i\in Q}c_i \ge \sum_{i\in Q}\hat{c}_i \cdot \frac{c_{max}}{M} = \left(\sum_{i \in Q} \hat{c}_i \right) \cdot \frac{c_{max}}{M} = \hat{c}(Q) \cdot \frac{c_{max}}{M} \ge \hat{c}(P) \cdot \frac{c_{max}}{M} \\ c(Q) \ge \hat{c}(P) \cdot \frac{c_{max}}{M} $$$$ c(Q) \ge \left(\frac{c(P)\cdot M}{c_{max}} - n \right) \cdot \frac{c_{max}}{M} \ge c(P) - \frac{n \cdot c_{max}}{n/\epsilon} \ge c(P) - \epsilon \cdot c_{max} \ge c(P) - \epsilon \cdot c(P) = (1-\epsilon) \cdot c(P) \\ c(Q) \ge (1-\epsilon) \cdot c(P) $$

Aproximační schéma