Algoritmy a dátové štruktúry prednáška 16

Zhrnutie prednášky

Prednáška nadväzuje na dynamické programovanie a najprv dokončuje porovnanie rekurzívneho a iteratívneho prístupu na úlohe počítania ciest v mriežke mesta s prekážkami, pričom sa rozoberá, kedy je výhodnejší iteratívny prístup (hustý priestor stavov, možnosť uvoľňovať nepotrebnú pamäť napríklad na dva riadky) a kedy rekurzia s memoizáciou (riedky priestor stavov, počítajú sa len naozaj potrebné podproblémy). Druhá časť rieši úlohu hľadania najdlhšej rastúcej podpostupnosti v poli čísel. Ukazuje sa, že naivná úvaha „zobrať alebo nezobrať posledný prvok“ narazí na problém, že podproblémy prestávajú byť rovnaké zadanie menšej úlohy, preto sa úloha preformuluje pomocou hodnoty best[i] = dĺžka najdlhšej rastúcej podpostupnosti končiacej na indexe i. Odvodí sa rekurentný vzťah cez všetkých možných predchodcov a implementuje sa iteratívne aj rekurzívne s memoizáciou, obe s časovou zložitosťou O(n²). Prednáška zhŕňa všeobecný postup návrhu dynamického programovania: nájsť rekurentný vzťah medzi väčším a menšími podproblémami, over počet rôznych podproblémov a zvoliť vhodné poradie ich vyhodnocovania.

• Porovnanie rekurzívneho a iteratívneho prístupu k dynamickému programovaniu
• Úspora pamäte pri iteratívnom riešení (napr. len posledné dva riadky tabuľky)
• Hustý vs riedky priestor stavov ako kritérium voľby prístupu
• Úloha najdlhšej rastúcej podpostupnosti (longest increasing subsequence)
• Zlyhanie jednoduchej úvahy "zobrať/nezobrať posledný prvok"
• Preformulovanie úlohy pomocou best[i] - dĺžka končiaca na indexe i
• Rekurentný vzťah cez všetkých možných predchodcov, zložitosť O(n²)
• Všeobecná metodika návrhu riešenia dynamickým programovaním

Zhrnutie pripravené s pomocou AI z prepisu videa.