Zkouška

• 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)

• 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

• $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)$

• 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

• 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)$

• 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)

• 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)$

• 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

• 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ů

• 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

• 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)

• 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$

indukcí přes topologické uspořádání, v čase $\Theta(n+m)$

• 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é)

• 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)

• 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

• $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

• 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)$

• 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

• 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ů

• 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 nekratšího $v_0v$-sledu o nejvýše $i$ hranách
• z toho vyplývá složitost $\Theta(n\cdot m)$

• 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$)

• 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: 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

• 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)$

• 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

• 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)$

• 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

• 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)$.

• 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)

• dokonale vyvážený je takový strom, pro jehož každý vrchol platí $||l(v)|-|r(v)||\leq 1$
• špatně se udržuje

• 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: 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)$

• 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

• 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)$

• 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.

• 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)$

• 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

• 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ý/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)

• 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|)$

• 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

• 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

• 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$

• 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

• 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,…$

• (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: 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í

• 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)$

• 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: 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í

• $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})$

• 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$)

• 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)$

• 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)$

• 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: 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)$

• 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

• 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

• 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)

• 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

• rekurze → memoizace → přepis rekurze na cykly (dynamika)
• např. Fibonacciho čísla

• 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)