Definice algoritmu

Výpočetní model RAM

• obvyklý pseudokód
• paměť tvoří proměnné a pole
• aritmetické operace konstantní, ale
  • všechny problémy jdou vyřešit v konstantním čase magií s čísly
  • aritmetické operace trvají log. k délce čísel
  • velikost čísel omezena velikostí slova $w$, adresy mají délku $w$, máme k dispozici $2^w$ paměti

Čas a prostor konkrétního výpočtu

• součet cen provedených instrukcí, vzdálenost maximální a minimální adresy

Časová a prostorová složitost

• maximální čas a prostor pro vstup dané délky

Asymptotická notace: O, Ω, Θ

• $f\in\mathcal O(g) \Leftrightarrow \exists c:\forall n > \varepsilon : f(n) < c\cdot g(n)$
• $f\in \Omega(g) \Leftrightarrow \exists c:\forall n > \varepsilon : f(n) > c\cdot g(n)$
• $f \in \Theta(g) \Leftrightarrow f \in \mathcal O(g) \and f \in \Omega(g)$

Základní grafové algoritmy

Prohledávání do šířky (BFS)

• nalezené nenavštívené vrcholy ukládám do fronty.
• procházíme po vrstvách
• existují pouze stromové, příčné a dopředné hrany, dopředné pouze do následující vrstvy

Prohledávání do hloubky (DFS)

• zásobník nebo rekurze
• vrcholy neviděné, otevřené, uzavřené
• na konci:
  • dosažitelný $\Leftrightarrow$ uzavřený
  • nedosažitelný $\Leftrightarrow$ neviděný
  • indukcí podle doby běhu $\Leftarrow$
  • minimální protipříklad $⇒$

Klasifikace hran $xy$ v DFS

• stromová -- využili jsme ji během prohledávání (otevřený → neviděný)
• zpětná -- ukazuje do otevřeného vrcholu (otevřený → otevřený)
• dopředná -- $x$ otevřeno před $y$ (otevřený → uzavřený)
• příčná -- $x$ otevřeno až po $y$ (otevřený → uzavřený)

Hledání mostů

• v každém vrcholu si pamatujeme $\text{low}(v)$ jako minimum z $\text{in}(w)$ pro všechny vrcholy dosažitelné odkudkoliv z podstromu
• to lze spočítat jedním průchodem, protože to je minimum z $\text{low}()$ potomků a $\text{in}()$ všech sousedních vrcholů

Algoritmy pro orientované grafy

Detekce cyklů pomocí DFS

• každý cyklus obsahuje alespoň jednu zpětnou hranu

  • každý cyklus obsahuje alespoň jednu hranu, na které roste $\text{out}()$ vrcholů

  • to platí pouze pro zpětné hrany

• zpětná hrana tvoří cyklus triviálně

Acyklický orientovaný graf (DAG), zdroj, stok

• orientovaný graf bez cyklů
• obsahuje minimálně jeden
  • zdroj -- vrchol s $\text{deg}_\text{in}()=0$
  • stok -- vrchol s $\text{deg}_\text{out}()=0$
  • Dk.:
    • jdeme od libovolného vrcholu
    • někdy narazíme na stok, jinak by byl graf nekonečný nebo cyklický
    • transponujeme a nalezneme zdroj (v $G^T$ stok)

Topologické uspořádání DAGu

• částečné uspořádání tvořené hranami DAGu doplněné na lineární
• lineární uspořádání, kde hrany vedou všechny jedním směrem

Konstrukce topologického uspořádání

• $\text{out}()$ opakovaného DAGu je v souladu s tímto uspořádáním

Princip indukce podle topologického uspořádání

• odstřiháváme stoky

Počet cest mezi dvěma vrcholy v DAGu

• součet počtů cest do všech předchůdců druhého vrcholu, TI.

Silná souvislost, její komponenty, graf komponent

• mezi vrcholy silně souvislé komponenty existuje cesta v obou směrech
  • všechny vrcholy na cyklu jsou součástí stejné komponenty
• tvoří graf komponent, který je DAG
  • kdyby byl v grafu komponent cyklus, cyklus je i v podkladovém grafu a všechny komponenty tvoří jednu

Rozklad grafu na komponenty silné souvislosti

