====== IN19 Metody konstrukce efektivních algoritmů ======
===== Zadanie ====

(Rozděl a panuj. Dynamické programování. Hladové strategie. Backtracking. Meze použitelnosti i jednotlivých technik. Příklady algoritmů postavených na jednotlivých technikách.)

===== Vypracovanie =====

==== Rozdeľ a panuj ====

Túto techniku je možné ľahko popísať týmito krokmi.

  - Problém rozdeľ na prodproblémy
  - Vyrieš podproblémy
  - Z riešení podproblémov zostav riešenie

<box 95% round blue|Problém 1, Maximálny a minimálny prvok>Problém nájdenia maximálneho a minimálneho prvku postupnosti
S[1..n]. Zložitostné kritérium - počet porovnaní prvkov.
</box>

=== Riešenie ===
<box 95% round red|Algoritmus 1, Naivný algoritmus riešiaci problém maximálneho prvku><code pascal>
Max(S)
1 max ← S[1]
2 for i = 2 to n do
3   if S[i] > max then max ← S[i] fi
4 od
</code></box>

Procedúra Max nájde najväčší prvok, podobne sa nájde medzi ostatnými prvkami najmenší prvok. Časová zložitosť tohto algoritmu je zrejme <color blue>(n - 1)</color>, pokud k tomu přidáme složitost hledání minimálního prvku (n-2) (hľadáme už len medzi n-1 prvkami) máme 2n-3.

  - Pole rozdeľ na 2 rovnaké postupnosti
  - Nájdi minimum a maximum oboch postupností
  - Maximálny prvok postupnosťí je väčší z maximálnych prvkov podpostupností, podobne minimálny

<box 95% round red|Algoritmus 2, Rozdeľ a panuj algoritmus riešiaci problém maximálneho a minimálneho prvku><code pascal>
function Maxmin(x, y) **predpoklad x < y
1  if y = x + 1 then return (max(S[x], S[y]),min(S[x], S[y])) fi
2  if y = x + 2
3    then použitím 3 porovnaní utrieď S[x], S[x + 1], S[y]
4    return (max, min)
5  fi
6  if y > x + 2 then
7    (max1, min1) ← Maxmin(x, ⌊(x + y)/2⌋)
8    (max2, min2) ← Maxmin(⌊(x + y)/2⌋ + 1, y)
9    return (max(max1, max2), min(min1, min2))
10 fi
</code></box>

