1. Algoritmy a datové struktury (95%)

tags: algo, `IV003¨

Pokročilé techniky návrhu algoritmů

Dynamické programování

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

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

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

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?

• 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

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

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}\]

Hladové strategie

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}\]

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

Analýza složitosti

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

Asymptotická notace

\(f(n) \in \Theta(g(n))\): \(f\) roste asymptoticky stejně rychle jako \(g\)

\(f(n) \in \mathcal{O}(g(n))\): \(f\) roste asymptoticky rychleji než \(g\)

\(f(n) \in \Omega(g(n))\): \(f\) roste asymptoticky pomaleji než \(g\)

Techniky dokazování složitosti

Příklad:
vygenerování všech permutací n-prvkové posloupnosti; jejich počet je n! a proto i dolní odhad je Ω(n!)

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)

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

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.

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í

• jednu skupinu typicky tvoří operace, které vytváří/přidávají obsah (push), druhou pak operace, které ho odebírají (pop, multipop)

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ů

Príklad: Zásobník

• 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

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

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

Zložitosti bežných algoritmov
* Očekávaná složitost je výrazně lepší.

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

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.

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}\)

Algoritmus Knuth-Morris-Pratt