====== IN-POS 2. Algoritmy a datové struktury ======

===== Zadání =====

  * Analýza složitosti, amortizovaná složitost.
  * Techniky návrhu algoritmů (rozděl a panuj, dynamické programování, hladové strategie).
  * Pokročilé datové struktury (haldy, union-find struktury).
  * Algoritmy pro práci s řetězci (algoritmy Karp-Rabin, KMP, Boyer-Moore, užití konečných automatů).


  * IV003

===== Vypracování =====

==== Analýza složitosti, amortizovaná složitost  ====

<box 90% red|Časová složitost>
Časová složitost je funkce velikosti vstupu.

Vyjadřuje závislost času potřebného pro provedení výpočtu na rozsahu (velikosti) vstupních dat.

Rozlišujeme časovou složitost v nejlepším, nejhorším a průměrném případě.
</box>


=== Asymptotická notace ===

  * abstrakce od detailů při udávání složitosti

<box 90% blue|Θ notace>
Pro danou funkci <math>g(n)</math> označuje symbol <math>\Theta(g(n))</math> množinu funkcí:


 <math>\Theta(g(n)) = \lbrace f(n) \mid \exists c_1, c_2, n_0 : \forall n \geq n_0: 0\leq c_1g(n) \leq f(n) \leq c_2g(n)</math> 

---

<math>f(n) \in \Theta(g(n))</math>: //f roste asymptoticky stejně rychle jako g//
</box>

<box 90% blue|O notace>
Pro danou funkci <math>g(n)</math> označuje symbol <math>\mathcal{O}(g(n))</math> množinu funkcí:


 <math>\mathcal{O}(g(n)) = \lbrace f(n) \mid \exists c, n_0 : \forall n \geq n_0: 0 \leq f(n) \leq cg(n)</math> 

---

<math>f(n) \in \mathcal{O}(g(n))</math>: //f roste asymptoticky rychleji než g//
</box>

<box 90% blue|Ω notace>
Pro danou funkci <math>g(n)</math> označuje symbol <math>\Omega(g(n))</math> množinu funkcí:


 <math>\Omega(g(n)) = \lbrace f(n) \mid \exists c, n_0 : \forall n \geq n_0: 0 \leq cg(n) \leq f(n)</math> 

---

<math>f(n) \in \Omega(g(n))</math>: //f roste asymptoticky pomaleji než g//
</box>



=== Složitost problému ===

  * **Dolní odhad složitosti problému**: důkazové techniky
  * **Horní odhad složitosti problému**: složitost konkrétního algoritmu pro daný problém
  * **Složitost problému**: určeno dolním a horním odhadem, problém těsných odhadů


=== Techniky ===


== Informační metoda ==

  * Řešení obsahuje určité množství informace.
  * V každém kroku jsme schopni určit pouze část této informace.

<box 90% blue|Permutace>

Generování všech permutací n-prvkové posloupnosti

  * počet různých permutací: <math>n!</math>
  * => dolní odhad: <math>\Omega(n!)</math>
  * => složitost problému: <math>\Theta(n!)</math>

</box>

<box 90% blue|Polynom>

Evaluace <math>a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_0</math> v bodě <math>x</math>.

  * Spracování všech koeficientů <math>\Omega(n)</math>
  * => dolní odhad: <math>\Omega(n)</math>
  * => složitost problému: <math>\Theta(n)</math>

</box>

== Metoda redukce ==

  * známe dolní odhad pro **Q**
  * **Q** redukujeme na **P** (**Q** řešíme za pomoci **P**)
  * dolní odhad pro **Q** je i dolním odhadem pro **P**

== Metoda sporu ==

  * Snažíme se dokázat dolní odhad složitosti.
  * Dvě varianty:
    * Předpokládáme, že má algoritmus asymptoticky menší složitost a konstruujeme vstup, pro který nevypočte korektní řešení.
    * Předpokládáme, že algoritmus najde vždy korektní řešení a konstruujeme vstup, pro který složitost přesáhne uvažovanou mez.

=== Amortizovaná složitost ===

