Seminar za računarstvo

 Matematički fakultet Univerziteta u Beogradu

Seminar Katedre za računarstvo i informatiku


Letnji semestar akademske 2017/2018. godine


Četvrtak, 14. 6. 2018. u 18.15h, Studentski Trg 16, sala 718

prof. Nikitas N. Karanikolas, Dept. of Informatics and Computer Engineering, University of West Attica
Natural Language Understanding (NLU) versus Natural Language Processing (NLP)
prikaz oblasti

Prikaži apstrakt
In this lecture we define the required steps for Natural Language Understanding. We discuss about te relevant topics which are Phonology, Morphology, Syntax, Semantics, Representation, Disambiguation, Anaphora resolution, Pragmatics and Discourse analysis. Next we discuss about some Natural Language Processing tasks. We provide information about Summarization, text Classification, Computer Assisted Assessment, Sentiment Analysis, Opinion Mining, Subjectivity Analysis, Corpus Building, etc.

Četvrtak, 7. 6. 2018. u 18.15h, Studentski Trg 16, sala 718

dr Stefan Mišković
VNS-LP algoritam za robusnu varijantu dinamičkog lokacijskog problema maksimalnog pokrivanja
prikaz rada

Prikaži apstrakt
U radu je predložena robusna varijanta dinamičkog lokacijskog problema maksimalnog pokrivanja (DMCLP) i uvedena formulacija bazirana na linearnom celobrojnom programiranju. Razvijen je hibridni algoritam za determinističku i robusnu varijantu DMCLP, koji predstavlja hibridizaciju metode promenljivih okolina i tehnike zasnovane na linearnom programiranju. Osnovna ideja hibridnog algoritma je raščlanjavanje polaznog problema na potprobleme i kombinovanje rešenja potproblema, u cilju dobijanja rešenja za polazni problem. Prezentovani su rezultati za determinističku varijantu DMCLP i upoređeni sa ostalim pristupima iz literature i rezultatima CPLEX rešavača. Na osnovu dobijenih rezultata, može se zaključiti da je predloženi hibridni algoritam ostvario bolje rezultate od ostalih pristupa za rešavanje DMCLP. Dodatno, prezentovani su i detaljno analizirani rezultati za robusnu varijantu DMCLP.

Četvrtak, 7. 6. 2018. u 18.15h, Studentski Trg 16, sala 718

dr Sana Stojanović Đurđević
ArgoGeoChecker - program za interaktivno i automatsko dokazivanje teorema
prikaz rada

Prikaži apstrakt

Razlika između neformalnih dokaza (koji se mogu naci u udžbenicima) i formalnih dokaza (koji se mogu proveriti uz pomoć računara) je neminovna. Razvoj interaktivnih i automatskih dokazivača teorema vodi ka tome da dokazi postanu razumljiviji za matematičare, pa čak i za učenike srednjih škola i fakulteta. Razmenjivanje dokaza između različitih dokazivača trenutno nije moguće i još uvek se smatra izazovnim problemom.

U ovom predavanju biće predstavljen način za transformisanje neformalnih geometrijskih dokaza u polu-formalne dokaze koji se mogu automatski proveriti uz pomoć programa ArgoGeoChecker. Takođe, prikazaćemo i nekoliko alata čiji razvoj je vodio do razvitka programa ArgoGeoChecker. Ovakav pristup se može koristiti za formalizovanje i automatsku verifikaciju dokaza teorema u Euklidskoj geometriji. Zasniva se na principima koherentne logike i koristi nekoliko dokazivača za automatsko dokazivanje teorema. Zahvaljujući vernakularu koji je razvijen za koherentnu logiku, u mogućnosti smo da generišemo čitljive dokaze u nekoliko formalnih i prirodnih jezika.

Č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ć.