Ming Li and P.M.B. Vitanyi: An Introduction to Kolmogorov Complexity and Its Applications, Springer Verlag 1997, ISBN 0-387-94868-6
odborné články
2-INF-163 Kolmogorovská zložitosť
| Odporúčaný ročník: | 2. |
| Semester: | zimný |
| Rozsah: | P3 |
| Hodnotenie: | 20/80 |
| Počet kreditov: | 4 |
| Vyučujúci: | prednáša doc. RNDr. Dana Pardubská CSc. |
| www stránka: | |
| Predmet je v tomto akademickom roku suspendovaný. | |
Cieľ:
Oboznámiť sa s pojmom a vlastnosťami Kolmogorovskej zložitosti a najmä jej rôznorodými aplikáciami.
Sylabus:
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: