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

Zhrnutie prednášky

Prednáška uvádza tému pažravých (greedy) algoritmov na sérii praktických príkladov. Najprv sa rieši úloha obchodovania s bitcoinom, kde sa dokazuje, že lokálne rozhodnutie kupovať pri raste ceny a predávať pri poklese vedie k optimálnemu zisku. Ďalej sa rieši rozmiestnenie autobusových zastávok v dedine pozdĺž cesty tak, aby každý dom mal zastávku do 500 metrov a počet zastávok bol minimálny, s dôkazom typu „nič nepokazíme, keď“. Tretia úloha je výber čo najväčšieho počtu neprekrývajúcich sa prednášok v rozvrhu (interval scheduling), kde sa postupne vyvracajú nesprávne pažravé stratégie a nakoniec sa dokazuje správnosť stratégie „vyber tú, čo najskôr končí“ spolu s efektívnou O(n log n) implementáciou pomocou zoradenia podľa konca intervalu. Na záver sa preberá problém vydávania mincí (najväčšia použiteľná minca), vrátane analýzy, kedy táto pažravá stratégia funguje (deliteľnosť nominálnych hodnôt) a kedy zlyháva na konkrétnom protipríklade.

• Pažravé (greedy) algoritmy - úvod a princíp lokálneho rozhodovania
• Problém obchodovania s bitcoinom - nákup a predaj podľa vývoja ceny
• Rozmiestnenie autobusových zastávok v dedine - pokrytie intervalov
• Dôkazová technika "nič nepokazíme, keď"
• Výber maximálneho počtu neprekrývajúcich sa prednášok (interval scheduling)
• Protipríklady na vyvrátenie nesprávnych pažravých stratégií
• Efektívna implementácia zoradením podľa konca intervalu, O(n log n)
• Problém vydávania mincí a podmienka funkčnosti pažravého algoritmu

Zhrnutie pripravené s pomocou AI z prepisu videa.