Tabelace je metoda DP, kdy ukládáme výsledky podproblémů do tabulky (klidně vícedimenzionální). Počítáme standardně rekurzivně, ale před každým zavoláním rekurze se nejprve ujistíme, zda výsledek již není uložen. Před vracením pak uložíme návratovou hodnotu do tabulky.

Pro některé úlohy nad orientovaným acyklickým grafem (Directed Acyclic Graph - DAG) lze využít topologického uspořádání DAGu k vyřešení úlohy za jeden průchod grafem.

Počítáme-li úlohu kterou jsme schopni pro daný uzel vyřešit snadno pokud známe řešení ve všech předcích, stačí úlohu řešit postupně pro uzel za uzlem v topologickém uspořádání.

Řešená úloha 1: Popište jak vypočítat hodnotu rekurzivní funkce $f(6, 7)$ pomocí dynamického programování, když je funkce $f$ rekurzivně definována takto:

a) $f(x, y) = \begin{cases} 0 & \mathrm{pokud} \ x = 0 \lor y = 0 \\ f(x-1, y-1) + f(x-1, y) + f(x, y-1) + 1 & \mathrm{jinak} \end{cases}$

b) $f(x, y) = \begin{cases} 0 & \mathrm{pokud} \ x = 0 \lor y = 0 \\ \max \ f(x-1, y-1), f(x-1, y) + f(x, y-1) + 1 & \mathrm{jinak} \end{cases}$

Řešená úloha 2: Navrhněte způsob jak lze pomocí dynamického programování spočítat kombinační číslo $\binom{n}{k}$.

S jakou asymptotickou složitostí vypočítá navržený algoritmus $\binom{n}{k}$? Napište v závislosti na $n$ a $k$.

Řešená úloha 3: Seřaďte topologicky uzly následujícího grafu.

Jak najdmeme takové topologické uspořádání, jehož vektor vypsaných uzlů bude lexikograficky nejmenší?

Řešená úloha 4: Popište, jak metodou DP určíte počet všech cest délky 3 v neváženém DAG, bez toho, že byste tyto cesty skutečně konstruovali nebo jednotlivě procházeli.

Úloha 5: Jak vypočtete hodnotu rekurzivní funkce f(5, 8,7) pomocí vyplňování hodnot v poli, když funkce j je rekurzivně definována takto

a) $f(x, y, z) = \begin{cases} 0 & \mathrm{pokud} \ x = 0 \lor y = 0 \lor z = 0 \\ f(x-1, y-1, z-1)+ f(x-1, y, z) + f(x, y-1, z) + f(x, y, z-1) + 1 & \mathrm{jinak} \end{cases}$

b) $f(x, y, z) = \begin{cases} 0 & \mathrm{pokud} \ x = 0 \lor y = 0 \lor z = 0 \\ 3 \cdot f(x-1, y-1, z) - f(x, y-1, z) - f(x-1, y, z-1) + 1 & \mathrm{jinak} \end{cases}$

⭐ Úloha 6: Snažíme se určit počet všech binárních vektorů délky N, které mají tu vlastnost, že v nich nikdy nestojí dvě (nebo více) jedničky těsně vedle sebe (vektor 0100100101 je přípustný, vektory 01100, 111 přípustné nejsou). Jak to uděláme pomocí DP?

💻 Rozšíření: Doplňte funkci numberOfValidStringsDP v následujícím Java kódu.

Soubor obsahuje také kód ke cvičení 2

Řešení

Úloha 7: K dispozici jsou tři druhy nákladních vozů: Kontejnerový vůz, výsypný vůz a cisterna. Vozy mohou být za sebou řazeny ve vlaku libovolně s jedinou výjimkou, dvě cisterny nesmí následovat bezprostředně za sebou, musí být mezi nimi alespoň jeden vůz jiného druhu. Kolik různých vlaků s 10 vozy lze sestavit? Označme symboly P(N, C), resp. P(N, K), resp. P(N, V) po řadě počet vlaků s N vozy, jejichž poslední vůz je cisterna, resp. kontejnerový vůz, resp. výsypný vůz.

Bonus: Cisterna smí být zařazena pouze za výsypným vozem, naopak výsypný vůz nesmí být zařazen za cisternou.

⚡ Úloha 8: Ackermannova funkce je definována pro dva celočíselné nezáporné parametry n, m, je tedy možné její hodnoty jednoduše zapisovat do tabulky. Popište, jak budete postupně vyplňovat tabulku, abyste se vyhnuli rekurzivnímu volání. Dokážete určit hodnotu A(4,4)?

$A(n, m) = \begin{cases} m+1 & \mathrm{pokud} \ n = 0 \\ A(n-1, 1) & \mathrm{pokud} \ n \> 0 \land m = 0 \\ A(n-1, A(n, m-1)) & \mathrm{pokud} \ n \> 0 \land m \> 0 \end{cases}$

Řešení

⚡ Úloha 9: Všech 16 navzájem různých binárních vektorů délky 4 tvoří uzly orientovaného grafu G. V grafu existuje hrana z uzlu A do uzlu B právě tehdy když A & B = A, kde operaci & chápeme jako běžný bitový součin, např. 0101 & 0110 = 0100. Určete, jestli G je acyklický a pokud ano, najděte jeho nějaké topologické uspořádání.