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 $$T(n) = a T\left(\frac{n}{b}\right) + f(n)$$ 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 konečeně $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.
Ř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á ú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á ú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á ú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 vztah popisující složitost algoritmu $\mathcal{A}$?
Ř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í
Ú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); abc(x); if (x > 0) ff(x–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.
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 $3N \times 3N$ 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í.
\begin{equation*}A(n, m) = \begin{cases} m + 1 & n = 0 \\ A(n-1, 1) & n > 0, m = 0 \\ A(n-1, A(n, m-1)) & n > 0, m > 0 \\ \end{cases} \end{equation*}
Zkuste spočítat hodnotu $A(4, 4)$.