2 - Rekurze

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.

• 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)$.

Ř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í (rozbalit)

Ř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í (rozbalit)

Ř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í (rozbalit)

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 vztah popisující složitost algoritmu $\mathcal{A}$?

Řešení (rozbalit)

Ř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 (rozbalit)

Mistrovská věta (rozbalit)

Substituční metoda (rozbalit)

Ú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));
}

Ú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.

1. Seřaď levou polovinu pole (rekurzivním voláním).
2. Seřaď pravou polovinu pole (rekurzivním voláním).
3. 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 $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)$.