počítá s celými čísly (vše ostatní můžeme reprezentovat čísly)
paměť = pole indexované čísly (záporné buňky obvykle slouží pro pracovní data, nezáporné pro vstup a výstup)
výpočet: v paměti dostaneme vstup, provádíme instrukce (dokud nenastane halt), v paměti odevzdáme výstup (zbytek paměti může obsahovat cokoliv – před spuštěním výpočtu i po jeho konci)
definujeme základní aritmetické, logické a řídicí instrukce
operandem může být literál, [adresa], [[nepřímá adresace]]
uložení: kam ← co
operace: kam ← a OP b, kde OP může být +-*/&|^«»
halt (za programem implicitní)
goto KAM
návěští lze umístit před libovolný řádek
if a REL b goto KAM
místo goto by tam mohl být i jiný příkaz kromě if
REL může být =, <>, <, >, <=, >=
doba běhu programu je rovna celkovému počtu provedených instrukcí
spotřebovanou paměť definujeme jako rozdíl mezi nejvyšším a nejnižším použitým indexem paměti
časová a paměťová složitost pak odpovídá maximu ze spotřeby času a paměti přes všechny vstupy dané velikosti
do časové složitosti nepočítáme načtení vstupu
podobně do prostorové složitosti nepočítáme vstup, do nějž se nezapisuje, ani výstup, pokud se jenom zapíše a pak už se nečte (takhle se někdy definuje pracovní prostor výpočtu)
je potřeba omezit kapacitu paměťové buňky
jednotková cena instrukce – omezíme šířku slova na W bitů
logaritmická cena instrukce – cena odpovídá počtu bitů operandů včetně adres (je přesný, ale nepohodlný na přemýšlení o algoritmech)
relativní logaritmická cena instrukce – u polynomiálně velkých čísel je cena jednotková, u obrovských čísel se cena zvyšuje (tohle budeme reálně používat – i když se k tomu budeme obvykle chovat jako k jednotkové ceně instrukce)
Definice: Čas a prostor konkrétního výpočtu, časová a prostorová složitost
pro různé úlohy používáme různé parametrizace vstupu (tedy velikost vstupu může být trochu něco jiného – někdy počet čísel, někdy jejich hodnota…)
doba běhu pro vstup x
t(x):= součet cen provedených instrukcí (může být ∞)
časová složitost výpočtu
T(n):=max{t(x)∣x vstup velikosti n}
prostor běhu pro vstup x
s(x):= max. adresa – min. adresa + 1
máme na mysli maximální a minimální adresy navštívené během výpočtu
prostorová složitost výpočtu
S(n):=max{s(x)∣x vstup velikosti n}
takhle jsme definovali složitosti v nejhorším případě, někdy se může hodit i průměrný případ
Definice: Asymptotická notace: O, Ω, Θ
f∈O(g)≡∃c∀∗nf(n)≤c⋅g(n)
f,g:N→R
∀∗n … pro všechna n až na konečně mnoho výjimek (existuje n0 takové, že pro všechna větší n už to platí)
f∈Ω(g)≡∃c∀∗nf(n)≥c⋅g(n)
Θ(g):=O(g)∩Ω(g)
Základní grafové algoritmy
Algoritmus: Prohledávání do šířky (BFS)
zpracování určitého vrcholu = odeberu ho z fronty, podívám se na sousední vrcholy a pokud jsou nenavštívené, tak je označím jako otevřené a přidám je do fronty ke zpracování, zpracovávaný vrchol zavřu
algoritmus začíná přidáním prvního vrcholu do fronty (to je ten vrchol, ze kterého graf prohledáváme)
algoritmus končí, jakmile je fronta prázdná
složitost Θ(n+m)
BFS najde cestu s nejmenším počtem hran (z výchozího vrcholu do libovolného vrcholu grafu) – tedy lze použít k hledání nejkratší cesty v grafech s jednotkovými hranami
klasifikace hran – rozdělíme vrcholy na vrstvy (podle toho, jak je BFS prochází ve vlnách)
stromová hrana – prošli jsme po ní při BFS
příčná hrana – v rámci vrstvy
zpětná hrana – do předchozí vrstvy nebo i o několik vrstev dozadu
„dopředně příčná“ hrana – do následující vrstvy
neexistuje hrana, která by vedla o víc než jednu vrstvu dopředu
Algoritmus: Prohledávání do hloubky (DFS)
lze implementovat rekurzí nebo jako BFS se zásobníkem místo fronty
na začátku jsou všechny vrcholy neviděné
DFS(v):
stav(v) ← otevřený
pro vw ∈E
pokud stav(w) = neviděný
DFS(w)
stav(v) ← zavřený
DFS spouštíme z nějaké vrcholu – navštívíme všechny vrcholy z něj dosažitelné
opakované DFS – algoritmus nespouštíme pouze pro jeden určitý vrchol, ale pro všechny (neviděné) vrcholy grafu → projdeme všechny komponenty souvislosti
stejného efektu lze docílit přidáním jednoho superzdroje, který bude připojen ke všem vrcholům grafu
složitost Θ(n+m)
Definice: Klasifikace hran v DFS
v orientovaném grafu
stromová hrana – hrana, po které jsme při DFS prošli
zpětná hrana – vede do předka (do otevřeného vrcholu)
dopředná hrana – vede do potomka (do uzavřeného vrcholu)
příčná hrana – vede do uzavřeného vrcholu v jiné větvi (není ani předkem, ani potomkem)
hrana nemůže být příčná v opačném směru – taková hrana je stromová
v neorientovaném grafu – každou hranu vidíme dvakrát
poprvé stromová, podruhé zpětná
poprvé zpětná, podruhé dopředná
hrana nemůže být poprvé dopředná, protože taková hrana je stromová
hrana nemůže být poprvé příčná, protože podruhé by byla příčná v opačném směru, což nejde
pokud ignorujeme druhé návštěvy, tak existují jenom stromové a zpětné hrany
klasifikaci lze určit i na základě uzávorkování průchodu vrcholy, když při otevření vrcholu vi napíšeme (i a při jeho uzavření )i
místo uzávorkování lze rovněž použít „hodiny“ a každému vrcholu nastavit čas otevření (in) a čas uzavření (out)
Algoritmus: Hledání mostů v neorientovaných grafech
Df: e∈E(G) je most ≡G−e má více komponent než G
e není most ⟺e leží na kružnici
zpětná hrana není nikdy most (leží na kružnici), tedy stačí poznat, zda stromová hrana leží na kružnici
stromová hrana xy není most ⟺∃ zpětná hrana ab, kde a leží v T(y) (podstromu y) a b v něm neleží
Df: low(v):=min{in(b)∣ab je zpětná hrana s a∈T(v)}
low pro v je minimum z low synů v a in zpětných hran z v (respektive in vrcholu, do nějž zpětná hrana z v vede)
stromová hrana xy není most ⟺low(y)<in(y)
stačí nám upravené DFS, běží v čase Θ(n+m)
Algoritmy pro orientované grafy
Algoritmus: Detekce cyklů pomocí DFS
lemma: na každém cyklu leží alespoň jedna zpětná hrana
mějme cyklus, na něm vrchol s minimálním outem
tedy další vrchol na cyklu bude mít větší out
tím získáváme hranu, na níž roste out – to platí pouze pro zpětné hrany
opačná implikace je jednoduchá (zpětná hrana nutně tvoří cyklus)
tedy stačí pustit opakované DFS a hledat zpětné hrany
věta: graf je DAG ⟺ opakované DFS nenajde zpětnou hranu
pro DAG G je GT graf vzniklý otočením šipek u G, je taky DAG (protože transpozice cyklu je cyklus), dojde k prohození zdrojů a stoků
Definice: Topologické uspořádání DAGu
topologické uspořádání grafu G=(V,E) je lineární uspořádání ≤ na V takové, že ∀uv∈E:u≤v
může jich být víc
Algoritmus: Konstrukce topologického uspořádání
postupným odtrháváním zdrojů (vezmeme libovolný vrchol, jdeme proti šipkám do zdroje, tento zdroj umístíme do uspořádání a odtrhneme ho z grafu) – to je ale složité na efektivní implementaci
opakované DFS opouští vrcholy v pořadí opačném topologickému uspořádání (důkaz přes klesající out na hraně a nepřítomnost zpětných hran)
Příklad: Princip indukce podle topologického uspořádání
mějme topologické uspořádání v1,…,vn
počítáme počet cest z vrcholu vi do všech vrcholů grafu
pro j<i:c(vj)=0
c(vi)=1
pro j>i induktivně c(vj)=∑kc(pk), kde pk jsou vrcholy, z nichž vede hrana do vj
Algoritmus: Počet cest mezi dvěma vrcholy v DAGu
indukcí přes topologické uspořádání, v čase Θ(n+m)
Definice: Silná souvislost, její komponenty, graf komponent
buď ↔ binární relace na vrcholech grafu definovaná tak, že x↔y, právě když existuje orientovaná cesta jak z x do y, tak z y do x
relace ↔ je ekvivalence, ekvivalenční třídy indukují podgrafy = komponenty silné souvislosti
graf je silně souvislý, má-li jednu komponentu (tedy pro každé dva vrcholy existuje cesta tam i zpět)
graf komponent C(G) má za vrcholy komponenty silné souvislosti grafu G, hrany mezi vrcholy vedou právě tehdy, když mezi danými komponentami vedou hrany v původním grafu
lemma: graf komponent je DAG (kdyby existoval cyklus, tak by se takto provázané komponenty slily do jedné)
Algoritmus: Rozklad grafu na komponenty silné souvislosti
opakované DFS v GT, při opouštění vrcholu ho dáme na zásobník
beru vrcholy ze zásobníku a pro vrcholy bez přiřazené komponenty provádím DFS
kdykoliv narazím na vrchol bez přiřazené komponenty, nastavím mu komponentu na „aktuální vrchol“ (to je ten vrchol, který jsem vzal ze zásobníku) a zanořím se (spustím rekurzivně DFS)
Nejkratší cesty
Definice: Vzdálenost v grafu
mějme orientovaný graf G=(V,E) s délkami hran l:E→R0+
délka uv-cesty P:l(P):=∑e∈Pl(e)
vzdálenost d(u,v):=min{l(p)∣P je uv-cesta}
může být ∞, pokud cesta neexistuje
Věta: Trojúhelníková nerovnost pro vzdálenost
d(u,v)≤d(u,w)+d(w,v)
důkaz
pokud je d(u,w) nebo d(w,v) nekonečná, nerovnost triviálně platí
jinak uvažujeme spojení nejkratší uw-cesty s nejkratší wv-cestou, to je nějaký uv-sled, který nemůže být kratší než nejkratší uv-cesta (protože nejkratší cesta = nejkratší sled; když se vrchol opakuje, tak část mezi opakováními vystřihneme)
kdybychom povolili hrany záporné délky, museli bychom zakázat záporné cykly
Algoritmus: Dijkstrův algoritmus
hledání nejkratších cest z daného vrcholu do všech vrcholů grafu
je to v podstatě BFS s budíky
funguje pro l∈Q0+
začínáme od nějakého vrcholu v0 (otevřeme ho a jeho ohodnocení h(v0) nastavíme na nulu)
dokud existují nějaké otevřené vrcholy, vybereme z nich ten, jehož h(v) je nejmenší (ten zavřeme) a všechny jeho následníky otevřeme a jejich h(w) snížíme na h(v)+l(v,w)
ukládáme předchůdce vrcholů, aby se cesta dala rekonstruovat
pozorování: každý vrchol zavřeme pouze jednou
pokud nejmenší h(v) hledáme pokaždé znova, tak to má složitost Θ(n2)
Příklad: Implementace Dijkstrova algoritmu pomocí haldy
cena operací
ExtractMin … TX
Insert … TI
Decrease … TD
složitost Dijkstra je O(n⋅TI+m⋅TD+n⋅TX)
vkládáme každý vrchol
decrease se provádí nejvýše jednou za každou hranu
extractujeme každý vrchol
v poli je vložení a odebrání O(n), decrease O(1)⟹O(n2)
v binární haldě jsou všechny tři operace O(logn)⟹O((n+m)logn)
v d-regulární haldě jsou Insert a Decrease O(logdn), ExtractMin je O(dlogdn)
logdn=logdlogn
je vhodné zvolit d=m/n, aby asymptotika vycházela hezky
ještě lepší je Fibonacciho halda
Algoritmus: Obecný relaxační algoritmus
jako Dijkstra, ale volíme libovolný otevřený vrchol (tedy ne nutně ten s nejnižším ohodnocením)
algoritmus
vstup: graf G, počáteční vrchol v0
na začátku jsou všechny vrcholy nenalezené, jejich ohodnocení je nekonečné, jejich předchůdci jsou nedefinováni
stav počátečního vrcholu nastavíme na otevřený, jeho ohodnocení na nulu
dokud existují otevřené vrcholy
vezmu nějaký otevřený vrchol v
pro všechny jeho následníky w provedu relaxaci, tzn.:
pokud h(w)>h(v)+l(v,w)
h(w)←h(v)+l(v,w)
stav(w) ← otevřený
P(w)←v
stav(v) ← uzavřený
výstup: ohodnocení vrcholů h a pole předchůdců
Algoritmus: Bellmanův-Fordův algoritmus
relaxační algoritmus, vrcholy ukládá do fronty (takže jako Dijkstra, akorát nebere nejlevnější, ale nejstarší)
funguje pro grafy bez záporných cyklů
má fáze
F0:= otevření v0
Fi:= zavírání vrcholů otevřených v Fi−1 a otevírání jejich následníků
invariant: na konci fáze Fi odpovídá h(v) délce nekratšího v0v-sledu o nejvýše i hranách
z toho vyplývá složitost Θ(n⋅m)
Minimální kostry
Algoritmus: Jarníkův algoritmus
klasický Jarník
hladový algoritmus
na začátku máme strom T, který obsahuje vrchol v0 (libovolný) a žádné hrany
vezmeme nejlehčí hranu vedoucí mezi stromem T a zbytkem grafu – tu přidáme do stromu
opakujeme, dokud takové hrany existují
složitost O(n⋅m)
Jarník podle Dijkstry
udržuju si haldu aktivních hran – to jsou hrany v aktuálním řezu
do stromu T vždycky přidávám minimum z haldy
když zjistím, že mám dvě aktivní hrany, které vedou do jednoho vrcholu mimo T, tak tu těžší zahodím
s polem složitost O(n2), s haldou O(mlogn) (protože nlogn se díky souvislosti grafu vejde do mlogn)
Věta: Lemma o řezech
Df: Mějme podmnožinu vrcholů A a jejich doplněk B. Elementární řez určený množinami A,B je množina hran, které leží jedním vrcholem v A a druhým v B.
lemma: Nechť G je graf opatřený unikátními vahami, R nějaký jeho elementární řez a e nejlehčí hrana tohoto řezu. Pak e leží v každé minimální kostře grafu G.
důkaz
v kostře musí ležet právě jedna hrana řezu
pro spor předpokládejme, že je to jiná hrana než e (a že je kostra minimální)
tuto hranu můžeme z kostry odstranit, tím vzniknou dva stromy
tyto stromy následně můžeme spojit pomocí hrany e
tím cena kostry klesne, což je spor s minimalitou
Věta: Jednoznačnost minimální kostry
věta: Souvislý graf s unikátními vahami má právě jednu minimální kostru (a Jarníkův algoritmus ji najde).
důkaz
každá hrana vybraná Jarníkovým algoritmem je nejlehčí hranou elementárního řezu mezi vrcholy stromu T a zbytkem grafu
každá hrana, kterou vybere, leží v každé minimální kostře
Algoritmus: Borůvkův algoritmus
paralelní verze Jarníkova algoritmu
na začátku T obsahuje izolované vrcholy grafu
dokud T není souvislý:
rozložíme T na komponenty souvislosti
pro každou komponentu najdeme nejlehčí hranu mezi komponentou a zbytkem vrcholů a přidáme ji do T
složitost
rozklad na komponenty v O(n+m), ale taky O(m) díky souvislosti
nalezení nejlehčích hran v O(m)
algoritmus se zastaví po nejvýše ⌊logn⌋ iteracích
z toho plyne složitost O(mlogn)
Algoritmus: Kruskalův algoritmus
hladový algoritmus
na začátku je T les izolovaných vrcholů
uspořádá hrany od nejlehčí po nejtěžší, postupně bere každou z nich (od nejlehčí)
vezme hranu a pokud jsou její krajní vrcholy v různých komponentách (zjišťuje se operací Find), tak ji přidá do T (a operací Union spojí komponenty)
konečnost zřejmá z omezeného počtu hran, správnost z řezového lemmatu (přidává nejlehčí hranu řezu)
složitost
třídění hran v O(mlogm)⊆O(mlogn2)=O(mlogn)
použijeme strukturu Union-Find
složitost algoritmu je O(mlogn+m⋅TF(n)+n⋅TU(n))
unionem přibývá hrana do kostry
Algoritmus: Union-Find
primitivně s polem Union O(n), Find O(1)
rychleji pomocí keříků
komponenta je keřík orientovaný do kořene
union se dělá připojením kořene jednoho keříku ke kořeni druhého keříku
find se dělá vystoupáním do kořene
kořen si pamatuje hloubku, při unionu budeme připojovat mělčí pod hlubší
tudíž hloubka keříku bude ≤logn
z toho plyne Union i Find O(logn)
pak má Kruskal složitost O(mlogn)
Vyhledávací stromy
Definice: Rozhraní slovníku, množiny a jejich uspořádaných verzí
množina – Find/Member, Insert, Delete
slovník – Get, Set, Delete
u statické struktury (např. setříděného pole) se navíc hodí operace Build
uspořádaná množina má navíc Min, Max, Pred, Succ
Definice: Binární vyhledávací strom (BVS)
BVS je binární strom, jehož každému vrcholu v přiřadíme unikátní klíč k(v) z univerza. Přitom musí pro každý vrchol v platit:
Kdykoliv a∈L(v), pak k(a)<k(v)
Kdykoliv b∈R(v), pak k(b)>k(v).
Algoritmus: Operace Find, Insert a Delete v BVS
Find: „binární vyhledávání“ (porovnávám s vrcholem – podle toho se zanořím do jednoho z podstromů nebo vrátím hodnotu vrcholu, případně ∅, pokud se nemám kam zanořit)
Insert: vložím vrchol tam, kde bych ho našel, kdyby ve stromu byl (pokud tam je, tak nic nedělám)
Delete: vrchol najdeme a smažeme; pokud má jednoho syna, tak ho připojíme pod otce smazaného vrcholu; pokud má dva syny, nejdříve nalezneme nejlevější vrchol v pravém podstromu a s tím ho prohodíme (fungovalo by to i symetricky)
Definice: Dokonale vyvážený strom
dokonale vyvážený je takový strom, pro jehož každý vrchol platí ∣∣l(v)∣−∣r(v)∣∣≤1
špatně se udržuje
Definice: AVL strom
AVL strom = hloubkově vyvážený strom
pro každý jeho vrchol platí ∣h(l(v))−h(r(v))∣≤1
tedy hloubka levého a pravého podstromu se liší nejvýše o jedna
Věta: Odhad hloubky AVL stromu
věta: AVL strom na n vrcholech má hloubku Θ(logn).
důkaz
jaká je maximální hloubka stromu o n vrcholech?
inverzní otázka: jaký je mininimální počet vrcholů ve stromu hloubky h?
u první nerovnosti odčítáme jedničku, u druhé nerovnosti dělíme konstantou (mírně) větší než jedna
Ah≥ch (dokázali jsme pro c=2)
tedy h≤logcn
kdyby h>log2n, pak n≥Ah≥ch>n, což je spor
dolní odhad
B0=1,B1=3,Bh=2Bh−1+1
Bh=2h+1−1≤2h+1
h≥logn−1≥logn
tedy h∈Θ(logn)
Definice: Rotace hrany stromu
jednoduchá rotace – hranu změním z levé na pravou (nebo naopak), převěsím jeden podstrom
dvojitá rotace – jeden vrchol „vytáhnu“ zespodu nahoru, převěsím dva podstromy
Algoritmus: Operace Insert a Delete v AVL stromech
Df: znaménko vrcholu
δ:V→{−1,0,+1}
δ(v):=h(r(v))−h(l(v))
insert a delete jako u BVS, ale navíc udržujeme znaménko a rotujeme, když je třeba
při insertu vkládáme list, posíláme nahoru signál o zvýšení hloubky
insert – signál o zvýšení hloubky přichází do vrcholu x BÚNO zleva (jinak bychom prohodili strany a znaménka)
vrchol x měl znaménko +
hloubka podstromů se vyrovnala, znaménko se změní na 0
hloubka hloubka podstromu T(x) se nezměnila, takže propagaci informace ukončíme
vrchol x měl znaménko 0
znaménko x se změní na −
hloubka T(x) vzrostla, pokračujeme v propagaci
vrchol x měl znaménko −, nově by měl −2⟹ musíme vyvažovat
označíme levého syna jako y
y má znaménko −
provedeme jednoduchou rotaci hrany xy
tím získají vrcholy x,y znaménko 0
hloubka se nezměnila, propagaci ukončíme
y má znaménko 0
nemůže nastat, protože z vrcholu se znaménkem 0 se informace nešíří výše (až na případ s listem, ale jeho otec x nemůže mít nikdy −)
y má znaménko +
pravého syna vrcholu y označíme jako z
provedeme dvojitou rotaci
novým kořenem podstromu je vrchol z, získá znaménko 0
hloubka se nezměnila, propagaci ukončíme
delete – informace o snížení hloubky přišla BÚNO z levého syna
vrchol x měl znaménko −
znaménko se změní na 0
hloubka T(x) se snížila, propagace pokračuje
vrchol x měl znaménko 0
znaménko se změní na +
hloubka T(x) se nezměnila, propagace končí
vrchol x měl znaménko +, nově +2⟹ vyvažujeme
označíme pravého syna jako y
vrchol y má znaménko +
provedeme rotaci hrany xy
tím získají vrcholy x,y znaménko 0
hloubka se snížila, změnu propagujeme
vrchol y má znaménko 0
rotujeme xy
vrchol x získá +, vrchol y znaménko −
hloubka se nezměnila, propagaci ukončíme
vrcholy y má znaménko −
levého syna vrcholu y označíme jako z
provedeme dvojitou rotaci, která celou konfiguraci překoření za vrchol z, ten získá znaménko 0
došlo ke snížení hloubky → propagujeme dál
při insertu se provádí maximálně jedna rotace, při deletu jich může být víc
operace Find, Insert, Delete v AVL stromu mají časovou složitost Θ(logn)
(a,b)-stromy
Definice: Vícecestný vyhledávací strom a (a,b)-strom
Obecný vyhledávací strom je zakořeněný strom s určeným pořadím synů každého vrcholu. Ty dělíme na vnitřní a vnější.
Vnitřní (interní) vrcholy obsahují libovolný nenulový počet (lineárně uspořádaných) klíčů. Ty slouží jako oddělovače hodnot v podstromech. Vrchol s k klíči má k+1 synů.
Vnější (externí) vrcholy neobsahují data, nemají potomky (jsou to listy). Značíme malými čtverečky.
(a,b)-strom pro parametry a≥2,b≥2a−1 je obecný vyhledávací strom, pro který navíc platí:
Kořen má 2 až b synů, ostatní vnitřní vrcholy a až b synů.
Všechny vnější vrcholy jsou ve stejné hloubce.
Věta: Odhad hloubky (a,b)-stromu
lemma: (a,b)-strom s n klíči má hloubku Θ(logn)
důkaz
Ah:= minimální počet klíčů ve stromu hloubky h
min. počet vrcholů na jednotlivých hladinách: 1,2,2a,2a2,…
na poslední interní hladině má aspoň 2ah−1 vrcholů, každý z nich obsahuje alespoň jeden klíč
Ah≥2ah−1∈Ω(ah)⟹ hloubka je O(logn)
podobně Ω(logn), tudíž i Θ(logn)
Algoritmus: Operace Insert a Delete v (a,b)-stromech
insert
přidáváme klíč do vrcholu na poslední interní hladině
když se vejde, je všechno v pořádku, jenom musíme přidat externí vrchol (list)
když se nevejde, tak ho rozdělíme na dva, prostřední klíč přesuneme o patro výš
když to přeteče o patro výš, tak vrchol zase rozdělíme…
přinejhorším nakonec rozdělíme kořen
co když nám při dělení vrcholu vzniknou dva moc malé?
to se nemůže stát, protože b=2a−1
přeteklý vrchol má b klíčů, jeden jde nahoru, zbývá b−1
rozdělíme na ⌊2b−1⌋ a ⌈2b−1⌉
kdyby se to pokazilo, tak ⌊2b−1⌋<a−1⟺b<2a−1
delete
mazání v poslední interní hladině je snadné, jenom musíme řešit podtečení vrcholu (tzn. počet klíčů ve vrcholu se nesmí snížit pod a−1)
pokud mažeme v hladině, která není poslední, tak to vyřešíme jako u BVS – daný klíč nahradíme maximem z levého podstromu nebo minimem z pravého (to je nutně na poslední interní hladině)
řešení podtečení
pokud má soused minimální povolený počet klíčů, tak můžu slučovat
podteklý vrchol má a−2 klíčů, soused má a−1 klíčů, k tomu přiberu klíč z otce, který je mezi nimi → dohromady jich bude 2a−2, což je v pořádku
tohle se může kaskádovat (až do kořene)
pokud má soused větší než minimální počet klíčů, tak mu jeden klíč utrhneme
BÚNO je soused pravý
podteklý vrchol si jako nové maximum vezme oddělovací vrchol z otce (ten, který odděloval podteklý vrchol a souseda)
otec si jako oddělovací vrchol vezme minimum ze souseda
tohle se nemůže kaskádovat
Příklad: Volba parametrů (a,b)-stromu
nechceme b výrazně větší než 2a, typicky b=2a−1 nebo b=2a
nechceme velké a, optimální jsou (2,3) nebo (2,4)
hodí se nastavit (a,b)-strom tak, aby se jeden vrchol vešel do jednoho bloku cache
Písmenkové stromy (trie)
Definice: Trie
písmenkový/prefixový strom
vrcholy odpovídají prefixům slov ze slovníku (množiny, kterou do trie ukládám) ⟹ počet vrcholů je O(∑i∣xi∣), kde xi je slovo (takže lineární velikost trie)
do stromu značíme, ve kterých vrcholech končí nějaké slovo ze slovníku (protože slovům nemusí odpovídat listy – nějaké slovo může být prefixem jiného)
každý vrchol dále obsahuje pole ukazatelů na syny (indexované abecedou)
Algoritmus: Operace Find, Insert a Delete v trii
find – procházím po vrcholech v lineárním čase (vůči délce hledaného slova)
insert – zkoušíme dané slovo najít, pokud nějaká hrana chybí, tak ji přidáme, poslední vrchol opatříme značkou; lineární čas vůči délce přidaného slova
delete – slovo najdeme, smažeme jeho značku a potom se vracíme do kořene, přičemž po cestě mažeme vrcholy, které nemají značku ani syny; lineární čas vůči délce mazaného slova
složitost v závislosti na velikosti abecedy ∣Σ∣ a délce slova L
find Θ(L)
insert Θ(∣Σ∣⋅L) – vyrábí pointery pro vrchol a nuluje ho
delete Θ(∣Σ∣⋅L) – kontroluje, jestli má vrchol dalšího syna
trie s BVS ve vrcholech – umí všechno v Θ(L⋅log∣Σ∣)
Příklad: Použití trie k reprezentaci čísel
zvolíme vhodný základ soustavy, čísla převedeme do této soustavy, tím dostaneme řetězce a ty ukládáme do trie (taková trie se někdy označuje jako radix tree, číslicový strom)
základ soustavy z
číslo z intervalu [0,M] má <logzM+1 číslic
pokud je základ soustavy rozumně malý, tak Find, Insert, Delete pracují v čase O(logzM)
z asymptotického hlediska to (oproti BVS) nepomáhá, z praktického hlediska to mívá lepší konstanty
Hešování
Definice: Hešování s řetězci v přihrádkach
máme universum U a množinu přihrádek [m]
hešovací funkce h:U→[m]
přání: h je rovnoměrná
máme n-prvkovou množinu X⊆U, kterou chceme do přihrádek umístit
počet prvků v jedné přihrádce bude ∼mn⟹ pro m≥n je to O(1)
⟹ Find, Ins, Del v O(1)? (pro nekonečné universum a konečně přihrádek to samozřejmě nemůže být pravda)
každá přihrádka má spojový seznam (řetězec)
v nejhorším případě se může celá množina X zahešovat do jedné přihrádky
Algoritmus: Operace Find, Insert a Delete v hešování s řetězci
každá z operací spočívá ve spočítání heše a průchodu daného spojového seznamu (řetězce), případně jeho úpravě
heš spočítáme v konstantním čase, řetězce mají n/m prvků, takže i průchod spojáku je konstantní pro m≥n
Algoritmus: Dynamické rozšiřování tabulky
na začátku založíme prázdnou hešovací tabulku s konstantním počtem přihrádek
když vkládáme prvek, zkontrolujeme faktor naplnění α=n/m (chceme ho udržet shora omezený konstantou)
když je tabulka příliš plná, zdvojnásobíme m (počet přihrádek) a všechny prvky přehešujeme
přehešování trvá Θ(n), mezi dvěma přehešováními vložíme řádově n prvků, takže každý přispěje konstantním časem ⟹Θ(1) insert
Definice: c-univerzální systém funkcí
Df: systém H funkcí z U do [m] je c-univerzální pro c>0≡ pravděpodobnost, že mi náhodně zvolená funkce konkrétní dva prvky hodí do stejné přihrádky, je malá (nejvýše c/m)
∀x,y∈U,x=y:Prh∈H[h(x)=h(y)]≤mc
kdyby funkce byla dokonale náhodně vybraná, tak by to vyšlo 1/m (takže c=1)
c bývá běžně 2,4,…
Věta: Konstrukce 1-univerzálního systému pomocí skalárního součinu
(standardní) skalární součin nad tělesem Zm
m … počet přihrádek, je to prvočíslo
U=Zmd (hešujeme d-složkové vektory se složkami ze Zm)
je to pravděpodobnost přes všechny volby a, takže to splňuje definici 1-univerzálního systému
Věta: Průměrná složitost operací při náhodné volbě hešovací funkce z c-univerzálního systému
věta: Pro x1,…,xn,y∈U navzájem různé a H c-univerzální systém z U do [m] platí Eh∈H[#i:h(xi)=h(y)]≤mcn.
důkaz
Ij … indikátor kolize (1 pokud h(xj)=h(y), jinak 0)
střední hodnota indikátoru je rovna pravděpodobnosti jevu
E[Ij]=Pr[h(xj)=h(y)]≤mc
# kolizí = ∑jIj=∑jE[Ij]≤mcn
důsledek
pro m∈Ω(n) je počet kolizí omezen konstantou, tedy průměrná složitost operací je konstantní
Rozděl a panuj
Algoritmus: Třídění sléváním (Mergesort)
na vstupu posloupnost
pokud je délka posloupnosti menší rovna jedné, mergesort vrátí vstup
jinak vrátí merge(mergesort(první polovina vstupu), mergesort(druhá polovina vstupu)), kde merge slévá dvě poloviční setříděné posloupnosti v lineárním čase
čas Θ(nlogn)
Algoritmus: Násobení n-ciferných čísel v čase O(nlog23)
Karacubovo násobení
násobíme dvě n-ciferná čísla x,y v soustavě o základu z
cifry obou čísel rozdělíme na dvě poloviny
x=a⋅zn/2+b
y=c⋅zn/2+d
pak x⋅y=(a⋅zn/2+b)(c⋅zn/2+d)=ac⋅zn+(ad+bc)⋅zn/2+bd
(ad+bc) lze vyjádřit jako (a+b)(c+d)−ac−bd
takže stačí 3 násobení
T(n)=3⋅T(n/2)+cn
časová složitost podproblému na vrstvě a počet podproblémů
1. vrstva n1
2. vrstva 2n3
i-tá vrstva 2in3i
poslední vrstva 13log2n
T(n)=∑i=0log2nn⋅(3/2)i∈Θ(n⋅(3/2)log2n), což lze převést na Θ(nlog23)
podle Master theorem a=3,b=2,c=1
Věta: Kuchařková věta (Master theorem)
věta: rekurentní rovnice T(n)=a⋅T(bn)+Θ(nc),T(1)=1 pro a∈N,a≥1,b∈R,b>1,c∈R0+ má řešení… (viz složitost u rozboru případů koeficientu níže)
důkaz
na i-té hladině podproblém velikosti bin, počet podproblémů ai
v jednom podproblému trávíme čas (bin)c
čas na i-tou hladinu Θ(ai⋅(bin)c)=Θ(nc⋅(bca)i), hladin je logbn
celkový čas T(n)=nci=0∑logbn(bca)i
označíme kvocient geometrické řady q=a/bc
pro q<1: součet je omezen konstantou ⟹Θ(nc)
pro q=1:∑=logbn∈O(logn)⟹Θ(nc⋅logn)
pro q>1:
Θ(nc⋅(a/bc)logbn), stačí započítat poslední prvek geometrické řady (důkaz ze součtu geometrické řady)
vstup rozdělíme na tři množiny – menší, větší a rovny pivotovi
porovnáme k s velikostmi množin, podle toho zjistíme, ve které hledat dál (a odpovídajícím způsobem upravíme k)
Věta: Průměrná časová složitost Quickselectu při náhodné volbě pivota
Df: skoromedián je prvek, který leží v prostředních dvou čtvrtinách setříděné posloupnosti
lemma o džbánu
E[# pokusů do 1. úspěchu]=p1, kde p= pravděpodobnost úspěchu
lze dostat úpravou E=1+(1−p)⋅E
kdybychom volili pivota jako skoromedián, tak podle Master theorem b=4/3,a=c=1⟹Θ(n)
protože v další hladině má ta množina, se kterou pracuji, velikost maximálně 43n
průměrnou složitost při náhodné volbě pivota dokážeme pomocí rozkladu na epochy
epocha skončí, kdykoliv se strefím do skoromediánu
průměrný počet průchodů v epoše je ≤2 (podle lemmatu o džbánu), protože pravděpodobnost výběru skoromediánu je 21
2 je konstanta, takže s náhodou volbou pivota můžeme v průměru zacházet, jako bychom volili skoromedián
z toho plyne Θ(n)
Algoritmus: k-tý nejmenší prvek v lineárním čase (algoritmus s pěticemi)
rozdělíme vstup na pětice, v konstantním čase najdeme jejich mediány
rekurzivním spuštěním téhož algoritmu najdeme medián mediánů
prvky jsme rozdělili na n/5 sloupečků o výšce 5
v nejhorším případě budeme v další hladině zpracovávat 107n, protože se nám podařilo zbavit jenom 103n
z toho plyne T(n)=T(51n)+T(107n)+Θ(n)
pro obecnější Master theorem lze určit Sα=109<1⟹Θ(n)
Algoritmus: Quicksort
pokud n≤1: vrátíme vstup
zvolíme pivota p
rozdělíme x1,…,xn podle p na L,S,P
L←QuickSort(L)
P←QuickSort(P)
vrátíme L,S,P
Věta: Průměrná časová složitost Quicksortu při náhodné volbě pivota
věta: QuickSort s náhodnou volbou pivota má časovou složitost se střední hodnotou Θ(nlogn).
důkaz
porovnání účtujeme prvku, který není pivot
Ti:= počet porovnání, kterých se účastní xi (a není pivot)
sleduju cestu jednoho prvku stromem rekurze
rozdělím cestu na epochy, epocha končí, když je pivot skoromedián
průměrný počet průchodů v epoše je ≤2
počet epoch pro prvek je Θ(logn), protože po každé epoše se problém zmenší na 43 (nebo na méně)
E[Ti]∈Θ(logn)
z linearity střední hodnoty dostaneme průměrnou časovou složitost algoritmu Θ(nlogn)
Dynamické programování
Algoritmus: Nejdelší rostoucí podposloupnost
vstup: posloupnost x1,…,xn
vyplňujeme pole délek nejdelších rostoucích podposloupností (označíme ho jako T), které končí v xi
tedy Ti:= délka nejdelší rostoucí podposloupnosti končící v xi
T1=1
pro každý další prvek xi se vždycky podíváme na prvky nalevo – najdeme maximální Tj takové, že xj<xi
zároveň si uložíme odkaz na předchůdce xj, abychom podposloupnost mohli následně vypsat
Algoritmus: Editační vzdálenost řetězců
na vstupu slova délky n,m
tabulka čísel o rozměrech (m+1)×(n+1), nad první řádek napíšeme jedno slovo, nalevo od prvního sloupce druhé slovo
předvyplníme poslední sloupec a poslední řádek (potkávají se v nule, směrem doleva/nahoru se zvyšují)
tabulku vyplňujeme zespodu zprava doleva nahoru, zapíšeme minimum z buňky dole, buňky vpravo a (buňky vpravo dole + δ), kde δ je rovna jedné, když písmena odpovídajícího řádku a sloupce liší, jinak je 0
výsledek je vlevo nahoře
Algoritmus: Konstrukce optimálního BVS
počítáme optimální podstrom s daným kořenem na dané množině vrcholů
jeho cena bude rovna ceně optimálního podstromu na vrcholech před kořenem + za kořenem + součtu cen vrcholů (to nám započítává cenu vrcholů a rovněž zohledňuje, že jsou ostatní vrcholy posunuté o vrstvu níž)
množina vrcholů je určena počátečním a koncovým vrcholem, takže takových množin bude O(n2), výpočet každé trvá O(n), takže celý algoritmus trvá O(n3) (když to zacachujeme nebo napíšeme dynamicky)
Algoritmus: Floydův-Warshallův algoritmus na výpočet vzdáleností v grafu
vstup: matice délek hran (hodnota je ∞, když cesta neexistuje, jinak Lij=l(vi,vj))
výstup: matice vzdáleností D (opět povolujeme nekonečno)
Dijk:= délka nejkratší cesty z vi do vj přes v1,…,vk (jakožto vnitřní vrcholy cesty)
D0=L,Dn=D
indukční krok Dijk=min{Dijk−1Dikk−1+Dkjk−1
dá se to dělat na místě, protože Dikk−1=Dikk a obdobně pro Dkj, k totiž nemůže být vnitřní vrchol cesty, když už je jejím krajním vrcholem
Příklad: Princip dynamického programování
rekurze → memoizace → přepis rekurze na cykly (dynamika)
u rostoucí podposloupnosti hledáme nejdelší cestu z 0 do n+1 (posloupnost n prvků jsme obložili −∞ a +∞), přičemž hrany vedou mezi prvky, které za sebou můžou v rostoucí podposloupnosti následovat (první je menší než druhý)
u editační vzdálenosti hledáme nejkratší cestu z levého horního do pravého dolního rohu, přičemž hrany vedou vodorovně (cena 1), svisle (cena 1) a diagonálně doprava dolů (cena 1 nebo 0)