50 godina Seminara računarske nauke i primenjena matematika: Pogled u budućnost II deo – Matematika

U okviru obeležavanja 50 godina Seminara računarske nauke i primenjena matematika organizujemo mini-simpozijum na temu “Pogled u budućnost – Računarstvo”, u okviru koga ćete imati priliku da saznate nešto novo i čujete mnoge aktuelne teme zahvaljujući mladim istraživačima sa FON-a i Matematičkog instituta SANU, koji će predstaviti rezultate svojih istraživanja.

Teme koje će biti obrađene i njihov kratak opis:

Petar Ćirković, Matematički institut SANU
INTERAKCIJA AJKULA I BAKALARA: IMPLIKACIJE KOMERCIJALNOG LOVA NA AJKULE
Biće predložen predator-plen model ajkule i bakalara sa Holing 2 funkcionalnim odgovorom kod kojeg je uključen Alejev efekat u funkciji rasta plena i nelinearna funkcija izlova tipa Mihaelis-Menten kod predatora. Biće izvršena detaljna matematička analiza predloženog modela koja uključuje pozitivnost i ograničenost rešenja, uniformnu perzistenciju, ispitivanje egzistencije i lokalne i globalne stabilnosti položaja ravnoteže. Zatim će biti izvršena opsežna bifurkaciona analiza koja će potvrditi postojanje transkritične, sedlo-čvor, račvaste, Hopfove i Bogdanov-Takens bifurkacije. Biće ispitana bistabilnost i tristabilnost u sistemu i jasno definisane oblasti atrakcije pri svim vrednostima parametara. Teorijski rezultati biće potvrđeni kroz numeričke simulacije. Biće pokazano da predloženi model dopušta razvoj politike izlovljavanja koja sprečava izumiranje populacija.

Predrag Đorđević, Matematički institut SANU
UTICAJ ALIJEVOG EFEKTA NA LESLIE-GOWER PREDATOR-PLEN MODEL SA RASTUĆIM FUNKCIONALNIM ODGOVOROM
Predavanje je posvećeno izučavanju dinamičkih osobina i bifurkacionoj analizi predator-plen modela sa funkcionalnim odgovorom predloženog od strane Kosnera i sa Alijevim efektom u populaciji plena. Funkcionalni odgovor opisuje ponašanje predatora koji traži hranu u linearnoj formaciji i pri kontaktu sa plenom lovi okupljajući se oko stada ili jata plena. Cilj je da se prikaže uticaj kako slabog tako i jakog Alijevog efekta na dinamiku sistema. Matematička analiza se fokusira na stabilnost i koegzistenciju položaja ravnoteže i svih mogućih bifurkacija koje se mogu manifestovati u sistemu. Razmatra se i izumiranje obe populacije. Teorijski rezultati dobijeni bifurkacionom analizom će biti potvrđeni numeričkim simulacijama. Uočeno je postojanje bi-stabilnosti kao i tri-stabilnosti, tako da se posebna pažnja posvećuje oblastima atrakcije u svim slučajevima kada postoje višestruki atraktori.

Dragutin Ostojić, Prirodno-matematički fakultet, Kragujevac
DEKOMPOZICIONI, ITERATIVNI, STOHASTICKI ALGORITAM ZA P||Cmax PROBLEM
Razvijena je efikasan (heuristički) algoritam za rasporedjivanje nezavisnih poslova na identične mašine koji koristi iterativnu stohastičku transformaciju zasnovanu na dekompoziciji (Decomposition-based Iterative Stochastic Transformation, DIST). Razmatrani problem rasporedjvanja poznat je kao $P||C_{max}$ i u literaturi je dokazano da je NP-kompletan. DIST primenjuje analogiju između $P||C_{max}$, problema pakovanja ranca (Knapsack problem) i problema višestrukih suma podskupova (Multiple Subset Sum problem) da bi obezbedio rešenja visokog kvaliteta. DIST se oslanja na strategiju particionisanja i iterativno izvodi nedeterminističke transformacije trenutnog (parcijalnog) rešenja tako da predstavlja stohastički algoritam pretraživanja. Ima ugrađeni mehanizam koji mu omogucuje da garantuje optimalnost datog rešenja i, ako ima dovoljno vremena, DIST uvek može da reši datu instancu do optimalnosti. Dodatno, DIST pokazuje veoma dobre performanse u kratkom vremenu izvršenja, što je demonstrirano eksperimentalnom evaluacijom na popularnim skupovima instanci iz literature.
Ovo je zajednički rad sa Andrijom Urošević (Matematički fakultet), Tatjanom Davidović, Tatjanom Jakšić Krüger (MISANU) i Dušanom Ramljakom (Pen State University).

