A blog az Emberi Erőforrások Minisztériuma UNKP-17-3 kódszámú Új Nemzeti Kiválóság Programjának támogatásával készült

Minimum Stack

A gyakorlaton láttuk, hogyan lehet egy minimum lekérdezését támogató vermet megalkotni. Ez egy olyan megoldás volt, ahol plusz $O(n)$ tárat használtunk fel. A továbbiakban megnézzük, hogyan lehet egy teljes plusz verem helyett egyetlen változóval, azaz plusz konstans tárral ugyanezt a logikát megvalósítani.

Lineáris rekurzió

A feladat a következő: Adjuk meg a Fibonacci-sorozat $N.$ elemét $mod~P$, ahol $N\sim 10^9$ és $P\sim 10^6$ prím.

Ha ezt for ciklussal akarnánk megkapni, az $O(N)$ idő, ami sok. Ha $10^9$-dik Fibonacci számot ugyanennyi milliszekundum alatt tudnánk kiszámolni, még az is $11$ napig tartana, ha ugyanennyi másodperc alatt, akkor pedig kb $31$ évig. Ennyit azért nem szeretnénk várni!

Fast Fourier transzformáció

Hol volt, hol nem volt, létezett egy Fourier transzformáció, amit az egyetem számos kurzusán megkíséreltek megtanítani nekem, de én mégsem értettem meg. Felbuzdulva azon, hogy a kedvenc előadóm egy két órás előadást tartott erről az egészen *magic* számba ment dologról, úgy gondoltam, hosszú wikipedia és tankönyv olvasgatás helyett, amiben több a képlet és a matek, mint amit képes egy infós szem felparsolni, végignéztem az előadást. És megtörtént a csoda! Hát ez egy hihetetlenül egyszerű cucc!