Technika pro přesnější určení složitosti.

  * Analyzujeme posloupnost operací jako celek, ne složitost každé operace.

== Používané metody ==

  * **Seskupení:** Operace seskupíme do skupin a analyzujeme složitost celé skupiny operací současně.

<box 90% blue|Zásobník>

  * Skupina 1: operace PUSH: součet složitostí nepřesáhne n
  * Skupina 2: operace POP a  MULTIPOP
    * Součet složitostí (= počet prvků vybraných ze zásobníku) nepřesáhne počet operací PUSH (= počet vložených prvků)
    * Složitost celé skupiny je n


  * Celá posloupnost n operací má v nejhorším případě složitost 2n.


</box>


  * **Metoda účtů:**
    * Každé operaci přiřadíme kredit (číslo), které může být různé od skutečné složitosti.
    * Při realizaci zaplatíme skutečnou cenu kredity
      * nedoplatek placen z účtu
      * přebytek vrácen na účet
    * Počáteční stav kreditů je 0.
    * Pokud je stav kreditů po celou dobu výpočtu nezáporný. Součet kreditů je <math>\geq</math> složitosti vykonaných operací.
    * Pro přehlednost lze kredity lze přiřazovat/odebírat objektům, na kterých se operace realizují.


<box 90% blue|Zásobník>

^ operace ^ složitost ^ kredity ^
| PUSH | 1 | 2 |
| POP | 1 | 0 |
| MULTIPOP | <math>\min(k, \mid S \mid)</math> | 0 |

  * Nezápornost kreditů dokážeme pomocí invariantu: "Počet kreditů na účtu je rovný počtu prvků na zásobníku."
  * Invariant platí na začátku.
  * PUSH zaplatí jeden kredit, 1 kredit dáme na účet
  * POP a MULTIPOP zaplatí kredity z účtu

  * Celá posloupnost n operací je <math>\leq</math> součet kreditů vykonaných operací. 
  * Součet kreditů vykonaných operací je <math>\leq 2n</math>

</box>

  * **Potenciálová funkce**
    * Zvolíme potenciálovou funkci, která přiřadí každého hodnotě datové struktury číslo.
    * Po celou dobu výpočtu nesmí hodnota klesnout pod počáteční mez.
    * Definujeme amortizované ceny operací pomocí skutečné ceny a změně potenciálu.
    *  Součet amortizovaných cen je <math>\geq</math> součtu skutečných cen. (Tedy je i horním odhadem složitosti posloupnosti operací.)


<box 90% blue|Zásobník>

^ operace ^ složitost ^ amortizovaná cena ^
| PUSH | 1 | <math>1 + (|S|+1) - |S| = 2 </math> |
| POP | 1 | <math>1 + |S| - (|S|+1) = 0 </math> |
| MULTIPOP | <math>\min(k, \mid S \mid)</math> | <math>
\begin{cases}
k + (\mid S \mid - k) - \mid S \mid = 0 \text{ pro } \mid S \mid \textgreater k \\
\mid S \mid + 0 - \mid S \mid = 0 \text{ pro } \mid S \mid \leq k
\end{cases}
</math> |

  * Celá posloupnost n operací je <math>\leq</math> součet amortizovaných cen. 
  * Součet amortizovaných cen je <math>\leq 2n</math>

</box>

==== Techniky návrhu algoritmů ====

=== Rozděl a panuj ===

  - Problém rozděl na podproblémy (stejného typu).
  - Vyřeš podproblémy.
  - Z řešení podproblému sestav řešení problému.


  * Příklady:
    * Merge sort
    * Quick sort
    * Násobení celých čísel
    * Násobení matic
    * Fast Fourier Transformation

