Kolmogorovská složitost

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

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.

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

Média použitá na této stránce

Mandelpart2 red.png
Closeup of the Mandelbrot set centered at (0.282, -0.01) at magnification 195.3125 times along the Y-Axis using 5000 iterations.