Cvicenie - Vypoctova zlozitost algoritmov 25.11.2020 13:00 Part 1

Zhrnutie prednášky

Cvičenie z výpočtovej zložitosti algoritmov nadväzuje na dynamické programovanie a opakuje riešenie problému batoha pomocou rekurzívnej funkcie. Vysvetľuje sa, že rekurzia musí mať triviálny prípad (j = 0) a rekurzívne volania znižujú parameter j, takže vždy skončia. Prístup zhora nadol (memoizácia) ukladá medzivýsledky do pamäte a opakované volania s rovnakými parametrami sa už nepočítajú. Hlavnou novou úlohou je prevoz skupiny ľudí loďkou s danou nosnosťou na najviac dva razy. Ukazuje sa, že ide o variant problému batoha, kde namiesto cien maximalizujeme celkovú hmotnosť v prvej jazde. Podmienka, že súčet hmotností nepresahuje dvojnásobok nosnosti, je nutná, ale nie postačujúca.

• - Dynamické programovanie zhora nadol je rekurzia s ukladaním medzivýsledkov do pamäte.
• - Rekurzia musí mať triviálny prípad a parametre sa pri volaniach k nemu blížia (j sa znižuje o 1 až do 0).
• - Problém batoha: maximalizovať súčet cien predmetov pri obmedzenej nosnosti batoha.
• - Úloha s loďkou: rozhodnúť, či sa ľudia dajú previezť na najviac dva razy, a určiť zloženie jázd.
• - Ak je súčet hmotností väčší ako dvojnásobok nosnosti, prevoz na dva razy nie je možný.
• - Opačne to neplatí: ľudí nemožno deliť, preto môže byť prevoz nemožný aj pri splnenej podmienke (napr. traja ľudia po 90 kg, nosnosť 135 kg).
• - Riešenie je malou úpravou programu pre batoh: ceny odpadajú a maximalizuje sa hmotnosť nastúpených ľudí v prvej jazde, zvyšok musí vojsť do druhej.

Zhrnutie pripravené s pomocou AI z prepisu videa.