Konvergenca ranga pri dinamičnem programiranjuGrujić, Maja (Avtor) Slivnik, Boštjan (Mentor) linearno tropsko dinamično programiranjekonvergenca rangaparalelizemtropski polkolobarKljub 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.20222022-05-26 08:45:00Magistrsko delo/naloga136952VisID: 34461COBISS_ID: 110168579sl