=== Dynamické programování ===

  * Charakteristická struktura problému:
    * Problém lze rozdělit na podproblémy.
    * Vhodné pro optimalizační problémy s překryvem podproblémů.
    * Počet různých podproblémů je polynomiální.
    * Optimální řešení problému v sobě obsahuje optimální řešení podproblému.
    * Existuje přirozené uspořádání podproblémů od nejmenšího po největší.
  
  - Rekurzivní definice hodnoty optimálního řešení.
  - Výpočet hodnoty optimálního řešení **zdola-nahoru**.
  - Z vypočítaných hodnost sestav optimální řešení.


  * **Memoizace** = Pamatování si hodnot podproblémů.
  * ➕ jednoduché na pochopení
  * ➖ nutné určit pořadí řešení podproblémů ručně

  * **Bottom-up**
  * ➕ nemá overhead způsobený rekurzí
  * ➖jednodušší analýza složitosti

  * Příklady:
    * Floydův alg.
    * Warshallův alg.


=== Hladové strategie  ====

  * Vhodné pro optimalizační problémy, kde optimální řešení obsahuje optimální řešení podproblémů.
  * Stačí získat optimální řešení jediného podproblému. (Výběr na základě **lokální optimality**.)
  * Postup **shora-dolů**


  * Příklady:
    * Dijkstrův algoritmus pro problém nejkratších cest z daného vrcholu
    * Kruskal a Prim pro nejlehčí kostry
    * Huffmanovy kódy
    * Problém mincí (placení co nejmenším počtem mincí)
    * Problém pásky
      * n souborů různých délek ukládáme postupně na pásku
      * minimalizace přístupového času


==== Pokročilé datové struktury ====

=== Haldy ===

  * **Halda** = Datová struktura pro reprezentaci prvků, nad kterými je definované úplné uspořádání.
  * Podporované operace:
    * MAKE_HEAP() vytvoří prázdnou haldu
    * INSERT(H, x) do haldy H
    * MINIMUM(H) najde minimální prvek v H
    * EXTRACT_MIN(H) z haldy H odstraní minimální prvek
    * DELETE(H, x) z hlady H odstraní prvek x
    * UNION(H1, H2) vytvoří novou haldu sjednocením H1 a H2
    * DECREASE_KEY(H, x, y) nahradí klíč x klíčem y (y < x)


