Prezentacia - Vypoctova zlozitost algoritmov 23.11.2020 9:15

Zhrnutie prednášky

Prednáška nadväzuje na dynamické programovanie a metódu rozdeľuj a panuj a predstavuje pažravé (greedy) algoritmy ako ďalšiu metódu vedúcu k efektívnym riešeniam; stručne avizuje aj backtracking, ktorý medzi efektívne metódy nepatrí. Pažravá stratégia je ukázaná na probléme mincovky, kde sa má suma rozmeniť čo najmenším počtom mincí. Výpočtový strom všetkých možností je veľký, no pažravý algoritmus si v každom kroku vyberie najväčšiu použiteľnú mincu a ide priamo po jednej ceste. Pri mincách 10, 20 a 50 a sume 60 tak nájde optimálne riešenie 50 + 10. Protipríklad s nominálmi 1, 3, 4 a sumou 6 však ukazuje, že pažravý výber dá 4 + 1 + 1, hoci optimum je 3 + 3, takže metóda nie vždy vedie k optimálnemu riešeniu.

• - Pažravé algoritmy sú metóda tvorby efektívnych algoritmov popri rozdeľuj a panuj a dynamickom programovaní.
• - Backtracking funguje pre rôzne problémy, ale nepatrí medzi efektívne metódy; problém riešiteľný len ním sa považuje za ťažký.
• - Mincovka je optimalizačná úloha: rozmeniť sumu čo najmenším počtom mincí.
• - Výpočtový strom obsahuje všetky možnosti vrátane tých, ktoré sa líšia iba poradím mincí.
• - Pažravá stratégia v každom kroku vyberie najväčšiu mincu, ktorá sa ešte zmestí do zostávajúcej sumy, a ostatné vetvy zahodí.
• - Pre mince 10, 20, 50 a sumu 60 dáva pažravý algoritmus optimálne riešenie 50 + 10.
• - Pre mince 1, 3, 4 a sumu 6 pažravý algoritmus zlyhá (4+1+1 namiesto 3+3), preto je riskantný a nie vždy správny.

Zhrnutie pripravené s pomocou AI z prepisu videa.