Leírás
Kivonat:
Ebben az áttekintő előadásban azt mutatom be, hogy hogyan lehet sztochasztikus algoritmusokkal jó becsléseket tenni nehéz leszámlálási problémákra. Két alapvető eljárást mutatok be, a rejection samplinget és a Markov lánc Monte Carlo módszert. Beszélek ezen eljárások hatékonyságáról, különös tekintettel a Markov láncok konvergenciasebességéről. Ismertetem, hogy hogyan lehet véletlen mintavételezéssel egy halmaz méretére becslést adni, majd a bemutatott módszereket három klasszikus példán szemléltetem.
Az előadás megértéséhez nem szükségesek bonyolultságelméleti előismeretek. Az előadás anyaga az alábbi cikkekből tevődik össze:
J. von Neumann. Monte Carlo Method, volume 12 of National Bureau of
Standards Applied Mathematics Series, chapter 13. Various techniques
used in connection with random digits, pages 36{38. Washington, D.C.:
U.S. Government Printing Office, 1951.
N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and
E. Teller. Equations of state calculations by fast computing machines.
Journal of Chemical Physics, 21(6):1087--1092, 1953.
M.R. Jerrum, L.G. Valiant, and V.V. Vazirani. Random generation
of combinatorial structures from a uniform distribution. Theoretical
Computer Science, 43(2{3):169--188, 1986.
A. Karzanov and L. Kachiyan. On the conductance of order Markov
chains. Order, 8:7--15, 1991.
M. Dyer. Approximate counting by dynamic programming. In Pro-
ceedings of the 35th Annual ACM Symposium on Theory of Computing
(STOC), pages 693--699, 2003.
Richard M Karp, Michael Luby, and Neal Madras. Monte-Carlo approximation
algorithms for enumeration problems. Journal of Algorithms, 10(3):429–448, 1989.
For Zoom access please contact Miklos Rasonyi (rasonyi.miklos[a]renyi.hu).