ὅδε οἶκος, ὦ ἑταῖρε, μνημεῖον ἐστιν ζῴων τῶν σοφῶν ἀνδρῶν, καὶ τῶν ἔργων αὐτῶν

Seminar for Mathematical Logic

 

PROGRAM


Plan rada Seminara za logiku za maj 2011.

Seminar za matematicku logiku Matematickog instituta SANU nastavlja rad u zimskom semestru 2009/2010.g. na novoj adresi: Kneza Mihaila 36/III sprat, soba 301f - sala za seminare. Cetvrtkom posle podne, ali od 15:00 sati, odrzavace se predavanja na Seminaru iz verovatnosnih logika pod rukovodstvom Profesora Miodraga Raskovica koji je u decembru 2007. dobio akreditaciju Naucnog veca Instituta. Na taj nacin, ponovo, kao pre vise decenija, postoje dva logicka seminara.



PETAK, 13.05.2011. U 16:15
Predrag Tanovic (Matematicki institut SANU i Matematicki fakultet Univerziteta u Beogradu)
SLUCAJNI GRAFOVI, SLUCAJNE STRUKTURE I FRAISSE-JONSONOVA KONSTRUKCIJA (Random graphs, random structures i Fraisse-Jonson's construction)

Sadrzaj: Pregledno predavanje (A survey lecture based on the book The Strange Logic of Random Graphs by Joel Spencer (Courant Institute, New York University), Springer-Verlag Berlin Heidelberg New York 2001)

Petak, 20.05.2011. U 16:15
Petar Markovic (Departman za matematiku i informatiku Prirodno-matematickog fakulteta Univerziteta u Novom Sadu)
CONSTRAINT SATISFACTION PROBLEM

Fixed template Constraint Satisfaction Problem je problem odlucivanja o postojanju homomorfizma iz konacne ulazne reacijske strukture u fiksiranu konacnu relacijsku strukturu na istom (konacnom) jeziku. Poznata Schaeferova teorema nam daje da je, za sve fiksirane dvoelementne strukture, ovaj problem slozenosti $NP$-kompletne ili u $P$. Ovu osobinu dvoelementnih struktura cemo zvati svojstvom dihotomije. Predstavicemo neke od rezultata dokazanih u poslednjih deset godina koji impliciraju da i troelementne, kao i neke druge male strukture imaju analogno svojstvo dihotomije. Narocito, prikazacemo uopstenje teoreme Bulatova sa troelementnih na visesortne troelementne strukture, kao i izvestaj o progresu po pitanju dihotomije za cetvoroelementne fiksirane strukture. Ovakav pristup sam po sebi izgleda kao zelja da se objavi rad u visoko citiranom casopisu, jer resiti 'prvih nekoliko od alef nula slucajeva' i nije neki progres na problemu opste dihotomije. Medjutim, iskustvo ovog istrazivaca je da su ti 'mali' slucajevi pomogli i ranije da se izoluju teske situacije, da se stvore opsti algoritmi koji ih resavaju, te da su doprineli dokazivanju mnogo opstijih parcijalnih Constraint Satisfaction Problem rezultata.
U pitanju je zajednicki rad sa J. Jovanovic, S. Moconjom i P. Tanovicem.

PETAK, 27.05.2011. U 16:15
Slavko Moconja (Matematicki fakultet Univerziteta u Beogradu)
NP KOMPLETNOST (NP completeness)

Abstract: Na predavanju ce biti definisan pojam $NP$-kompletnosti, predstavljen dokaz Kukove teoreme i data lista nekih $NP$-kompletnih problema.

OBAVESTENJA:

1) Dejan Ilic (Saobracajni fakultet Univerziteta u Beogradu) branice magistarsku tezu pod naslovom: Dimenzija modela neprebrojivo kategoricne teorije (Dimension of model of an uncountably categorical theory) u PETAK, 25. FEBRUARA 2011.G. U 18:00 SATI U SALI 844, V SPRAT, STUDENTSKI TRG 16, MATEMATICKI FAKULTET UNIVERZITETA U BEOGRADU

2) Profesor Predrag Tanovic (Matematicki institut SANU) pocinje u UTORAK, 1. MARTA 2011.G. U 16:15 SATI U SALI 301F, III SPRAT, KNEZA MIHAILA 36, Kurs iz teorije modela (A course in model theory)

Profesor Kosta Dosen drzi u letnjem semestru 2009/2010. skolske godine kurs iz izbornog predmeta FILOZOFIJA MATEMATIKE na cetvrtoj godini studija filozofije na Odeljenju za filozofiju Filozofskog fakulteta Univerziteta u Beogradu, Cika Ljubina 18-20, u sali 308, III sprat(nove zgrade Filozofskog fakulteta) sredom od 18:30, pocevsi od srede 10. februara 2010.g. Uz kurs su predvidjene vezbe petkom od 18:00 sati u sali Srpskog filozofskog drustva (prvi sprat starih prostorija Filozofskog fakulteta), koje drzi Milos Adzic. Kurs je posvecen filozofiji matematike Gotloba Fregea, a vezbe poglavljima iz logike relevantnim za filozofiju matematike.

Ukoliko zelite mesecne programe ovog Seminara u elektronskom obliku, obratite se: vdjordje@mi.sanu.ac.rs. Programi svih seminara Matematickog instituta SANU nalaze se na sajtu: www.mi.sanu.ac.rs



Beograd, 1. marta 2010.g.
Rukovodioci Seminara: Kosta Dosen i Djordje Vukomanovic