Skip to content

Latest commit

 

History

History
1006 lines (990 loc) · 60.5 KB

zkouska.md

File metadata and controls

1006 lines (990 loc) · 60.5 KB
Raw

Zkouška

Vyhledávání v textu

  • Definice: Terminologie okolo řetězců (podslova, prefixy, suffixy)
    • 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$
  • Algoritmus: Knuth-Morris-Pratt (jedna jehla v seně)
    • 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)$
  • Algoritmus: Aho-Corasicková (více jehel v seně)
    • 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)$
  • Algoritmus: Rabin-Karp (okénkové hešování)
    • 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
  • Věta: Počet kolizí u okénkového hešování
    • pro dokonale rovnoměrnou hashovací funkci $1/M$ pro $M$ okének
    • přesnější odhad nebude na zkoušce

Toky v sítích

  • Definice: Síť, tok, přebytek, velikost toku
    • 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)$
  • Definice: Řez, kapacita řezu
    • $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)$
  • Věta: Velikost toku se dá měřit na každém řezu
    • 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í
  • Definice: Rezerva hrany, nasycená hrana
    • 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
  • Algoritmus: Ford-Fulkerson (zlepšující cesty)
    • 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
  • Věta: Minimální řez je stejně velký jako maximální tok
    • 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
  • Definice: Průtok (čistý tok)
    • 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
  • Příklad: Celočíselná síť má celočíselný maximální tok
    • 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
  • Algoritmus: Největší párování v bipartitním grafu
    • 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)$
  • Definice: Blokující tok, vrstevnatá síť
    • 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$
  • Algoritmus: Dinicův algoritmus (zlepšující toky)
    • 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)$
  • Definice: Vlna, převedení přebytku po hraně
    • $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$
  • Algoritmus: Goldbergův algoritmus (výšky a přebytky)
    • 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)$
  • Algoritmus: Goldbergův algoritmus s výběrem nejvyššího vrcholu
    • 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)$

Algebraické algoritmy

  • Věta: Reprezentace polynomu grafem
    • 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$
  • Definice: Primitivní n-tá odmocnina z jedničky
    • 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
  • Věta: Rychlá Fourierova transformace a její inverze
    • 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: Násobení polynomů pomocí Fourierovy transformace
    • 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

Paralelní algoritmy

  • Definice: Hradlová síť
    • 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)
  • Algoritmus: Sčítání přirozených čísel hradlovou sítí
    • čí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)$
  • Algoritmus: Násobení přirozených čísel hradlovou sítí
    • 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
  • Definice: Komparátorová síť
    • 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
  • Algoritmus: Bitonické třídění komparátorovou sítí
    • 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í

Geometrické algoritmy

  • Algoritmus: Konvexní obal
    • 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ů)
  • Algoritmus: Průsečíky úseček
    • 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
  • Definice: Voroného diagram
    • 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
  • Algoritmus: Lokalizace bodu v mnohoúhelníkové síti
    • 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
  • Algoritmus: Semipersistentní binární vyhledávací strom
    • (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í

Převody problémů

  • Definice: Rozhodovací problém
    • rozhodovací problém $\equiv$ funkce $f:\set{0,1}^*\to\set{0,1}$
  • Příklad: Bipartitní párování jako rozhodovací problém, kódování vstupu
    • 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
  • Definice: Převod mezi problémy
    • 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)
  • Věta: Vlastnosti převoditelnosti (reflexivita, tranzitivita apod.)
    • 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ů
  • Definice: Problémy: klika, nezávislá množina, SAT, 3-SAT, 3,3-SAT, 3D-párování
    • 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
  • Algoritmus: Převod klika ↔ nezávislá množina
    • 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
  • Algoritmus: Převod SAT → 3-SAT → 3,3-SAT
    • 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
  • Algoritmus: Převod 3-SAT → nezávislá množina
    • 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
  • Algoritmus: Převod nezávislá množina (NzMna) → SAT
    • 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)$
  • Algoritmus: Převod 3,3-SAT → 3D-párování
    • $K$ kluci, $D$ děvčata, $Z$ zvířátka
    • $T$ … kompatibilní trojice
    • BÚNO každý literál se vyskytuje maximálně dvakrát
      • kdyby se vyskytoval třikrát, mohli bychom proměnnou v ohodnocení nastavit na 0/1 (podle literálu) a všechny výskyty ve formuli smazat (respektive smazat celé takové klauzule – jde v podstatě o jednotkovou propagaci)
    • gadget pro proměnnou
      • 2 kluci, 2 děvčata, 4 zvířátka
      • volba kompatibilních dvojic odpovídá trojúhelníčkům
      • gadget pro proměnnou
      • 2 stavy
        • 0 … $\blacktriangle$, z2 a z4 jsou volné
        • 1 … $\triangle$, z1 a z3 jsou volné
    • gadget pro klauzuli
      • pro klauzuli $k$ přidáme 1 kluka a 1 děvče a připojíme je (jako kompatibilní trojice) ke třem (již existujícím) zvířátkům
      • tato tři zvířátka odpovídají třem literálům v klauzuli
      • např. $z_a$ tedy bude zvířátko, které je volné, když je první literál v klauzuli splněn
      • gadget pro klauzuli
    • nějaká zvířátka zbydou
      • zbude zvířátek: 2 × počet proměnných – počet klauzulí
        • každá proměnná přidá čtyři zvířátka, z toho dvě ubytuje
        • každá klauzule ubytuje právě jedno zvířátko
      • přidáme tolik párů $k,d$
      • pro každý takový pár přidáme trojice se všemi zvířátky
      • poznámka: v Průvodci je chyba

