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

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

ZS 2013/2014

TIN085 - 2/1 Z, Zk

Čas konání: Středa 9:00, první přednáška 9. října
Místo konání: S7 - Malá Strana

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován teorii informace a jejímu použití v komunikační složitosti. Soustředíme se na nové partie související s tzv. information cost protokolů a jejímu použití v důkazech dolních odhadů.

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

• Informace, entropie, vzájemná informace
• Relativní informace a její vlastnosti
• Komprese dat - Shannon-Fanův kód, Huffmanův kód
• Kolmogorovská složitost, Kolmogorovská informace, symetrie Kolmogorovské informace
• Model komunikační složitosti
• Information cost - vnitřní a vnější. Privacy
• Dolní odhady
• Direct sum věty
• Komprese protokolů

Literatura:

• Akualizované poznámky k přednášce.
• T.M. Cover, J.A. Thomas, Elements of Information Theory. John Wiley & Sons, 2nd edition, 2006.
• Stručný úvod do Kolmogorovské složitosti.
• Eyal Kushilevitz, Noam Nisan, Communication complexity, Cambridge University Press 1997.

Shrnutí pravděpodobnosti.

Domácí úkoly

1. Do 6.11. 2013. (posunuto kvůli děkanskému dni)
2. Do 27.11. 2012.
3. Do 8.1. 2014.