Zkouška

• slovo $\alpha$ … konečná posloupnost znaků z abecedy $\Sigma$
• prázdný řetězec $\varepsilon$
• $i$-tý znak $\alpha[i]$ (počítáme od nuly)
• podřetězec/podslovo $\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$

• udržujeme si informaci o tom, jakým nejdelším prefixem jehly končí zatím přečtená část sena
• tento prefix postupně zvětšujeme – pokud nejde zvětšit, pomocí zpětné funkce získáme menší prefix jehly a zkusíme zvětšit ten
• pro získání zpětné funkce stačí postavit vyhledávací automat nad jehlou
  • vrcholy (stavy) = prefixy jehly (od prázdného prefixu $\varepsilon$ k celé jehle)
  • dopředné hrany … spojují prefixy zleva doprava
  • zpětné hrany … odpovídají zpětné funkci (např. z barba vede zpětná hrana do ba)
• algoritmus rozdělíme na tři
  • KmpKrok
    • spouštíme pro nově přečtený znak a aktuální stav, vrátí nám nový stav
    • algoritmus projde po zpětných hranách (postupně zkouší kratší a kratší prefixy), dokud nedojde do stavu 0 ($\varepsilon$) nebo nenajde prefix, který pokračuje tím přečteným znakem
    • pokud ten prefix najde, tak stav zvýší o jedna
    • implementační detail: za poslední znak jehly musíme připojit fiktivní znak (takový, který se v seně nevyskytuje)
  • KmpHledej
    • spouštíme pro seno a automat nad jehlou, postupně jsou hlášeny jednotlivé výskyty
    • iterujeme přes všechny znaky sena a spouštíme KmpKrok
    • pokud se stav rovná délce jehly, ohlásíme výskyt
    • časová složitost $\Theta(S)$
      • pro každý znak se prochází nejvýše po jedné dopředné hraně
      • každá zpětná hrana vede aspoň o jeden stav doleva – tedy průchodů po zpětných hranách bude nejvýše tolik, po kolika dopředných hranách jsme prošli
  • KmpKonstrukce
    • nastavíme zpětnou hranu ze stavu 1 do stavu 0
    • provádíme jakoby KmpHledej, akorát jako seno použijeme jehlu bez prvního znaku
    • na základě výsledného stavu z každého kroku algoritmu nastavíme zpětnou hranu
    • časová složitost $\Theta(J)$
• celkem čas $\Theta(J+S)$

• 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 (použijeme při hlášení výskytů)
• 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
• algoritmy/procedury
  • AcKrok
    • na vstupu aktuální stav a přečtený znak, na výstupu nový stav
    • projde dopředu po jedné hraně z aktuálního stavu nebo zkouší procházet po zpětných hranách, dokud nebude moct projít dopředu (přinejhorším vrátí kořen)
  • AcHledej
    • na vstupu seno a automat, postupně ohlašuje výskyty
    • spouští AcKrok pro každý znak sena
    • pokud je v daném stavu označen konec jehly, hlásí výskyt
    • prochází po zkratkových hranách a hlásí jednotlivé výskyty
    • složitost $\Theta(S+V)$, kde $S$ je délka sena a $V$ je počet výskytů
  • AcKonstrukce
    • nejdříve sestrojíme trii
    • zpětné hrany můžou vést křížem mezi větvemi stromu
    • proto je konstruujeme po hladinách (BFS, pomocí fronty)
    • pro vrchol $v$ a rodiče $r$ zkusíme k vrcholu Zpět(r) přidat písmeno na hraně $rv$, čímž dostaneme Zpět(v)
    • pokud pokud je Zpět(v) konec jehly, tak Zkratka(v) nastavíme na Zpět(v), jinak nastavíme Zkratka(v) na Zkratka(Zpět(v))
    • algoritmus jakoby hledá všechny jehly (jako u KMP)
    • složitost $\Theta(J)$, kde $J$ je součet délek jednotlivých jehel
• celkem čas $\Theta(J+S+V)$

• hledání jedné jehly
• zahashuju si posloupnost $J$ znaků a porovnám s hashem jehly
• hashovací funkce pro řetězec $x_1\dots x_J$
  • $h(x_1,\dots,x_J)=x_1P^{J-1}+x_2P^{J-2}+\dots+x_JP^0\mod M$
• postupně přehashovávám pro každý takový úsek sena (hashování v lineárním čase, přehashování v konstantním)
  • $h(x_2,\dots,x_{J+1})=P\cdot h(x_1,\dots,x_j)-x_1 P^J+x_{J+1}\mod M$
• pokud se hash posloupnosti znaků shoduje s hashem jehly, ověříme, zda je to opravdu jehla
• průměrná časová složitost $\Theta(J+S+JV+{SJ\over M})$ pro rovnoměrnou hashovací funkci
  • jehlu hashujeme lineárně Hornerovým schématem
  • provádíme $S$ přepočítání hashovací funkce
  • nahlášení každého výskytu trvá $JV$ (ověřujeme, zda je to jehla)
  • pro dvě různé posloupnosti znaků se hashe shodují s pravděpodobností $1/M$ (viz věta o počtu kolizí) – takže průměrně $\Theta({SJ\over M})$ strávíme kontrolou falešně pozitivních výsledků
  • chceme $M\in\Omega(SJ)$, abychom minimalizovali vliv kolizí