^ Operace ^ Seznam ^ Binární halda ^ Binomiální halda ^ Fibonacciho halda ^
| MAKE_HEAP | <math>\Theta(1)</math> | <math>\Theta(1)</math>  | <math>\Theta(1)</math> | <math>\Theta(1)</math> |
| MINIMUM | <math>\Theta(n)</math> | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> |
| INSERT | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> * | <math>\Theta(1)</math> |
| UNION | <math>\Theta(1)</math> | <math>\Theta(n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> |
| EXTRACT_MIN | <math>\Theta(n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> * |
| DELETE | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> * |
| DECREASE_KEY | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> * |

* amortizovaná složitost

<box 100% blue|Binomiální halda>

  * Na rozdíl od **binární haldy** tvořena lesem binomiálních stromů.
  * Umožňuje snadné spojování stromů.

{{https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/750px-Binomial_Trees.svg.png}}
</box>

<box 100% blue|Fibonacciho halda>

  * zobecnění binární haldy
  * struktura může obsahovat víc stromů; ukládáme ukazatel na minimální prvek
  * odkládáme operace až na dobu, kdy je to nutné
  * dvě hlavní mota (viz video [[https://www.youtube.com/watch?v=CEvUqy1uF1E|Amortized analysis of Fibonacci heap]]):
    * //Někdy se vyplatí nechat nepořádek narůst. (A uklidit hromadně.)//
      * = Nové uzly přidáváme jako jednouzlové stromy. Stromy se stejným stupněm spojujeme hromadně až při ''extract-min''. 
    * //Tvoji rodiče chtějí hodně vnoučat a pokud nemáš moc dětí, tak tě zavrhnou.//
      * = Uzel, který již dvakrát ztratil při ''decrease-key'' potomka je přesunut jako nový strom.
  * Efektivně realizujeme UNION, INSERT a DECREASE_KEY, ale nezhoršujeme amortizovanou složitost ostatních operací.

<box 90% blue|EXTRACT_MIN>

{{https://upload.wikimedia.org/wikipedia/commons/thumb/4/45/Fibonacci_heap.png/375px-Fibonacci_heap.png}}

  * Odebrání prvku (1) a rozpad potomků.

{{https://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Fibonacci_heap_extractmin1.png/255px-Fibonacci_heap_extractmin1.png}}

  * Spojení a finální stav po EXTRACT_MIN

{{https://upload.wikimedia.org/wikipedia/commons/thumb/9/95/Fibonacci_heap_extractmin2.png/195px-Fibonacci_heap_extractmin2.png}}

</box>

<box 90% blue|DECREASE_KEY>

{{https://upload.wikimedia.org/wikipedia/commons/thumb/4/45/Fibonacci_heap.png/375px-Fibonacci_heap.png}}

  * Snížení hodnoty z (9) na (0)

{{https://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Fibonacci_heap-decreasekey.png/375px-Fibonacci_heap-decreasekey.png}}

</box>
</box>

=== Union-find struktury  ===

  * Reprezentace disjunktních množin.
  * Operace:
    * MAKE_SET(x) vytvoří množinu obsahující prvek x
    * UNION(H1, H2) vytvoří novou množinu sjednocením H1 a H2
    * FIND_SET(x) najde reprezentanta množiny obsahující x

  * Aplikace:
    * Kruskalův agoritmus
    * komponenty souvislosti
    * ekvivalence konečných automatů

^ algoritmus ^ MAKE_SET ^ UNION ^ FIND_SET ^
| reverzní stromy | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(n)</math> |
| reverzní stromy (optimalizace) | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(\log n)</math> | <math>\mathcal{O}(\log n)</math> |
| plytké stromy | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(\log n)</math> | <math>\mathcal{O}(1)</math> |

Stromy s kompresí: Posloupnost m operací UNION, FIND_SET a MAKE_SET, z toho n operací MAKE_SET má složitost <math>O(m . \alpha(n))</math>

<box 100% blue|Reverzní stromy (Reversed trees)>

  * Každá množina reprezentována stromem.
  * Jeden vrchol stromu odpovídá jednomu prvku množiny.
  * Každý vrchol obsahuje odkaz na rodiče.
  * Kořen ukazuje na sebe a je reprezentantem množiny.


  * Implementace pomocí pole/seznamu.
  * MAKE_SET, UNION: konstantní složitost
  * FIND_SET: až lineární k počtu prvků prohledávané množiny

  * Optimalizace:
    * Při spojení dvou množin se kořen menší množiny stane synem kořene větší množiny.
    * Ke každému vrcholu asociujeme hloubku stromu jehož je kořenem.
    * MAKE_SET konstantní složitost
    * UNION, FIND_SET <math>\mathcal{O}(\log n)</math>
</box>

<box 100% blue|Plytké stromy (Shallow threaded trees)>

  * Množinu reprezentujeme jako spojovaný seznam, první prvek je reprezentantem.
  * Každý prvek má ukazatele na následníka a na reprezentanta.
  * Reprezentant obsahuje údaj o kardinalitě množiny.

  * MAKE_SET, FIND_SET konstantní složitost
  * WEIGHTED_UNION <math>\mathcal{O}(\log n)</math> amortizovaná složitost
</box>

<box 100% blue|Stromy s kompresí (Trees with path compresion)>

  * FIND_SET: Při postupu zpět napojíme vrcholy na cestě přímo na kořen.
  * Posloupnost m operací UNION, FIND_SET a MAKE_SET, z toho n operací MAKE_SET má složitost <math>O(m . \alpha(n))</math>

</box>



==== Algoritmy pro práci s řetězci ====

<note tip>Některé algoritmy (naivní, Karp-Rabin, automaty) jsou podrobněji rozepsány zde: http://statnice.dqd.cz/home:inf:in17</note>

Algoritmy pro:
  * Vyhledávání vzorku v textu.
  * Vzdálenosti řetězců a transformace řetězců
  * Společná podposloupnost
  * Aproximace řetězců
  * Opakující se podřetězce

^ Algoritmus ^ Předspracování ^ Vyhledávání ^
| Úplné prohledávání | <math>O</math> | <math>\mathcal{O}((n-m+1)m)</math> |
| Karp-Rabin * | <math>\Theta(m)</math> | <math>\mathcal{O}((n-m+1)m)</math> |
| Konečné automaty | <math>\mathcal{O}(m |\Sigma|)</math> | <math>\Theta(n)</math> |
| Knuth-Morriss-Pratt | <math>\Theta(m)</math> | <math>\Theta(n)</math> |
| Boyer-Moore * | <math>\Theta(m + |\Sigma|)</math> | <math>\mathcal{O}((n-m+1)m)</math> |

* Očekávaná složitost je výrazně lepší.

<box 100% blue|Karp-Rabin>

  * Řetězce chápeme jako čísla v desítkové soustavě.
  * Vzorek i jednotlivé podřetězce hašujeme (pomocí Hornerova schématu) a porovnáváme tyto haše.
  * Při posunutí o jednu pozici jsme schopni přepočíst haš v konstantním čas.

  - Příprava: <math>\Theta(m)</math>
    - Vypočteme haš hledaného řetězce.
    - Vypočteme haš prvního podřetězce.
  - Výpočet: <math>O((n-m+1)m)</math>
    - Porovnáme haš vzorku a haš aktuálního podřetězce. (Pokud je roven, porovnáme řetězce a případně uložíme nalezenou pozici.)
    - Posuneme se o jednu pozici v prohledávaném textu  a přepočteme haš (v konstantním čase).
    - Porovnáváme a posouváme se dokud jsme nedosáhli <math>(m-1)</math>-té pozice od konce. Poté vrátíme všechny nalezené pozice.

  * Očekávaná složitost pro //c// nálezů: <math>\mathcal{O}((n-m+1) + cm)</math>
    * ➕ vhodné pro delší vzorky s malým počtem očekávaných nálezů
</box>

<box 100% blue|Užití konečných automatů>
  * Pro daný vzorek zkonstruujeme konečný automat.
    * Využití sufixové funkce <math>\sigma</math> určující délku nejdelšího prefixu vzorku, který je sufixem slova.
    * <math>\delta(q, a) = \sigma(P[1] ... P[q] a)</math>
    * Tato metoda v <math>\mathcal{O}(m^3 \times \mid\Sigma\mid)</math>.
      * Existuje procedura s <math>\mathcal{O}(m \times \mid\Sigma\mid)</math>.
  * Text zpracujeme konečným automatem. <math>\Theta(n)</math>
</box>

<box 100% blue|KMP>
  * Nekonstruujeme celý automat ale před vyhledáváním vypočteme **prefixovou funkci** pro vzorek.
    * Postupně pro každou pozici ve vzorku určíme délku největšího podvzorku, který je zároveň prefixem i sufixem dosud zpracované části vzorku.
    * <math>\mathcal{O}(m)</math>
  * Samotný výpočet pak probíhá obdobně jako naivní prohledávání, ale při neshodě (nebo nalezení vzorku) se:
    * na textu nevracíme
    * na vzorce posuneme na pole dle prefixové funkce
  * <math>\mathcal{O}(n)</math>
</box>

<box 100% blue|Boyer-Moore>
  * Postupujeme zleva doprava a porovnáváme vzorek a text zprava.
  * Při neshodě můžeme využít dvě pravidla pro přeskočení pozic (vybereme větší skok):
    * **Heuristika špatného znaku**
      * nejbližší další pozice znaku z textu ve vzorku
      * symbol se nevyskytuje ve vzorku => posun o i pozic      
    * **Heuristika dobrého suffixu**
      * najdeme nejpravější výskyt u = T[j+i+1...m-1], před kterým je symbol různý od a
        * => posun o i-r pozic (r = index znaku různého od a)
      * nenajdeme nejdelší řetězec v, který je současně prefixem i sufixem P
        * => posun vzorku o m-|v| pozic
  * Tabulky pro heuristiky si lze ze vzorku předpočítat před samotným výpočtem. <math>\mathcal{O}(m \times |\Sigma|)</math>
  * Vyhledávání <math>\mathcal{O}(m \times n)</math>, ale očekávaně výrazně lepší.
    * nejlepší případ: <math>\mathcal{O}(\frac{n}{m})</math>
</box>

===== Zdroje: =====

  * slidy IV003 (verze 2016)