• DFS ze stokové komponenty projde pouze tuto komponentu
• jak najít stokovou komponentu?
  • pokud vede hrana z komponenty $C_1$ do komponenty $C_2$, bude maximální $\text{out}()$ v $C_1$ větší než v $C_2$ -- máme zdrojovou
  • zdrojová v $G^T$ je stoková v $G$
  • během procházení $G^T$ a zavírání vrcholů stavíme zásobník
  • odebíráním vrcholů ze zásobníku vždy nejdříve najdeme vrchol stokové komponenty, který můžeme odlomit

Nejkratší cesty

Vzdálenost v grafu

• ohodnocené hrany
• $≥ 0$, jinak je to hodně divočina
  • když neexistují záporné cykly, není to tak špatný
• může existovat sled stejně dlouhý jako nejkratší cesta (smyčka na něm je nulová)
• trojúhélníková nerovnost platí

Trojúhelníková nerovnost pro vzdálenost

• platí, ale může tam být sled

Dijkstrův algoritmus

• nastavujeme si budíky, skáčeme na nejbližší zvonící budík
• procházíme body sousední od toho aktuálního, přenastavujeme budíky, pokud mají být menší

Implementace Dijkstrova algoritmu pomocí haldy

• bereme si vrchol pomocí ExtractMin, aktualzujeme budíky pomocí Update

• složitost: $\mathcal O(n\cdot T_E + m\cdot T_D + n\cdot T_I)$
• d-regulární haldy better

Obecný relaxační algoritmus

• otevřeme první vrchol
• procházíme otevřené vrcholy a všem sousedům snižujeme $h(w)$ na $h(v)+l(v,w)$
  • tím je otevřeme
  • samotný vrchol tím zavřeme
• dijkstra vybírá z otevřených vždy ten s nejmenším $h()$

Bellmanův-Fordův algoritmus

• relaxace, ale otevřené jsou fronta

Minimální kostry

Jarníkův algoritmus

• začínáme v libovolném bodě
• do kostry přidáváme nejmenší nalezenou hranu

Lemma o řezech

• nejmenší hrana v každém řezu leží na kostře
• na minimální kostře musí existovat cesta mezi vrcholy $a$ a $b$ na koncích minimální hrany
• tato cesta musí vést někudy přes řez
• pokud vede jinou hranou řezu, můžeme hranu odstranit a přidat $ab$, čímž kostru zmenšíme
• vyžaduje různé hrany, uspořádání se dá dodělat např. čísly hran

Jednoznačnost minimální kostry

• vyplývá z lemma o řezech

(Jarník + Dijkstra)

• udržujeme haldu nalezených hran, ale pouze nejmenší pro každý vrchol -- aktivní hrany

Borůvkův algoritmus

• Jarník od každého bodu
• po každé fázi má každý strom alespoň $2^k$ vrcholů ⇒ fází je $\log n$
• fáze trvá $\mathcal O(m)$

Kruskalův algoritmus

• seřadím hrany dle velikosti
• přidávám nejmenší, pokud nevytvoří cyklus
• m·Find, n·Union
• s logaritmickým UnionFindem $\mathcal O (m\log n)$

Union-Find

• datová struktura která umí
  • Union -- spojit dva vrcholy do jedné množiny
  • Find -- zjistit, jsou-li dva stromy v jedné množině
• pamatování si čísel komponent -- Find v $\mathcal O(1)$, ale Union v $\mathcal O(n)$
• pomocí keříků
  • Find v $\mathcal O(\text{hloubka keříků})$
  • Union v $\mathcal O(1)$ -- spojíme keříky dohromady (nejdřív musíme Findnout kořen tho)
  • pokud vždy lepíme menší keřík pod kořen většího, udržujeme log. hloubku

Vyhledávací stromy

Rozhraní slovníku, množiny a jejich uspořádaných verzí

• slovník: klíč → hodnota
• množina: klíč → nachází se nebo ne
• Find, Insert, Delete, Build, (Min, Max, Next, Prev)

Binární vyhledávací strom (BVS)

• binární vyhledávací strom, kde platí, že všechny prvky levého podstromu jsou menší než kořen a pravého větší

Operace Find, Insert a Delete v BVS

• Find

• Insert -- Find a umístění na dané místo

• Delete

  • list -- Find a odstranění
  • jeden syn -- Find a nahrazení synem
  • dva synové -- Find, minimum z pravého podstromu

• všechny operace lineární s hloubkou

