V této úloze nás zajímá sekvence (ne nutně sousedících) prvků v poli, taková, že každý prvek nalevo je menší než každý prvek napravo.

Uvážíme úlohu jako hledání nejdelší podposloupnosti ke které můžeme připojit poslední prvek pole a tak vytvořit kandidáta na nejdelší posloupnost celkově. Když známe rostoucí podposloupnosti všech délek pro zkrácené pole (pole bez posledního prvku) můžeme z nich vybrat nejdelší posloupnost, která končí menším číslem. Připojením našeho prvku vznikne posloupnost o 1 delší, kterou si zapamatujeme, pokud končí nižším číslem než posloupnost stejné délky, pokud takovou už máme uloženou. Toto využití řešení menšího problému je ta “optimal substructure”. Nalezené podposloupnosti budou využity i pro přidávání dalšího prvku, tedy máme “overlapping subproblems”.

Stačí si zapamatovat tyto výsledky a dočasné podposloupnosti a jsme schopni vyřešit úlohu v $\mathrm{O}(n \log n)$, jelikož procházíme $n$ prvků a vždy hledáme nejdelší posloupnost končící menším číslem, což můžeme dělat půlením intervalu.

V této úloze máme několik matic rozdílných rozměrů v daném pořadí které chceme pronásobit. Záleží nám na pořadí provedení jednotlivých násobení - na uzávorkování součinu, které povede k minimu operací. Pro $A \in \mathbb{R}^{r \times m}$ a $B \in \mathbb{R}^{m \times c}$ bude složitost násobení $A B$ rovna $r \cdot m \cdot c$.

Jedno velké násobení $n$ matic si představíme jako $n-1$ možných násobení 2 matic podle toho jak rozdělíme $n$ matic na 2 části jejichž složitost násobení umíme snadno spočítat. Ty 2 části jsou naše “optimal substructure” a to, že mnoho z onich rozdělení využijeme vícekrát ukazuje na “overlapping subproblems”.

Složitost najití optimálního uzávorkování bude $\Theta(n^3)$. Odvození viz přednáška, ale odhad lze udělat z toho, že vyplňujeme polovinu tabulky $n \times n$ a každé číslo dosazujeme hledáním maxima z až $n$ výpočtů.

Řešená úloha 1: Najděte nejdelší rostoucí podposloupnost dané posloupnosti. Použijte metodu dynamického programování, napište tabulku průběžných délek částečných výsledků a tabulku předchůdců

Řešená úloha 2: Rozměry matic $A, B, C, D, E$ jsou po řadě: $2\times 5$, $5 \times 3$, $3 \times 6$, $6 \times 2$, $2 \times 4$. Určete pomocí dynamického programování, jak uzávorkovat součin $A \times B \times C \times D \times E$, aby počet operací násobení dvou čísel během výpočtu celého součinu byl co nejmenší. Kolik to bude operací?

💻 Úloha 3: Naimplementujte řešení hledání nejdelší rostoucí podposloupnosti.

Template kód

Úloha 4: Najděte nejdelší rostoucí podposloupnost dané posloupnosti. Použijte metodu dynamického programování, napište tabulku průběžných délek částečných výsledků a tabulku předchůdců.

Úloha 5: Určete, jak lze využít nebo přizpůsobit metodu hledání nejdelší rostoucí podposloupnosti pro hledání:
a) nejdelší klesající podposloupnosti,
b) nejdelší neklesající podposloupnosti,
c) nejdelší konstantní podposloupnosti,
d) nejdelší alternující posloupnosti. (V alternující posloupnosti $a_1, a_2, \ldots a_n$ platí $(a_k - a_{k-1}) \cdot (a_{k+1} - a_k) < 0$, pro $k = 2, 3, \ldots n-1$)

⚡ Úloha 6: Kolika různými způsoby lze uzávorkovat součin matic? (Různé způsoby závorkování odpovídají různému průběhu výpočtu a obecně různým mezivýsledkům. Závorkování $(X)$ a $((X))$ pokládáme za totožné.)

Co v obecném případě $n$ matic? Zkuste formulujte algoritmus DP který to spočítá pro dané $n$.

Úloha 7:

Určete, pro které hodnoty $n$ je výhodnější vypočítat součin $(A \times B) \times C$ než vypočítat součin $A \times (B \times C)$.

⭐ Úloha 8: Rozměry matic $A, B, C, D, E$ jsou stejné jako v úloze 2 (popořadě $2\times 5$, $5 \times 3$, $3 \times 6$, $6 \times 2$, $2 \times 4$). Z důvodů např. testování HW/SW si přejeme součin uzávorkovat tak, aby počet operací násobení dvou čísel byl co největší.

Rozhodněte, zda lze metodu hledání co nejvýhodnějšího uzávorkování přizpůsobit pro řešení této modifikované úlohy. Jaký bude algoritmus řešení?

⭐ Úloha 9: V dané matici začneme kdekoli v prvním sloupci a dále vždy postupujeme jen ve směru SV, V, JV až kamkoli do posledního sloupce. Cena cesty je součet hodnot navštívených polí. Jaká může být nejmenší?

Co když cena za cestu bude součet absolutních hodnot rozdílů cen sousedních navštívených polí?