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

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

ZS 2017/2018

NTIN085 - 2/1 Z, Zk

Z důvodů děkanského dne se přednáška 8.11. nekoná.

Čas konání: Středa 9:00 (první přednáška 11.10.2017)
Místo konání: S1, Malá Strana

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován expanderům a náhodným procházkám na grafech. 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ů. 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.

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 1.11. 2017.
  2. Do 29.11. 2012.