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