• naše polynomiální hashovací funkce není dokonale rovnoměrná (místo $1/M$ bude pravděpodobnost kolize $J/M$), ale podrobnější analýza nebude zkoušena

• pro dokonale rovnoměrnou hashovací funkci $1/M$ pro $M$ okének
• přesnější odhad nebude na zkoušce

• síť je čtveřice
  • 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^+$
• tok je funkce $f:E\in\mathbb R_0^+$ taková, že
  • $\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\setminus\set{z,s}:f^\Delta(v)=0$
• pro $v\in V$
  • přítok $f^+(v)\coloneqq \sum_{uv\in E} f(uv)$
  • odtok $f^-(v)\coloneqq \sum_{vw\in E}f(vw)$
  • přebytek $f^\Delta(v)\coloneqq f^+(v)-f^-(v)$
• velikost toku $|f|\coloneqq f^\Delta(s)$

• $E(A,B)\coloneqq E\cap (A\times B)$
• tedy $E(A,B)=\set{uv\in E\mid u\in A\land v\in B}$
• řez je $E(A,B)$ pro $A\subseteq V,\;B=V\setminus A$
  • přičemž $z\in A,\;s\in B$
• kapacita řezu $c(A,B)\coloneqq \sum_{e\in E(A,B)} c(e)$
• $f(A,B)\coloneqq \sum_{e\in E(A,B)} f(e)$
• $f^\Delta(A,B)\coloneqq f(A,B)-f(B,A)$

• lemma: pro každý řez $E(A,B)$ a každý tok $f$ platí $f^\Delta(A,B)=|f|$
• důkaz
  • $\sum_{v\in B}f^\Delta(v)=f^\Delta(s)=|f|$
    • podle Kirchhoffova zákona
  • $\sum_{v\in B}f^\Delta(v)=f(A,B)-f(B,A)=f^\Delta(A,B)$
    • hrany zleva doprava přispívají kladně
    • hrany zprava doleva přispívají záporně
    • ostatní hrany nepřispívají

• rezerva hrany $uv$
  • $r(uv)\coloneqq c(uv)-f(uv)+f(vu)$
• hrana je nasycená $\equiv$ má nulovou rezervu
• hrana je nenasycená $\equiv$ má kladnou rezervu

• cesta je nenasycená $\equiv$ žádná její hrana není nasycená / všechny mají kladné rezervy
• algoritmus
  • iterujeme, dokud existuje nenasycená cesta ze zdroje do stoku
  • spočítáme rezervu celé cesty (minimum přes rezervy hran cesty)
  • pro každou hranu upravíme tok – v protisměru odečteme co nejvíc, zbytek přičteme po směru
• pro celočíselné kapacity vrátí celočíselný tok
• racionální kapacity převedeme na celočíselné
• pro iracionální kapacity se může rozbít
• lemma: pokud se algoritmus zastaví, vydá maximální tok
  • algoritmus se zastavil
  • množinu vrcholů, do nichž existuje nenasycená cesta ze zdroje označíme jako $A$, ostatní vrcholy budou v množině $B$
  • všimneme si, že $E(A,B)$ je řez
  • hrany řezu mají zjevně nulovou rezervu
  • po hranách řezu vedoucích z A do B teče tok rovný kapacitě, po hranách z B do A neteče nic
  • nalezli jsme tedy řez $E(A,B)$, pro nějž $f^\Delta(A,B)=c(A,B)$
  • tedy tento řez je minimální a tok $f$ maximální
• věta: pro každou síť s racionálními kapacitami se Fordův-Fulkersonův algoritmus zastaví a vydá maximální tok a minimální řez
  • vzhledem k operacím, které algoritmus provádí, nemůže z celých čísel vytvořit necelá
• důsledek: velikost maximálního toku je rovna kapacitě minimálního řezu
• důsledek: síť s celočíselnými kapacitami má aspoň jeden z maximálních toků celočíselný a Fordův-Fulkersonův algoritmus takový tok najde

• pro každý tok $f$ a každý řez $E(A,B)$ platí $|f|\leq c(A,B)$
• důkaz: $|f|=f^\Delta(A,B)=f(A,B)-f(B,A)\leq f(A,B)\leq c(A,B)$
• pokud $|f|=c(A,B)$, pak je tok $f$ maximální a řez $E(A,B)$ minimální
• z analýzy Fordova-Fulkersonova algoritmu plyne, že velikost maximálního toku je rovna kapacitě minimálního řezu

