Prezentacia - Vypoctova zlozitost algoritmov 16.11.2020 9:15

Zhrnutie prednášky

Prednáška nadväzuje na dynamické programovanie ako odvodeninu metódy rozdeľuj a panuj, ktorá zlyháva pri vzájomne závislých podproblémoch, pretože sa opakujú výpočty. Na príklade kombinačného čísla je ukázaná memoizácia, teda postup zhora nadol s rekurziou a tabuľkou medzivýsledkov, a postup zdola nahor, ktorý rekurziu nahrádza cyklami. Hlavnou témou je problém batoha: z N predmetov so zadanými hmotnosťami a cenami treba vybrať množinu s maximálnou cenou, ktorá sa zmestí do nosnosti batoha. Vyčerpávajúce prehľadávanie všetkých 2^N podmnožín má exponenciálnu zložitosť, preto sa úloha formuluje ako funkcia B(H, J) a rieši sa rekurzívne, pričom sa ukáže, že pri tejto úlohe môže byť postup zhora nadol efektívnejší než zdola nahor.

• - Dynamické programovanie vzniklo vylepšením metódy rozdeľuj a panuj pre vzájomne závislé podproblémy.
• - Memoizácia ukladá už vypočítané medzivýsledky do tabuľky a pri opakovanom volaní ich len načíta.
• - Postup zhora nadol je rekurzívny s memoizáciou, postup zdola nahor používa cykly a začína od najmenších podproblémov.
• - Rekurzia má časové aj pamäťové náklady (zásobník), no zdola nahor nie je vždy výhodnejšie.
• - Problém batoha: z N predmetov s hmotnosťami a cenami vybrať množinu s maximálnou cenou v rámci nosnosti H_max.
• - Úplné prehľadávanie všetkých 2^N podmnožín je exponenciálne a použiteľné len pre malé vstupy.
• - Riešenie sa formuluje matematicky ako funkcia B(H, J) a následne sa prepíše do programu; vzorový príklad s nosnosťou 10 má optimum z predmetov 1 a 3 s cenou 46.

Zhrnutie pripravené s pomocou AI z prepisu videa.