ADS2

• 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

• 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

• 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í

• větví se
• jsou označené vrcholy, kde končí nějaká jehla
• zpětné hrany mohou vést úplně náhodně

• 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

• 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

kontrolujeme manuálně

• 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

kromě zdroje a stoku platí, že dovnitř teče právě tolik jako ven ($f^Δ(v) =

0$pro všechna$v$mimo$z,s$)

• řez toku → velikost toku
• min. řez sítě → max. velikost toku

všechny nasycené a velikost našeho toku je rovna velikosti řezu

o 1

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

• 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

možné cesty je $n$

• 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{++}$

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

• 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

polynomy → grafy → násobení v $Θ(n)$ → polynomy

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

na mocninu $2$ nahoru)

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

$$
\begin{align*}
    y_j &= \sum_{i=0}^{n-1} x_iω^{ij}\\
        &= \sum_{i=0}^{n-1} p_i(ω^j)^i\\
\end{align*}
$$

$$
\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}
$$

• 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é

• carry vyřešíme zvlášť pomocí $\log n$ stromečků, vyhodnocujeme, jestli je carry 0, 1 nebo <

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

• síť složená z vrstev komparátorů – dostanou dva vstupy a pokud jsou ve špatném pořadí, prohodí je

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

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

• 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ů

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

funkce, pro kterou platí, že $∀x: A(x) = B(f(x))$

kvaziuspořádání

negace hran bruh

• pro klauzule delší než 3 – nová proměnná $x$:
• $(v_1 ∨ v_2 ∨ x), (¬x ∨ v_3...)$

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

každá klauzule trojúhélník, všechny $x$ spojeny hranou se všemi $\lnot x$

• 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

• 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

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

počítači, duh

hradel, všechno se dá převést na AND a NOT