• toku $f$ přiřadíme průtok $f^*$ takto: $f^*(uv)\coloneqq 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)$
• lemma: pokud funkce $f^*:E\to\mathbb R$ splňuje tato pozorování, pak existuje tok $f$, jehož průtokem je $f^*$
• důkaz lemmatu
  • mějme $uv,vu\in E$
  • BÚNO $f^*(uv)\geq 0$
  • $f(uv)\coloneqq f^*(uv)$
  • $f(vu)=0$
• takže můžeme místo s toky počítat s průtoky, přičemž si to pak ekvivalentně převedeme na toky

• vzhledem k operacím, které Fordův-Fulkersonův algoritmus provádí, nemůže z celých čísel vytvořit necelá
• z analýzy Fordova-Fulkersonova algoritmu plyne, že síť s celočíselnými kapacitami má aspoň jeden z maximálních toků celočíselný a Fordův-Fulkersonův algoritmus takový tok najde

• z bipartitního grafu vytvoříme síť
  • nalezneme partity grafu, budeme jim říkat levá a pravá
  • hrany zorientujeme zleva doprava
  • přidáme zdroj a vedeme z něj hrany do všech vrcholů levé partity
  • přidáme spotřebič a vedeme do něj hrany ze všech vrcholů pravé partity
  • všem hranám nastavíme jednotkovou kapacitu
• najdeme maximální celočíselný tok
• je to párování?
  • kdyby nebylo, dvě hrany by měly společný vrchol
  • z každého vrcholu levé partity může vytékat maximálně jedna jednotka (víc jich nemůže přitéct)
  • podobně pro vrchol pravé partity
  • tedy dvě hrany nemůžou mít společný vrchol
• je párování největší?
  • z každého toku umíme vytvořit párování, z každého párování umíme vytvořit tok
  • tedy existuje bijekce, ta zachovává velikost
  • největší tok proto musí odpovídat největšímu párování
• časová složitost
  • úvodní konstrukce v čase $O(n+m)$
  • jedna iterace v čase $O(n+m)$ – nenasycenou cestu najdeme pomocí BFS, tok zlepšíme v čase lineárním s délkou cesty
  • každá iterací zlepší tok aspoň o 1, takže iterací bude nejvýš $n$
  • celkem $O(nm)$

• tok $f$ je blokující $\equiv$ pro každou cestu $P$ ze $z$ do $s$ existuje $e\in P$ taková, že $f(e)=c(e)$
• síť $S$ je vrstevnatá (pročištěná) $\equiv$ každý vrchol i hrana leží na nějaké nejkratší cestě ze $z$ do $s$

• k síti $(V,E,z,s,c)$ a toku $f$ v ní je síť rezerv $(V,E,z,s,r)$, kde $r(uv)=c(uv)-f^*(uv)$
• lemma o zlepšování toků: pro tok $f$ v síti a tok $g$ v odpovídající síti rezerv existuje tok $h$ v původní síti takový, že $|h|=|f|+|g|$ a lze ho najít v čase $O(m)$
  • toky přímo sčítat nemůžeme (mohli bychom se dostat přes kapacitu hrany), ale průtoky ano
• algoritmus
  • začneme s nulovým tokem $f$
  • opakujeme (tyto kroky tvoří jednu fázi)
    • sestrojíme síť rezerv a smažeme z ní nulové hrany
    • pročistíme síť rezerv (pokud je prázdná, skončíme)
    • najdeme v síti rezerv blokující tok $g$
    • vylepšíme $f$ pomocí $g$
  • vrátíme $f$
• pročištění sítě rezerv
  • pomocí BFS ze zdroje rozdělíme graf na vrstvy
  • smažeme vrstvy za stokem
  • smažeme hrany, které nevedou o vrstvu vpřed
  • smažeme slepé uličky
    • všechny vrcholy, které nemají odchozí hrany, naházíme do fronty
    • vrcholy ve frontě postupně mažeme
    • pokud jsme přitom vytvořili další vrchol bez odchozích hran, vložíme ho do fronty
    • každý vrchol a každá hrana se účastní nejvýš jednou – v čase $O(m)$
  • čas $O(m)$
• nalezení blokujícího toku
  • začneme s nulovým tokem $g$
  • 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$
  • čas $O(nm)$
    • síť je vrstevnatá $\implies$ 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)$
• lemma: pokud se algoritmus zastaví, vydá maximální tok
  • algoritmus se zastaví, když už neexistuje cesta ze zdroje do stoku po hranách s kladnou rezervou
  • tehdy by se zastavil i Fordův-Fulkersonův algoritmus, který je korektní
• lemma: během každé fáze vzroste počet vrstev pročištěné sítě aspoň o jedna
  • 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
• fáze trvá $O(nm)$, takže Dinicův algoritmus najde maximální tok v čase $O(n^2m)$

• $f$ je vlna $\equiv$
  • $\forall e\in E:f(e)\leq c(e)$
  • $\forall v\neq z,s: f^\Delta(v)\geq 0$
• převedení přebytku
  • $f^\Delta(u)\gt 0$
  • $r(uv)\gt 0$
  • $\delta\coloneqq \min(f^\Delta(u),r(uv))$
  • po hraně $uv$ navíc pošleme $\delta$
    • $f^*(uv)\mathrel{+}=\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$