NP-úplnost

  • Definice: Třídy složitosti P a NP
    • problém $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)$
    • problém $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ý)
    • $\text P\subseteq\text{NP}$ (rovnost se neví)
  • Definice: NP-těžké a NP-úplné problémy
    • $L$ je NP-těžký $\equiv\forall K\in\text{NP}:K\to L$
    • $L$ je NP-úplný $\equiv L$ je NP-těžký $\land;L\in\text{NP}$
  • Věta: Pokud $A\to B$ a $B\in \text P$, pak $A\in \text P$
    • máme převodní funkci $f$, kterou lze spočítat v $O(n^c)$
    • máme algoritmus pro $B$, který běží v $O(m^d)$
      • kde $m$ je délka převedeného vstupu
    • tedy $m$ je délka výstupu převodní funkce
    • algoritmus běžící v čase $t$ nemůže vyrobit výstup delší než $t$
    • takže $m\in O(n^c)$
    • tudíž $f$ složená s algoritmem pro $B$ běží v čase $O(n^c+(n^c)^d)\subseteq O(n^{cd})$
  • Věta: Pokud $A→B$, $B\in \text{NP}$ a $A$ je NP-úplný, pak $B$ je NP-úplný
    • $\forall Z\in\text{NP}:Z\to A$
    • převoditelnost je tranzitivní, takže $Z\to B$
  • Věta: (Cook, Levin) SAT je NP-úplný (náznak důkazu)
    • ukážeme, že $L\in\text{NP}$ lze převést na obvodový SAT
    • obvodový SAT převedeme na SAT
    • lemma: pro každý problém $L\in \text P$ existuje polynomiální algoritmus, který pro každou délku vstupu sestaví hradlovou síť řešící $L$
    • důkaz lemmatu odmáváme
      • počítače jsou velké hradlové sítě
      • budeme mít polynomiálně mnoho kopií počítače
      • s každým tikem hodin pošle jedna kopie mezivýsledek té druhé
      • počítač potřebuje polynomiálně mnoho paměti
    • věta: obvodový SAT je NP-úplný
    • důkaz
      • evidentně obvodový SAT $\in$ NP
      • mějme $L\in\text{NP}$
      • máme verifikátor $V$ a omezující polynom $g$ dle definice NP
      • BÚNO chceme certifikáty délky rovné $g(n)$
        • $n$ je délka vstupu
        • certifikáty doplníme o jedničku a samé nuly
      • z použití lemmatu na $V$ dostaneme hradlovou síť s $n+g(n)$ vstupy
        • tato hradlová síť kontroluje, zda je certifikát správný
      • do hradlové sítě zadrátujeme konkrétní vstup
      • vyjde nám hradlová síť, která má $g(n)$ vstupů a 1 výstup (výsledná hodnota „formule“)
        • jakmile najdeme splňující ohodnocení vstupů, našli jsme řešení problému
    • nakonec použijeme lemma o převodu obvodového SATu na 3-SAT
  • Algoritmus: Převod obvodového SATu na SAT
    • lemma: obvodový SAT lze převést na 3-SAT
    • důkaz
      • převedeme obvod, aby měl jen AND a NOT
      • zavedeme proměnné pro výstupy hradel
      • $x\to\boxed{\neg}\to z$
        • přidáme klauzule:
        • $x\implies\neg z$
        • $\neg x\implies z$
      • $x,y\to\boxed{\land}\to z$
        • přidáme klauzule:
        • $x\land y\implies z$
        • $\neg x\implies\neg z$
        • $\neg y\implies\neg z$
      • implikace převedeme na disjunkce
  • Příklad: Klasické NP-úplné problémy
    • 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$)

