A következő kombinatorika szeminárium ideje

helye

Ez a terem az Aradi Vértanúk téri lépcsőházbol nyílik. Az előadás:

A döntési fa talán a legegyszerűbb modell Boole-függvények kiszámítására. A változók értékeinek tesztelésével szertenénk összegyűjteni annyi információt, hogy az f Boole-függvény értékét ismerjük az adott inputon. A kérdések száma a számítás költsége. A modell véletlen változata természetes módon bevezethető. A modell egyszerűsége miatt igen sok tétel igazolható, nagy népszerűségnek örvend.

Gráftulajdonságok véletlen döntési fákkal való kiszámítása egy klasszikus problemakör. Központi sejtése (Karp) mind a mai napig megoldatlan: Nemtriviális, monoton gráftulajdonság véletlen döntesi fa bonyolultsága Omega(v^2) (ahol v a csúcsok szama, azaz a változók n száma \binom{v}{2}). Erről beszélek majd.

A fő cel, hogy ÓDonnell, Saks, Schramm, Servedio: Every decision tree has an influential variable cikkének gondolatmenetébe beletekintsünk.

Minden érdeklődőt szeretettel várunk,

Péter

Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073 projekt, "Telemedicina fókuszú kutatások Orvosi, Matematikai és Informatikai tudományterületeken"