Cvicenie - Vypoctova zlozitost algoritmov 9.12.2020 13:00

Zhrnutie prednášky

Cvičenie nadväzuje na predchádzajúcu hodinu, kde bol problém obchodovania so zlatom riešený pomocou backtrackingu generovaním všetkých 2^n kombinácií rozhodnutí (nákup/predaj/nič) a výberom maxima. Hlavnou témou je riešenie toho istého problému pažravým (greedy) algoritmom, ktorý namiesto prehľadávania všetkých možností nakupuje v lokálnych minimách ceny zlata a predáva v lokálnych maximách. Vysvetľuje sa, ako určiť, či je daný deň lokálnym minimom alebo maximom porovnaním hodnoty s predchádzajúcim a nasledujúcim dňom, vrátane okrajových prípadov na začiatku a konci postupnosti. Algoritmus prechádza poľom cien iba raz (jeden cyklus), pričom sa priebežne eviduje aktuálny majetok buď v hotovosti alebo v zlate. Na konci sa overuje, že výsledná hodnota majetku (437,50 €) zodpovedá výsledku získanému predtým backtrackingovým riešením.

• - Nadväzuje sa na úlohu z minulej hodiny riešenú backtrackingom generovaním 2^n možností (n=8 dní)
• - Backtracking overil všetky kombinácie nákup/predaj/nič a našiel maximálny zisk 437,50 €
• - Pažravá stratégia: nakupovať v lokálnom minime ceny, predávať v lokálnom maxime
• - Lokálne minimum/maximum sa určuje porovnaním hodnoty i-teho dňa s predchádzajúcim (i-1) a nasledujúcim (i+1) dňom
• - Okrajové prípady (prvý a posledný deň) sa riešia osobitne, keďže chýba jedna susedná hodnota
• - Algoritmus prechádza poľom cien iba jedenkrát (jeden cyklus) a eviduje majetok buď ako hotovosť alebo zlato
• - Výsledok pažravého algoritmu (437,50 €) sa zhoduje s výsledkom backtrackingu, čím sa overuje správnosť riešenia

Zhrnutie pripravené s pomocou AI z prepisu videa.