20.500.12556/RUL-136952 Konvergenca ranga pri dinamičnem programiranju Rank convergence in dynamic programming 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. Even though parallel programming has been in use for a long time, many researchers are still dealing with the topic of parallel implementation of dynamic programming, as solving optimization problems involves a lot of computing, even using dynamic programming. In this work, we focus on Rank-1 method for problems of dynamic programming that belong to the linear-tropical dynamic programming class of problems. The method is tested on various randomly generated input data and using the Bellman-Ford algorithm and seam carving algorithm. In case of the Bellman-Ford and seam carving algorithms, the parallel Rank-1 method does not show any improvements, compared to the sequential implementation of those algorithms. In case of randomly selected input data, we see that the speed of solving the problem depends on how many input matrices are of rank 1. In case that at least one matrix has rank 1, the algorithm can already bring some improvements. linearno tropsko dinamično programiranje konvergenca ranga paralelizem tropski polkolobar linear-tropical dynamic programming rank convergence parallelism tropical semiring true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2022-05-26 08:45:00 2022-05-26 08:45:05 2022-09-15 04:14:29 0000-00-00 00:00:00 2022 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 34461 110168579 Grujic_Maja_-_Konvergenca_ranga_pri_dinamicnem_programiranju.pdf Grujic_Maja_-_Konvergenca_ranga_pri_dinamicnem_programiranju.pdf 1 639D4F85AFF8F03B696075A495D3F763 4c40daacf01fca2e28ab6959a89b35508622edab1ec073a2f6827cd6e1f2261f 44805cf3-dcbf-11ec-8aca-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=156774 Fakulteta za računalništvo in informatiko 0 0 0