STUDENT Seminar

 

PROGRAM

---

Plan rada Studentskog seminara za MART 2024.

Petak, 01.03.2024. u 12:00, sala 301f, Kneza Mihaila 36 i On-line
Momčilo Tošić i Jana Živković, Matematički fakultet Univerziteta u Beogradu
MODELI MAŠINSKOG UČENJA ZA PREDIKCIJU VREMENA REŠAVANJA INSTANCI P||Cmax PROBLEMA
U ovom radu dajemo okvirni predlog modela mašinskog učenja za predikciju vremena rešavanja instanci problema raspoređivanja n nezavisnih zadataka na m identičnih mašina (P||Cmax). Pretpostavljamo da su unapred poznati i fiksirani: problem, algoritam (rešavač) i računar na kojem se izvode eksperimenti. Naš pristup, osim primene metoda mašinskog učenja, sadrži i korake u kojima se konstruišu i biraju ulazne (nezavisne) promenljive koje su (potencijalno) prediktivne za izlaznu (zavisnu, ciljnu) promenljivu. Neprekidne ulazne promenljive se diskretizuju koristeći različite strategije, dok se kategorijalne promenljive transformišu koristeći standardnu tehniku binarizacije. Na taj način dobijamo novi skup binarnih promenljivih kojim proširujemo skup neprekidnih ulaznih promenljivih. Nove promenljive, kojima se opisuju interakcije, konstruišu se međusobnim množenjem promenljivih iz proširenog skupa. U ovom radu se prvenstveno fokusiramo na primenu elementarnih metoda mašinskog učenja za regresiju jer je njihova interpretacija očigledna, te ne otkriva samo prediktivnu moć modela, nego nam omogućuje i analizu uticaja pojedinih ulaznih promenljivih na izlaznu promenljivu. S obzirom da je broj ulaznih promenljivih u proširenom skupu značajno uvećan, koristimo standardne regularizacione tehnike kao što su ridž, laso i elastik net za izbor prediktivnih promenljivih još u fazi učenja.
Ovo je zajednički rad sa Tatjanom Davidović, Slobodanom Jelićem i Tatjanom Jakšić Kruger.

---

Petak, 08.03.2024. u 12:00, sala 301f, Kneza Mihaila 36 i On-line
Vladimir Janković, Ana Mijović i Luka Radanović, Matematički fakultet Univerziteta u Beogradu
METAHEURISTIČKI PRISTUPI 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 celobrojnog linearnog programa (ILP) su analizirane i upoređene na podskupu malih test instanci korišćenjem CPLEX komercijalnog solvera. Pored toga, za rešavanje ovog problema koristili smo i dve metaheurističke metode. Prva je populaciona metaheuristika poznata kao optimizacija kolonijom pčela (BCO), dok druga predstavlja uopštenu metodu promenljivih okolina (GVNS).
Efikasnost obe metode je testirana na skupu teških primera iz literature. Pristup zasnovan na GVNS metodi je postigao bolje rezultate od trenutno najboljeg algoritma koji je zasnovan na osnovnoj VNS metodi.

---

Petak, 15.03.2024. u 12:00, sala 301f, Kneza Mihaila 36 i On-line
Veljko Radić, Matematički fakultet Univerziteta u Beogradu
JEDNA NEJEDNAKOST IZMEĐU INVARIJANTI ČVOROVA
Jedan od osnovnih problema teorije čvorova je detekcija različitih čvorova. Iako generalni odgovor na to pitanje trenutno ne postoji, do delimičnih odgovora se može doći posmatranjem različitih invarijanti čvorova. U ovom predavanju ćemo uvesti tri invarijante - minimalni broj presecanja (crossing number), štapovski broj (stick number) i lučni indeks (arc index). Zatim ćemo dokazati jednu nejednakost između njih koju su korejski matematičari Youngsik Huh i Seungsang Oh dokazali 2011. godine. Zanimljivo je da ta nejednakost vodi poreklo iz takozvane Remzijeve teorije čvorove koja predstavlja spoj klasične kombinatorne Remzijeve teorije sa teorijom čvorova.
U samom početku predavanja ćemo uvesti osnovne pojmove iz teorije čvorova i kratko spomenuti njenu istoriju. Navešćemo i neke od otvorenih problema u oblasti. Poput teorije brojeva, mnogi od njih imaju prilično jednostavnu formulaciju. Međutim, za rešavanje mnogih od njih moguće je da nije neophodno veliko teorijsko znanje, kao što američki matematičar Kolin Adams tvrdi u svojoj knjizi The Knot Book: The Elementary Introduction to The Mathematical Theory of Knots. Usled toga, on smatra da je ova oblast prilično pogodna za istraživački rad mlađih studenata i samu knjigu je napisao kao pomoć pri mentorstvu takvog rada.

---

Petak, 29.03.2024. u 12:00, sala 301f, Kneza Mihaila 36 i On-line
Pavle Martinović, Triniti koledž, Univerzitet u Kembridžu
LAGRANŽIJANI U HIPERGRAFOVIMA
Na ovom predavanju ćemo predstaviti koncept Lagranžijana u hipergrafu. Lagranžijan je veličina koja se može pripisati svakom hipergrafu koji predstavlja maksimalnu vrednost određene analitičke funkcije, i meri (u nekom smislu) koliko su gusto spakovani čvorovi hipergrafa u njegovim granama. Obradićemo kompletnu analizu Lagranžijana u slučaju 2-regularnih hipergrafova (odnosno grafova), uključujući primenu u vidu Mockinovog dokaza Turanove teoreme. Dalje ćemo se pozabaviti većim regularnostima, primarno u svrhu predstavljanja rada Frankla i Rodla u kojima su dali kontraprimer za Erdoševu hipotezu "o skačućim hipergrafovima". Najzad, ako ostane vremena, osvrnućemo se na problem maksimizacije lagranžijana u hipergrafovima sa tačno k grana, kojim su se bavili Tjomkjin, Lecter, Grislis i Morison.

---

Predavanja su namenjena širokom krugu slušalaca. Održavaju se petkom sa početkom u 12:00 sati u sali 301f na trećem spratu zgrade Matematičkog instituta SANU, Knez Mihailova 36.

---