Vabim vas še na zadnji seminar iz računalništva, ki ga bomo izvedli na FMF. Gre za enodnevni (5h - eno popoldne na FMF + 3h dela na daljavo (VOX + spl. učilnica) seminar na temo DInamično programiranje.
Seminar bomo izvedli v maju, datum pa bomo določili z anketo med tistimi, ki bodo (pred)prijavljeni v Katisu na dan 20. april. Lahko pa se "prijavite" tudi z e-sporočilom na Matija.Lokar@fmf.uni-lj.si.
Zakaj gre pri Dinamičnem programiranju:
Ravnateljica se je odločila. Ni kaj, šolska blagajna je povsem prazna, še za kredo ni več. Oddajali bomo telovadnico! Saj otroci lahko telovadijo tudi v učilnicah in po hodniku. Na oglas se je usulo ponudb. Vsi bi radi telovadnico najeli za določene tedenske termine in za to ponujajo različne vsote ojrov. Posamezno ponudbo lahko opišemo s časom začetka, časom konca in zaslužkom. Kako zaslužiti čim več?
Kapitan Kljuka se je odločil nagraditi svojega zvestega krmarja Enookega. Poklical ga je v kabino, kjer je na mizi v vrsti čakalo 10 mošnjičkov z zlatniki. Na vsakem mošnjičku je pisalo, koliko kovancev je v njem. Enooki lahko pobere kolikor mošnjičkov hoče, le nikoli ne sme vzeti obeh sosednjih. Katere naj pobere, da si bo lahko kupil novo stekleno oko in mu bo ostalo še za rum! Koliko znate "nabrati", če so vrednosti 2, 4, 3, 2, 5, 2, 2, 6, 2, 1, 5, 4, 3, 3, 5? Boste dobili 29? Kaj pa več?
Imamo 480 minut časa in 14 opravil (popravljanje domačih nalog, vpis manjkajočih …). Za vsako opravilo poznamo čas trajanja in pomembnost (faktor za ustrezni steber ;-) ), da ga opravimo. Vsako opravilo, ki ga začnemo, moramo opraviti do konca, sočasno pa znamo delati le eno. Katera opravila izbrati (seveda hočemo dobiti kar se da velik skupni faktor)?
Vse tri (in še številne druge) probleme lahko rešimo s pomočjo tehnike, ki ji pravimo dinamično programiranje. V sklopu seminarja si bomo ogledali nekaj osnovnih idej o dinamičnem programiranju, sklop dodatnih nalog, rešljivih z DP (in seveda začrtali način, s katerim rešimo vse zgornje tri probleme). Ob tem se bomo naučili še, kako lahko ukrotimo "požrešnost rekurzije" ter pokazali nekaj zgledov, ki bodo učence in dijake morda prepričale, da nam gola računska moč računalnika ne pomaga kaj dosti, če v naši glavi ni dovolj znanja...