2 - Rekurze
Připomenutí teorie
Přednáška 2 v oddíle Přednášky
Rekurzivní funkce je ta, která volá sebe samu (přímo i nepřímo). Jednoduchým příkladem je například Fibonacciho posloupnost \(f(N) = f(N-2) + f(N-1)\). Jejich složitost lze často vyjádřit pomocí vzorce
kde \(a\) je počet rekurzivních zavolání z jednoho průchodu funkce, \(\frac{n}{b}\) je velikost vstupu pro dané podproblémy (vstup \(n\) je rozdělen na \(b\) stejných částí), a \(f(n)\) je složitost jednoho průchodu funkce. Typicky složitost rozdělení dat a složení podvýsledků dohromady.
Složitost rekurzivních funkcí lze počítat různými způsoby.
-
Metodou rekurzivních stromů - rozkreselním stromu volání a sečtením složitosti.
-
Substituční metodou - Odhadem a následým ověřením skrze důkaz indukcí.
-
Mistrovskou větou (Master theorem) - Dosazením do vzorce a výpočtem.
-
pokud \(f(n) \in \mathrm{O}\left(n^{\log_b(a) - \epsilon}\right), \epsilon > 0\), pak \(T(n) \in \Theta \left(n^{\log_b(a)}\right)\),
-
pokud \(f(n) \in \Theta\left(n^{\log_b(a)}\right)\), pak \(T(n) \in \Theta\left(n^{\log_b(a)}\log(n)\right)\),
-
pokud \(f(n) \in \Omega\left(n^{\log_b(a) + \epsilon}\right), \epsilon > 0\), a \(a f\left(\frac{n}{b}\right) \leq c f(n), c < 1\), pak \(T(n) \in \Theta\left(f(n)\right)\).
-
Jupyter notebook
Vybrané úlohy jsou připraveny v Jupyter notebooku.
Také na Google Colab.
Řešené úlohy
Úvod
Řešená úloha 1:
Kolikrát bude zavolána funkce xyz() při zavolání rekur(5)?
void rekur(int x) {
if(x < 1) return;
rekur(x-1);
xyz();
rekur(x-2);
}Řešení
Řešená úloha 2:
Charakterizujte slovy, jakou hodnotu vrátí funkce f(x, y) v závislosti na
hodnotách jejích vstupních parametrů.
int f(int x, int y) {
if(x > 0) return f(x - 1, y) + y;
return 0;
}Řešení
Vrátí \(x \cdot y\).
Řešená úloha 3:
Napište rekurzivní funkci, která pro zadané číslo \(N\) vypíše řetězec skládající
se z \(N\) jedniček následovaných \(2N\) dvojkami. Pro dané \(N\) bude funkce volat
sama sebe právě \(N\)-krát. Příklad: pro \(N = 2\) vypíše 112222.
Řešení
def f(N):
if N > 0:
print(1)
f(N - 1)
print(2)
print(2)Řešená úloha 4: Rekurzivní algoritmus \(\mathcal{A}\) dělí úlohu o velikosti \(n\) na 2 stejné části. Každou část musí zpracovat dvakrát. Čas potřebný na rozdělení úlohy na části a na spojení dílčích řešení je úměrný hodnotě \(n\). Jak lze matematicky vyjádřit rekurentní vztah popisující složitost algoritmu \(\mathcal{A}\)?
Řešení
\(T(n) = 4 T\left(\frac{n}{2}\right) + n\)
Počítání složitosti
Řešená úloha 5: Rekurzivní algoritmus \(\mathcal{A}\) pracuje tak, že pro \(n > 1\) data rozdělí na \(4\) části stejné velikosti, zpracuje \(5\) těchto částí (tj. jednu dvakrát), a pak jejich řešení spojí. Na samotné rozdělení problému a spojení řešení menších částí potřebuje dobu úměrnou \(n^2–n\).
Určete asymptotickou složitost pomocí
-
stromu rekurze,
-
Mistrovské věty,
-
a substituční metody.
Strom rekurze
-
V \(i\)-té úrovni je \(5^i\) uzlů, protože v každé úrovni se počet uzlů zvětší \(5\)-krát.
-
V jednom uzlu v hloubce \(i\) proběhne \(\left(\frac{n}{4^i}\right)^2 - \frac{n}{4^i}\) operací, protože v \(i\)-té úrovni jsme problém zmenšili \(4^i\)-krát.
-
Hloubka stromu je \(\log_4(n)\), protože v každé úrovni dělíme problém na čtvrtiny, a \(\frac{n}{4^i} = 1\) pro \(i = \log_4 n\).
-
Nejhlubší úroveň má konstantní složitost v každém uzlu, \(5^{\log_4(n)} = n^{\log_4(5)}\) uzlů. Tedy \(\Theta\left(n^{\log_4(5)}\right)\).
-
Hloubka \(i\) vyžaduje \(5^i \left[ \left(\frac{n}{4^i} \right)^2 - \frac{n}{4^i}\right] = n^2 \left(\frac{5}{16}\right)^i - n \left(\frac{5}{4}\right)^i, 0 \leq i \leq d - 1\) operací.
-
Celkem tedy:
\(\sum_{i=0}^{\log_4 n-1} n^2 \left(\frac{5}{16}\right)^i - n \left(\frac{5}{4}\right)^i = n^2 \sum_{i=0}^{\log_4 n - 1} \left(\frac{5}{16}\right)^{i} - n \sum_{i=0}^{\log_4 n - 1}\left(\frac{5}{4}\right)^{i}\)
-
Což jsou součty 2 geometrických posloupností. Vzorec pro součet prvků geoemetrické posloupnosti je nám známý: \(\sum_{i=0}^{k-1} a_1q^{i} = a_1\frac{q^k - 1}{q - 1}, q \neq 1\).
-
-
Celková složitost je
Mistrovská věta
Ze zadání máme \(T(n) = 5T\left(\frac{n}{4}\right) + (n^2 - n)\), tedy \(a=5\), \(b=4\) a \(f(n) = n^2 - n\). Z hrubého porovnání \(f(n)\) a \(n^{\log_b(a)}\), tedy \(\Theta(n^2)\) a \(n^{\log_4 5}\) odhadneme, že by mohlo jít o 3. možnost.
Existuje takové \(\epsilon > 0\), aby \((n^2-n) \in \Omega\left(n^{\log_4(5) + \epsilon}\right)\)? Pro \(\epsilon = 2 - \log_4(5)\) dostáváme \((n^2 - n) \in \Omega\left(n^2\right)\), což jistě platí, protože \((n^2 - n) \in \Theta(n^2)\).
Existuje takové \(c<1\), aby \(5 \left(\frac{n^2}{16} - \frac{n}{4}\right) \leq c (n^2 - n)\)? Ano, například \(c=5/16\).
Takže \(T(n) \in \Theta(n^2 - n) = \Theta(n^2)\)
Substituční metoda
Chceme ukázat, že \(T(n) \in O(n^2)\), kde \(T(n) = 5T\left(\frac{n}{4}\right) + (n^2 - n)\). Tedy z definice: \(T(n) \leq c n^2\) pro nějaké \(c > 0\) a \(n_0 > 0\).
Přecházíme k indukci:
-
Předpokládáme, že platí \(T\left(\frac{n}{4}\right) \leq c \left(\frac{n}{4}\right)^2\) a chceme ukázat \(T(n) \leq c n^2\)
-
\(T(n) = 5 T\left(\frac{n}{4}\right) + (n^2 - n)\)
-
\(T(n) \leq 5 c\left( \frac{n}{4} \right)^2 + (n^2 - n)\) (z indukčního předpokladu)
-
\(T(n) \leq n^2(\frac{5c}{16} + 1) - n \leq cn^2\) což platí např. pro \(c = 16\).
-
Zbývá najít \(n_0\):
což platí i pro \(n_0 = 1\)
Dokázali jsme \(T(n) \in O(n^2)\). Pro \(T(n) \in \Omega(n^2)\) bychom postupovali obdobně, a z toho že \(T(n) \in O(n^2) \cap \Omega(n^2)\) získáme \(T(n) \in \Theta(n^2)\)
Další úlohy
Úloha 6:
Určete, jakou hodnotu vypíše program po vykonání
příkazu print(rekur(4));
int rekur(int x) {
if (x < 1) return 2;
return (rekur(x-1) + rekur(x-1));
}Co tato funkce počítá?
Úloha 7: Uvažujte podobnou funkci jako ve cvičení 2. Doplňte prázdná místa tak, aby vracela \(x^y\).
int f(int x, int y) {
if(____) return ____;
return ____;
}Úloha 8:
Daná funkce ff je volána takto: ff(a, b);, a i b jsou celá kladná čísla. Napište vztah, který
určí, kolikrát bude volána funkce abc(x), v závislosti na hodnotě parametrů a, b.
void ff(int x, int p) {
if (x > 0) ff(x–p, p);
abc(x);
if (x > 0) ff(x–p, p);
}Úloha 9:
Pomocí rekurzivní funkce vypište pro zadané kladné číslo
N posloupnost čísel:
1 2 … N−2 N−1 N N N−1 N−2 … 2 1
Úloha 10: Rekurzivní algoritmus \(\mathcal{A}\) dělí úlohu o velikosti \(n\) na 3 stejné části a pro zisk výsledku stačí, když zpracuje pouze dvě z nich. Čas potřebný na rozdělení úlohy na části a na spojení dílčích řešení je úměrný hodnotě \(n^2\). Zapište rekurentní vztah pro asymptotickou složitost algoritmu \(\mathcal{A}\).
⭐ Úloha 11: Daný rekurzivní algoritmus pracuje tak, že pro \(n > 1\) data rozdělí na \(3\) části stejné velikosti, zpracuje každou tuto část dvakrát a pak jejich řešení spojí. Na samotné rozdělení problému a spojení řešení menších částí potřebuje dobu úměrnou hodnotě \(n^{1/2} \cdot \log_2(n)\). Jakou má daný algoritmus asymptotickou složitost?
Řešte pomocí Vaší oblíbené metody.
⭐ Úloha 12: Uvažme následující algoritmus pro řazení pole délky n.
-
Seřaď levou polovinu pole (rekurzivním voláním).
-
Seřaď pravou polovinu pole (rekurzivním voláním).
-
Zkombinuj výsledky do seřazeného pole.
Jaká je asyptotická složitost tohoto algoritmu, pokud přepokládáme, že jsme schopni výsledky zkombinovat v \(\Theta(n)\)? A co v případě, že to zkombinování má složitost \(\Theta(n^2)\)?
Úloha 13: Složitost rekurzivního algoritmu je dána rekurencí:
a) \(T(n) = 3 \cdot T(\lfloor n/2 \rfloor) + n\)
b) \(T(n) = T(n/2) + n^2\)
c) \(T(n) = 4 \cdot T(n/2 + 2) + n\)
Použijte metodu stromu rekurze k nalezení vhodného (těsného)
horního asymmptotického odhadu funkce \(T(n)\).
Ověřte výsledek substituční metodou.
⭐ Úloha 14: Složitost rekurzivního algoritmu je dána rekurencí:
a) \(T(n) = T(n−1) + T(n/2) + n\)
b) \(T(n) = T(n−a) + T(a) + cn\), kde \(a \ge 1, c \> 0\)
c) \(T(n) = T(\alpha n) + T((1 − \alpha)n) + cn\), kde \(0 < \alpha < 1, c > 0\).
Použijte metodu stromu rekurze k nalezení vhodného horního odhadu funkce \(T(n)\).
Úloha 15: Pro složitost rekurzivního algoritmu platí T(1) = 1. Pro každé n > 1 je T(n) dána rekurencí:
a) \(T(n) = \sum_{k=1}^{n-1} T(k) + 1\)
b) \(T(n) = \sum_{k=1}^{n-1} T(k) + 7\)
c) \(T(n) = \sum_{k=1}^{n-1} T(k) + n^2\)
d) \(T(n) = 2\sum_{k=1}^{n-1} T(k) + 1\)
Určete řád růstu funkce \(T(n)\).
Úloha 16: Sierpińského koberce
Prvky pole \(P_N\) o velikosti \(3^N \times 3^N\) jsou pouze čísla \(1\) a \(0\). Obrázky níže znázorňují pole \(P_N\) pro několik hodnot \(N\), modrá barva představuje hodnotu \(1\), bílá \(0\). Napište kód, který pro dané \(N\) vytvoří a vyplní pole \(P\) podle daného vzoru.
Úloha 17: Seznamte se s Ackermanovou funkcí.
Zkuste spočítat hodnotu \(A(4, 4)\).
⭐ Úloha 18: Násobení matic
Nechť \(X\) a \(Y\) jsou matice tvaru \(n \times n\), kde n je přirozené číslo. Uvažujme násobení matic \(Z = X \cdot Y\) podle definice pro násobení matic, tedy: \(z_{ij} = \sum_{k=1}^{n} x_{ik} \cdot y_{kj}\).
Jaká je složitost výpočtu podle této definice?
Nyní uvažujme násobení matic pomocí rekurze. Pro jednoduchost předpokládejme, že n je mocninou dvou. Pak můžeme matice násobit po blocích. Představme, si že matice \(X\) a \(Y\) rozdělíme na 4 stejně velké podmatice:
\(X = \begin{bmatrix} A & B \\ C & D \end{bmatrix}\)
\(Y = \begin{bmatrix} E & F \\ G & H \end{bmatrix}\)
Pak můžeme využít vztahu:
\(X \cdot Y = \begin{bmatrix} {AE + BG} & {AF + BH} \\ {CE + DG} & {CF + DH} \end{bmatrix}\).
Jaká je asymptotická složitost takového rekurzivního algoritmu?
Jaká je asymptotická složitost Strassenova algoritmu, pro který platí:
\(X \cdot Y = \begin{bmatrix} {T_5 + T_4 - T_2 + T_6} & {T_1 + T_2} \\ {T_3 + T_4} & {T_1 + T_5 - T_3 - T_7} \end{bmatrix}\),
kde:
\(T_1 = A(F - H)\)
\(T_2 = (A + B)H\)
\(T_3 = (C + D)E\)
\(T_4 = D(G - E)\)
\(T_5 = (A + D)(E + H)\)
\(T_6 = (B - D)(G + H)\)
\(T_7 = (A - C)(E + F)\)?