Student Računarskog fakulteta Dragomir Božanić je u sredu, 9. jula 2025. godine odbranio diplomski rad na temu Pakovanje krugova: algoritmi i primena pred komisijom koju su činili mentor dr Marko Mladenović i član dr Selena Vukotić.
U uvodu svog rada Dragomir je istakao:
Problemi pakovanja su deo inženjerskih nauka, kao i teoretskih, poput matematike i računarski nauka. Na primer, u matematičkoj estetici kao i u prepoznavanju geometrijskih oblika kod biljaka proučavani su još od početka XX veka, npr. u radu Arnolda Emcha ([1]). Isti autor, u radu o Doule-ovim spiralama u filotaksi1 1910 je prvi postavio problem pakovanja krugova u krug ([2, 3]). Za razliku od problema ranca (eng. knapsack problem, pogledati seminalni rad Karpa [4]), koji je diskretan, problemi pakovanja su kontinualni i geometrijske prirode. Neki od problema pakovanja mogu da glase:
• koliko maksimalno krugova istog prečnika možemo upisati u jedinički krug?
• Koliko maksimalno krugova istog prečnika možemo upisati u pravougaonik?
• Analogno za krugove različitih prečnika, itd.
…
Dakle kao što vidimo Circle Packing ima širok spektar primena od kojih su recimo neki od osnovnih biologija, medicina, IT, agrokultura i još mnogi drugi.
U ovom radu je prikazana razlika u efikasnosti 4 algoritma koji su korišćeni za pronalaženje najmanjeg prečnika kružnog kontejnera za krugove različitih dimenzija. Iako je greedy optimalan u odredjenim uslovima ovde pokazujemo da to nije slučaj. Ali pošto je ovo NP-problem ne postoji garancija da je to optimalno rešenje, već da je to jednostavno rešenje koje smo dobili. – zaključio je Dragomir.
Fotografije sa odbarne dostupne su u galeriji.