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

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

ZS 2022/2023

NTIN085 - 2/1 Z, Zk

Čas konání: St. 12:20-13:50
Místo konání: S11, 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

Literatura:

Domácí úkoly

  1. Do 2. 11. 2022.
  2. Do 7. 12. 2022.