• výška $h:V\to\mathbb N$
• algoritmus
  • nastavíme počáteční výšky – zdroji nastavíme výšku $n$, ostatním vrcholům 0
  • vytvoříme počáteční vlnu – $f$ je všude nulová kromě hran ze zdroje, ty nastavíme na maximum (tedy nechť se $f$ rovná jejich kapacitě)
  • dokud existuje vrchol $u\neq z,s$, který má $f^\Delta(u)\gt 0:$
    • pokud může přebytek někam „stéct“ (existuje hrana $uv$ s nenulovou rezervou a $u$ je výš než $v$), převedeme přebytek po $uv$
    • pokud přebytek nemůže nikam stéct, zvedneme $u$ o 1
• invariant A (základní)
  • $f$ je vlna
  • výška vrcholů neklesá
  • výška zdroje a stoku se nemění
  • přebytek ve všech vrcholech kromě zdroje je větší roven 0
• invariant S (o spádu)
  • neexistuje hrana s nenulovou rezervou, která by vedla o více než jednu úroveň dolů
    • na začátku to 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)
• lemma K (o korektnosti)
  • pokud se algoritmus zastaví, finální $f$ je maximální tok
    • $f$ je tok
    • $f$ je maximální
    • kdyby nebyl maximální, pak podle Fordova-Fulkersonova algoritmu 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
• invariant C (cesta do zdroje)
  • mějme vrchol, jehož přebytek je kladný
  • pak existuje nenasycená cesta z tohoto vrcholu do zdroje
  • 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}$
      • $f(\overline A,A)=0$, protože jinak by existovala nenasycená cesta $v\to x$, kde $x$ je nějaký vrchol v $\overline A$, což by byl spor
    • 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
• invariant V (o výšce)
  • $\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
• lemma Z (zvednutí)
  • počet zvednutí je nejvýš $2n^2$
  • protože každý z $n$ vrcholů vystoupá nejvýše do výšky $2n$ (z invariantu V)
• lemma S (sytá převedení)
  • převedení je nasycené (syté) $\equiv$ vynuluje rezervu
  • pozorování: nenasycené převedení po hraně $uv$ vynuluje $f^\Delta(u)$
  • lemma: počet sytých převedení $\leq n\cdot m$
  • důkaz
    • 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
• potenciál $\Phi$ definujeme jako součet výšek vrcholů různých od zdroje a stoku, které mají kladný přebytek
  • na počátku je nulový
  • zvednutí ho zvýší o 1
    • celkem $\leq 2n^2$
  • syté převedení po hraně $uv$ ho možná sníží o $h(u)$ a možná zvýší o $h(v)$, takže se $\Phi$ zvýší nejvýš o $2n$
    • celkem $\leq 2n^2m$
  • nenasycené převedení po hraně $uv$ o určitě sníží o $h(u)$ a možná ho zvýší o $h(v)$, přičemž $h(u)=h(v)+1$, takže se $\Phi$ sníží aspoň o 1
• lemma N (nenasycená převedení)
  • počet nenasycených převedení $\in O(n^2m)$
  • rozbor viz potenciál (snižovat o 1 můžeme nejvýš tolikrát, kolikrát jsme zvyšovali o 1)
• implementace
  • seznam vrcholů s kladným přebytkem
    • údržba v $O(1)$ při změně přebytku
    • nalezení nějakého vrcholu s kladným přebytkem v $O(1)$
  • pro každý vrchol seznam hran s kladnou rezervou, které z něj vedou z kopce
    • převedení v $O(1)$
    • zvednutí vrcholu v $O(n)$
• složitost
  • inicializace v čase $O(m)$
  • $\leq 2n^2$ zvedání v $O(n)$
  • $\leq mn$ sytých převedení v $O(1)$
  • $O(n^2m)$ nenasycených převedení v $O(1)$
  • celkem čas $O(n^2m)$

• rozšíření původního Goldbergova algoritmu
• lemma N'
  • když vybereme vždy nejvyšší $v$ s kladným přebytkem, tak nastane $O(n^3)$ nenasycených převedení
• důkaz
  • $H$ … výška nejvyššího vrcholu s kladným přebytkem
  • 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 nenasycených převedení je $O(n^3)$
• složitost algoritmu je $O(n^3)$
  • odhad není optimální, lze ukázat $O(n^2\sqrt m)$

• graf … vyhodnocení polynomu v několika bodech (vektor)
  • mějme pevné $x_0,\dots,x_{n-1}$
  • mějme polynom $P$ stupně $n-1$ (tedy velikosti $n$)
  • jeho graf je vektor $(P(x_0),\dots,P(x_{n-1}))$
• věta
  • buďte $P,Q$ polynomy stupně nejvýše $d$
  • pokud platí $P(x_i)=Q(x_i)$ pro navzájem různá čísla $x_0,\dots,x_d$, pak $P$ a $Q$ jsou identické
    • tedy polynom stupně $d$ je určený $d+1$ body
