| |
|
Wenn die Kolmogorov-Komplexität einer Zeichenkette mindestens so groß ist wie die Zeichenkette selber, dann bezeichnet man die Zeichenkette als unkomprimierbar, zufällig oder auch strukturlos. Je näher die Kolmogorov Komplexität an der Länge der Zeichenkette liegt, desto 'zufälliger' ist die Zeichenkette.
Das Prinzip der Kolmogorov-Komplexität wurde unabhängig im Jahre 1964 von R. J. Solomonoff, im Jahre 1965 von A. N. Kolmogorov und 1969 von Gregory Chaitin entwickelt, und hat Bezüge zur Shannonschenschen Informationstheorie.
Die Kolmogorov-Komplexität wird manchmal auch Algorithmische Komplexität oder Beschreibungskomplexität genannt, darf aber nicht mit der Komplexität von Algorithmen verwechselt werden.
| Table of contents |
|
2 Zufall oder Ordnung? 3 Berechnung 4 Anwendungen 5 Literatur 6 Weblinks |
Beispiel
Ein Beispiel zur Erzeugung einer Folge von 1000 Nullen mag die Kompression veranschaulichen:
Die Zahl 1000 lässt sich (in Binärform) durch 10 Bit darstellen.
Bei einem gegebenen (konstanten) Programm zum Ausdrucken einer Nullfolge kann man die Kolmogorov Komplexität einer Folge von n Nullen als "Konstante + log(n)" angeben.
Zufall oder Ordnung?
Es gibt allerdings (in diesem Sinne) auch nur scheinbar zufällige Zahlenfolgen.
Beispielsweise gibt es ein kurzes Programm, welches die Dezimalentwicklung der Kreiszahl Pi in beliebiger Genauigkeit erzeugt.
Damit ergibt sich ebenfalls eine Komplexität der Form "Konstante + log(n)", wobei n die Genauigkeit der Darstellung angibt.
Berechnung
In der Praxis ist eine Angabe der Kolmogorov-Komplexität für eine konkrete Zeichenkette oft schwierig; es gibt keine konstruktive Vorschrift zu ihrer Berechnung.Anwendungen
Heute findet die Kolmogorov-Komplexität Anwendung in der Informatik, der Biologie und anderen Wissenschaften, die Strukturen oder Informationen betrachten.Literatur
Weblinks