Kolmogorov-Komplexität

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die Kolmogorov-Komplexität ist ein Maß für die Strukturiertheit Zeichenkette und ist durch die Länge des Computerprogrammes gegeben das diese Zeichenkette erzeugt. Dieses Computerprogramm gibt somit eine beste Komprimierung der Zeichenkette ohne dass Information verlorengeht.

Wenn die Kolmogorov-Komplexität einer Zeichenkette mindestens groß ist wie die Zeichenkette selber dann man die Zeichenkette als unkomprimierbar zufällig oder strukturlos. Je näher die Kolmogorov Komplexität an Länge der Zeichenkette liegt desto 'zufälliger' ist Zeichenkette.

Das Prinzip der Kolmogorov-Komplexität wurde unabhängig Jahre 1964 von R. J. Solomonoff im Jahre 1965 von A. N. Kolmogorov und 1969 von Gregory Chaitin entwickelt und hat Bezüge zur Shannonschen 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.

Inhaltsverzeichnis

1 Beispiel

2 Zufall oder Ordnung?

3 Berechnung

4 Anwendungen

5 Literatur

6 Weblinks

Beispiel

Ein Beispiel zur Erzeugung einer Folge 1000 Nullen mag die Kompression veranschaulichen: Die 1000 lässt sich (in Binärform ) durch 10 Bit darstellen. Bei einem gegebenen (konstanten) Programm Ausdrucken einer Nullfolge kann man die Kolmogorov einer Folge von n Nullen als "Konstante + log( n )" angeben.

Zufall oder Ordnung?

Es gibt allerdings (in diesem Sinne) nur scheinbar zufällige Zahlenfolgen . Beispielsweise gibt es ein kurzes Programm die Dezimalentwicklung der Kreiszahl Pi in beliebiger Genauigkeit erzeugt. Damit ergibt ebenfalls eine Komplexität der Form "Konstante + n )" wobei n die Genauigkeit der Darstellung angibt.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Kolmogorov_Komplexit%E4t.html">Kolmogorov-Komplexität </a>