Vybrané kapitoly z výpočetní složitosti I

Michal Koucký
<koucky@math.cas.cz>

ZS 2012/2013

TIN085 - 2/1 Z, Zk

Čas konání: Pátek 13:40-15:40
Místo konání: S4 - Malá Strana

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován náhodným procházkám na grafech. Náhodné procházky na grafech mají fascinující vlastnosti, souvisí s mnoha jinými obory jako například s toky v elektrických sítích a mají nesčetně aplikací: počínaje konstrukcí nejrůznějších algoritmů pro testování souvislosti grafů (paralelně, v malém prostoru...), přes clustering až po PageRank firmy Google.

Přednáška je určena především studentům vyšších ročníků studia a doktorandům. Přednáška předpokládá základní znalosti z výpočetní složitosti, pravděpodobnosti a diskrétní matematiky. Přednášku je možné si zapsat opakovaně.

Plán přednášky

Markovův proces
Stacionární distribuce, konvergence k ní
Užití: self-adjusting fronty
Náhodná procházka na grafu
Očekávaná doba první návštěvy a pokrytí
Užití: Testování souvislosti, hledání pokladů
Krátké náhodné procházky
Náhodné procházky na dynamických grafech
(Elektrický) odpor grafů
Užití: PageRank, individuální PageRank, clustering

Literatura:

Rozdané poznámky.
James R. Norris. Markov Chains, Cambridge University Press, 1998.
Olle Häggström. Finite Markov Chains and Algorithmic Applications, Cambridge University Press, 2002.
László Lovász. Random Walks on Graphs: A Survey.
David Aldous and James Allen Fill. Reversible Markov Chains and Random Walks on Graphs.
Peter G. Doyle. J. Laurie Snell. Random walks and electric networks.
Greg Barnes and Uriel Feige. Short random walks on graphs. SIAM J. Discrete Math. 9(1): 19-28 (1996).
Satoshi Ikeda, Izumi Kubo, Norihiro Okumoto, and Masafumi Yamashita. Impact of local topological information on random walks on finite graphs. ICALP 2003.
Chen Avin, Michal Koucký, and Zvi Lotker. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). ICALP 2008.
Prasad Tetali. Random Walks and the Effective Resistance of Networks. Journal of Theoretical Probability 4 (1991), 101-109.
Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The Electrical Resistance of a Graph Captures its Commute and Cover Times. Computational Complexity, 6(4): 312-340 (1997).
Reid Andersen, Fan Chung, and Kevin Lang. Using pagerank vectors to locally partition a graph. Internet Math. 4(1):35-64 (2007).

Shrnutí pravděpodobnosti.

Vybrané kapitoly z výpočetní složitosti I

Plán přednášky

Domácí úkoly