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

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

 

ZS 2008/2009

 

TIN085 - 2/1 Z, Zk

Čas konání: Středa 12:20
Místo konání: 3 patro, chodba nad KAMem, 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 a expanderům. Náhodné procházky na grafech mají mnoho aplikací: počínaje konstrukcí nejrůznějších algoritmů pro testování souvislosti grafů (paralelně, v malém prostoru...) a konče PageRankem firmy Google. Expandery jsou grafy s velkou souvislostí, jejichž užití nalezneme jak ve výpočetní složitosti (například při zmenšování chyby pravděpodobnostních algoritmů), tak při konstrukci samoopravných kódů.

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

Literatura:

Shrnutí pravděpodobnosti.

Domácí úkoly

  1. Do 29.10. 2008.
  2. Do 19.11. 2008.
  3. Do 9.1. 2009.