Dokonale vyvážený strom

• počet prvků v levém podstromu je stejný (o jedna rozdílný) než v pravém
• logaritmická hloubka
• když jdeme dolů, pokaždé máme pod sebou polovinu vrcholů než předtím

AVL strom

• hloubka levého podstromu je max. o jedna rozdílná než pravého

Odhad hloubky AVL stromu

• minimální velikost stromu dané hloubky $A_h=A_{h-1}+A_{h-2}+1$
• stačí odhad $A_h ≥ 2^{\frac h2}$
  • indukce $A_h > 2^{\frac{h-1}{2}} + 2^{\frac{h-2}{2}} = 2^h \cdot (2^{-\frac 12} + 2^{-1}) ; (2^{-\frac 12} + 2^{-1}) > 1$

Rotace hrany stromu

• převedení levé hrany na pravou a naopak
• 

Operace Insert a Delete v AVL stromech

• jako u BVS, ale rotujeme, když je třeba
• udržujeme ve vrcholu znaménko
• Insert: 5 možností příchodu signálu o zvýšení z levého podstromu, pravý analogicky
  • máme + → 0
  • máme 0 → --
  • máme –
    • příchozí vrchol --
    • příchozí vrchol +
    • příchozí vrchol 0 nenastane
• Delete: všech 6 možností signálu o snížení

(a,b)-stromy

Vícecestný vyhledávací strom a (a,b)-strom

• vyhledávací strom s více klíči v jednom vrcholu
  • $a≥2, b≥2a-1$
  • počet synů každého vrcholu je mezi $a$ a $b$ (kořen mezi $2$ a $b$)
  • všechny externí vrcholy jsou na poslední hladině

Odhad hloubky (a,b)-stromu

• minimální velikost stromu pro hloubku $h$ je $2a^{h-1} \in \Omega(a^h)$
• hloubka je $\mathcal O(\log n)$

Operace Insert a Delete v (a,b)-stromech

• Insert
  • vložíme list
  • ten nesmíme vložit, takže vysuneme o patro výše
  • pokud překročíme počet klíčů, prostřední klíč vysuneme opět nahoru
  • nikdy nevzniknou moc malé vrcholy protože $b≥ 2a-1, a≤\frac{b-1}{2}$
• Delete
  • v neposlední hladině prohodíme s maximem pravého podstromu
  • v poslední hladině
    • pokud má (BÚNO pravý) soused minimální počet klíčů, sloučíme se
    • jinak minimum (BÚNO pravého) souseda do klíče, klíč jako moje nové maximum, nejlevější souseda nyní nejpravější náš

Volba parametrů (a,b)-stromu

• vysoké hodnoty cool na točivý disky

Písmenkové stromy (trie)

Definice trie

• hrany tvoří písmenka abecedy, pokud slovo končí ve vrcholu, má tam svoji hodnotu

Operace Find, Insert a Delete v trii

• Find -- triv
• Insert -- vyrábíme děti dokud to jde
• Delete -- mažeme děti dokud to jde
• můžeme nasvačit BVS do vrcholů, když máme lorg abecedu

Použití trie k reprezentaci čísel

• RadixSort wahooo
• ne až tak useful ale implementačně hodně ez

Hešování

Hešování s řetězci v přihrádkach

• hešovací funkce umístí prvky do přihrádek
• více prvků v přihrádce reprezentujeme linkáčem

Operace Find, Insert a Delete v hešování s řetězci

• Find -- heš, projití linkáče
• Insert -- heš, projití linkáče, přilepení na konec
• Delete -- heš, projití linkáče, odstranění prvku

Dynamické rozšiřování tabulky

• jako dynamická alokace pole -- vždy dvojnásobíme

c-univerzální systém funkcí

• pravděpodobnost kolize $=\frac cm$, kde $m$ je počet přihrádek
• celkový počet kolizí $n\frac cm$
  • pokud je $n \in \mathcal O(m)$, bude kolizí konstantně mnoho

Konstrukce 1-univerzálního systému pomocí skalárního součinu

• prvočíslo $p=m$, vektorový prostor $\Z_p^d$, kde $d$ je zvoleno, aby se do vektoru dalo zakódovat jakékoliv vstupní číslo
• náhodně zvolíme vektor $t \in \Z_p^d$
• spočteme standartní skalární součin $h_t(x) = \Braket{t|x}\mod p$
• pokud se vektory liší v jedné složce $x_i$, pak ke kolizi dojde v právě jedné možné hodnotě v $t_i$ -- pravděpodobnost $\frac 1p$