Jak zvládnout těžký problém

  • Algoritmus: Nezávislá množina ve stromu
    • 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
    • hladový algoritmus
    • algoritmus (DFS) pro vrchol $v$
      • přidáme $v$ do NzMna
      • pro každého syna $s$ vrcholu $v$
        • rekurzivně spustíme algoritmus pro $s$
        • pokud $s\in$ NzMna, odebereme $v$ z NzMna
    • složitost $O(n)$
  • Algoritmus: Barvení intervalového grafu
    • 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
    • procházení po přímce = procházení kalendáře událostí
      • události = začátky a konce intervalů
    • 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)$
  • Algoritmus: Pseudopolynomiální algoritmus pro problém batohu
    • máme
      • 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$
    • $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)$
      • první varianta: předmět $k$ nepoužijeme
      • druhá varianta: předmět $k$ použijeme
        • připadá v úvahu, jen pokud $c-c_k\geq 0$
    • celou tabulku vyplníme v čase $O(nC)$
    • maximální dosažitelná 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)$
  • Definice: Aproximační algoritmus
    • 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í cenou $c^*$
      • vystačíme si s jeho $\alpha$-aproximací, tedy s přípustným řešením s cenou $c'\leq\alpha c^*$ pro nějakou konstantu $\alpha\gt 1$
      • tedy relativní chyba $\frac{c'-c^}{c^}$ nepřekročí $\alpha-1$
        • $c'\leq\alpha c^*$
        • $c'-c^\leq\alpha c^-c^*$
        • $\frac{c'-c^}{c^}\leq\alpha-1$
      • $\alpha$ … aproximační poměr
      • $\alpha-1=\varepsilon$ … relativní chyba aproximace
    • jindy chceme maximalizovat cenu $c^*$
      • $\alpha$-aproximace je řešení s cenou $c'\geq\alpha c^*$ pro $\alpha\in (0,1)$
      • $\frac{c^-c'}{c^}\leq1-\alpha$
      • $1-\alpha=\varepsilon$
    • $c$ minimalizujeme u TSP, naopak ho maximalizujeme u batohu
  • Algoritmus: 2-aproximace obchodního cestujícího v metrickém prostoru
    • mějme úplný graf
    • nechť platí trojúhelníková nerovnost
    • do jednoho vrcholu se nesmíme vrátit víckrát (kromě toho, kde jsme začali)
    • najdeme minimální kostru
    • $T$ … součet délek hran minimální kostry
    • obchodní cestující ať obejde minimální kostru
      • nachodí $2T$
      • vrcholy navštěvuje víckrát
    • přidáme zkratky
      • z posloupnosti měst $A,B,A,C$ uděláme $A,B,C$
      • díky trojúhelníkové nerovnosti si tím neublížíme
      • obchodní cestující nachodí $\leq 2T$
    • pozorování: $T\leq$ optimum
    • výstup $\leq 2T\leq 2$ opt.
    • tedy jsme našli $2$-aproximaci
    • umí se $1.5$-aproximace
  • Věta: Neaproximovatelnost obchodního cestujícího bez trojúhelníkové nerovnosti
    • věta: pokud pro $t\geq 1$ existuje algoritmus $t$-aproximující TSP v úplných grafech bez trojúhelníkové nerovnosti v polynomiálním čase, pak $\text P=\text {NP}$
    • princip důkazu: $t$-aproximace $\implies$ polynomiální algoritmus pro hamiltonovskou kružnici $\implies\text P=\text{NP}$
      • TSP v podstatě odpovídá hledání vhodné hamiltonovské kružnice v úplném grafu
      • hamiltonovská kružnice (tedy zda v daném grafu existuje) je NP-úplná, takže kdyby existoval polynomiální algoritmus, tak by pro libovolný problém z NP existoval polynomiální algoritmus (protože je převoditelný na hamiltonovskou kružnici)
    • důkaz
      • mějme algoritmus, který v polynomiální čase $t$-aproximuje TSP v úplných grafech bez trojúhelníkové nerovnosti
      • 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$
      • podle délky nejkratší hamiltonovské kružnice poznáme, zda v $G$ existuje
        • potřebujeme $tn\lt n-1+c$, abychom to poznali i přes zkreslení způsobené aproximací
        • $c\gt tn-n+1=(t-1)n+1$
        • splníme $c=tn$
  • Definice: Polynomiální aproximační schéma (PTAS)
    • PTAS $\equiv$ algoritmus, který pro vstup velikosti $n$ a $\varepsilon\gt 0$ najde aproximaci s chybou $\leq\varepsilon$ v čase $O(\text{polynom}(n))$ pro každé $\varepsilon$
    • složitost se může výrazně měnit v závislosti na $\varepsilon$
      • proto se zavádí FPTAS, kde je složitost polynomiální i vůči $\frac 1\varepsilon$
  • Definice: Plně polynomiální aproximační schéma (FPTAS)
    • FPTAS $\equiv$ algoritmus, který pro vstup velikosti $n$ a $\varepsilon\gt 0$ najde aproximaci s chybou $\leq\varepsilon$ v čase $O(\text{polynom}(n,\frac1\varepsilon))$
  • Algoritmus: FPTAS pro problém batohu
    • 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}$
      • $\hat c_i$ … přeškálovaná cena $i$-tého předmětu
    • chyba pro jeden předmět $\leq\frac{c_\max}M$
      • když dělíme nějakým $k$, tak je to ekvivalentní zaokrouhlení na násobky $k$, takže chyba je nejvýš $k$
    • chyba celkem $\leq n\cdot \frac{c_\max}M\overset{\text{chceme}}\leq\varepsilon\cdot c^*$
    • pozorování: po zahození předmětů s $h_i\gt H$ bude $c^*\geq c_\max$
      • chyba celkem $\leq n\cdot\frac{c_\max}M\leq n\cdot\frac{c^}{M}\overset{\text{chceme}}\leq\varepsilon\cdot c^$
      • takže musíme zvolit $M\geq \frac n\varepsilon$
    • časová složitost
      • škálování v lineárním čase
      • nově $C\leq n\cdot M$
      • takže algoritmus poběží v $O(n^2M)=O(n^3/\varepsilon)$
    • ceny můžeme zaokrouhlovat (dostaneme aproximaci), hmotnosti ne, protože by se nám to rozbilo
    • tak jsme získali $(1-\varepsilon)$-aproximaci batohu
      • jen je při implementaci potřeba dávat pozor na horní a dolní celé části
    • algoritmus
      • odstraníme předměty s $h_i\gt H$
      • najdeme $c_\max$
      • určíme $M$ jako $\lceil n/\varepsilon\rceil$
      • určíme $\hat c_i$ jako $\left\lfloor c_i\cdot \frac M{c_\max}\right\rfloor$
      • použijeme dynamické programování (tedy nám známý pseudopolynomiální algoritmus)
    • 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}\left\lfloor c_i\cdot \frac M{c_\max}\right\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$
        • protože $|P|\leq 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)$
        • poslední nerovnost platí, protože $Q$ je optimální řešení přeškálované úlohy, zatímco $P$ je nějaké řešení přeškálované úlohy
      • dohromady dostaneme
        • $c(Q)\geq\frac{c_\max}M\left(\frac M{c_\max}c(P)-n\right)=c(P)-n\cdot\frac{c_\max}M$
        • $\geq c(P)-\varepsilon c_\max$
          • protože $M\geq n/\varepsilon$
        • $\geq c(P)-\varepsilon c(P)$
          • protože $c(P)\geq c_\max$
        • tudíž $c(Q)\geq(1-\varepsilon)\cdot c(P)$, což jsme chtěli
    • takto jsme vyrobili plně polynomiální aproximační schéma, protože algoritmus má složitost $O(n^3/\varepsilon)$