Računarski fakultet može se pohvaliti još jednim doktorom nauka. Doktorand Dalibor Ristić je 27. oktobra 2023. godine odbranio svoju doktorsku disertaciju pod nazivom Implementacija metoda promenljivih okolina za rešavanje P-sledeći problema nad skupom čvorova grafa, pred tročlanom komisijom koju su činili predsednik dr Dragan Urošević i članovi dr Filip Marić i dr Milanka Gardašević Filipović.
Predsednik komisije dr Dragan Urošević predstavio je prisutnima kandidata nakon čega je Dalibor Ristić počeo izlaganje.
U sažetku svog rada Dalibor je istakao sledeće:
Problem p-centra je već dugo predmet interesovanja operacionih istraživanja. Poznat je još od sredine prošlog veka i predstavlja identifikaciju lokacija za postavljanje p centara, kao i njihovu dodelu korisnicima, na takav način da je maksimalna udaljenost korisnika od dodeljenog centra minimizovana. Postoji mnogo, kako egzaktnih matematičkih modela, tako i heurističkih algoritama koji uspešno rešavaju problem p-centra.
Međutim, vremenom se postavilo pitanje šta u slučaju otkaza dodeljenog centra. U poslednjoj dekadi, kao potencijalni odgovor na ovo pitanje, predstavljeno je proširenje problema p-centra poznato kao problem p- sledećeg centra. Problem p-sledećeg centra predstavlja identifikaciju lokacija za postavljanje i dodelu p centara, ali na takav način da je minimizovana maksimalna suma rastojanja korisnika do najbližeg centra i rastojanja između tog i njemu najbližeg centra.
Poseban tip, poznat kao problemi nad skupom čvorova grafa, čine problemi optimalne selekcije centara iz skupa čvorova grafa koji predstavljaju sve korisnike i potencijalne centre. Postoji mali broj članaka i algoritama koji se bave problemom otkaza centra i stoga je u disertaciji definisano nekoliko problema i rešenja upravo iz klase problema ograničenih izborom centara iz skupa čvorova grafa. Posmatrani su problemi p-sledećeg, kao i p-drugog centra koji predstavlja identifikaciju p od potencijalnih n centara na takav način da je minimizovana maksimalna suma rastojanja korisnika do najbližeg i drugog najbližeg centra.
Dalibor je na kraju disertacije istakao sledeće:
U disertaciji, zajedno sa predloženim rešenjima, predstavljeno je nekoliko “p-problema” nad skupom čvorova grafa koji kao deo svog rešenja daju odgovor i na eventualni otkaz dodeljenih centara. Prvi takav problem, definisan 2015. godine u radu [1], nazvan je p-sledeći centar problem. Predstavlja identifikaciju p od potencijalno n centara sa ciljem minimizacije maksimalne sume rastojanja korisnika do najbližeg centra i
rastojanja između tog i njemu najbližeg centra, kao zamenskog centra koji preuzima ulogu opsluživanja korisnika u slučaju otkaza primarnog centra. Svi problemi su definisani na osnovu opšteg neusmerenog težinskog grafa čiji čvorovi predstavljaju korisnike i centre, a težine grana rastojanja između njih. Rešenje problema predstavlja promocija tačno p od ukupno n čvorova grafa u tzv. centre koji funkcionalno opslužuju sve korisnike, opet pozicionirane u čvorovima grafa. U osnovi, disertacija se bavi optimizacionim problemima, tako da se centri biraju sa ciljem da odgovarajuća rastojanja među njima, odnosno korisnicima, budu minimalna. Svi posmatrani problemi su NP-teški i stoga su predložena rešenja kao implementacija heurističkih algoritama zasnovanih na generičkom metodu promenljivih okolina.
Čestitamo dr Daliboru Ristiću.
Slike sa odbrane pogledajte u galeriji.