• lemma (důkaz případně v Průvodci): pro polynom $P$ stupně $d\geq 0$ je počet $x$ takových, že $P(x)=0$, nejvýše $d$
• důkaz věty
  • $R(x)\coloneqq P(x)-Q(x)$
  • $\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 $\implies d=-1\implies R\equiv 0$

komplexní číslo $x$ je primitivní $n$-tá odmocnina z 1, pokud $x^n=1$ a žádné z čísel $x^1,x^2,\dots,x^{n-1}$ není rovno 1

• algoritmus násobení polynomů
  • jsou dány polynomy $P,Q$ velikosti $n$ určené svými koeficienty
  • BÚNO horních $n/2$ koeficientů je nulových, takže jejich součin bude polynom velikosti $n$
  • zvolíme navzájem různá čísla $x_0,\dots,x_{n-1}$
  • spočítáme grafy polynomů $P$ a $Q$
  • z toho vypočteme graf součinu $R$ vynásobením po složkách $R(x_i)=P(x_i)\cdot Q(x_i)$
  • podle grafu najdeme koeficienty polynomu $R$
• algoritmus vyhodnocení polynomů
  • použijeme metodu Rozděl a panuj
  • polynom $P$ velikosti $n$ chceme vyhodnotit v $n$ bodech
  • body zvolíme tak, aby byly spárované = tvořily dvojice lišící se znaménkem: $\pm x_0,\pm x_1,\dots,\pm x_{n/2-1}$
  • polynom $P$ rozložíme na dva polynomy $P_s$ a $P_\ell$
    • $P(x)=p_0x^0+p_1x^1+\dots+p_{n-1}x^{n-1}$
    • $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_\ell(x^2)$
  • navíc $P(-x)=P_s(x^2)-x\cdot P_\ell(x^2)$
  • vyhodnocení polynomu $P$ v bodech $\pm x_0,\dots,\pm x_{n/2-1}$ lze tedy převést na vyhodnocení polynomů $P_s,P_\ell$ poloviční velikosti v bodech $x_0^2,\dots,x^2_{n/2-1}$
  • na to bychom mohli rekurzivně použít stejný algoritmus
  • to by vedlo na algoritmus s časovou složitosti $T(n)=2T(n/2)+\Theta(n)$
    • tedy $T(n)=\Theta(n\log n)$ podle Master theorem
  • v $\mathbb R$ jsou však druhé mocniny nezáporné, tedy je uvnitř rekurze nelze spárovat
• rychlá Fourierova transformace
  • polynomy doplníme nulami tak, aby jejich velikost $n$ byla mocninou dvojky
  • zvolíme nějakou primitivní $n$-tou odmocninu z jedničky $\omega$
    • pro obecné $n\gt 2$ existují alespoň dvě primitivní odmocniny: $\omega=e^{2\pi i/n},\,\overline\omega=e^{-2\pi i/n}$
  • polynom vyhodnocujeme v bodech $\omega^0,\omega^1,\dots,\omega^{n-1}$
  • $\omega^{n/2},\dots,\omega^{n-1}$ se od $\omega^0,\dots,\omega^{n/2-1}$ liší pouze znaménkem, tedy jsou správně spárované
  • $\omega^2$ je primitivní $(n/2)$-tá odmocnina z jedničky, takže i v rekurzi bude existovat správné párování
  • použijeme původní algoritmus vyhodnocení polynomů, teď již běží v $\Theta(n\log n)$
  • algoritmu chybí ještě základní případ pro $n=1$, ten je potřeba doplnit, aby to fungovalo (graf konstantní funkce pro libovolné $x$ odpovídá koeficientu konstantního členu)
• inverze FFT
  • nahlédneme, že diskrétní Fourierova transformace (DFT) je zobrazení $\mathcal F:\mathbb C^n\to \mathbb C^n$, které vektoru $x$ přiřadí vektor $y$ daný předpisem $y_j=\sum_{k=0}^{n-1}x_k\cdot\omega^{jk}$
    • $y$ se označuje jako Fourierův obraz vektoru $x$
    • $\omega$ je nějaká pevně zvolená primitivní $n$-tá odmocnina z jedné
  • v našem případě – pro $p$ vektor koeficientů polynomu je $\mathcal F(p)$ graf tohoto polynomu
  • DFT (tedy $\mathcal F$) je lineární zobrazení, takže ho lze zapsat jako násobení $x$ maticí $\Omega$, kde $\Omega_{jk}=\omega^{jk}$
  • hledáme $\Omega^{-1}$, abychom mohli najít inverzní funkci
  • platí $\omega^{-1}=\overline \omega$ (protože $\omega$ je komplexní jednotka)
  • lemma: $\Omega^{-1}=\frac1n\cdot\overline\Omega$
  • důkaz
    • chceme $\Omega\cdot\overline\Omega=n\cdot E_n$
    • $(\Omega\cdot\overline\Omega)_{jk}=\sum_\ell(\Omega_{j\ell}\cdot\overline\Omega_{\ell k})=\sum\omega^{j\ell}\omega^{-\ell k}=\sum\omega^{(j-k)\ell}$
    • poslední suma je geometrická řada
    • když $j=k$, jsou všechny členy rovny jedné, takže se sečtou na $n$
    • když $j\neq k$ použijeme vzorec pro součet geometrické řady pro $q=\omega^{j-k}$
      • $\sum_\ell q^\ell=\frac{q^n-1}{q-1}=\frac{\omega^{(j-k)n}-1}{\omega^{j-k}-1}=\frac{1^{j-k}-1}{\omega^{j-k}-1}=0$
      • protože $\omega^n=1$
  • $\overline\omega=\omega^{-1}$ je také primitivní $n$-tou odmocninou z jedničky, takže inverzi FFT lze spočítat stejným algoritmem, jenom výsledek musíme vydělit $n$