Robert Doža, Matematički fakultet, Beograd
UOPŠTENA METODA PROMENLJIVIH OKOLINA ZA SPEKTRALNU REKONSTRUKCIJU GRAFA
Karakterizacija grafa na osnovu njegovog spektra je veoma atraktivan istraživački problem koji ima brojne primene. Pokazano je da graf nije nužno jednoznačno određen svojim spektrom u najopštijem slučaju, tj. može postojati nekoliko neizomorfnih grafova koji odgovaraju istom spektru. Svi takvi grafovi se nazivaju kospektralni. Međutim, u većini slučajeva važno je pronaći bar jedan graf čiji je spektar jednak zadatom vektoru. Ovaj problem naziva se Spektralna rekonstrukcija grafa (SRG) i poznat je kao jedan od najtežih problema optimizacije. Mi pristupamo SRG problemu metaheurističkim metodama, a trenutno razvijamo Uopštenu metodu promenljivih okolina (General Variable Neighborhood Search, GVNS). Osnovna ideja je da se iz zadatog vektora (koji predstavlja spektar traženog grafa) izvuče što je moguće više informacija i da se one koriste prilikom konstrukcije polaznog grafa (početnog rešenja) i kasnijih modifikacija analiziranih grafova u cilju pronalaženja konačnog rešenja. Korišćena su tri tipa okolina vezana za premeštanje grana u grafu i dodatne strukture podataka koje omogućavaju efikasno pretraživanje okolina. Predložena GVNS metoda poređena je sa drugim pristupima iz relevantne literature o rekonstrukciji nekih poznatih grafova.
Istražvanje u okviru letnje prakse sprovedeno je u saradnji sa Markom Milenkovićem (PMF, Niš), Predragom Đorđevićem, Tatjanom Davidović (MISANU) i Milicom Anđelić (Kuwait University)

Jovana Rađenović, Rudarsko-geološki fakultet, Beograd
METODA PROMENLJIVIH OKOLINA ZA REŠAVANJE PROBLEMA p-CENTRA SA POUZDANOM MREŽOM
Razmatran je problem p-centra sa pouzdanom mrežom (engl. Reliable p-center facility location problem – RpCFLP). Rešavanje problema podrazumeva inicijalno uspostavlјanje p resursa i alokacije korisnika, kao i naknadnu realokaciju korisnika u skladu sa novonastalim scenarijima koji sadrže informacije o onesposoblјenim resursima i ostalim izmenjenim ulaznim podacima. Za rešavanje posmatranog problema predložena je metaheuristika zasnovana na iterativnoj varijanti osnovne metode promenlјivih okolina (engl. Iterated basic variable neighborhood search – IBVNS). Rezultati testiranja predložene metaheuristike ukazuju na njenu efikasnost u pogledu kvaliteta rešenja i brzine izvršavanja u odnosu na postojeće rezultate iz literature.
Ovo je zajednički rad sa Stefanom Miškovićem (Matematički fakultet) i Oliverom Stančić (Ekonomski fakultet, Kragujevac).

Luka Radanović, Matematički fakultet, Beograd
UOPŠTENA METODA PROMENLJIVIH OKOLINA ZA PROBLEM MAKSIMALNE RAZNOLIKOSTI SA OGRANIČENJIMA KAPACITETA I BUDŽETA
Razmatran je problem alokacije resursa, poznat kao problem maksimalne raznolikosti sa ograničenjima kapaciteta i budžeta, koji uključuje uspostavljanje nekih objekata na takav način da se maksimizira udaljenost između dva najbliža uspostavljena objekta. Broj objekata koje treba uspostaviti nije unapred definisan. Dve matematičke formulacije u obliku mešovitog celobrojnog linearnog programa (MILP) su analizirane i upoređene na podskupu malih test instanci korišćenjem CPLEX komercijalnog solvera. Pored toga, razvili smo uopštenu metodu promenljivih okolina (GVNS) koja koristi kombinatornu formulaciju razmatranog problema. Definisane su tri vrste okolina koje se pretražuju u okviru predložene GVNS metode. Efikasnost predloženog pristupa testirana je na skupu teških primera iz literature i postignuti su bolji rezultati od trenutno najboljeg algoritma koji je zasnovan na osnovnoj VNS metodi.
U okviru letnje prakse na ovom problemu radili su i Ana Mijović, Vladimir Janković (Matematički fakultet), pod mentorstvom Dragana Uroševića, Tatjane Davidović (MISANU) i Rake Jovanovića (Qatar Environment and Energy Research Institute).