Průměrná složitost operací při náhodné volbě hešovací funkce z c-univerzálního systému

$\mathcal O(c)$

Rozděl a panuj

Třídění sléváním (Mergesort)

• rozdělíme posloupnost na $n$ přihrádek, potom v každé patře dvě skupinky spojíme dohromady vybíráním minima z první nebo druhé skupinky
• $\mathcal O(n\log n)$
• rekurence, do které hooodně dosazujeme

Násobení n-ciferných čísel v čase $\mathcal O(n\log_23)$

• rozdělíme činitele $i,j$ na poloviny: $i = 2^m\cdot a + b$ $j = 2^m \cdot c + d$
• výsledek se pak dá zapsat jako: $ij = 2^{2m}ac + 2^mad + 2^mbc + bd$
• vytvoříme tři součiny $S_1 = (a + b)(c+d) = ac + ad + bc + bd$ $S_2 = ac$ $S_3 = bd$
• $ij = 2^{2m}S_2+2^m(S_1-S_2-S_3)+S_3$

Kuchařková věta (Master theorem)

• $t(n) = \mathcal O(n^c) +a\cdot t(\frac nb)$
• $t(1)=1$
• $t(n) = n^c + a\cdot \frac{n^c}{b^c} + a^2\cdot \frac{n^c}{b^{2c}} = n^c \cdot \left((\frac a{b^c})^0 + (\frac a{b^c})^1 + (\frac a{b^c})^2...(\frac a{b^c})^{\log_bn}\right)=n^c\cdot\sum_{i=0}^{\log_bn}(\frac a{b^c})^i$
• geometrická řada s $q=\frac a{b^c}$, s $\log_b n$ prvků
• $q=1: n^c \log_b n$
• $q < 1:$ geom. řada konverguje k prvnímu členu ($1$): $n^c$
• $q>1:$ geom. řada konverguje k poslednímu členu ($(\frac a{b^c})^{\log_bn}$): $n^c\cdot (\frac a{b^c})^{\log_bn} = \frac{n^c\cdot a^{\log_bn}}{b^{c\cdot \log_bn}}= \frac{n^c\cdot a^{\log_bn}}{n^c}=a^{\log_bn}=b^{\log_ba\cdot \log_bn}=n^{\log_ba}$

Strassenův algoritmus na násobení matic (vzorce nezkouším)

• vytvoříme sedm součinů, z nich matici poskládáme

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

Quickselect – hledání k-tého nejmenšího prvku

• náhodně zvolíme pivot
• rozdělíme prvky na menší a větší
• pokud je před pivotem více či méně prvků než $k$, zavoláme se na tu skupinu
• pokud ne, máme $k$-tý prvek
• $t(n) = n^1\cdot 1t(n/2); q=\frac 12; t(n) \in \mathcal O(n)$
  • pokud vždy zahodíme $\Omega(n)$ prvků, bude algoritmus v $\mathcal O(n)$

Průměrná časová složitost Quickselectu při náhodné volbě pivota

• džbán: skoromedián trefím s pravděpodobností $\frac 12$, v průměru na to budu potřebovat dva pokusy
• pokaždé, když trefím skoromedián, ukončím epochu
• $\mathcal O(n)$ epoch, epochy jsou konstantně dlouhé díky džbánu

k-tý nejmenší prvek v lineárním čase (algoritmus s pěticemi)

• bruhec

Quicksort

• rekurzivní QuickSelect

Průměrná časová složitost Quicksortu při náhodné volbě pivota

• $q$ je v každé epoše kroku $≤ 1$
• epochy konstantně krátké -- se džbánem chodíme pro skoromedián

Dynamické programování

Nejdelší rostoucí podposloupnost

• $n^2$ goes brr

Editační vzdálenost řetězců

• $n^2$ also goes brr

Konstrukce optimálního BVS

• idfk

Floydův-Warshallův algoritmus na výpočet vzdáleností v grafu

• uuuuuh matice something something?

Princip dynamického programování

• keše go brrr

Grafová interpretace dynamického programování

• DAG stavů
• pokud je DAG polynomiálně velký, vyhráli jsme