• věta: je-li $n$ mocnina dvojky, lze v čase $\Theta(n\log n)$ spočítat DFT v $\mathbb C^n$ i její inverzi

• věta: polynomy velikosti $n$ nad tělesem $\mathbb C$ lze násobit v čase $\Theta(n\log n)$
• důkaz
  • nejprve vektory koeficientů doplníme nulami tak, aby jejich délka byla mocnina dvojky (a aspoň $2n$)
  • pomocí DFT v čase $\Theta(n\log n)$ převedeme oba polynomy na grafy
  • v $\Theta(n)$ vynásobíme grafy po složkách
  • pomocí inverzní DFT v čase $\Theta(n\log n)$ převedeme výsledný graf zpátky na koeficienty polynomu

• hradlo arity $k$ má $k$ vstupů a jeden výstup
  • počítá funkci $f:\Sigma^k\to\Sigma$
• $\Sigma$ … konečná abeceda, typicky $\set{0,1}$
• booleovská hradla
  • binární: AND, OR, XOR, $\leq$ (implikace), … (je jich 16)
  • unární: NOT (a „buffer“)
  • nulární, konstanty: 0, 1
• hradlová síť obsahuje
  • hradla
  • vstupní porty
  • výstupní porty
  • acyklické propojení
• výpočet probíhá v taktech
  • 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
• tak dostáváme rozklad sítě na vrstvy, kde v $i$-té vrstvě jsou hradla a porty, které byly ohodnoceny v $i.$ taktu
• čas = počet vrstev
• prostor = počet hradel
  • 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ů)
• je nutné omezit počet vstupů a výstupů – jinak bychom mohli cokoliv počítat v konstantním čase
• kombinační obvody … na obecné abecedě $\Sigma$
• booleovské obvody … $\Sigma=\set{0,1}$
• hradlová síť má pevnou velikost vstupu
• tedy ekvivalent programu ve světě hradlových sítí by byla sada různých hradlových sítí pro různé velikosti vstupu
  • tedy výpočetní model je neuniformní
• chceme tyto sítě efektivně generovat – ale stačí nám polynomiální čas
• co se týče časové složitosti hradlových sítí – obvykle chceme polylogaritmickou složitost (tedy nějakou mocninu logaritmu)

• čísla označíme $x,y$, jejich výsledek jako $z$
• $c_i$ … přenos z $(i-1)$-ního řádu do $i$-tého
• $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)$
  • $\text{Majorita}(x, y, z)=(x\land y)\lor(x\land z)\lor(y\land z)$
• 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ů
  • počítá součet bitů $x_i\dots x_j$ a $y_i\dots y_j$
• chování bloku – závislost $c_\text{out}$ na $c_{\text{in}}$
  • na blok se můžeme dívat jako na funkci, která dostane přenos zespoda a vydá přenos nahoru
  • takové funkce (tedy „chování bloku“) existují čtyři
    • $f(x)=0$
    • $f(x)=1$
    • $f(x)=x$
    • $f(x)=\neg x$
  • jednobitové bloky se chovají jednoduše
    • hodnoty … odpovídající funkce
    • 00 … 0
    • 01 … x
    • 10 … x
    • 11 … 1
  • větší blok můžeme rozdělit na dva podbloky – horní (levý) a dolní (pravý)
    • když hornímu podbloku odpovídá konstantní funkce, tak výsledná funkce pro celý blok je opět konstantní
    • naopak když hornímu podbloku odpovídá funkce identita (tzn. $f(x)=x$, tedy horní podblok kopíruje přenos), tak výsledná funkce pro celý blok odpovídá funkci spodního podbloku
• nejdříve tedy v logaritmickém čase zanalyzujeme chování podbloků
  • od jednotkových k jednomu velkém bloku
• pak v logaritmickém čase spočítáme všechny přenosy
  • od jednoho bloku k jednotkovým
• nakonec v konstantním čase provedeme samotné XORování
• takže umíme sčítat v čase $O(\log n)$

