Prednáška 3 | Základy algoritmizácie a programovania (2020/2021)

Zhrnutie prednášky

Prednáška najskôr nadväzuje na predchádzajúcu tému efektívnosti algoritmov pomocou príkladu spočítavania ľudí v miestnosti, kde sa ukazuje kompromis medzi rýchlosťou a zložitosťou ošetrenia okrajových prípadov. Hlavnou témou je Fibonacciho postupnosť a jej implementácia pomocou robota Karla, ktorý nemôže používať premenné ani aritmetiku, a preto musí čísla vyjadrovať kopírovaním značiek medzi pozíciami. Na vyriešení problému kopírovania značiek bez pomocných premenných sa demonštruje princíp rekurzie – funkcia definovaná prostredníctvom volania samej seba. Vysvetľuje sa dôležitosť ukončovacej podmienky rekurzie, aby nedošlo k nekonečnému volaniu, a súvislosť s pamäťou, keďže každé volanie funkcie zaberá miesto v pamäti až do jej ukončenia. Na konci sa rozoberá, prečo je pri probléme robota Karla rekurzívne riešenie výhodnejšie než iteratívne.

• - Efektívnosť algoritmu spočítavania ľudí rastie so zložitosťou ošetrenia zvyšku (okrajových prípadov)
• - Fibonacciho postupnosť: každé číslo je súčtom dvoch predchádzajúcich, začína 1,1
• - Robot Karel nemôže používať premenné ani aritmetiku, preto Fibonacciho čísla vyjadruje kopírovaním značiek
• - Kopírovanie značky znamená zodvihnúť ju a položiť naspäť aj o pozíciu vpred
• - Rekurzia je definícia funkcie prostredníctvom volania samej seba (copy_beepers)
• - Nutnosť ukončovacej podmienky (if) v rekurzii, inak vzniká nekonečné volanie funkcie
• - Každé volanie funkcie zaberá miesto v pamäti, ktoré sa uvoľní až po jej ukončení, čo pri nekonečnej rekurzii vedie k vyčerpaniu pamäte

Zhrnutie pripravené s pomocou AI z prepisu videa.