# 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 `out`em - 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 nekratší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)