• 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
  • kompresor funguje tak, že pro tři sčítané bity na $i$-té pozici spočítá součet a carry – součty se píšou do jednoho řádku, carry do druhého (tak vzniknou dva sčítance)
  • 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

• posloupnost $x_0,\dots,x_{n-1}$ je
  • č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á
• separátor $S_n$
  • 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 vždy mezi $i$-tým prvkem v levé polovině a $i$-tým prvkem v pravé polovině
      • takže vlastně mezi $x_i$ a $x_{n/2+i}$
  • proč to funguje
    • 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
  • čas $O(1)$
  • prostor $O(n)$
• bitonická třídička $B_n$
  • 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)$
• slévačka $M_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}$
• třídička $S_n$
  • 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
• pozorování: z dolního odhadu složitosti třídění plyne, že hloubka každé třídicí sítě je $\Omega(\log n)$
  • dá se to $O(\log n)$, ale konstanta je obrovská
• algoritmy odvozené od komparátorových sítí se velmi snadno vektorizují

• princip
  • nejlevější bod určitě bude součástí obalu
  • ukotvíme v něm polopřímku, otáčíme jí, než se dotkne dalšího bodu
  • 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
  • bod přidáme do obou obálek (z jedné nebo z obou z nich ho později možná odstraníme)
• č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
    • budeme mít kalendář událostí
  • 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 (takže na žádný průsečík nezapomeneme)
• algoritmus
  • inicializujeme průřez na $\emptyset$
  • do kalendáře vložíme začátky a konce všech úseček
  • dokud kalendář není prázdný
    • odebereme nejvyšší událost
    • je to začátek úsečky → zatřídíme novou úsečku do průřezu
    • je to konec úsečky → odebereme ji z průřezu
    • je to průsečík → nahlásíme ho a prohodíme tyto dvě úsečky v průřezu
    • přepočítáme průsečíkové události v kalendáři (protože změna v průřezu mohla změnit sousednosti)
      • pokud jsme zrušili sousednost, zrušíme průsečík z kalendáře (pokud existoval)
        • tohle není potřeba z hlediska korektnosti algoritmu (viz strana 7, poznámka 1), použijeme to pouze při analýze složitosti
      • pokud jsme přidali sousednost, přidáme průsečík do kalendáře
      • takto odebereme nejvýše dvě události a nejvýše dvě přidáme
• reprezentace
  • průřez
    • BVS s úsečkami jako klíči nad lineárním uspořádáním úseček, kde $x\lt y\equiv$ $x$ je vlevo od $y$
    • maximálně $n$ úseček
    • každá operace v $O(\log n)$
  • kalendář
    • halda nebo BVS
    • maximálně $3n$ událostí
      • začátky a konce úseček ($2n$)
      • průsečíky pro každou dvojici sousedních úseček v průřezu (úseček je nejvýš $n$, takže počet průsečíků $\lt n$)
    • každá operace v $O(\log n)$
      • tady se vlastně ukazuje, že asymptoticky stejné složitosti bychom dosáhli, i kdybychom v kalendáři měli všechny průsečíky
• při vyhodnocení každé události provedeme konstantní počet logaritmických operací s datovými strukturami
• 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 libovolnému 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ů (těch je $n$)
  • použijeme algoritmus z průsečíků přímek – pro každý pás uložíme „průřez“
  • 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
    • uvnitř pásu se žádné přímky nekříží
  • dotaz v $O(\log n)$
  • paměť $O(n^2)$ – to je moc
    • předzpracování v čase $O(n^2)$
• přístup 2
  • použijeme semipersistentní binární vyhledávací strom
  • budeme udržovat průřez v persistentním stromu
  • pro každý pás uložíme identifikátor verze persistentního stromu
  • předzpracování Voroného diagramu a vytvoření persistentního stromu
    • $O(n)$ operací s průřezem → čas $O(n \log n)$
    • $O(n)$ verzí → prostor $O(n\log n)$
  • dotaz v $O(\log n)$
    • nejprve vyhledáme správný pás
    • pak se příslušné verze stromu zeptáme na přímky

• (semi)persistentní datová struktura
  • pamatuje si historii
  • provedením operace, která mění stav datové struktury, vzniká nová verze
• semipersistentní BVS
  • jeho vrcholy nebudeme měnit
  • místo toho si vždycky pořídíme kopii vrcholu a tu změníme
  • musíme změnit i ukazatel na daný vrchol, aby ukazoval na kopii
  • tedy zkopírujeme otce vrcholu a upravíme v něm ukazatel
  • takhle postupně zkopírujeme všechny předky až ke kořeni (a upravíme ukazatele)
    • tedy zkopírujeme celou cestu $P$ z upravovaného vrcholu do kořene, ta má délku $O(\log n)$
    • tato cesta se odkazuje na podstromy z minulé verze
  • kopie kořene se stane identifikátorem nové verze
  • $O(\log n)$ čas na operaci
  • $O(\log n)$ paměť na verzi
    • umí se i $O(1)$ amortizovaně
  • po každé operaci následuje vyvážení stromu, ale to upravuje pouze vrcholy v konstantní vzdálenosti od cesty $P$, takže to složitost nemění

