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

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

 

LS 2010/2011

 

TIN086 - 2/1 Z, Zk

Čas konání: Pá 12:20.
Místo konání: S6

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován ”klasičtějším“ partiím výpočetní složitosti. Ukázali bychom některé základní, dnes již prakticky klasické výsledky, např. Todovu větu (Polynomiální hierarchie vs. #P), větu Immermana a Szelepcsényiho (NL=coNL), Reingioldovu větu (SL=L), zmínili se o pravděpodobnostních výpočtech a pseudonáhodných generátorech (Nisanův PRG), a dále bychom se věnovali základům komunikační složitosti.

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 1.4. 2011.
  2. Do 22.4. 2011.
  3. Do 20.5. 2011
  4. Do do zkoušky.