STUDENT Seminar

 

PROGRAM

---

Predavanja možete pratiti i online putem MITEAM stranice Studentskog seminara:
https://miteam.mi.sanu.ac.rs/asset/F37EF2gbfK8dWqxpw

---

Plan rada Studentskog seminara za MART 2026.

Petak, 13.03.2026. u 12:15, sala 301f, Kneza Mihaila 36 i On-line
Milkica Savić, Filozofski fakultet Univerziteta u Istočnom Sarajevu
O NEKIM PRIMJENAMA PROBABILISTIČKOG METODA
Probabilistički metod predstavlja jedan od osnovnih alata moderne kombinatorike koji omogućava dokazivanje postojanja različitih kombinatornih struktura bez njihove eksplicitne konstrukcije. U ovom izlaganju najprije ćemo predstaviti osnovnu ideju ovog metoda i neke od njegovih tipičnih tehnika, kao što je linearnost očekivanja. Zatim ćemo kroz nekoliko klasičnih primjera ilustrovati kako se ovaj pristup primjenjuje u raznovrsnim problemima diskretne matematike. Na kraju ćemo se detaljnije zadržati na problemu skupova slobodnih za sume i prikazati probabilistički dokaz da svaki skup od n nenultih realnih brojeva sadrži podskup slobodan za sume kardinalnosti veće od n/3. Ovaj primjer je značajan jer pokazuje da opšta ideja probabilističkog metoda prirodno vodi ka problemima aditivne kombinatorike.

---

Petak, 27.03.2026. u 12:15, sala 301f, Kneza Mihaila 36 i On-line
Vladimir Branković, University of Warwick
ŠIRINA STABLA - TREEWIDTH
Robertson i Sejmor su osamdesetih i devedesetih godina prošlog veka razvijali dokaz Teoreme o minoru grafa – svaki beskonačni niz konačnih grafova čini dobar-kvazi-poredak nad operacijom minora. Jedna od najvažnijih tehnika koje su proizišle kao rezultat jeste stablo dekompozicije i karakteristika grafa poznata kao širina stabla (treewidth) – koja nam govori koliko graf liči na stablo. Pojam je prvobitno uveo Halin 1976, a nezavisno ponovo otkrili dvojica pomenutih, da bi ubrzo bilo primećeno da često NP-teški problemi mogu biti rešeni u polinomijalnom vremenu za klase grafova ograničene širine stabla. Najpoznatiji rezultat je Kurselova teorama – za svaki problem koji može biti predstavljen u monadnoj logici drugog reda, postoji linearan algoritam parametrizovan širinom stabla. Na predavanju ćemo proći kroz osnovne definicije ove tehnike, ekvivalentne reprezentacije (k-parcijalna stabla, klika-suma grafovi), malo se dotaći Teoreme o minoru grafa i prikazati parametrizovan algoritam za maksimalni nezavisan skup.

---

Predavanja su namenjena širokom krugu slušalaca. Održavaju se petkom sa početkom u 12:00 sati u sali 301f na trećem spratu zgrade Matematičkog instituta SANU, Knez Mihailova 36.

---