Definice: Terminologie okolo řetězců (podslova, prefixy, suffixy)
slovo α … konečná posloupnost znaků z abecedy Σ
prázdný řetězec ε
i-tý znak α[i] (počítáme od nuly)
podřetězec/podslovo α[i:j] (od i-tého znaku do (j-1). znaku včetně)
prefix α[:j]=α[0:j]
suffix α[i:]=α[i:∣α∣]
α[:]=α
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 ε 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 (ε) 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 Θ(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 Θ(J)
celkem čas Θ(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 (α→αx)
konce jehel (označíme v trii)
zpětné hrany – vedou z α do nejdelšího vlastního suffixu α, který je stavem (tohle obvykle v trii nebývá)
zkratkové hrany – vedou z α 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 Θ(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 Θ(J), kde J je součet délek jednotlivých jehel
celkem čas Θ(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 x1…xJ
h(x1,…,xJ)=x1PJ−1+x2PJ−2+⋯+xJP0modM
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(x2,…,xJ+1)=P⋅h(x1,…,xj)−x1PJ+xJ+1modM
pokud se hash posloupnosti znaků shoduje s hashem jehly, ověříme, zda je to opravdu jehla
průměrná časová složitost Θ(J+S+JV+MSJ) 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ě Θ(MSJ) strávíme kontrolou falešně pozitivních výsledků
chceme M∈Ω(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∈E⟹vu∈E)
chybějící hrana má jakoby nulovou kapacitu
zdroj z∈V
spotřebič s∈V,s=z
kapacity c:E→R0+
tok je funkce f:E∈R0+ taková, že
∀e∈E:f(e)≤c(e)
Kirchhoffův zákon
zákon zachování, tekutina se nám nikam neztrácí
∀v∈V∖{z,s}:fΔ(v)=0
pro v∈V
přítok f+(v):=∑uv∈Ef(uv)
odtok f−(v):=∑vw∈Ef(vw)
přebytek fΔ(v):=f+(v)−f−(v)
velikost toku ∣f∣:=fΔ(s)
Definice: Řez, kapacita řezu
E(A,B):=E∩(A×B)
tedy E(A,B)={uv∈E∣u∈A∧v∈B}
řez je E(A,B) pro A⊆V,B=V∖A
přičemž z∈A,s∈B
kapacita řezu c(A,B):=∑e∈E(A,B)c(e)
f(A,B):=∑e∈E(A,B)f(e)
fΔ(A,B):=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Δ(A,B)=∣f∣
důkaz
∑v∈BfΔ(v)=fΔ(s)=∣f∣
podle Kirchhoffova zákona
∑v∈BfΔ(v)=f(A,B)−f(B,A)=fΔ(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):=c(uv)−f(uv)+f(vu)
hrana je nasycená ≡ má nulovou rezervu
hrana je nenasycená ≡ má kladnou rezervu
Algoritmus: Ford-Fulkerson (zlepšující cesty)
cesta je nenasycená ≡ žá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Δ(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∣≤c(A,B)
důkaz: ∣f∣=fΔ(A,B)=f(A,B)−f(B,A)≤f(A,B)≤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):=f(uv)−f(vu)
pozorování
f∗(uv)=−f∗(vu)
f∗(uv)≤c(uv)
−c(vu)≤f∗(uv)
∀v=z,s:∑uv∈Ef∗(uv)=0
tzn. pro takové v platí ∑uv∈Ef∗(uv)=fΔ(v)
lemma: pokud funkce f∗:E→R splňuje tato pozorování, pak existuje tok f, jehož průtokem je f∗
důkaz lemmatu
mějme uv,vu∈E
BÚNO f∗(uv)≥0
f(uv):=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í ≡ pro každou cestu P ze z do s existuje e∈P taková, že f(e)=c(e)
síť S je vrstevnatá (pročištěná) ≡ 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
ε←mine∈P(r(e)−g(e))
∀e∈P:g(e)←g(e)+ε 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á ⟹ 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í ≤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(n2m)
Definice: Vlna, převedení přebytku po hraně
f je vlna ≡
∀e∈E:f(e)≤c(e)
∀v=z,s:fΔ(v)≥0
převedení přebytku
fΔ(u)>0
r(uv)>0
δ:=min(fΔ(u),r(uv))
po hraně uv navíc pošleme δ
f∗(uv)+=δ
důsledky
f zůstane vlnou
fΔ(u)−=δ,fΔ(v)+=δ
r(uv)−=δ,r(vu)+=δ
Algoritmus: Goldbergův algoritmus (výšky a přebytky)
výška h:V→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=z,s, který má fΔ(u)>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:={t∈V∣∃ nenasycenaˊ cesta v→t}
chceme ukázat z∈A
∑a∈AfΔ(a)=0f(A,A)−≥0f(A,A)
f(A,A)=0, protože jinak by existovala nenasycená cesta v→x, kde x je nějaký vrchol v 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)
∀v:h(v)≤2n
invariant C ⟹ invariant V
uvažme první porušení – zvedáme v∈V z výšky 2n
tehdy fΔ(v)>0⟹∃P nenasycená cesta v→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ýš 2n2
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é) ≡ vynuluje rezervu
pozorování: nenasycené převedení po hraně uv vynuluje fΔ(u)
lemma: počet sytých převedení ≤n⋅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)>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 Φ 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 ≤2n2
syté převedení po hraně uv ho možná sníží o h(u) a možná zvýší o h(v), takže se Φ zvýší nejvýš o 2n
celkem ≤2n2m
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 Φ sníží aspoň o 1
lemma N (nenasycená převedení)
počet nenasycených převedení ∈O(n2m)
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)
≤2n2 zvedání v O(n)
≤mn sytých převedení v O(1)
O(n2m) nenasycených převedení v O(1)
celkem čas O(n2m)
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(n3) 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. 2n2-krát
H vždy roste o 1
snížení aspoň o 1
max. 2n2-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(n2), takže nenasycených převedení je O(n3)
složitost algoritmu je O(n3)
odhad není optimální, lze ukázat O(n2m)
Algebraické algoritmy
Věta: Reprezentace polynomu grafem
graf … vyhodnocení polynomu v několika bodech (vektor)
mějme pevné x0,…,xn−1
mějme polynom P stupně n−1 (tedy velikosti n)
jeho graf je vektor (P(x0),…,P(xn−1))
věta
buďte P,Q polynomy stupně nejvýše d
pokud platí P(xi)=Q(xi) pro navzájem různá čísla x0,…,xd, 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≥0 je počet x takových, že P(x)=0, nejvýše d
důkaz věty
R(x):=P(x)−Q(x)
∀j:R(xj)=P(xj)−Q(xj)=0
stupeň R≤d
podle lemmatu R≡0, takže P≡Q
kdyby byl d≥0, tak by to byl spor s lemmatem, protože se R(x) rovná nule v d+1 bodech ⟹d=−1⟹R≡0
Definice: Primitivní n-tá odmocnina z jedničky
komplexní číslo x je primitivní n-tá odmocnina z 1, pokud xn=1 a žádné z čísel x1,x2,…,xn−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 x0,…,xn−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(xi)=P(xi)⋅Q(xi)
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: ±x0,±x1,…,±xn/2−1
vyhodnocení polynomu P v bodech ±x0,…,±xn/2−1 lze tedy převést na vyhodnocení polynomů Ps,Pℓ poloviční velikosti v bodech x02,…,xn/2−12
na to bychom mohli rekurzivně použít stejný algoritmus
to by vedlo na algoritmus s časovou složitosti T(n)=2T(n/2)+Θ(n)
tedy T(n)=Θ(nlogn) podle Master theorem
v 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 ω
pro obecné n>2 existují alespoň dvě primitivní odmocniny: ω=e2πi/n,ω=e−2πi/n
polynom vyhodnocujeme v bodech ω0,ω1,…,ωn−1
ωn/2,…,ωn−1 se od ω0,…,ωn/2−1 liší pouze znaménkem, tedy jsou správně spárované
ω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 Θ(nlogn)
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í F:Cn→Cn, které vektoru x přiřadí vektor y daný předpisem yj=∑k=0n−1xk⋅ωjk
y se označuje jako Fourierův obraz vektoru x
ω je nějaká pevně zvolená primitivní n-tá odmocnina z jedné
v našem případě – pro p vektor koeficientů polynomu je F(p) graf tohoto polynomu
DFT (tedy F) je lineární zobrazení, takže ho lze zapsat jako násobení x maticí Ω, kde Ωjk=ωjk
hledáme Ω−1, abychom mohli najít inverzní funkci
platí ω−1=ω (protože ω je komplexní jednotka)
lemma: Ω−1=n1⋅Ω
důkaz
chceme Ω⋅Ω=n⋅En
(Ω⋅Ω)jk=∑ℓ(Ωjℓ⋅Ωℓk)=∑ωjℓω−ℓk=∑ω(j−k)ℓ
poslední suma je geometrická řada
když j=k, jsou všechny členy rovny jedné, takže se sečtou na n
když j=k použijeme vzorec pro součet geometrické řady pro q=ωj−k
∑ℓqℓ=q−1qn−1=ωj−k−1ω(j−k)n−1=ωj−k−11j−k−1=0
protože ωn=1
ω=ω−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 Θ(nlogn) spočítat DFT v Cn i její inverzi
Věta: Násobení polynomů pomocí Fourierovy transformace
věta: polynomy velikosti n nad tělesem C lze násobit v čase Θ(nlogn)
důkaz
nejprve vektory koeficientů doplníme nulami tak, aby jejich délka byla mocnina dvojky (a aspoň 2n)
pomocí DFT v čase Θ(nlogn) převedeme oba polynomy na grafy
v Θ(n) vynásobíme grafy po složkách
pomocí inverzní DFT v čase Θ(nlogn) 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:Σk→Σ
Σ … konečná abeceda, typicky {0,1}
booleovská hradla
binární: AND, OR, XOR, ≤ (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ě Σ
booleovské obvody … Σ={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
ci … přenos z (i−1)-ního řádu do i-tého
zi=xi⊕yi⊕ci
kde ⊕ je XOR
ci+1=Majorita(xi,yi,ci)
Majorita(x,y,z)=(x∧y)∨(x∧z)∨(y∧z)
jednoduchá implementace má Θ(n) hladin a Θ(n) hradel – musíme čekat na přenosy (ci)
jak předpovídat přenosy?
blok = souvislá posloupnost bitů
počítá součet bitů xi…xj a yi…yj
chování bloku – závislost cout na cin
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)=¬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(logn)
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(log2n)
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é 32n čísel, ve třetí (32)2n čísel, …, v poslední 2 čísla, ty sečteme klasickou sčítačkou
kompresorových vrstev bude O(logn), hloubka kompresoru je O(1)
závěrečná sčítačka bude O(logn)
takže celková složitost násobení bude O(logn)
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 Θ(n) vrstvách
Algoritmus: Bitonické třídění komparátorovou sítí
posloupnost x0,…,xn−1 je
čistě bitonická ≡∃k:x0<x1<⋯<xk>⋯>xn−1
bitonická ≡ má čistě bitonickou rotaci
tedy ∃l:xl,xl+1,…,xl+n−1 (kde indexy jsou modulo n) je čistě bitonická
separátor Sn
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 xi a xn/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é
xk … prvek, kterým začíná hora
xk+n/2 … prvek, kterým končí hora
k je BÚNO menší než n/2
jak fungují komparátory?
pro i<k neprohazujeme
pro i≥k prohazujeme
levý výstup = rotace údolí
pravý výstup = rotace hory
čas O(1)
prostor O(n)
bitonická třídička Bn
na vstupu bitonická posloupnost
na výstupu rostoucí posloupnost
logn 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(logn)
prostor O(nlogn)
slévačka Mn
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 B2n
třídička Sn
na vstupu je n prvků
na výstupu je monotónní rostoucí posloupnost n prvků
budeme mít logn pater slévaček, každá má nejhůř logn pater, takže celkem O(log2n)
prostorová složitost O(nlog2n)
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 Ω(logn)
dá se to O(logn), 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 x1,…,xn∈R2
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 Θ(nlogn)
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 ε
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 Θ(n2)
chceme složitost O(hezkaˊ 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 ≡ 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 ∅
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<y≡x je vlevo od y
maximálně n úseček
každá operace v O(logn)
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ů <n)
každá operace v O(logn)
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)logn) čas
O(n) paměť
umí se O(nlogn+p) čas
Definice: Voroného diagram
místa a oblasti
oblast oi odpovídá místu xi, je to část roviny, jejíž body jsou k místu xi 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(nlogn), 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
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(logn)
tato cesta se odkazuje na podstromy z minulé verze
kopie kořene se stane identifikátorem nové verze
O(logn) čas na operaci
O(logn) 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 ≡ funkce f:{0,1}∗→{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:{0,1}∗→{0,1}∗ taková, že ∀α∈{0,1}∗:A(α)=B(f(α)) a f lze spočítat v čase polynomiálním vzhledem k ∣α∣
značíme A→B nebo A≤PB
funkci f říkáme převod (případně redukce)
Věta: Vlastnosti převoditelnosti (reflexivita, tranzitivita apod.)
je reflexivní (A→A) … f je identita
je tranzitivní (A→B∧B→C⟹A→C) … když f převádí A na B a g převádí B na C, tak f∘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á ≡ žádné dva vrcholy ležící v této množině nejsou spojeny hranou
SAT: existuje dosazení 0 a 1 za proměnné tak, aby ψ(…)=1?
kde ψ je v CNF
3-SAT: jako SAT, akorát každá klauzule formule ψ 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⊆A×B×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
(α∨β)→(α∨ζ)∧(β∨¬ζ)
převod funguje i naopak (viz rezoluce)
jak rozštípnout dlouhou klauzuli délky ℓ?
α nechť má délku 2
β nechť má délku ℓ−2
po přidání ζ dostanu konjunkci klauzulí délky 3 a ℓ−1
klauzuli délky ℓ−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>3 výskyty
pro každý výskyt si pořídíme nové proměnné x1,…,xk
ekvivalenci všech xi zajistíme řetězcem implikací
x1⟹x2
x2⟹x3
⋮
xk⟹x1
každá proměnná xi 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≥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)
∀i∈[n]:xi=1⟺i∈ NzMna
∀ij∈E:(¬xi∨¬xj) … 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
yij=1≡ vrchol j je i-tým v NzMna
i=1,…,k
j=1,…,n
ve sloupci je maximálně 1 jednička
∀i,i′,j:(¬yij∨¬yi′j)
v řádku je právě jedna jednička
∀i,j,j′:(¬yij∨¬yij′)
∀i:(yi1∨yi2∨⋯∨yin)
propojíme klauzule
∀ij:(yij⟹xj)∼(¬yij∨xj)
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
2 stavy
0 … ▲, z2 a z4 jsou volné
1 … △, 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ř. za tedy bude zvířátko, které je volné, když je první literál v klauzuli splněn
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∈P≡∃A algoritmus ∃p polynom takový, že ∀x vstup platí, že A(x) doběhne do p(∣x∣) kroků ∧A(x)=L(x)
problém L∈NP≡∃V∈P (verifikátor) ∃g polynom (omezení délky certifikátů) ∀x:L(x)=1⟺∃y certifikát ∣y∣≤g(∣x∣) (krátký) ∧V(x,y)=1 (schválený)
P⊆NP (rovnost se neví)
Definice: NP-těžké a NP-úplné problémy
L je NP-těžký ≡∀K∈NP:K→L
L je NP-úplný ≡L je NP-těžký ∧L∈NP
Věta: Pokud A→B a B∈P, pak A∈P
máme převodní funkci f, kterou lze spočítat v O(nc)
máme algoritmus pro B, který běží v O(md)
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∈O(nc)
tudíž f složená s algoritmem pro B běží v čase O(nc+(nc)d)⊆O(ncd)
Věta: Pokud A→B, B∈NP a A je NP-úplný, pak B je NP-úplný
∀Z∈NP:Z→A
převoditelnost je tranzitivní, takže Z→B
Věta: (Cook, Levin) SAT je NP-úplný (náznak důkazu)
ukážeme, že L∈NP lze převést na obvodový SAT
obvodový SAT převedeme na SAT
lemma: pro každý problém L∈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 ∈ NP
mějme L∈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
číselné: součet podmnožiny, batoh, 2 loupežníci, nulajedničkové řešení soustavy lineárních rovnic (v Z)
Jak zvládnout těžký problém
Algoritmus: Nezávislá množina ve stromu
lemma: Je-li T strom a ℓ jeho list, pak aspoň jedna největší nezávislá množina obsahuje ℓ.
důkaz
nechť M je nějaká největší nezávislá množina
pokud ℓ∈M, pak máme hotovo
pokud ℓ∈/M, pak ℓ má souseda s
pokud s∈/M, můžu ℓ přidat do M, což je spor, protože M je největší
pokud s∈M, můžu z M odebrat s a přidat tam ℓ, čí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∈ 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
{u,v}∈E≡u∩v=∅
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(nlogn)
průchod začátků a konců v 2n krocích
takže celkem O(nlogn)
Algoritmus: Pseudopolynomiální algoritmus pro problém batohu
máme
předměty 1,…,n
hmotnosti h1,…,hn
ceny c1,…,cn
nosnost batohu H
chceme I⊆{1,…,n} takovou, že h(I)≤H, c(I) je maximální
chceme algoritmus polynomiální v n, C=∑ici
Ak(c):= minimální hmotnost podmnožiny z {1,…,k}, která má cenu c
může být +∞, pokud taková podmnožina neexistuje
sestavujeme tabulku z hodnot Ak(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
A0(0)=0
A0(c)=+∞ pro c>0
Ak(c)=min(Ak−1(c),Ak−1(c−ck)+hk)
první varianta: předmět k nepoužijeme
druhá varianta: předmět k použijeme
připadá v úvahu, jen pokud c−ck≥0
celou tabulku vyplníme v čase O(nC)
maximální dosažitelná cena c∗:=max{c∣An(c)≤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 α-aproximací, tedy s přípustným řešením s cenou c′≤αc∗ pro nějakou konstantu α>1
tedy relativní chyba c∗c′−c∗ nepřekročí α−1
c′≤αc∗
c′−c∗≤αc∗−c∗
c∗c′−c∗≤α−1
α … aproximační poměr
α−1=ε … relativní chyba aproximace
jindy chceme maximalizovat cenu c∗
α-aproximace je řešení s cenou c′≥αc∗ pro α∈(0,1)
c∗c∗−c′≤1−α
1−α=ε
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í ≤2T
pozorování: T≤ optimum
výstup ≤2T≤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≥1 existuje algoritmus t-aproximující TSP v úplných grafech bez trojúhelníkové nerovnosti v polynomiálním čase, pak P=NP
princip důkazu: t-aproximace ⟹ polynomiální algoritmus pro hamiltonovskou kružnici ⟹P=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 ≥n−1+c
podle délky nejkratší hamiltonovské kružnice poznáme, zda v G existuje
potřebujeme tn<n−1+c, abychom to poznali i přes zkreslení způsobené aproximací
c>tn−n+1=(t−1)n+1
splníme c=tn
Definice: Polynomiální aproximační schéma (PTAS)
PTAS ≡ algoritmus, který pro vstup velikosti n a ε>0 najde aproximaci s chybou ≤ε v čase O(polynom(n)) pro každé ε
složitost se může výrazně měnit v závislosti na ε
proto se zavádí FPTAS, kde je složitost polynomiální i vůči ε1
Definice: Plně polynomiální aproximační schéma (FPTAS)
FPTAS ≡ algoritmus, který pro vstup velikosti n a ε>0 najde aproximaci s chybou ≤ε v čase O(polynom(n,ε1))
Algoritmus: FPTAS pro problém batohu
umíme řešit v čase O(nC), kde C=∑ici,C≤n⋅cmax
chceme menší C
idea: {0,…,cmax}→{0,…,M}
c^i:=ci⋅cmaxM
c^i … přeškálovaná cena i-tého předmětu
chyba pro jeden předmět ≤Mcmax
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 ≤n⋅Mcmax≤chcemeε⋅c∗
pozorování: po zahození předmětů s hi>H bude c∗≥cmax
chyba celkem ≤n⋅Mcmax≤n⋅Mc∗≤chcemeε⋅c∗
takže musíme zvolit M≥εn
časová složitost
škálování v lineárním čase
nově C≤n⋅M
takže algoritmus poběží v O(n2M)=O(n3/ε)
ceny můžeme zaokrouhlovat (dostaneme aproximaci), hmotnosti ne, protože by se nám to rozbilo
tak jsme získali (1−ε)-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 hi>H
najdeme cmax
určíme M jako ⌈n/ε⌉
určíme c^i jako ⌊ci⋅cmaxM⌋
použijeme dynamické programování (tedy nám známý pseudopolynomiální algoritmus)