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

Zhrnutie prednášky

Prednáška uvádza tému dynamického programovania, pričom najprv vysvetľuje rozdiel medzi matematickým pojmom funkcie (referenčne transparentná, rovnaký výstup pre rovnaký vstup) a funkciou v programovacích jazykoch, ktorá môže závisieť od globálnych premenných, náhodnosti či vstupu. Na príklade naivného rekurzívneho výpočtu Fibonacciho čísel sa demonštruje exponenciálna časová zložitosť spôsobená opakovaným počítaním rovnakých podproblémov. Následne sa zavádza memoizácia (pomocou slovníka aj poľa), ktorá redukuje časovú zložitosť na polynomiálnu, a ukazuje sa aj čisto iteratívna verzia výpočtu zdola nahor. Diskutujú sa aj limity rekurzie v Pythone a stručne sa spomína maticové umocňovanie ako pokročilejší spôsob výpočtu Fibonacciho čísel v logaritmickom čase. Druhá časť prednášky rieši úlohu počítania najkratších ciest v mriežke mesta s prekážkami (len pohyby doprava a dole), kde sa objaví súvislosť s Pascalovým trojuholníkom a odvodí sa rekurentný vzťah pre dynamické programovanie.

• Rozdiel medzi matematickou funkciou a funkciou v programovacom jazyku
• Naivná rekurzia pre Fibonacciho čísla a jej exponenciálna zložitosť
• Memoizácia pomocou slovníka a poľa
• Iteratívne (bottom-up) dynamické programovanie
• Limity hĺbky rekurzie v Pythone
• Maticové umocňovanie ako rýchlejší výpočet Fibonacciho čísel (stručná zmienka)
• Počítanie ciest v mriežke mesta s prekážkami
• Súvislosť s Pascalovým trojuholníkom a odvodenie rekurentného vzťahu

Zhrnutie pripravené s pomocou AI z prepisu videa.