Adattudomány, hálózatok és modellezés

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.

 

https://www.crcpress.com/Computational-Complexity-of-Counting-and-Sampling/Miklos/p/book/9781138035577

 

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