Cvicenie - Vypoctova zlozitost algoritmov 2.12.2020 13:00

Zhrnutie prednášky

Cvičenie nadväzuje na dynamické programovanie a venuje sa metódam backtracking a hladové (pažravé) algoritmy. Backtracking hľadá riešenie prehľadaním všetkých možností, hladový algoritmus si v každom kroku vyberá lokálne najlepšiu možnosť, a preto funguje len tam, kde sa dá dokázať jeho správnosť. Ako príklad slúži investičná úloha: so 300 eurami a známym vývojom ceny zlata na 8 dní treba nájsť stratégiu nákupov a predajov s maximálnym ziskom. Jednorazový nákup a predaj dá 400 eur, viacnásobné obchodovanie v lokálnych minimách a maximách až 437 eur. Hladová stratégia je ťažko použiteľná v praxi, lebo dopredu nevieme, či ide o lokálne minimum alebo maximum. Obe riešenia sa majú naprogramovať a porovnať, pričom hladové je jednoduchšie, keďže stačí cyklus, kým backtracking vyžaduje rekurziu.

• - Backtracking prehľadáva všetky možnosti riešenia a z nich vyberie optimum.
• - Hladový algoritmus vyberá v každom kroku lokálne najlepšiu voľbu a nemusí vždy viesť k optimu.
• - Hladovú stratégiu možno použiť len vtedy, keď sa dá ukázať, že funguje.
• - Investičná úloha: 300 eur, 8 dní, známy vývoj ceny zlata, cieľ je maximálny zisk.
• - Jeden nákup a predaj dáva 400 eur, nákup v lokálnych minimách a predaj v maximách až 437 eur.
• - Hladová stratégia kupuje v lokálnom minime a predáva v lokálnom maxime, no vyžaduje poznať budúci vývoj ceny.
• - Hladové riešenie sa programuje cyklom, backtracking si vyžaduje rekurziu; výsledky sa majú porovnať.

Zhrnutie pripravené s pomocou AI z prepisu videa.