Naslov magistrskega dela: Konvergenca ranga pri dinamičnem programiranju

Povzetek: 

Kljub temu, da je vzporedno programiranje v uporabi že dolgo časa, se številni raziskovalci še vedno ukvarjajo s tematiko vzporednega izvajanja dinamičnega programiranja, saj reševanje optimizacijskih problemov vključuje veliko računanja tudi ob uporabi dinamičnega programiranja in je generičnih rešitev za tovrstne probleme zelo malo. V tem delu obravnavamo vzporedno Rang-1 metodo za probleme dinamičnega programiranja, ki spadajo v razred linearnega tropskega dinamičnega programiranja. Metodo najprej preizkusimo na različnih naključno generiranih vhodnih podatkih, nato pa še na Bellman-Fordovem algoritmu in na algoritmu rezanja šivov. Ugotovimo, da v primeru Bellman-Fordovega algoritma in algoritma rezanja šivov vzporedna Rang-1 metoda ne prinese pohitritve v primerjavi z zaporednim izvajanjem algoritma. V primeru naključno izbranih vhodnih podatkov pa ugotovimo, da je pohitritev reševanja problema odvisna od tega, koliko vhodnih matrik je ranga 1. V primeru, da je vsaj ena matrika ranga 1, algoritem že lahko prinese določene pohitritve. 

Mentor: doc. dr. Boštjan Slivnik

Komisija za zagovor:

izr. prof. dr. Polona Oblak, predsednica

izr. prof. dr. Tomaž Curk, član

doc. dr. Tomaž Dobravec, član

Povezava do video kanala, po katerem se bo prenašal zagovor in ga bo možno spremljati, bo dodana najkasneje na dan zagovora (predvidoma 30 minut pred terminom izvedbe zagovora) na spletni strani: https://ucilnica.fri.uni-lj.si/course/view.php?id=35