ADŠ prednáška 13: Pažravé algoritmy 1 - voľba optimálnej podmnožiny.

Zhrnutie prednášky

Prednáška uvádza koncept pažravých (greedy) algoritmov, ktoré sa snažia dosiahnuť globálne optimum sériou jednoduchých lokálnych rozhodnutí. Na ilustráciu slúži úloha s predpovedaným vývojom ceny Bitcoinu, kde sa ukazuje, že optimálnu stratégiu nákupu a predaja možno určiť len na základe porovnania dvoch po sebe idúcich cien, bez potreby poznať celý budúci vývoj. Výsledný algoritmus je lineárny, jednoducho implementovateľný a doplnený dôkazom správnosti. Následne sa vysvetľuje, prečo sú pažravé algoritmy obľúbené (efektívnosť, jednoduchosť), ale aj to, že pre mnohé problémy pažravý prístup nevedie k optimálnemu riešeniu, preto je dôležité vždy dokazovať jeho korektnosť. Na záver sa zavádza druhá úloha o rozmiestnení domov pozdĺž cesty v dedine, ktorá bude slúžiť ako ďalší príklad na precvičenie pažravého uvažovania.

• - Pažravé algoritmy dosahujú globálne optimum sériou lokálnych rozhodnutí.
• - Príklad: optimálne obchodovanie s Bitcoinom na základe predpovedanej postupnosti cien.
• - Optimálna stratégia: nakupovať keď cena rastie, predávať keď klesá – rozhoduje sa len podľa dvoch susedných cien.
• - Riešenie je lineárne (jeden cyklus cez pole cien) a jednoduché na implementáciu.
• - Výhody pažravých algoritmov: efektívnosť a jednoduchosť implementácie.
• - Riziko: pažravé riešenie nemusí byť pre každý problém optimálne, treba dokazovať jeho korektnosť.
• - Zavedená nová úloha o optimálnom umiestnení/pripojení domov pozdĺž cesty v dedine ako ďalší príklad.

Zhrnutie pripravené s pomocou AI z prepisu videa.