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

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

LS 2012/2013

TIN086 - 2/1 Z, Zk

Čas konání: Pá 13:10, první přednáška se koná až 8. března.
Místo konání: S5

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován tzv. data streamovým algoritmům. Jedná se o relativně nový algoritmický model, při kterém data protékají přes uzel, který je zpracovává. Daný uzel má za úkol o datech spočítat určitou funkci. Při analýze se využívá nejrůznějších prostředků z výpočetní 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

• Count-min sketch (pravděpodobnostní, deterministický), počítaní ||A||_1, ||A||_2
• Počet různých prvků, počet singletonů
• Počítaní trojúhelníků, maximální párovaní
• Testování konzistence prioritní fronty
• Quantiles při nejhorším a při náhodném uspořádání
• TBA

Literatura:

• Muthu Muthukrishnan, Data Streams: Algorithms and Applications, In Foundations and Trends in Theoretical Computer Science, 2005.
• Muthu Muthukrishnan, Data Stream Algorithms, Lecture notes from Annual Workshop on Computational Complexity, 2009.

• N. François and F. Magniez, Streaming complexity of checking priority queues, In Proceedings of 30th Symposium on Theoretical Aspects of Computer Science, 2013.
• N. Shrivastava, C. Buragohain, D. Agrawal, S. Suri, Medians and Beyond: New Aggregation Techniques for Sensor Networks, ACM SenSys '04, pp. 239-249, 2004.
• S. Guha, A. McGregor, Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams, SIAM Journal of Computing, 38 (2009), no. 5, 2044-2059.

Domácí úkoly

1. Do 19.4. 2013.
2. Do 3.5. 2013.
3. Do do zkoušky.