|
|
|
|
|
|
|
|
Év szerint | Hónap szerint | Ugrás a hónaphoz | |
|
|
Miklós István (Rényi Intézet): Leszámlálások és mintavételezések bonyolultságelmélete |
|
|
|
|
Csütörtök, 21. Március 2019, 15:00 - 17:00
|
|
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. |
|
Hely : Szeged, Árpád tér 2., 220-as szemináriumi terem |
Vissza
JEvents v3.1.8 Stable
Copyright © 2006-2013
Esemény exportálása 