tok - funkce f, která přiřazuje hranám f(uv)≤c(uv), v každém vrcholu
kromě zdroje a stoku platí, že dovnitř teče právě tolik jako ven ($f^Δ(v) =
0provsˇechnavmimoz,s$)
velikost toku =f+(s)
řez - rozdělení V na A a B, kdy z∈A, s∈B, A∩B=Ø, A∪B=V
kapacita řezu - součet kapacit všech hran vedoucích mezi stranami řezu
řez toku → velikost toku
min. řez sítě → max. velikost toku
rezerva hrany r(uv)=c(uv)−f(uv)+f(vu), r(uv)=0⇒uv je nenasycená
Ford-Fulkerson
začínáme s nulovým tokem
hledáme cestu, kde všechny hrany mají r(e)=0
zvýšíme na cestě tok o minimum z rezerv hran
vznikne řez, kde do A vedou nenasycené hrany z z, tedy hrany na řezu jsou
všechny nasycené a velikost našeho toku je rovna velikosti řezu
algoritmus doběhne pro celočíselné sítě, protože pokaždé se zvětší tok alespoň
o 1
Největší párování
FF jde použít
tok v síti, zdroj → leva strana bip. grafu → prava strana bip. grafu → stok
kapacity 1
FF doběhne v 𝓞(nm)
Dinic
průtok = tok, kde nám nezáleží, kterým směrem něco teče
f∗(uv)=f(uv)−f(vu)
f∗(vu)=−f∗(uv)
f∗(uv)≤c(uv)
platí Kirchhoff
díky výše uvedeným podmínkám můžeme převést průtok na tok
síť rezerv R má místo c(e)r(e)
alg
vytvoříme průtok f nulový
opakuj
vytvoříme síť rezerv, nulové hrany smažeme
najdeme nejkratší cestu z z do s a rozdělíme graf na vrstvy
odstraníme všechny hrany, které vedou uvnitř vrstev nebo za s,
rekurzivně pak hrany, které nikam nevedou
najdeme max. tok v pročištěné síti, z sítě odstraňujeme dál hrany,
které jsme nasytili
vylepšíme f o nový tok
síť rezerv vytvoříme v 𝓞(m)
nejkratší cesta a rozdělení na vrstvy je také v 𝓞(m)
čištění je v 𝓞(m)
hledání max. toku je v 𝓞(nm)
iterací je n - v každém kroku se nejkratší cesta zvětší o 1 a délka nejdelší
možné cesty je n
složitost je 𝓞(n2m)
Goldberg
vlna - tok, kde akceptujeme přetlak ve vrcholech mimo z,s, ale ne podtlak!
alg
přiřadíme vrcholům výšku ∀u:h(u)←0
pro zdroj z : h(z)←n
f je vlna, vytvoříme přelak ze z:∀zv∈E:f(zv)=c(zv)
dokud je v nějakém vrcholu u mimo s,z přebytek
pokud existuje nějaká hrana uv, kde h(u)>h(v) a r(uv) > 0
převedu přebytek – f(uv)+=δ, kde δ=min{r(uv),fΔ(u)}
jinak h(u)++
invarianty a lemmata
základní A
f je vlna
h(z)=n,h(s)=0
výšky neklesají
přebytky jsou nezáporné (plyne z vlny)
o spádu S
spád na hraně s kladnou rezervou uv:h(u)−h(v)≤1
pokud je na hraně rezerva, vždy nejdříve vyřešíme tu, než zvedneme
vrchol, posílání v protisměru taky nejde
korektnost
je tok? kapacitní omezení platí i pro vlny, Kirchhoff - algoritmus se
zastaví až když platí Kirchhoff
je maximální? kdyby nebyl, existuje nenasycená cesta, tedy cesta celá
z kopce dolů na nejvýše n−1 hranách, což je spor s inv. S, musela by
se pomocí n−1 jedniček snížit z n na 0
Algebraické algoritmy (aneb fakin efeftéčko)
reprezentace polynomu grafem - polynom stupně n je plně určen n+1 body
polynom stupně n má nejvýše n kořenů:
je možné z něj vydělit součin nejvýše n závorek formátu: (x−α)
P(xj)=Q(xj) pro x0...xd
R:=P−Q,R(xj)=P(xj)−Q(xj)=0
R≡0, protože je rovno nule v d+1 bodech
násobení polynomů pomocí grafu
polynomy → grafy → násobení v Θ(n) → polynomy
pokus o rozděl a panuj
P(x)=Ps(x2)+xPl(x2)
pořád potřebujeme evaluovat polynomy poloviční velikosti v n bodech
řekněme, že určíme n bodů tak, že máme vždy ±x0...±xn/2
pak x2=(−x)2 a P(−x)=Ps(x2)−xPl(x2)
stačí nám tedy jen evaluovat rekurenci jen pro prvních n/2 bodů
dále v rekurenci už ale pokračovat nemůžeme, protože tam nebude možné
rozdělit x symetricky
stejný pokus jako výše, akorát zvolíme xj=n1j (zaokrouhlíme n
na mocninu 2 nahoru)
pak xj2=n/21j
alg FFT(n=2k, ω, p0...pn−1)
a = FFT(n/2, ω2, p0,p2...)
b = FFT(n/2, ω2, p1,p3...)
pro j od 0 do n/2−1
xj=aj+ωbj
pro j od n/2 do n−1
xj=aj−ωbj
DFT je lin. zobrazení vektoru x0...xn−1:
yj=i=0∑n−1xiωij=i=0∑n−1pi(ωj)i
matice zobrazení Ω je
1111⋮1(ω1)1(ω2)1(ω3)1⋮1(ω1)2(ω2)2(ω3)2⋮1(ω1)3(ω2)3(ω3)3⋮............⋱
Ω⋅Ω=n⋅E⇒Ω−1=n1Ω
Paralelní algoritmy
hradlová síť
DAM (DAG, but mutligraf)
vstupy, hradla a výstupy
hradla mají aritu
všechno musí být korektně zapojené
přípojky do hradel jsou očíslované
sčítání
carry vyřešíme zvlášť pomocí logn stromečků, vyhodnocujeme, jestli je
carry 0, 1 nebo <
násobení
vytvoříme si pro bity čísel xn...x0 a yn...y0n2 čísel:
(xn\andy)≪n,...,(x0\andy)≪0
tyto čísla pak sečteme pomocí kompresorů
v konstantní hloubce udělají z tří čísel dvě jejichž součet je stejný
jako původních 3
první číslo reprezentuje součet všech tří bez carry p=x⊕y⊕z
druhé číslo jsou všechny carry bity qi+1=maj(xi,yi,zi)
kompresory zkompresují všechna čísla v 𝓞(log2/3n)=𝓞(logn)
(zbývající dvě vezmeme třeba normální sčítačkou)
komparátorová síť
síť složená z vrstev komparátorů – dostanou dva vstupy a pokud jsou ve
špatném pořadí, prohodí je
bitonické třídění
chceme mergesort, na ten potřebujeme slévací krabičky
slévací krabička je např. bitonická třídička
bitonická třídička lze složit ze separátorů, které umí rozložit bit.
posloupnost na dvě, kde jedna je celá menší než druhá
separátor porovnává xi s xn/2+i - všechny lze porovnat paralelně
logn separátorů je třídička = slévací krabička (dvě posloupnosti
slejeme tak, že druhou otočíme a bitonicky setřídíme), těch potřebujeme také
logn, celkem 𝓞(log2n)
Geometrické algoritmy
konvexní obal
zametáme, stack horní a spodní, ze stacku odstraňujeme body, pokud
zatáčíme na druhou stranu - každý bod jednou přidáme jednou odebereme 𝓞(n)
průsečíky úseček
zametáme, máme průřez a kalendář, na začátku jsou v kalendáři jen začátky
a konce úseček
bereme z kalendáře
začátek: přidáme úsečku do průřezu a přidáme do kalendáře průsečíky
všech nově sousedících úseček a odstraníme těch, které už nesousedí
konec: odebereme úsečku z průřezu a opět aktualizujeme průsečíky v kalendáři
průsečík: zahlásíme průsečík, prohodíme úsečky v průřezu,
aktualizujeme kalendář
kalendář je halda, 𝓞(logn) na operaci, průřez je strom, taky 𝓞(logn) na operaci
z kalendáře odebereme jednou začátek, jednou konec každé úsečky a každý
hlášený průsečík, po každém odebrání provedeme 𝓞(logn) operací s DS,
celá složitost je 𝓞((n+s)logn), kde s je výsledný počet průsečíků
Voroného diagram
zametáme přímkou, udržujeme pobřeží a kalendář
v kalendáři jsou všechna místa
odebíráme z kalendáře
pokud místo
přidáme parabolu, v pobřeží doprostřed tím rozdělíme už existující
region, v diagramu začne vznikat úsečka rozdělující nové místo a místo původní paraboly
pokud kružnice
daná parabola zanikne, ve středu kružnice v diagramu vznikne bod
zakončující úsečku krajních míst s prostředním a začne vznikat
úsečka obou krajních míst mezi sebou
aktualizujeme kružnicové události
𝓞(nlogn)
Převody problémů
Rozhodovací problémy
funkce {0,1}∗→{0,1}
Bipart. párování jako rozhodovací problém
t jedniček – určíme si velikost slova
jedno slovo pro n
jedno slovo pro k (kolik chceme aby existovalo minimálně hran v párování)
n2 bitů pro matici sousednosti
Převody mezi problémy
problém A je převoditelný na B (A→B), pokud existuje polynomiální
funkce, pro kterou platí, že ∀x:A(x)=B(f(x))
převoditelnost je tansitivní, reflexivní, ale ne nutně antisymetrická –
kvaziuspořádání
klika ↔ nezávislá množina
negace hran bruh
SAT → 3-SAT
pro klauzule delší než 3 – nová proměnná x:
(v1∨v2∨x),(¬x∨v3...)
3-SAT → 3,3-SAT
pokud se proměnná vyskytuje víc než 3×, vytvoříme novou proměnnou za každý
výskyt a vytvoříme chain implikací:
(x1⇒x2),(x2⇒x3),...,(xn⇒x1)
3-SAT → NzMna
každá klauzule trojúhélník, všechny x spojeny hranou se všemi ¬x
NzMna → SAT
vrchol → proměnná
hrana → klauzule
vynucení počtu pomocí matice X velikosti k×n, Xij=1≡ vrchol
j je i-tým vrcholem v NzMně
v každém sloupci nejvýše jedna 1
v každém řádku právě jedna 1
3,3-SAT → 3D párování
gadget pro proměnnou – čtyři trojice, cyklus K,D,K,D, ke každé trojici
připojeno jedno Z – nesmí se zároveň použít horizontální a vertikální Z
gadget pro klauzuli – dvojice K,D, připojena k trojici Zek, jedno z každé
proměnné, horizontální pro ¬, vertikální pro ¬¬
dostatek univerzálních K a D pro nevyužitá Z
NP-úplnost
problém je v P, pokud je řešitelný poly. algoritmem
problém L je v NP, pokud pro K v P platí ekvivalence ∀x:L(x)=1⟺∃y:K(x,y)=1
A→B∧B∈P⇒A∈P - proof by fucking obviousness
A→B∧B∈NP∧NP-complete(A)⇒NP-complete(B) -
dokazuji, že B je NP-těžký, pokud A je NP-těžký, pokud všechno můžu
převést na A, můžu to pak převést i na B
SAT je NP-úplný – obvod-SAT je NP-úplný, protože je umíme reprezentovat v počítači, duh
obvod SAT → SAT – proměnné reprezentují splnitelnost vstupu nebo výstupu
hradel, všechno se dá převést na AND a NOT