Ľahko dokážeme, že tento algoritmus je korektný. Jeho časová zložitosť je:
<math> T(n)= \left\{ \begin{array}{ll}
         1 & \mbox{$n = 2$}\\
         3 & \mbox{$n = 3$}\\
         T(\lfloor n/2 \rfloor ) + T(\lceil n/2 \rceil) + 2 &    \mbox{inak} \end{array} \right. 
</math>

Indukciou sa dá ľahko dokázať, že <math>T(n) \le \frac{5}{3}n - 2</math>

Časovú zložitosť máme často určenú rekurzívne. Vtedy sa jej dôkaz často oplatí použiť tzv. Master Theorem.

<box 95% round orange|Def. 1, Master Theorem>Ak <math>T(n) \le a \cdot T(\lceil n/b \rceil) + O(n^d)</math> pre kladné a, b, d, potom:
<math> T(n)= \left\{ \begin{array}{ll}
         O(n^d) &                \mbox{$a < b^d$}\\
         O(n^d \cdot \log n) &   \mbox{$a = b^d$}\\
         O(n^{\log_b a}) &       \mbox{$a > b^d$}\end{array} \right. 
</math>
Zde <math>n</math> je velikost problému, <math>a</math> je počet podproblémů, <math>n/b</math> je délka jednoho podproblému a <math>O(n^d)</math> udává časovou složitost výpočtu mimo rekurzivní volání, vč. samotného rozdělení problému na podproblémy a sestavení konečného řešení z částečných řešení.
</box>

Inými typickými príkladmi použitia Rozdeľ a panuj sú algoritmy mergesort, ... .

==== Dynamické programovanie ====

  - Charakterizuj štruktúru optimálneho riešenia //optimálne riešenie problému v sebe zahrňuje optimálne riešenia podproblémov//
  - Rekurzívne definuj hodnotu optimálneho riešenia
  - Vypočítaj hodnotu optimálneho riešenia zdola nahor
  - Z vypočítaných hodnôt zostav optimálne riešenie

Táto technika je vhodná pre riešenie //optimalizačných problémov//, u ktorých dochádza k prekrývaniu podproblémov.

<box 95% round blue|Problém 2, Najväčšia spoločná podpostupnosť>Nech X = <math>< x_1,x_2, ..., x_n ></math> a Z = <math>< z_1,z_2, ..., z_m ></math> sú postupnosti symbolov. Z je <color blue>podpostupnosťou</color> X práve vtedy, ak existuje rastúca postupnosť indexov <math>i_1, i_2, ..., i_k</math> postupnosti X taká, že pre všetky j = 1, ..., k platí <math>x_{i_j} = z_j</math>.
Pre dané 2 postupnosti symbolov X a Y hovoríme, že Z je ich <color blue>spoločnou podpostupnosťou</color> práve ak Z je podpostupnosťou X aj Y.
<color blue>Problém najdlhšej podpostupnosti</color> je pre dané dve postupnosti X a Y nájsť ich najdlhšiu spoločnú podpostupnosť (NSP).
</box>

=== Štruktúra optimálneho riešenia problému najväčšej podpostupnosti ===
Označenie: pre postupnosť X = <math>< x_1,x_2, ..., x_n ></math> definujeme jej i-ty prefix (pre i=0,...,n) ako <math>X_i = < x_1, ..., x_i ></math>
Nech X = <math>< x_1,x_2, ..., x_n ></math> a Y = <math>< y_1, ..., y_m ></math> sú postupnosti symbolov a nech Z = <math>< z_1, ..., z_k ></math> je ich NSP.
  - Ak x<sub>n</sub> = y<sub>m</sub>, tak z<sub>k</sub> = x<sub>n</sub> = y<sub>n</sub> a Z<sub>k-1</sub> je NSP postupností X<sub>n-1</sub> a Y<sub>m-1</sub>.
  - Ak <math>x_n \neq y_m</math> a <math>z_k \neq x_n</math>, tak Z je NSP postupností X<sub>n-1</sub> a Y. 
  - Ak <math>x_n \neq y_m</math> a <math>z_k \neq y_m</math>, tak Z je NSP postupností X a Y<sub>m-1</sub>. 
 
=== Hodnota optimálneho riešenia ===
Definujme c[i,j] ako dĺžku NSP postupností X<sub>i</sub> a Y<sub>j</sub>. Platí
<math> c[i,j] = \left\{ \begin{array}{ll}
         0 &                               \mbox{ak i = 0 alebo j = 0}\\
         c[i - 1, j - 1] + 1 &             \mbox{ak $i, j > 0$ a $x_i = y_j$}\\
         max(c[i, j - 1], c[i - 1, j]) &   \mbox{ak $i, j > 0$ a $x_i \neq y_j$}\end{array} \right. 
</math>
Poradie výpočtu:
c[1,1],...,c[1,m]
c[2,1],...,c[2,m]
.
.
.
c[n,1],...,c[n,m]

<box 95% round red|Algoritmus 2, Výpočet optimálneho riešenia><code pascal>
NSP(X, Y)
1 for i = 1 to m do c[i, 0] ← 0 od
2 for j = 0 to n do c[0, j] ← 0 od
3 for i = 1 to m do
4   for j = 1 to n do
5     if Xi = Yj then
6       c[i, j] ← c[i − 1, j − 1] + 1
7       b[i, j] ← ♣
8     else if c[i − 1, j] ≥ c[i, j − 1] then
9       c[i, j] ← c[i − 1, j]
10      b[i, j] ← ♠
11    else 
12      c[i, j] ← c[i, j − 1]
13      b[i, j] ← ♥
14    fi fi od od
15 return c, b
</code>
</box>

<box 95% round red|Algoritmus 2, Zostavenie optimálneho riešenia><code pascal>
Print NSP(b, X, i, j)
1 if i = 0 ∨ j = 0 then return fi
2 if b[i, j] = ♣ then 
3   Print NSP(b, X, i − 1, j − 1)
4   print xi
5 else if b[i, j] = ♠ then
6   Print NSP(b, X, i − 1, j)
7 else 
8   Print NSP(b, X, i, j − 1)
9 fi fi
</code>
</box>

Ďalšími príkladmi dynamického programovanie sú algoritmy: Floydov algoritmus, Warshallov algoritmus, Konštrukcia vyváženého vyhľadávacieho stromu, ... .

==== Hladové algoritmy ====
  - Technika je vhodná pre riešenie optimalizačných problémov, ktoré majú optimálnu subštruktúru (Optimálne riešenie problému v sebe obsahuje optimálne riešenie podproblémov).
  - Pre získanie optimálneho riešenie stačí poznať optimálne riešenie jedného z podproblémov. Tento podproblém vyberáme na základe kritéria lokálnej optimality (KLO), t.j. bez znalosti jeho riešenia. 
  - Vo výpočte postupujeme zhora nadol.

Táto technika však nie je použiteľná pre všetky optimalizačné problémy.

<box 95% round blue|Problém 3, Problém pásky>Je daných n súborov dĺžky m<sub>1</sub>,..., m<sub>n</sub> . Súbory sa majú uložiť na pásku. Všetky súbory sa budú z pásky čítať. Prístupový čas k súboru i je rovný súčtu dĺžok súborov uložených pred ním plus jeho dĺžka m<sub>i</sub>. Úlohou je uložiť súbory na pásku v takom poradí, aby sa súčet jednotlivých prístupových časov k súborom minimalizoval.
</box>

Problém má optimálnu štruktúru, pretože ak ako prvý uložíme na pásku súbor i, ostané súbory musíme usporiadať optimálne. 

Hladový algoritmus: KLO = vyber spomedzi ešte neuložených súbor najkratší a ulož ho na pásku (t.j. ulož na pásku súbory od najkratsieho po najdlhší)

Dôkaz, že je takýto algoritmus naozaj korektný je možné nájsť v slajdoch k predmetnu Návrh algoritmů II.

Medzi iné hladové algoritmy patrí Dijsktrov algoritmus, Primov a Kruskallov algoritmus pre najlacnejšie kostry, Huffmanove kódy, ...

==== Bactracking ====

Technika prehľadávania priestoru potencionálnych riešení založená na princípe Rozdeľ a panuj.
  * do priestoru potencionálnych riešení vnesieme stromovú štruktúru, (binárne reťazce, k-arne reťazce, permutácie, kombinácie)
  * stromovú štruktúru prehľadávame do hĺbky
  * prehľadávanie zefektívnime odrezávaním ciest, ktoré dokázateľne nevedú k hľadanému riešeniu  

=== Návrh backtrakovacieho algoritmu ===
  - Voľba spôsobou reprezentácie potencionálnych riešení
  - Generovanie potencionálnych riešení technikou rozdeľ a panuj
  - Testovanie požadovanej vlastnosti
  - Odrezávanie neperspektívnych ciest

<box 95% round blue|Problém 4, Problém tyčí>Daných je n tyčí dĺžky d<sub>1</sub>,...,d<sub>n</sub> a číslo <math>D \in \mathbb{N}</math>. Úlohou je vybrať tyče tak, aby súčet ich dĺžok bol presne //D//.
</box>

=== Rešenie ===
  - Potencionálne riešenia sú všetky spôsoby výberu tyčí. Riešenia budeme reprezentovať ako binárne reťazce, konkrétne pomocou binárneho poľa A[1..n]. A[//i//]=1 ak tyč //i// bola vybraná. Binárne reťazce vytvárajú stromovú štruktúru.
  - Strom prehľadávame do hĺbky: pole A napĺňame zprava
  - Požadovanú vlastnosť testujeme vtedy, ak máme vygenerované celé potenciálne riešenie.
  - Cesty odrezávame, keď dĺžka vybraných tyčí prekročí daný limit. 

Pozn. Tento problém je riešiteľný dynamickým programovaním v O(nD).

<box 95% round red|Algoritmus 3, Algoritmus riešiaci problém n-tyčí><code pascal>
Tyč(m, l)
1  if m = 0 then 
2    if l = 0 then print A fi
3  else 
4    A[m] ← 0
5    Tyč(m − 1, l)
6
7    if dm ≤ l then 
8      A[m] ← 1
9      Tyč(m − 1, l − dm)
10   fi
11 fi
</code></box>

Pri používaní backtrackingu budeme často potrebovať preskúšať všetky permutácie. Tu je algoritmus na ich zistenie.

<box 95% round red|Algoritmus 4, Algoritmus pre získanie všetkých permutácií><code pascal>
procedure Permutácie(m)
1 if m = 1 then kontrola vlastností else Permutácie(m − 1)
2 for i = m − 1 downto 1 do
3   vymeň A[m] a A[i]
4   Permutácie(m − 1)
5   vymeň A[m] a A[i]
6 od fi
</code></box>

===== Predmety =====
  * [[https://is.muni.cz/auth/predmety/predmet.pl?kod=IB108|FI:IB108]] Návrh algoritmů II, prof. RNDr. Ivana Černá, CSc.

===== Použitá literatúra =====
  * prof. RNDr. Ivana Černá, CSc., [[https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|slajdy z přednášok]]
===== Vypracoval =====
  Ľuboš Pecho, 172463, tomorrow@mail.muni.cz, 18.6.2008
~~DISCUSSION~~