ADŠ prednáška 17: Dynamické programovanie 1 - funkcie v matematickom zmysle slova, memoizácia.

Zhrnutie prednášky

Prednáška otvára sériu o dynamickom programovaní úvahou o rozdiele medzi funkciou v matematickom a v programátorskom zmysle. Matematická funkcia vráti pre rovnaké vstupy vždy rovnaký výstup, kým programová funkcia môže závisieť aj od globálnych premenných, náhodných čísel, nastavení prostredia (napr. lokalizácie a usporiadania reťazcov), času či vstupu od používateľa. Funkcionálne jazyky sa snažia tieto vplyvy odstrániť, no čisté funkcie možno písať aj v C++. Z vlastnosti, že výsledok sa nemení, plynie pravidlo „nerob dvakrát“: už vypočítanú hodnotu stačí uložiť a znova ju nepočítať. Ako príklad slúži demoscéna, kde sa predpočítavali tabuľky sínusov a kosínusov s lineárnou interpoláciou, čo urýchlilo programy približne desaťnásobne.

• - Matematická funkcia je jednoznačne určená vstupmi, programová funkcia môže závisieť aj od globálnych premenných, náhodných čísel, prostredia, času a vstupu od používateľa.
• - Funkcionálne programovacie jazyky sa snažia tieto vplyvy eliminovať, aby funkcie boli funkciami aj v matematickom zmysle.
• - Čisté funkcie sa dajú písať aj v bežných jazykoch ako C++, ak si na to dáme pozor.
• - Zásada efektívnych algoritmov: nerob zbytočne a nerob dvakrát.
• - Keďže výsledok matematickej funkcie sa nemení, stačí si ho zapamätať a nepočítať ho opakovane.
• - Príklad z demosceny: predpočítaná tabuľka sínusov a kosínusov s krokom 0,1° a lineárna interpolácia urýchlili programy približne desaťnásobne.

Zhrnutie pripravené s pomocou AI z prepisu videa.