Matematički fakultet Univerziteta u Beogradu

Seminar Katedre za računarstvo i informatiku


Letnji semestar akademske 2017/2018. godine


Četvrtak, 12. 4. 2018. u 18.15h, Studentski Trg 16, sala 718

dr Aleksandar Kartelj
Particionisanje retkih bioloških mreža na k-plex podmreže
prikaz rada

Prikaži apstrakt

U mreži, k-plex predstavlja podskup od n čvorova takav da je je stepen svakog čvora podmreže indukovane tim podskupom čvorova najmanje n-k. Problem k-plex maksimalnog težinskog particionisanja po granama (Max-EkPP) je NP-težak problem koji podrazumava pronalaženje k-plex particionisanja ulazne mreže takvog da je suma težina svih grana u dobijenim indukovanim k-plex podmrežama maksimalna. Rešavanje Max-EkPP ima značajnu ulogu u otkrivanju novih informacija u velikih retkim biološkim mrežama.

U radu je predstavljena metoda promenljivih okolona (engl. variable neighborhood method - VNS) za rešavanje problema Max-EkPP. Eksperimentalna testiranja su izvršena nad realnim metaboličkim mrežama i nad drugim dostupnim test skupovima iz literature. Predložena VNS metoda potvrđuje sva optimalna rešenja dobijena modelom celobrojnog linearnog programiranja. Za sva ostala rešenja iz literature, za koja ne postoji potvrda optimalnosti, VNS ili dostiže najbolje poznato rešenje ili ga poboljšava. VNS je takođe testiran nad test problemima velikih dimenzija koji prethodno nisu razmatrani u literaturi.

Četvrtak, 22. 3. 2018. u 18.15h, Studentski Trg 16, sala 718

prof. dr Filip Marić
Brz formalni dokaz Erdoš-Sekerešove hipoteze za konveksne poligone sa najviše 6 tačaka
prikaz rada

Prikaži apstrakt

Hipoteza koju su formulisali Klajn i Sekereš 1932 (danas poznata pod imenom "Erdoš-Sekerešova hipoteza" ili "Hipoteza sa srećnim krajem") tvrdi za svako m>=3 svaki skup koji sadrži 2m-2+1 tačku u opštem položaju (nikoje tri različite tačke nisu kolinearne) sadrži konveksni m-tougao. Hipoteza je potvrđena za svako m<=6. Slučaj m=6 su nedavno rešili Sekereš i Peters pomoću računarske pretrage koja je konzumirala "više od 3000 GHz časova".

Opisujemo dokaz koji je unapređen u nekoliko smerova. Pomoću promene reprezentacije, razmatranja simetrija i pomoću modernih SAT rešavača, smanjili smo vreme dokaza na oko samo pola sata na običnom ličnom računaru (tj. naš dokaz zahteva samo oko 1 GHz čas). Takođe, formalizovali smo dokaz u dokazivaču Isabelle/HOL, što ga čini mnogo pouzdanijim.

Četvrtak, 8. 3. 2018. u 18.15h, Studentski Trg 16, sala 718

Bojan Vučković
Indukovana bojenja grafova
prikaz rada

Prikaži apstrakt

Bojenje grafova podrazumeva dodelu boja čvorovima, granama, ili čvorovima i granama grafa. Uobičajeni uslov ovakvog bojenja je da se susednim čvorovima, incidentnim granama, odnosno čvorovima i njima incidentnim granama, dodeljuju različite boje. Ovakva bojenja se nazivaju valjanim, i glavno pitanje koje se razmatra je koji je minimalan broja boja potrebnih da bi se takvo bojenje izvelo.

Pored valjanih bojenja, poslednjih decenija postoji značajno interesovanje za indukovana bojenja grafova. To su ne obavezno valjanja bojenja kod kojih se boja čvora izvodi iz boja njemu incidentnih grana. Bojenja se najčešće izvode po sumi ili po skupu, pri čemu se postavlja uslov da svaka dva susedna čvora, ili generalno svaka dva čvora grafa, imaju različite izvedene vrednosti.

Na izlaganju će biti prikazane definicije raznih vrsta indukovanog bojenja grafa, kao i hipoteze po pitanju potrebnog broja boja da bi se izvelo traženo bojenje za proizvoljan graf. Kod mnogih od ovih tipova bojenja postignuti rezultati su još uvek daleko od pretpostavljenih gornjih granica datih u hipotezama, i ostavljaju prostora za unapređivanje.

Četvrtak, 1. 3. 2018. u 18.15h, Studentski Trg 16, sala 706

Društvo za informatiku Srbije i Matematički fakultet u Beogradu
Tribina o razvoju u problemima IT nauke u Srbiji
tribina

Prikaži apstrakt

Društvo za informatiku Srbije u saradnji sa Matematičkim Fakultetom organizuje tribinu o razvoju i problemima IT nauke u Srbiji. Republika Srbija je uočila značaj IT industrije i započela niz akcija podrške ovoj grani privredne delatnosti. Ne želeći da (i) u ovoj oblasti budemo puki izvršioci, namera nam je da pokrenemo akciju koja bi trebalo da rezultuje boljom podrškom države razvoju IT nauke.

Na tribinu su pozvani predstavnici ETF-a, Matematičkog fakulteta i FON-a iz Beograda, Elektronskog fakulteta iz Niša, FTN-a i Matematičkog fakulteta iz Novog Sada, predstavnici Matematičkog instituta SANU, instituta »Mihajlo Pupin«, Ministarstva za prosvetu i nauku, kao i iz IT kompanija i drugih instistucija.

Do sada, diskusije su prijavili:

  • Doc. dr Mladen Nikolić, Matematički fakultet, Univerziteta Beogradu
  • Prof. dr Jelica Protić, ETF, Univerziteta u Beogradu
  • Mirjana Ivanović, Prirodno-matematički fakultet, Univerzitet u Novom Sadu
  • Prof. dr Dejan Simić, FON Univerziteta u Beogradu
  • Prof. dr Ivan Luković, FTN, Univerzitet u Novom Sadu
  • Prof. dr Sanja Vraneš, Institut »Mihailo Pupin«, Beograd
  • Dr Bojan Marinković, Matematički institut SANU, Beograd
Moderator: prof.dr Dragana Bečejski Vujaklija


Raniji sastanci

2017/2018 godina (zimski)
2016/2017 godina (letnji, zimski)
2015/16. godina (letnji, zimski)
2014/15. godina (letnji, zimski)
2013/14. godina (letnji, zimski)
2012/13. godina (letnji, zimski)
2011/12. godina (letnji, zimski)
2010/11. godina (letnji, zimski)
2009/10. godina (letnji, zimski)


Seminar

Seminar Katedre za računarstvo i informatiku vodi poreklo od Seminara za računarstvo i informatiku, osnovanog daleke 1977. godine. Od osnivanja Katedre, 1987. godine, Seminar radi, sa povremenim kraćim prekidima, pod sadašnjim imenom. Seminar je osnovao i prvi rukovodio njime prof. Nedeljko Parezanović. Kasniji rukovodioci Seminara bili su prof. Vojislav Stojković, prof. Gordana Pavlović- Lažetić, doc. Nenad Mitić, prof. Duško Vitas. Na Seminaru se izlažu naučni razultati iz različitih oblasti računarstva, istraživača sa Matematičkog fakulteta kao i gostujućih istraživača iz zemlje i inostranstva.

Sastanci se (uz izuzetke) održavaju svakog drugog četvrtka od 18h u prostorijama Matematičkog fakulteta na Studentskom trgu.


Aktuelni rukovodilac seminara je prof. Miodrag Živković.