Kolmogorow-Komplexität
aus Wikipedia, der freien Enzyklopädie
Die Kolmogorow-Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Computerprogrammes gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Computerprogramm gibt somit eine beste Komprimierung der Zeichenkette, ohne dass Information verlorengeht.
Wenn die Kolmogorow-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 Kolmogorow-Komplexität an der Länge der Zeichenkette liegt, desto 'zufälliger' ist die Zeichenkette.
Das Prinzip der Kolmogorow-Komplexität wurde unabhängig im Jahre 1964 von R. J. Solomonoff, im Jahre 1965 von Andrei Kolmogorow und 1969 von Gregory Chaitin entwickelt, und hat Bezüge zur Shannonschen Informationstheorie.
Die Kolmogorow-Komplexität wird manchmal auch Algorithmische Komplexität oder Beschreibungskomplexität genannt, darf aber nicht mit der Zeit- oder Raumkomplexität von Algorithmen verwechselt werden. Etwas präziser ist die Bezeichnung Algorithmischer Informationsgehalt, die auch die Verbindung zu dem Begriff des Informationsgehalts nach Shannon herstellt. Ein verwandter, aber deutlich abzugrenzender Ansatz ist die Algorithmische Tiefe, die sich auf den Aufwand bezieht, der betrieben werden muss, um eine bestimmte Nachricht zu erzeugen oder zu entschlüsseln. Die Algorithmische Informationstheorie von Gregory Chaitin präzisiert den Ansatz Kolmogorows in Bezug auf das Maschinenmodell.
Inhaltsverzeichnis |
[Bearbeiten] 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 Kolmogorow-Komplexität einer Folge von n Nullen als "Konstante + log(n)" angeben.
[Bearbeiten] 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.
[Bearbeiten] Berechnung
Die Kolmogorow-Komplexität ist nicht berechenbar, sie ist allerdings von oben rekursiv aufzählbar.
[Bearbeiten] Anwendungen
Heute findet die Kolmogorow-Komplexität Anwendung in der Informatik, der Biologie und anderen Wissenschaften, die Strukturen oder Informationen betrachten.
- Datenkompression
- Definition der Zufälligkeit in Zeichenketten
[Bearbeiten] Literatur
- Ming Li and Paul Vitanyi: An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, New York, (1993).
