Zkouška

Definice algoritmu

• Definice: Výpočetní model RAM
  • není náhodný, ale po paměti umí skákat libovolně
  • 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 $\infty$)
  • časová složitost výpočtu
    • $T(n):= \text{max}\lbrace t(x)\mid x \text{ vstup velikosti }n\rbrace$
  • 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):= \text{max}\lbrace s(x)\mid x \text{ vstup velikosti }n\rbrace$
  • 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\in O(g)\equiv\exists c\,\forall^*n\;f(n)\leq c\cdot g(n)$
    • $f,g:\mathbb N\to\mathbb R$
    • $\forall^*n$ … pro všechna $n$ až na konečně mnoho výjimek (existuje $n_0$ takové, že pro všechna větší $n$ už to platí)
  • $f\in \Omega(g)\equiv\exists c\,\forall^*n\;f(n)\geq c\cdot g(n)$
  • $\Theta(g):= O(g)\cap \Omega(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 $\Theta(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 $\in 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 $\Theta(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 $v_i$ 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\in E(G)$ je most $\equiv G-e$ má více komponent než $G$
    • $e$ není most $\iff 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 $\iff\exists$ zpětná hrana $ab$, kde $a$ leží v $T(y)$ (podstromu $y$) a $b$ v něm neleží
  • Df: $\text{low}(v):=\text{min}\lbrace \text{in}(b)\mid ab$ je zpětná hrana s $a\in T(v)\rbrace$
  • 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 $\iff\text{low}(y)\lt \text{in}(y)$
  • stačí nám upravené DFS, běží v čase $\Theta(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 $\iff$ opakované DFS nenajde zpětnou hranu
• Definice: Acyklický orientovaný graf (DAG), zdroj, stok
  • DAG je orientovaný graf bez cyklů :)
  • zdroj je vrchol s $\text{deg}^{\text{in}}(v)=0$
  • stok je vrchol s $\text{deg}^{\text{out}}(v)=0$
  • lemma: každý DAG má alespoň jeden zdroj a stok
  • pro DAG $G$ je $G^T$ 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í $\leq$ na $V$ takové, že $\forall uv\in E: u\leq 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í $v_1,\dots,v_n$
  • počítáme počet cest z vrcholu $v_i$ do všech vrcholů grafu
  • pro $j\lt i:c(v_j)=0$
  • $c(v_i)=1$
  • pro $j\gt i$ induktivně $c(v_j)=\sum_k c(p_k)$, kde $p_k$ jsou vrcholy, z nichž vede hrana do $v_j$
• Algoritmus: Počet cest mezi dvěma vrcholy v DAGu
  • indukcí přes topologické uspořádání, v čase $\Theta(n+m)$
• Definice: Silná souvislost, její komponenty, graf komponent
  • buď $\leftrightarrow$ binární relace na vrcholech grafu definovaná tak, že $x\leftrightarrow y$, právě když existuje orientovaná cesta jak z $x$ do $y$, tak z $y$ do $x$
  • relace $\leftrightarrow$ 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 $\mathcal 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 $G^T$, 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\to \mathbb R^+_0$
  • délka $uv$-cesty $P:l(P):=\sum_{e\in P}l(e)$
  • vzdálenost $d(u,v):=\text{min}\lbrace l(p)\mid P$ je $uv$-cesta$\rbrace$
    • může být $\infty$, pokud cesta neexistuje
• Věta: Trojúhelníková nerovnost pro vzdálenost
  • $d(u,v)\leq 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\in\mathbb Q_0^+$
  • začínáme od nějakého vrcholu $v_0$ (otevřeme ho a jeho ohodnocení $h(v_0)$ 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 $\Theta(n^2)$
• Příklad: Implementace Dijkstrova algoritmu pomocí haldy
  • cena operací
    • ExtractMin … $T_X$
    • Insert … $T_I$
    • Decrease … $T_D$
  • složitost Dijkstra je $O(n\cdot T_I+m\cdot T_D + n\cdot T_X)$
    • 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)\implies O(n^2)$
  • v binární haldě jsou všechny tři operace $O(\log n)\implies O((n+m) \log n)$
  • v d-regulární haldě jsou Insert a Decrease $O(\log_d n)$, ExtractMin je $O(d\log_dn)$
    • $\log_dn=\frac{\log n}{\log d}$
    • 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 $v_0$
    • 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)\gt h(v)+l(v,w)$
          • $h(w)\leftarrow h(v)+l(v,w)$
          • stav(w) $\leftarrow$ otevřený
          • $P(w)\leftarrow v$
        • stav(v) $\leftarrow$ 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
    • $F_0:=$ otevření $v_0$
    • $F_i:=$ zavírání vrcholů otevřených v $F_{i-1}$ a otevírání jejich následníků
  • invariant: na konci fáze $F_i$ odpovídá $h(v)$ délce nejkratšího $v_0v$-sledu o nejvýše $i$ hranách
  • z toho vyplývá složitost $\Theta(n\cdot m)$

Minimální kostry

• Algoritmus: Jarníkův algoritmus
  • klasický Jarník
    • hladový algoritmus
    • na začátku máme strom $T$, který obsahuje vrchol $v_0$ (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\cdot 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(n^2)$, s haldou $O(m\log n)$ (protože $n\log n$ se díky souvislosti grafu vejde do $m\log n$)
• 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 $\lfloor\log n\rfloor$ iteracích
    • z toho plyne složitost $O(m\log n)$
• 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(m\log m)\subseteq O(m\log n^2)=O(m\log n)$
    • použijeme strukturu Union-Find
    • složitost algoritmu je $O(m\log n+m\cdot T_F(n)+n\cdot T_U(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 $\leq\log n$
    • z toho plyne Union i Find $O(\log n)$
    • pak má Kruskal složitost $O(m\log n)$

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\in L(v)$, pak $k(a)\lt k(v)$
    • kdykoliv $b\in R(v)$, pak $k(b)\gt 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ě $\emptyset$, 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)||\leq 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))|\leq1$
  • 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 $\Theta(\log n)$.
  • 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$?
      • $A_h:=$ min. počet vrcholů pro hloubku $h$
      • $A_0=1,\;A_1=2$
      • $A_h=A_{h-1}+A_{h-2}+1$ (za kořen)
        • to vede na Fib. čísla
      • tvrzení: $A_h\geq 2^{h/2}$
      • důkaz indukcí
      • pro $A_0,A_1$ platí
      • indukční krok: $A_h=A_{h-1}+A_{h-2}+1\geq 2^{h/2}\cdot 2^{-1/2}+2^{h/2}\cdot2^{-1}\geq 2^{h/2}$
        • u první nerovnosti odčítáme jedničku, u druhé nerovnosti dělíme konstantou (mírně) větší než jedna
      • $A_h\geq c^h$ (dokázali jsme pro $c=\sqrt{2}$)
      • tedy $h\leq \log_cn$
      • kdyby $h\gt \log_2n$, pak $n\geq A_h\geq c^h\gt n$, což je spor
    • dolní odhad
      • $B_0=1,\;B_1=3,\;B_h=2B_{h-1}+1$
      • $B_h=2^{h+1}-1\leq 2^{h+1}$
      • $h\geq\log n-1\geq \log n$
    • tedy $h\in\Theta(\log n)$
• 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
    • $\delta: V\to \lbrace-1,0,+1\rbrace$
    • $\delta(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\implies$ 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\implies$ 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 $\Theta(\log n)$

(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\geq2,\;b\geq2a-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 $\Theta(\log n)$
  • důkaz
    • $A_h:=$ minimální počet klíčů ve stromu hloubky $h$
    • min. počet vrcholů na jednotlivých hladinách: $1, 2, 2a, 2a^2,\dots$
    • na poslední interní hladině má aspoň $2a^{h-1}$ vrcholů, každý z nich obsahuje alespoň jeden klíč
    • $A_h\geq 2a^{h-1}\in\Omega(a^h)\implies$ hloubka je $O(\log n)$
    • podobně $\Omega(\log n)$, tudíž i $\Theta(\log n)$
• 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 $\lfloor\frac{b-1}2\rfloor$ a $\lceil\frac{b-1}2\rceil$
      • kdyby se to pokazilo, tak $\lfloor\frac{b-1}2\rfloor \lt a-1\iff b \lt 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) $\implies$ počet vrcholů je $O(\sum_i|x_i|)$, kde $x_i$ 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 $|\Sigma|$ a délce slova $L$
    • find $\Theta(L)$
    • insert $\Theta(|\Sigma|\cdot L)$ – vyrábí pointery pro vrchol a nuluje ho
    • delete $\Theta(|\Sigma|\cdot L)$ – kontroluje, jestli má vrchol dalšího syna
  • trie s BVS ve vrcholech – umí všechno v $\Theta(L\cdot \log |\Sigma|)$
• 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á $\lt\log_zM+1$ číslic
  • pokud je základ soustavy rozumně malý, tak Find, Insert, Delete pracují v čase $O(\log_zM)$
  • 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 $\mathcal U$ a množinu přihrádek $[m]$
  • hešovací funkce $h:\mathcal U\to [m]$
  • přání: $h$ je rovnoměrná
    • máme $n$-prvkovou množinu $X\subseteq\mathcal U$, kterou chceme do přihrádek umístit
    • počet prvků v jedné přihrádce bude $\sim \frac nm\implies$ pro $m\geq n$ je to $O(1)$
    • $\implies$ 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\geq 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í $\alpha=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á $\Theta(n)$, mezi dvěma přehešováními vložíme řádově $n$ prvků, takže každý přispěje konstantním časem $\implies \Theta(1)$ insert
• Definice: c-univerzální systém funkcí
  • Df: systém $\mathcal H$ funkcí z $\mathcal U$ do $[m]$ je $c$-univerzální pro $c\gt 0\equiv$ pravděpodobnost, že mi náhodně zvolená funkce konkrétní dva prvky hodí do stejné přihrádky, je malá (nejvýše $c/m$)
    • $\forall x,y\in\mathcal U,\,x\neq y:\text{Pr}_{h\in\mathcal H}[h(x)=h(y)]\leq\frac cm$
  • 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 $\mathbb Z_m$
    • $m$ … počet přihrádek, je to prvočíslo
  • $\mathcal U=\mathbb Z_m^d$ (hešujeme d-složkové vektory se složkami ze $\mathbb Z_m$)
  • hešovací funkci parametrizujeme vektorem $a\in\mathbb Z_m^d$
  • $\mathcal H=\lbrace h_a\mid a\in\mathbb Z^d_m\rbrace$
  • $h_a(x)=\braket{a,x}$ (v tělese)
    • tedy $\braket{a,x}=\sum_{i=1}^da_ix_i\bmod m$
  • věta: Tento systém je 1-univerzální.
  • důkaz
    • pro $x\neq y$
    • $\text{Pr}_{h\in\mathcal H}[h(x)=h(y)]=Pr_a[\braket{a,x}=\braket{a,y}]$
      • $ax=ay$
      • $a(x-y)=0$
      • $\sum_{i=1}^d a_i(x_i-y_i)=0$
    • BÚNO $x_1\neq y_1$ (přečíslováním souřadnic)
    • $a_1(x_1-y_1)+\sum^d_{i=2}a_i(x_i-y_i)=0$
    • neznámá $a_1\;\cdot$ nenulová konst. $(x_1-y_1)$ + konstanta = 0
      • lineární rovnice, existuje právě jedno řešení $a_1$
    • pravděpodobnost, že $a_1$ je řešení je $1/m$
    • 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 $x_1,\dots,x_n,y\in\mathcal U$ navzájem různé a $\mathcal H$ c-univerzální systém z $\mathcal U$ do $[m$] platí $\mathbb E_{h\in\mathcal H}[\text{\#}i:h(x_i)=h(y)]\leq \frac{cn}m$.
  • důkaz
    • $I_j$ … indikátor kolize (1 pokud $h(x_j)=h(y)$, jinak 0)
    • střední hodnota indikátoru je rovna pravděpodobnosti jevu
    • $\mathbb E[I_j]=\text{Pr}[h(x_j)=h(y)]\leq \frac cm$
    • # kolizí = $\sum_jI_j=\sum_j\mathbb E[I_j]\leq \frac {cn}m$
  • důsledek
    • pro $m\in\Omega(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 $\Theta(n\log n)$
• Algoritmus: Násobení n-ciferných čísel v čase $O(n^{\log_23})$
  • 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\cdot z^{n/2}+b$
    • $y=c\cdot z^{n/2}+d$
  • pak $x\cdot y=(a\cdot z^{n/2}+b)(c\cdot z^{n/2}+d)=ac\cdot z^{n}+(ad+bc)\cdot z^{n/2}+bd$
  • $(ad+bc)$ lze vyjádřit jako $(a+b)(c+d)-ac-bd$
  • takže stačí 3 násobení
  • $T(n)=3\cdot T(n/2)+cn$
  • časová složitost podproblému na vrstvě a počet podproblémů
    • 1. vrstva $\quad n\quad1$
    • 2. vrstva $\quad\frac n2\quad3$
    • i-tá vrstva $\quad \frac {n}{2^i}\quad 3^i$
    • poslední vrstva $\quad 1\quad 3^{\log_2 n}$
  • $T(n)=\sum_{i=0}^{\log_2 n}n\cdot(3/2)^i\in\Theta(n\cdot (3/2)^{\log_2n})$, což lze převést na $\Theta(n^{\log_23})$
  • podle Master theorem $a=3,\,b=2,\,c=1$
• Věta: Kuchařková věta (Master theorem)
  • věta: rekurentní rovnice $T(n)=a\cdot T(\frac nb)+\Theta(n^c),\;T(1)=1$ pro $a\in\mathbb N,\,a\geq 1,\,b\in\mathbb R,\,b\gt 1,\,c\in\mathbb R^+_0$ má řešení… (viz složitost u rozboru případů koeficientu níže)
  • důkaz
    • na i-té hladině podproblém velikosti $\frac n{b^i}$, počet podproblémů $a^i$
    • v jednom podproblému trávíme čas $(\frac{n}{b^i})^c$
    • čas na i-tou hladinu $\Theta(a^i\cdot (\frac{n}{b^i})^c)=\Theta(n^c\cdot(\frac a{b^c})^i)$, hladin je $\log_b n$
    • celkový čas $$T(n)=n^c \sum^{\log_bn}_{i=0}\left(\frac a{b^c}\right)^i$$
    • označíme kvocient geometrické řady $q=a/b^c$
    • pro $q\lt 1:$ součet je omezen konstantou $\implies\Theta(n^c)$
    • pro $q=1:\sum=\log_bn\in O(\log n)\implies\Theta(n^c\cdot \log n)$
    • pro $q\gt 1:$
      • $\Theta(n^c\cdot(a/b^c)^{\log_b n})$, stačí započítat poslední prvek geometrické řady (důkaz ze součtu geometrické řady)
      • upravíme $$n^c\cdot(a/b^c)^{\log_b n}=\frac{n^ca^{\log_bn}}{b^{c\log_bn}}=a^{\log_bn}=b^{\log_ba\cdot\log_bn}=n^{\log_ba}$$
      • z toho vyplývá složitost $\Theta(n^{\log_ba})$
    • poznámka: nevadí nám, že $n$ nemusí být mocnina $b$, v asymptotice se to ztratí
• Algoritmus: Strassenův algoritmus na násobení matic (vzorce nezkouším)
  • $X\cdot Y=\begin{pmatrix}A&B \\ C&D \end{pmatrix}\cdot\begin{pmatrix}P&Q \\ R&S \end{pmatrix}=\begin{pmatrix}AP+BR&AQ+BS \\ CP+DR&CQ+DS \end{pmatrix}$
  • jedno z 8 násobení lze ušetřit, z toho dostaneme $\Theta(n^{\log_27})$

Třídění a vyhledávání

• Algoritmus: Quickselect – hledání k-tého nejmenšího prvku
  • určíme pivota
  • 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
    • $\mathbb E[$# pokusů do 1. úspěchu$]=\frac 1p$, kde $p=$ pravděpodobnost úspěchu
    • lze dostat úpravou $\mathbb E=1+(1-p)\cdot\mathbb E$
  • kdybychom volili pivota jako skoromedián, tak podle Master theorem $b=4/3,\,a=c=1\implies \Theta(n)$
    • protože v další hladině má ta množina, se kterou pracuji, velikost maximálně $\frac 34 n$
  • 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 $\leq 2$ (podle lemmatu o džbánu), protože pravděpodobnost výběru skoromediánu je $\frac 12$
  • 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 $\Theta(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 $\frac 7{10} n$, protože se nám podařilo zbavit jenom $\frac 3{10}n$
  • z toho plyne $T(n)=T(\frac 15 n)+T(\frac 7{10}n)+\Theta(n)$
  • pro obecnější Master theorem lze určit $S_\alpha=\frac {9}{10}\lt 1\implies \Theta(n)$
• Algoritmus: Quicksort
  • pokud $n\leq 1$: vrátíme vstup
  • zvolíme pivota $p$
  • rozdělíme $x_1,\dots,x_n$ podle $p$ na $L,S,P$
  • $L\leftarrow \text{QuickSort}(L)$
  • $P\leftarrow \text{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 $\Theta(n\log n)$.
  • důkaz
    • porovnání účtujeme prvku, který není pivot
    • $T_i:=$ počet porovnání, kterých se účastní $x_i$ (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 $\leq 2$
    • počet epoch pro prvek je $\Theta(\log n)$, protože po každé epoše se problém zmenší na $\frac 34$ (nebo na méně)
    • $\mathbb E[T_i]\in\Theta(\log n)$
    • z linearity střední hodnoty dostaneme průměrnou časovou složitost algoritmu $\Theta(n\log n)$

Dynamické programování

• Algoritmus: Nejdelší rostoucí podposloupnost
  • vstup: posloupnost $x_1,\dots,x_n$
  • vyplňujeme pole délek nejdelších rostoucích podposloupností (označíme ho jako $T$), které končí v $x_i$
    • tedy $T_i:=$ délka nejdelší rostoucí podposloupnosti končící v $x_i$
  • $T_1=1$
  • pro každý další prvek $x_i$ se vždycky podíváme na prvky nalevo – najdeme maximální $T_j$ takové, že $x_j\lt x_i$
    • zároveň si uložíme odkaz na předchůdce $x_j$, 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)\times (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 + $\delta$), kde $\delta$ 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(n^2)$, výpočet každé trvá $O(n)$, takže celý algoritmus trvá $O(n^3)$ (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 $\infty$, když cesta neexistuje, jinak $L_{ij}=l(v_i,v_j)$)
  • výstup: matice vzdáleností $D$ (opět povolujeme nekonečno)
  • $D_{ij}^k:=$ délka nejkratší cesty z $v_i$ do $v_j$ přes $v_1,\dots,v_k$ (jakožto vnitřní vrcholy cesty)
  • $D^0=L,\;D^n=D$
  • indukční krok $$D_{ij}^k=\text{min} \begin{cases}D_{ij}^{k-1}\\ D_{ik}^{k-1}+D_{kj}^{k-1}\end{cases}$$
  • dá se to dělat na místě, protože $D^{k-1}_{ik}=D^k_{ik}$ a obdobně pro $D_{kj}$, $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)
  • např. Fibonacciho čísla
• Příklad: Grafová interpretace dynamického programování
  • u rostoucí podposloupnosti hledáme nejdelší cestu z $0$ do $n+1$ (posloupnost $n$ prvků jsme obložili $-\infty$ a $+\infty$), 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)