Algoritmy a datové struktury 2

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

• 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

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

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

• 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

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

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

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

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

• $uv,vu\in E$
• BÚNO $f^*(uv)\geq 0$
• $f(uv):=f^*(uv)$
• $f(vu)=0$

$m$ … počet hran

• $h^*(uv)=f^*(uv)+g^*(uv)$
• $g^*(uv)\leq r(uv)\leq c(uv)-f^*(uv)$
• …

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

• 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

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

• 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

• $\forall e\in E:f(e)\leq c(e)$
• $\forall v\neq z,s: f^\Delta(v)\geq 0$

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

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

$f\leq c,\,\forall v\neq z,s:f^\Delta(v)\geq 0$

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

• $f$ je vlna
• $\forall v: h(v)$ neklesá
• $h(z)=n,\, h(s)=0$
• $\forall v\neq z:f^\Delta(v)\geq 0$

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

pokud se algoritmus zastaví, finální $f$ je maximální tok

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

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

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

• počet zvednutí je nejvýš $2n^2$
• protože každý z $n$ vrcholů vystoupá nejvýše do výšky $2n$ (z invariantu V)

počet nasycených převedení $\leq n\cdot m$

• 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

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

počet nenasycených převedení $\in O(n^2m)$

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

• inicializace v čase $O(m)$
• čas celkem $O(2n^2\cdot n+nm\cdot 1+n^2m\cdot 1)=O(n^2m)$

v algoritmu s výběrem nejvyššího $v$ s $f^\Delta(v)\gt 0$ nastane $O(n^3)$ nenasycených převedení

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

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

• 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

polynom stupně $d$ je určený $d+1$ body

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

…

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

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

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

• binární: AND, OR, XOR, $\leq$ (implikace), … (je jich 16)
• unární: NOT (a „buffer“)
• nulární, konstanty: 0, 1

• hradla
• vstupní porty
• výstupní porty
• acyklické propojení

• 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

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

tedy výpočetní model je neuniformní

• 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

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

• 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

• 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

• č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á

• 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

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

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

• 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

dá se to $O(\log n)$, ale konstanta je obrovská

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

• 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

• 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

vstup: bipartitní graf a $k\in\mathbb N$

začíme $A\to B$ nebo $A\leq_P B$

• 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

• nechť $A\to B$, $B$ řešitelné v polynomiálním čase
• potom $A$ je řešitelné v polynomiálním čase

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

…

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

• CNF … konjunkce klauzulí
• klauzule … disjunkce literálů
• literál … proměnná nebo její negace

…

je potřeba zvalidovat vstup, jestli je 3-SAT – pro nevalidní vstupy chceme vrátit NE

• 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

…

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

• 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

použijeme předchozí algoritmus pro všechny proměnné s $\geq 3$ výskyty

• 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

• 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

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

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

• nechť $K\in\text{NP}$
• $K\to L$ (díky NP-těžkosti)
• $\implies K\in P$ … proto $\text{NP}\subseteq \text P$

• nechť $M\in\text{NP}$
• pak $M\to K\to L$
• tedy $M\to L$

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

• ukážeme, že $L\in\text{NP}$ lze převést na obvodový SAT
• obvodový SAT převedeme na SAT

• 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

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

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

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

• 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

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

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