Kolmogorovská složitost

Z Wikipedie, otevřené encyklopedie
Jump to navigation Jump to search
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 nestruč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 k 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.