# 1. Algoritmy a datové struktury (95%)

###### tags: `algo`, `IV003¨

:::warning
* Pokročilé techniky návrhu algoritmů:
* dynamické programování
* hladové strategie
* **backtracking** *{nie je moc dobre spoznamkovaný}*
* Amortizovaná analýza
* Vyhledávání řetězců:
* naivní algoritmus pro hledání řetězců
* Karp-Rabinův algoritmus
* hledání řetězců pomocí konečných automatů.
* Algoritmus Knuth-Morris-Pratt

:::

## Pokročilé techniky návrhu algoritmů
### Dynamické programování

:::success
1. Charakterizuj strukturu 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ší.
2. Rekurzivně definuj hodnotu optimálního řešení
3. Vypočítej hodnotu optimálního řešení **zdola-nahoru**
4. Z vypočítaných hodnot sestav optimální řešení

:::

> vhodné pro řešení optimalizačních problémů, u kterých dochází k překrývání podproblému
> tj. tam kde by se mi mohlo stát, že bych tu samou situaci musel počítat několikrát

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

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

> [color=#7D2FAA] **Príklad: Rozvrh událostí**
>
>* daných je n událostí označených $1, ... n$
>* každá událost $i$ je specifikovaná svým začátkem $s_i$ a koncem $f_i$ (kde $s_i$ $\leq$ $f_i$) a hodnotou $v_i$
>* dvě události jsou kompatibilní, pokud se nepřekrývají ($i,j$ jsou kompatibilní když $s_i \geq f_j$ nebo $s_j \geq f_i$)
>* úlohou je najít takovou množinu vzájemně kompatibilních úloh $S \subseteq {1,...,n}$ pro kterou hodnota $\sum_{i \in S} v_i$ je maximální možná
>* předpokládáme uspořádání událostí podle koncového času $f_1 \Leftarrow f_2 \Leftarrow ... f_n$
>
>> [color=#449750]**Terminologie**
>>* událost $i$ je před událostí $j$ právě když $i < j$
>>* pro událost $j$ definujeme $p(j)$ jako největší index $i < j$ takový, že události $i$ a $j$ jsou disjunktní (kompatibilní)
>>* pokud index požadovaných událostí neexistuje, pak $p(j) = 0$
>
>:::success
>
>**Identifikace problému**
>nech $\mathcal O$ je optimálne riešenie
>udaloosť $n$ buď patrí alebo nepatrí do optimálneho >riešenia $\mathcal O$
>
>* $n$ patrí do $\mathcal O$
> * žiadna z udalostí $p(n-1) \Rightarrow 1,..., n-1$ nepatrí do $\mathcal O$
> * $\mathcal O$ musí obsahovať optimálne riešenie problému pre udalosti ${1,...,n-1}$
> * *dôkaz sporom*
>* $n$ nepatrí do $\mathcal O$
> * $\mathcal O$ je optimálnym rešením pre udalosti ${1,...,n}$
>
>:::
>
> > nájsť optimálne riešenie pre udalosti ${1,...,n}$ znamená nájsť optimálne rešenie pre menšie problémy tvaru ${1,...,j}$
>
>**Cena optimálneho riešenia**
>* označme pre $1 \leq j \leq n$ symbolom $\mathcal O_j$ optimálne riešenie pre udalosti ${1,...,j}$; nech $OPT(j)$ je hodnota $\mathcal O_j$
>* definujeme $\mathcal O_0 = \emptyset$ a $OPT(0) = 0$
>* hľadané riešenie $\mathcal O$ je práve $\mathcal O_n$
>* platí
$$OPT(j) =
\begin{cases}
0, & \text{ak $j=0$} \\[2ex]
\max{(v_j + OPT(p(j)), OPT(j - 1))}, & \text{ak $0 < j \leq n$}
\end{cases}$$
> * udalosť $j$ patrí do $\mathcal O_j$ práve vtedy, ak $v_j + OPT(p(j)) \geq OPT(j-1)$
>
>
>**Ako na to dynamickým programovaním?**
>:::info
>* využijeme na to rekurzívny vzťah medzi cenou riešenia problemu ($OPT(j)$)
>* ceny počítame v poradí $OPT(0), OPT(1),...,OPT(n)$ - čiže **zdola-hore**
>:::
>* pokiaľ si všetky vyššie uvedené údaje oodvodíte, potom je samotný algoritmus iba prepis rekurzívneho vzťahu do kódu:
>
> $\operatorname {ITERATIVE\_COMPUTEOPT}(j)$
$M[0] = 0$
**for** $j=0$ **to** $n$ **do**
$M[j] = \max{(v_j+M[p(j)],M[j-1])}$
**od**
>* **Složitost**
> * $\mathcal O(n)$
>* **Korektnost**
> * korektnost daní korektností rekurzivního vztahu

> [color=#7D2FAA] **Príklad 2.: Nejdelší společná podposloupnost(NSP)**
>
>- nechť $X= <x_1, ... x_m>, Y= <y_1, ...y_n>$ a $Z= <z_1, ... z_k>$ jsou posloupnosti symbolů
>- $Z$ je podposloupností $X$ právě když existuje rostoucí posloupnost indexů $1 <= i_1 < ... < i_k \leq m$ taková, že pro všechny $j = 1, ... k$ platí $x_{ij}=z_j$
>- Z je společnou podposloupností právě $X$ a $Y$ právě když je podposloupností $X$ a zároveň $Y$
–- problém $NSP$ je pro dané dvě posloupnosti najít jejich nejdelší společnou podposloupnost
>
> ::: success
>**Určení podproblémů:**
>- nech $X = <x_1,...x_m>$ a $Y = <y_1,...y_n>$ sú postupnosti symbolov a nech $Z = <z_1,...z_k>$ je ich najdlhšia spoločná podpostupnosť $(NSP)$
> - ak $x_m = y_n$ tak
> - $z_k = x_m = y_n$ a
> - $Z_{k-1}$ je NSP postupností $X_{m-1}$ a $Y_{n-1}
> - ak $x_m \ne y_n$ a $x_m \ne z_k$ tak
> - $Z$ je NSP postupností $X_{m-1}$ a $Y$
> - ak $y_n \ne x_m$ a $y_n \ne z_k$ tak
> - $Z$ je NSP postupností $X$ a $Y_{n-1}
>:::
>- Definujeme funkcoiu $c$ takú, že $c[i,j]$ označuje dlžku spoločnej podpostupnosti $X_i$ a $Y_j$
>
>$$c[i,j] =
\begin{cases}
0, & \text{ak $i=0$ alebo $j=0$} \\[1ex]
c[i-1,j-1]+1, & \text{ak $i,j > 0$ a $x_i = y_j$}\\[1ex]
\max{c[i,j-1],c[i-1,j]}, & \text{ak $i,j > 0$ a $x_i \ne y_j$}
\end{cases}$$
>
>**Dynamický algoritmus**
>- nepoužijeme rekurzi, namísto toho budeme počítat od hodnot s nejnižším indexem a budeme postupně zvyšovat indexy v obou směrech
>- takto si spočítáme celý prostor a poznačíme si shody v posloupnostech, dojde i k počítání neperspektivních hodnot, nicméně velkému množství výpočtů se vyhneme, protože je nebudeme opakovat
>- v samostatném průchodu pak nalezneme řešení
>- poradie výpočtu
>$$\begin{pmatrix}c[1,1], & ... & ,c[1,n]\
\\ c[2,1], & ... & ,c[2,n]\
\\ ... & ... & ...\\
\\ c[m,1], & ... & ,c[m,n]\end{pmatrix}$$

:::info
**Kdy použít dynamické programování:**
- počet různých podproblémů je polynomiální
- řešení původního problému lze snadno vypočítat z řešení podproblémů
- existuje přirozené uspořádání podproblémů od nejmenších po největší (abychom mohli postupovat zdola nahoru)
- existuje jednoduchá rekurze, která umožní řešit podproblémy pomocí menších podproblémů

:::
---

### Hladové strategie

:::success
* Technika vhodná pro řešení optimalizačních problémů, které mají **optimální substrukturu** (tj. optimální řešení problému v sobě obsahuje optimální řešení podproblémů)
* Pro získání optimálního řešení stačí znát optimální řešení **jednoho z podproblémů**. Tento podproblém vyberu na základě **kritéria lokální optimality**, tj. bez znalosti jeho řešení
* Ve výpočtu směřuji **zdola nahoru**

:::

:::info
* technika NENÍ použitelná pro všechny optimalizační problémy
* hladové algoritmy se velmi dobře navrhují, ale zatraceně špatně dokazují, pozor na to!
:::

> [color=#7D2FAA] **Príklad: Mince**
>
>- k dispozici jsou mince hodnoty $h_1, ... ,h_k$
>- počet mincí každé hodnoty je neomezený
>- úlohou je pro dané $N$ zaplatit sumu $N$ za použití co nejméně mincí
>- problém má optimální substrukturu, protože pokud použiju minci k, tak na zaplacení $N - h_i$ musím opět použít optimální počet mincí
>- označme $MIN[i]$ minimální počet mincí, které jsou potřebné pro zaplacení sumy $i$:
>$$MIN[j] =
\begin{cases}
0, & \text{pre $i=0$} \\[2ex]
1 + \max_{1 \leq j \leq k}({MIN[i-h_j]}), & \text{pre $i > 0$}
\end{cases}$$

> ::: info
> Strategie:
>- Dynamický přístup
> - vypočítáme hodnoty $MIN[1], .... ,MIN[N]$
> - složitost je $\mathcal Ο(N * k)$, algoritmus vždy najde optimální hodnotu
>- Hladový přístup
> - použijeme kritérium lokální optimality
> - když mám zaplatit sumu i, tak vyberu minci $h_x$ maximální hodnoty, tak aby platilo $h_x \leq i$ (vezmu nejvyšší možnou minci)
>:::
> Hladový algoritmus
> $Mince(i):$
> predpokladáme, že $h_1 > h_2 > ... > h_k$
> $s \gets 0$
> **for** $m = 1$ **to** $k$ **do**
>- **while** $i \geq h_m$ **do** $i \gets i - h_m$
$s \gets s + 1$ **od**
>- **od**
>
> **od**
> **return** $s$
> >POZOR: Pro mince hodnoty 6, 4, 1 a sumu 8 algoritmus nenalezne optimální řešení! U mincí záleží na jejich hodnotě, u mnoha kombinací nebudou hladové algoritmy fungovat.

---
### Backtracking
> úprimne som moc ani nenašla, že by sme sa tým na algo2 príliš zaoberali, čiže len tak v krátkosti

* Rekurzívna algoritmická technika používaná na riešenie problemov tak, že sa postupne pokúšame zostavovať riešenie - kus po kuse - pričom odstraňujeme tie riešenia, ktoré v žiadnom okamihu nespĺňajú obmedzenia problému (časom tu označujeme čas, ktorý uplynul do dosiahnutia akejkoľvek úrovne stromu vyhľadávania)

---
## Amortizovaná analýza
:::info
Jedná sa o techniku umožňujúcu presnejšie určenie zložitosti, preto najprv **definujeme** a **rozpíšeme** klasickú analýzu zložitosti

:::

### Analýza složitosti
:::success
**Č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ě.

Rozlišujeme složitost **problému** a složitost **konkrétního algoritmu**
:::

U složitosti problému se bavíme o horním a dolním odhadu, kde horní odhad je složitost konkrétního algoritmu pro daný problém; dolní odhad je pak nejmenší složitost se kterou lze daný problém řešit

> - mějte na paměti, že kromě analýzy složitosti, se provádí i **analýza konečnosti** a **parciální korektnosti**; ačkoliv to není přímo v otázce, může na to okrajově dojít řeč

#### Složitost problému
:::success
* **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ů
:::

#### Asymptotická notace
:::success
**$Θ$ notace**
Pro danou funkci $g(n)$ označuje symbol $\Theta(g(n))$ množinu funkcí:
$\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)$
:::

> [color=#1167b1] $f(n) \in \Theta(g(n))$: $f$ roste asymptoticky stejně rychle jako $g$

<br />

:::success
**$\mathcal{O}$ notace**

Pro danou funkci $g(n)$ označuje symbol $\mathcal{O}(g(n))$ množinu funkcí:
$\mathcal{O}(g(n)) = \lbrace f(n) \mid \exists c, n_0 : \forall n \geq n_0: 0 \leq f(n) \leq cg(n)$
:::

> [color=#1167b1] $f(n) \in \mathcal{O}(g(n))$: $f$ roste asymptoticky rychleji než $g$

<br />

:::success
**$\Omega$ notace**

Pro danou funkci $g(n)$ označuje symbol $\Omega(g(n))$ množinu funkcí:
$\Omega(g(n)) = \lbrace f(n) \mid \exists c, n_0 : \forall n \geq n_0: 0 \leq cg(n) \leq f(n)$
:::

> [color=#1167b1] $f(n) \in \Omega(g(n))$: $f$ roste asymptoticky pomaleji než $g$

### Techniky dokazování složitosti
:::info

**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.
* často lze aplikovat rozhodovací stromy, kde vnitřní vrcholy jsou dotazy na vstupní instanci a hrany jsou možnými odpověďmi;
* listy jsou pak výstupy;
* časová složitost v rozhodovacím stromě odpovídá nejdelší cestě od kořene k listu

:::
:::success
**Permutace**
Generování všech permutací n-prvkové posloupnosti

počet různých permutací: $n!$
⇒ dolní odhad: $\Omega(n!)$
⇒ složitost problému: $\Theta(n!)$
:::

:::success
**Polynom**
Evaluace $a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_0$ v bodě $x$.

Spracování všech koeficientů $\Omega(n)$
⇒ dolní odhad: $\Omega(n)$
⇒ složitost problému: $\Theta(n)$
:::

> [color=#7D2FAA] **Příklad:**
vygenerování všech permutací n-prvkové posloupnosti; jejich počet je n! a proto i dolní odhad je Ω(n!)

> [color=#7D2FAA] **Příklad rozhodovacího stromu:**
vstup je setřízené pole $A[1 ... n]$, a mám rozhodnout, zda $X$ se vyskytuje v $A$, pokud ano mám také určit jeho polohu (tzv. problém slovníku)

:::info
#### 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

:::
> [color=#7D2FAA] **Příklad: (Q) opakuje se některé číslo v posloupnosti čísel x_1, ... x_n?**
$(P)$ minimální kostra v Euklidovském grafu - zde znám dolní odhad.
Redukce: převedení posti na body $(x_1; 0), ... (x_n; 0)$ nyní mohu tento problém řesit jako problém minimální kostry v Eukl. grafu. V posloupnosti se opakuje číslo právě tehdy, když minimální kostra obsahuje hranu délky $0$.
Závěr: Dolní odhad pro problém $P$ je $Ω(n \log n)$

:::info
#### 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.
* pod metodu sporu dále patří i **metoda protivníka**, jedná se o formu hry mezi protivníkem a algoritmem
* protivník volí vstupní instanci a algoritmus mu na ni klade otázky protivník odpovídá tak, aby algoritmus udělal co nejvíce práce
:::

> [color=#7D2FAA] **Příklad:** Lema - Nechť algoritmus $Q$ je založený na porovnávání prvků a nechť $Q$ řeší problém maximálního prvku. Potom $Q$ musí na každém vstupu vykonat alespoň $n-1$ porovnání.
>
> Důkaz (Princip 1):
>* Nechť $x = (x_1, ... x_n)$ je vstup délky $n$, na kterém $Q$ vykoná méně než $n-1$ porovnání a nechť $x_r$ je maximální prvek v $x$.
>* Potom musí existovat prvek $x_p$ takový, že $p \ne r$ a v průběhu výpočtu $x_p$ nebyl porovnávaný se žádným prvkem větším než on sám. Existence takového prvku plyne z počtu vykonaných porovnání.
>* Když v $x$ změníme hodnotu $x_p$ na $x_r + 1$, tak $Q$ určí jako maximální prvek $x_r$ - ==**spor**==

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

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

> potenciálová funkce je asi nejsložitější, ale také jediná univerzální; seskupení a účty mohou v některých případech zklamat; na druhou stranu pokud lze něco spočítat více způsoby, poslouží to jako kontrola správnosti

#### Používané metody:

### **Seskupení**

:::success
Operace seskupíme do skupin a analyzujeme složitost celé skupiny operací současně.
:::
>- jednu skupinu typicky tvoří operace, které vytváří/přidávají obsah (push), druhou pak operace, které ho odebírají (pop, multipop)

> [color=#7D2FAA] **Príklad:** **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$.

### **Metoda účtů**
:::success
* 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
* počáteční stav účtu je vždy 0 kreditů
* když je cena operace menší nebo rovná kreditu operace, tak za operaci zaplatíme tolik kreditů, jaká je cena a zbytek uložíme na účet
* když je cena operace větší než kredit operace, tak kredity potřebné pro její provedení zaplatíme z účtu
* Pokud je stav kreditů po celou dobu výpočtu nezáporný. Součet kreditů (vykonaných operací) je $\geq$ složitosti (ceně) vykonaných operací.
* pokud kdykoliv během výpočtu klesne stav kreditů na účtu pod 0, je tento výpočet špatně/neplatný!

Pro přehlednost lze kredity lze přiřazovat/odebírat objektům, na kterých se operace realizují.
:::

> [color=#7D2FAA] **Príklad:** **Zásobník**

| **operace** |**složitost** | **kredity** |
| ----------------- |:----------------------- |:----------------------- |
| PUSH | 1 | 2 |
| POP | 1 | 0 |
| MULTIPOP | $min(k,\vert S \vert )$ | 0 |

> [color=#7D2FAA]
>* 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.
>* S každou operací PUSH si uložím kredit navíc na účet, čímž si předplatím POP/MULTIPOP;
> * 1 kredit dáme na účet
>* POP a MULTIPOP zaplatí kredity z účtu
> > Lze lehko ověřit, že stav účtu nikdy neklesne pod nulu. Vyplývá to z invariantu, který říká, že počet kreditů na účtu je roven počtu prvků na zásobníku.
>* Celá posloupnost $n$ operací je $\leq$ součet kreditů vykonaných operací.
>* Součet kreditů vykonaných operací je $\leq 2n$
>
>Jako variantu metody účtů lze kredity přiřazovat objektům datové struktury, nad kterou se operace realizují. Cena operace se zaplatí kredity objektů, se kterými operace manipuluje.

### **Potenciálová funkce**
:::success
Operace se realizují nad datovou strukturou.

* Zvolíme potenciálovou funkci $ϕ$, která přiřadí každé hodnotě datové struktury číslo.
* Po celou dobu výpočtu nesmí hodnota klesnout pod počáteční mez.
* Uvažujme posloupnost n operací. Nechť skutečná cena $i$-té operace v této posloupnosti je $c_i$.
* Označme $D_0$ iniciální hodnotu datové struktury a $D_i$ její hodnotu po vykonání $i$-té operace.
* Definujeme amortizované ceny operací pomocí skutečné ceny a změně potenciálu.
* cena $i$-té operace $\hat c_i$ předpřisem:
$\hat c_i = c_i + ϕ(D_i) - ϕ(D_{i-1})$
* Součet amortizovaných cen je $\geq$ součtu skutečných cen. (Tedy je i horním odhadem složitosti posloupnosti operací.)
* $\sum_{i=1}^n \hat c_i = \sum_{i=1}^n (c_i + ϕ(D_i) - ϕ(D_{i-1})) \\ = \sum_{i=1}^n c_i + ϕ(D_n) - ϕ(D_{0})$

Za predpokladu ze $ϕ(D_n) \geq ϕ(D_0)$ platí:
* $\sum_{i=1}^n \hat c_i \geq \sum_{i=1}^n c_i$
Tj. součet amortizovaných cen operací je horním odhadem pro složitost celé posloupnosti operací.
:::

> [color=#7D2FAA] **Príklad:** **Zásobník**

| **operace** |**složitost** | **kredity** |
| ----------------- |:----------------------- |:----------------------- |
| PUSH | 1 | $\hat c_i = 1+(\vert S \vert +1)-\vert S \vert =2$ |
| POP | 1 | $\hat c_i = 1+\vert S \vert -( \vert S \vert +1)=0$ |
| MULTIPOP | $min(k,\vert S \vert )$ |  |

> [color=#7D2FAA]
>* Pre všetky $1 \leq i \leq n$ platí $ϕ(D_n) \geq ϕ(D_0)$
>* Zložitosť postupnosti $n$ operácií je $\sum_{i=1}^n c_i \leq \sum_{i=1}^n \hat c_i \leq 2n$
> > * Celá posloupnost n operací je $\leq$ součet amortizovaných cen.
> >* Součet amortizovaných cen je $\leq 2n$
---
## Vyhledávání řetězců
:::info
**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
:::

:::success
Je daný text $T$ a vzorka (alebo pattern) $P$ - reťazce nad abecedou $\sum$. Úlohou je vyhľadať všetky výskyty vzorky v texte. Text je daný ako pole $T[1..n]$, vzorka ako $P[1..m]$.

Hovoríme, že vzorka $P$ sa vyskytuje v texte T s posunom s ak $0 \leq s \leq n-m$ a $T[s+1..s+m] = P[1..m]$ (t.j. $T[s+j] = P[j], 1 \leq j \leq m$). Číslo s uvedených vlastností sa nazýva platným posunom pre text $T$ a vzorku $P$.

Problém vyhľadania vzorky môžeme formulovať ako úlohu nájsť pre dané $T$ a $P$ všetky platné posuny. Na riešenie tohto problému môžeme použiť rôzne algoritmy, ktoré sa líšia zložitosťou predspracovania textu a samotného vyhľadávania:
:::

> [color=#449750] Zložitosti bežných algoritmov
> \* *Očekávaná složitost je výrazně lepší.*

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

### **Naivní algoritmus pro hledání řetězců**

:::info
Ide o naivné vyhľadávanie: vzorku $P$ postupne „prikladáme“ (posúvame o jedno miesto doprava v texte) k textu $T$ a porovnávame jednotlivé písmená až kým sa vzorka už nedá posunúť (jej prvé písmeno je na pozícii $n-m$ v texte).
:::

**Zložitosť:** cyklus sa vykoná $n-m+1$ krát, v každom cykle sa vykoná m porovnaní. Spolu teda $\mathcal{O}((n-m+1)m)$. Iba v najhoršom prípade (vzorka a príslušná časť textu sa líšia len v poslednom písmene) sa vykoná m porovnaní (v najlepšom prípade len 1 porovnanie).

### **Karp-Rabin**
Karp-Rabinov algoritmus využíva naivné vyhľadávanie, ale zameriava sa na zrýchlenie porovnávania vzorky s časťou textu (časť algoritmu $P[1..m] = T[s+1..s+m]$), používa na to hašovaciu funkciu.


:::success
* Ř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: $\Theta(m)$**
1. Vypočteme haš hledaného řetězce.
2. Vypočteme haš prvního podřetězce.

**Výpočet: $\mathcal{O}((n-m+1)m)$**
1. 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.)
2. Posuneme se o jednu pozici v prohledávaném textu a přepočteme haš (v konstantním čase).
3. Porovnáváme a posouváme se dokud jsme nedosáhli (m-1)-té pozice od konce. Poté vrátíme všechny nalezené pozice.

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

Predpokladajme, že $\Sigma = \{0,1,...,9\}$. Každý reťazec nad abecedou $\Sigma$ môžeme chápať ako číslo zapísané v desiatkovej sústave. Označme $p$ číslo zodpovedajúce reťazcu $P[1..n]$ a $ts$ čísla zodpovedajúce reťazcom $T[s+1..s+m]$. Problém overiť, či s je platným posunom sa redukuje na problém overiť, či $ts = p$.

Najskôr si predspracujeme vzorku (vypočítame jej hash), v našom prípade pomocou Hornerovej schémy (ak a=1, b=2, c=3, cast textu 'ab' = 12, 'bc' = 23) v čase $\Theta (m)$. Podobne spočítame hash $T[1..m]$ v čase $\Theta (m)$. Trik Karp-Rabinovho algoritmu spočina v tom, že hash ďalšej časti textu ($T[2..m+1]$ atď.) môžeme vypočítať z predchádazjúceho hasha v konštantnom čase. Zvyšné hashe ($t_1..t_{n-m}$) teda spočítame v čase $\Theta (n-m).$

Ak sú čísla $p,ts$ príliš veľké, používa sa výpočet modulo $q$, kde typicky $q$ je prvočíslo také, že $10q ≈$ počítačové slovo. Test $ts = p$ sa nahradí testom $t_s \equiv\ p\ (mod\ q)$. Číslo $s$, pre ktoré platí uvedená rovnosť je len potenciálnym posunom, jeho platnosť sa musí overiť porovnaním príslušných reťazcov.

Zložitosť predspracovania je $\Theta (m)$, zložitosť výpočtu v najhoršom prípade (t.j ak pre všetky s platí skúmaná rovnosť) je $O((n-m+1)m)$. Zložitosť konkrétneho výpočtu je daná počtom platných posunov. Ak očakávaný počet platných posunov je $c$, tak očakávaná zložitosť algoritmu je v $\mathcal{O}((n-m+1)+cm)$.

Algoritmus Karp-Rabin je vhodné použiť, ak v texte hľadáme celé vety (neočakávame, že výskytov bude veľa), v tom prípade algoritmus dosahuje priemernú zložitosť $\mathcal {O}(n)$. V prípade hľadania krátkych slov, ktorých je v texte veľa alebo použitia nevhodnej hashovacej funkcie je zložitosť podobná ako pri použití naivného vyhľadávania.

### Algoritmus založený na konečných automatoch
Pre danú vzorku $P[1..m]$ skonštruujeme konečný automat $A=(\{0,...,m\},\Sigma,\delta,\{0\},\{m\})$. Následne text $T[1..n]$ spracujeme automatom $A$.


Zložitosť spracovania textu je $\Theta (n)$, musíme ale ešte skonštruovať konečný automat $A$ (jeho prechodovú funkciu).

Nech $P_q = P[1]..P[q]$ a $T_q = T[1]..T[q]$. Definujeme sufixovú funkciu $\sigma : \Sigma^* \rightarrow \{0,1,...,m\}$, kde $\sigma(x)$ je dĺžka najdlhšieho prefixu vzorky $P$, ktorý je sufixom slova $x$.

Napr. pre $P = popapopa$ je $\sigma (\epsilon) = 0$, $\sigma (papap) = 1$, $\sigma (papop) = 3$, $\sigma (popapo) = 6$.

Konečný automat pre $P$ je $A=(\{0,...,m\},\Sigma,\delta,\{0\},\{m\})$, kde prechodová funkcia $\delta$ je definovaná predpisom:
$\delta(q,a) = \sigma(P_{q}a)$ Prechodovú funkciu $\delta$ konštruujeme podľa nasledovného algoritmu:


Zložitosť konštrukcie automatu je $\mathcal {O}(m^3 |\Sigma |)$ (riadok 2 $m$-krát, riadok 3 $|Σ|$-krát a riadok 5 v najhoršom prípade $m2$-krát). Existuje efektívnejšia procedúra zložitosti $\mathcal {O}(m|\Sigma |)$.
Zložitosť predspracovania je teda v $\mathcal {O}(m|\Sigma |)$ a zložitosť vyhľadávania pomocou konečných automatov v $\Theta (n)$.

Príkladom automatu, ktorý v texte rozoznáva reťazce abaa je konečný automat v otázke Konečné automaty, ktorý si jemne upravíme:
$\delta(q_{abaa},a) = q_{a}$
$\delta(q_{abaa},b) = q_{ab}$

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

---

## Algoritmus Knuth-Morris-Pratt
:::success
* 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.
* $\mathcal{O}(m)$
* 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
* $\mathcal{O}(n)$
:::