Leírás
SZTE, TTIK, Bolyai Intézet, Kombinatorika szeminárium
Absztrakt. A matematikai objektumok leszámlálása egy természetes matematikai feladat. Megkérdezhetjük, pl., hogy hány d-reguláris gráf létezik n ponton, hány növekvő részpermutáció van egy permutációban, hány olyan n hosszú szekvencia van az {a,b} ABC felett, amelyik nem tartalmazza az aba részstringet, stb. A modern statisztika igényli különböző random matematikai objektumok generálását. Pl. random Latin négyzetek kellenek az experimentális tervezéseknél. Null-hipotézisek háttér eloszlásának empirikus meghatározásához is gyakran random mintavételezésre van szükség. Ismert, hogy a leszámlálásoknak és a mintavételezéseknek gyakran hasonló a számolási bonyolultsága, azaz az az idő, amelyet az a számítógépes program használ, amelyik ezeket a feladatokat végrehajtja.
Az előadás célja az, hogy egy általános áttekintést adjon a leszámlálások és mintavételezések bonyolultságelméletéről. Az előadás olyan egyszerű példákkal fog kezdődni, mint a Fibonacci rekurzió, és folyamatosan halad a bonyolultabb feladatok felé, mint pl. a teljes párosítások planáris gráfokban, hogy a végén a legújabb eredményekhez érkezzen meg, mint pl. a #BIS-teljesség vagy a holografikus redukciók.