Matematički fakultet Univerziteta u Beogradu

Seminar Katedre za računarstvo i informatiku


Letnji semestar akademske 2016/2017. godine


Četvrtak, 23. 3. 2017. u 18.15h, Studentski Trg 16, sala 716

Julien Narboux, University of Strasbourg
GeoCoq, foundations of geometry formalized in Coq
Zajednički sastanak sa ARGO seminarom

Prikaži apstrakt

In this talk we will give an overview of the GeoCoq library developed by our team in Strasbourg (http://geocoq.github.io/GeoCoq/). GeoCoq library contains a systematic development of geometry from Tarski’s or Hilbert’s axioms. From these axiom systems, we formalized the culminating results of both Tarski, Schwabhäuser, Szmielew, Metamathematische Methoden in der Geometrie and Hilbert, Foundations of Geometry, namely the arithmetization of geometry. This connection between synthetic geometry and algebra, allows us to use algebraic methods for automated deduction in geometry in a synthetic setting. We have also studied the formal proof of the equivalence between 34 versions of the parallel postulates. We work in neutral geometry in an intuitionistic setting and study the impact of different continuity properties on the equivalence proofs. This result in four groups of postulates, which are all equivalent assuming Archimedes’ axiom but distinct, in constructive logic without Archimedes’ axiom.

Finally, I will report our ongoing work toward the formalization of Euclid’s Elements proposition in Coq.


Četvrtak, 16. 3. 2017. u 18.15h, Studentski Trg 16, sala 716

Nina Radojičić
Primena fazi logike za rešavanje NP-teških problema rutiranja vozila i lokacije resursa metodama računarske inteligencije
predlog prijave teme doktorske disertacije

Prikaži apstrakt

Fazi logika predstavlja matematički aparat koji omogućava rad sa raznovrsnim informacijama koje ne mogu precizno da se izraze uz pomoć klasične logike i teorije klasičnih skupova. Podobnost fazi logike za predstavljanje neizvesnih, nepreciznih i nesigurnih informacija, doprinosi njenoj sve široj primeni.

Matematička optimizacija je oblast u preseku računarstva i matematike sa širokim spektrom primene. Klasa problema rutiranja vozila (engl. Vehicle Routing Problems– VRPs), koja predstavlja uopštenje problema trgovačkog putnika, jedna je od poznatijih klasa problema kombinatorne optimizacije. Posebno značajno mesto među često proučavanim problemima matematičke optimizacije imaju lokacijski problemi. Predmet izlaganja biće analiza i rešavanje tri NP-teška problema: problem rutiranja vozila sa ograničenim rizikom (engl. Risk-constrained Cash-in-Transit Vehicle Routing Problem - RCTVRP), problem ravnomernog opterećenja (engl. Load Balancing Problem - LOBA) i problem maksimizacije minimalnog rastojanja (engl. Max-Min Diversity Problem - MMDP).

Metaheuristike predstavljaju generalizovane strategije računarske inteligencije koje se često koriste za rešavanje NP-teških optimizacionih problema. U okviru izlaganja biće prikazana metoda GRASP (engl. Greedy Randomized Adaptive Search Procedure), kao i metoda ponovnog povezivanja puta (engl. Path relinking - PR) za rešavanje problema RCTVRP, LOBA i MMDP. GRASP je metaheuristička metoda koja se sastoji od višestrukog pokretanja lokalne pretrage nad početnim rešenjima dobijenim primenom neke pohlepne heuristike. PR predstavlja način pretraživanja trajektorija (putanja) između dobrih rešenja. Glavna ideja ove metode je pretpostavka da dobra rešenja imaju neke zajedničke karakteristike, tako da se kretanjem po trajektoriji između dva dobra rešenja prolazi kroz rešenja koja su potencijalno bolja.

Fazi logika će biti primenjena u dva različita aspekta: prilikom modeliranja problema i prilikom rešavanja problema metaheuristikama. S obzirom da mnogi problemi iz realnog sveta sadrže različite vrste nepouzdanosti, potreban je matematički, formalan način koji će omogućiti da se precizno kreiraju matematički modeli koji će odgovarati tim problemima. U toku izlaganja biće predloženi novi modeli razmatranih problema koji uz pomoć korišćenja fazi logike bolje opisuju realne situacije. Pored toga, biće predstavljene neke mogućnosti upotrebe fazi logike za poboljšanje performansi predloženih metaheurističkih metoda za rešavanje razmatranih problema.


Četvrtak, 23. 2. 2017. u 18.15h, Studentski Trg 16, sala 716

Bojan Vučković
Neki konstruktivni dokazi u diskretnoj matematici
predlog prijave teme doktorske disertacije

Prikaži apstrakt

Diskretna matematika je oblast matematike koja se bavi proučavanjem matematičkih objekata koji su diskretni, odnosno objekata koji se sastoje od različitih ili nepovezanih elemenata. Za razliku od realnih brojeva objektima diskretne matematike mogu se dodeliti zasebne celobrojne vrednosti. Diskretna matematika se koristi kad god se broje objekti, kada se proučavaju odnosi između konačnih skupova, kao i kada postupak podrazumeva konačan broj koraka za analizu. Glavni razlog porasta značaja diskretne matematike, počev od sredine dvadesetog veka je ta što se često podaci diskretne matematike mogu skladištiti i njima rukovati pomoću računara. Pojmovi i obeležavanje iz diskretne matematike su značajni za proučavanje i opis objekata i problema iz raznih oblasti računarskih nauka, poput kompjuterskih algoritama, programskih jezika, razvoja softvera, kriptografije i automatskog dokazivanja teorema. Među najviše korišćenim matematičkim objektima koji potpadaju pod diskretnu matematiku nalaze se celi brojevi, skupovi, grafovi i matrice. Diskretna matematika se pojavila na univerzitetskim programima početkom 80-ih godina prošlog veka, kao kurs u okviru programa računarskih nauka. Od tada je popularnost ove oblasti znatno porasla, tako da se diskretna matematika, pored mnogih univerziteta, proučava i u određenom broju srednjih škola.

Konstruktivni pristup je veoma čest u rešavanju problema iz diskretne matematike. Među poznatijim primerima je svakako rešenje problema ćetiri boje (Four Color Problem). Ovaj problem, postavljen 1852. godine, tvrdi da je dovoljno četiri ili manje boja da bi se izvelo bojenje regiona bilo koje mape, tako da svaka dva regiona koji dele zajedničku granicu budu obojena različitom bojom. Dokaz koji su Apel (Appel) i Haken (Haken) izveli 1976. godine sastoji se od konstrukcije neizbežnog skupa od 1936 svodljivih konfiguracija. Kao posledica izvodi se zaključak da ne postoji minimalni protivprimer grafa za čije bojenje je potrebno više od četiri boje. U izvođenju dokaza da graf neizbežno sadrži neku od svodljivih kofiguracija neophodna je pomoć raqunara, što dokaz problema četiri boje čini jednim od prvih dokaza potpomognutih računarom (computer-aided proof).

Nešto drugačija veza konstruktivnog pristupa i računara je mogućnost programske implementacije jasno definisanih konstruktivnih algoritama. Na ovaj način se, pored dokaza zadovolivosti određenog svojstva, može efektivno dobiti primer objekta sa traženim svojstvima.

Proučavanje raznih tipova bojenja grafova, poput bojenja čvorova, bojenja grana, totalnog bojenja, i raznih varijacija bojenja grafova. Među njima su valjana bojenja, indukovana bojenja, čvor-razlikujuća, kao i sused-razlikujuća bojenja. Pored hromatske teorije grafova, obrađuju se problemi iz Bulove teorije matrica, kao i Franklova hipoteza iz teorije skupova.

Metode za dobijanje poboljšanja u odnosu na poznate rezultate obuhvataju:

  1. Konstrukcije grafova sa odgovarajućim karakteristikama.
  2. Opis kako rekurzivnih tako i nerekurzivnih algoritama koji obezbe]uju bojenje grafa uz korišćenje minimalnog broja različitih boja.
  3. Dokazivanje ispravnosti algoritama, ;esto korišćenjem matematičke indukcije. Dokazivanje nepostojanja minimalnog protivprimera sa određenim karakteristikama.
  4. Dokazivanje teorema iscrpljivanjem mogućnosti ili analizom slučajeva, bilo uz pomoć računara ili klasičnim pristupom.


Raniji sastanci

2016/2017 godina (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ć.