rozhodovací problém $\equiv$ funkce $f:\set{0,1}^*\to\set{0,1}$

• problém: existuje v zadaném grafu párování, které obsahuje alespoň $k$ hran?
  • je jedno, jestli chceme alespoň $k$ hran nebo právě $k$ hran, protože podmnožina párování je párování
• vstup musíme zapsat řetězcem bitů
  • na začátku kódu budou jedničky a nula, počet jedniček určí, v kolika bitech je uloženo $n$ a $k$
  • následují dvojkově zapsané $n$ a $k$ a matice sousednosti grafu
• budeme kontrolovat syntaxi vstupu, na všechny chybné vstupy odpovíme nulou

• mějme rozhodovací problémy $A,B$
• problém $A$ je převoditelný na problém $B$ právě tehdy, když existuje funkce $f:\set{0,1}^*\to\set{0,1}^*$ taková, že $\forall\alpha\in\set{0,1}^*:A(\alpha)=B(f(\alpha))$ a $f$ lze spočítat v čase polynomiálním vzhledem k $|\alpha|$
• značíme $A\to B$ nebo $A\leq_P B$
• funkci $f$ říkáme převod (případně redukce)

• je reflexivní $(A\to A)$ … $f$ je identita
• je tranzitivní $(A\to B\land B\to C\implies A\to C)$ … když $f$ převádí $A$ na $B$ a $g$ převádí $B$ na $C$, tak $f\circ g$ převádí $A$ na $C$ (přičemž složení polynomiálně vyčíslitelných funkcí je polynomiálně vyčíslitelná funkce)
• není antisymetrická – např. problémy „vstup má sudou délku“ a „vstup má lichou délku“ lze mezi sebou převádět oběma směry
• existují navzájem nepřevoditelné problémy – např. mezi problémy „na každý vstup odpověz 0“ a „na každý vstup odpověz 1“ nemůže existovat převod
• převoditelnost je částečné kvaziuspořádání na množině všech problémů

• klika: existuje úplný podgraf grafu $G$ na alespoň $k$ vrcholech?
• nezávislá množina: existuje nezávislá množina vrcholů grafu $G$ velikosti aspoň $k$?
  • množina vrcholů grafu je nezávislá $\equiv$ žádné dva vrcholy ležící v této množině nejsou spojeny hranou
• SAT: existuje dosazení 0 a 1 za proměnné tak, aby $\psi(\dots)=1$?
  • kde $\psi$ je v CNF
• 3-SAT: jako SAT, akorát každá klauzule formule $\psi$ obsahuje nejvýše tři literály
• 3,3-SAT: jako 3-SAT, akorát se každá proměnná vyskytuje v maximálně třech literálech
• 3D-párování
  • vstup: tři množiny $A,B,C$ a množina kompatibilních trojic $T\subseteq A\times B\times C$
  • výstup: existuje perfektní podmnožina trojic? tzn. existuje taková podmnožina, v níž se každý prvek množin $A,B,C$ účastní právě jedné trojice

• pokud v grafu prohodíme hrany a nehrany, stane se z každé kliky nezávislá množina a naopak
• převodní funkce zneguje hrany

• vyrábíme ekvisplnitelnou formuli
• SAT → 3-SAT
  • $(\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
• 3-SAT → 3,3-SAT
  • 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
• 3,3-SAT* … navíc každý literál max. 2×
  • použijeme předchozí algoritmus pro všechny proměnné s $k \geq 3$ výskyty

• pro každou z $k$ klauzulí formule vytvoříme trojúhelník a jeho vrcholům přiřadíme literály klauzule
  • pokud klauzule obsahuje méně než tři literály, tak přebývající vrcholy smažeme
• spojíme hranami všechny dvojice konfliktních literálů
• v takovém grafu existuje nezávislá množina velikosti alespoň $k$ právě tehdy, když je formule splnitelná
  • máme-li splňující ohodnocení, můžeme z každé klauzule vybrat jeden pravdivý literál – ty umístíme do nezávislé množiny
  • máme-li nezávislou množinu velikosti $k$, vybereme literály odpovídající těmto vrcholům a podle nich nastavíme odpovídající proměnné
    • v nezávislé množině velikosti $k$ nemůžou být dva vrcholy ze stejného trojúhelníku – tedy z každého trojúhelníku (klauzule) bude v množině právě jeden vrchol
    • v nezávislé množině nemohou být dva vrcholy s opačnými literály, protože takové vrcholy jsou spojeny hranou

• BÚNO $V(G)=[n]$ (očíslujeme vrcholy grafu 1 až $n$)
• $\forall i\in[n]:x_i=1\iff i\in$ NzMna
• $\forall ij\in E:(\neg x_i\lor\neg x_j)$ … zajistí, že vrcholy v nezávislé množině nebudou spojeny hranou
• navíc potřebujeme zkontrolovat, že NzMna je dostatečně velká
• 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)$