Kolmogorovská složitost

Kolmogorovská složitost je pojem z oboru teoretické informatiky, přesněji z algoritmické informační teorie. Pro daná data se jí rozumí délka nejstručnějšího počítačového programu (v předem daném programovacím jazyce), který taková data dokáže vygenerovat. Přesná hodnota složitosti různých dat je určena tím, jaký programovací jazyk je zvolen, ovšem volba jazyka má jen omezený vliv.

Příklad: Detail Mandelbrotovy množiny obsahuje statisíce pixelů a tedy po pixelech uložený zabírá statisíce bajtů, ale k jeho vytvoření stačí jednoduchý počítačový program, který zabere o mnoho méně místa

Tento přístup ke složitosti objektů (a tím také ke komprimaci dat) popsal v roce 1963 sovětský matematik Andrej Nikolajevič Kolmogorov, po kterém je koncept pojmenován. Souběžně s ním byli průkopníky této teorie Gregory John Chaitin a Ray Solomonoff.

Externí odkazy

• Obrázky, zvuky či videa k tématu Kolmogorovská složitost na Wikimedia Commons