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

Zhrnutie prednášky

Prednáška nadväzuje na tému pažravých algoritmov, najprv rozoberá riešenie domácej úlohy o zostavovaní tímu (minimaxová úvaha, kombinácia pažravého a hrubou silou riešeného kroku). Ďalej sa preberajú úlohy, kde záleží na poradí vykonávania krokov, riešené technikou výmeny dvoch susedných prvkov (exchange argument): napĺňanie vody z pumpy do vedierok rôznej veľkosti, poskladanie číslic do najväčšieho možného čísla (s netriviálnym porovnávaním reťazcov typu a+b vs b+a) a optimálne poradie použitia raketových motorov na maximalizáciu prejdenej dráhy. Podrobne sa rieši aj plánovanie jednotkových úloh s termínmi (deadline) a pokutami, kde viacero intuitívnych pažravých kritérií zlyháva a správne riešenie postupuje od najneskoršieho deadline naspäť pomocou haldy (heap) s časovou zložitosťou O(n log n). Na záver sa rieši frakčný batoh (delenie syra podľa pomeru cena/hmotnosť) s dôkazom optimality a diskutuje sa rozdiel oproti nedeliteľnému (0/1) batohu, kde pažravá stratégia podľa hustoty ceny nie je vždy optimálna.

• Riešenie domácej úlohy - minimaxový výber tímu
• Úlohy závislé od poradia - technika výmeny susedných prvkov (exchange argument)
• Napĺňanie vedierok vodou - minimalizácia celkového času čakania
• Skladanie číslic do najväčšieho čísla - porovnávacia funkcia a+b vs b+a
• Optimálne poradie použitia raketových motorov
• Plánovanie úloh s deadline a pokutou pomocou haldy (heap), O(n log n)
• Frakčný batoh (syr) - pažravý výber podľa pomeru cena/hmotnosť
• Nedeliteľný (0/1) batoh - zlyhanie pažravej stratégie a aproximácia

Zhrnutie pripravené s pomocou AI z prepisu videa.