2-INF-163 Kolmogorovská zložitosť
kedy?
Utorok 14:50 - 17:20 IV
o čom?
Kolmogorovská zložitosť reťazca - definovaná ako dĺžka najkratšieho programu, ktorý ho generuje – poskytuje o.i. aj definíciu pojmu náhodného reťazca. To umožňuje elegantné využitie pri dolných odhadoch na zložitosť problémov z rôznych oblastí.
- Kolmogorovská zložitosť – definícia, základné vlastnosti, nestlačiteľnosť, informačný obsah,...
- Testovanie náhodnosti
- Aplikácie v teórii zložitosti, teórii grafov, broadcastovacích algoritmoch,...
- Varianty Kolmogorovskej zložitosti
literatúra
- Ming Li, Paul Vitanyi: An Introduction to Kolmogorov Complexity and Its Applications. Springer Verlag
- odborné články
- nove slidy po kapitolách (8.1.2014)
priebeh