Dynamické programovanie

Zhrnutie prednášky

Prednáška uvádza dynamické programovanie ako matematickú techniku z polovice 20. storočia od Richarda Bellmana, ktorá sa podrobnejšie preberá v predmete Optimalizácia. Jej podstatou je delenie problému na menšie, sa prelínajúce podproblémy a ukladanie ich medzivýsledkov do jednorozmernej alebo dvojrozmernej tabuľky, z ktorých sa potom spätne skladá optimálne riešenie, ako pri Fibonacciho postupnosti. Technika sa porovnáva s princípom rozdeľuj a panuj. Ako ukážkové úlohy sa spomínajú najdlhšia spoločná vybraná podpostupnosť (LCS), editačná vzdialenosť a problém batohu. Praktická časť začína riešením LCS pre dva reťazce pomocou dvojrozmernej tabuľky, ktorej prvý riadok a stĺpec sa inicializujú nulami.

• - Dynamické programovanie ukladá medzivýsledky podproblémov do tabuľky, aby sa neprepočítavali opakovane.
• - Podmienkou je optimálna podštruktúra a prelínajúce sa podproblémy, ktorých výsledky sa dajú skombinovať do riešenia väčšieho problému.
• - Riešenie sa buduje od najmenších podproblémov smerom hore, podobne ako pri Fibonacciho postupnosti.
• - Metódu sformuloval Richard Bellman v 50. rokoch 20. storočia; hlbšie sa preberá v predmete Optimalizácia.
• - Ukážkové úlohy sú LCS (najdlhšia spoločná podpostupnosť), editačná vzdialenosť a problém batohu.
• - Editačná vzdialenosť hľadá najmenší počet úprav (prepísanie, vymazanie, vloženie) na zmenu jedného reťazca na druhý.
• - LCS sa rieši dvojrozmernou tabuľkou, v ktorej sa riadok a stĺpec pre prázdny reťazec inicializujú nulami.

Zhrnutie pripravené s pomocou AI z prepisu videa.