WikiDer > Kolmogorov-Komplexität

Dieses Bild zeigt einen Teil der Mandelbrot-Sammlungfraktal sehen. Alle 24 . speichernbisschenFarbpixel in diesem Bild würde 1,62 Millionen Bit kosten. Ein wenig Computer Programm kann diese 1,62 Millionen Bits mit der Definition der Mandelbrot-Menge reproduzieren. Somit beträgt die Kolmogorov-Komplexität dieser Rohdatei viel weniger als 1,62 Millionen.

Das Kolmogorov-Komplexität oder algorithmische Komplexität (auch bekannt als die beschreibende Komplexität, Kolmogorov-Chaitin-Komplexität, stochastische Komplexität, algorithmische Entropie oder Komplexität der Programmgröße) ist der Grad, zu dem a Model oder System in Mathe oder algorithmisch Begriffe beschrieben werden können. Dies ist das Prinzip der minimalen Beschreibungslänge (Prinzip der Mindestbeschreibungslänge, MDL-Prinzip), die Länge der kürzesten Computer Programm um eine Datenstruktur zu generieren. Dieser Teil der algorithmische Informationstheorie (ein Teilbereich der Informatik), ist nach dem russischen Mathematiker benannt Andrey Kolmogorov.

Nehmen Sie zum Beispiel die folgenden zwei Saiten beide mit der Länge 64, die jeweils nur aus Kleinbuchstaben, Zahlen und Leerzeichen bestehen:

Abababababababababababababababababababababababababababababababab4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf 

Der erste String hinterlässt eine kurze Beschreibung im niederländische Sprache erhöht, nämlich "ab 32 mal". Diese Beschreibung besteht aus 10 Zeichen. Die zweite Zeichenfolge hat keine sofort auffallende einfache Beschreibung (mit derselben Zeichensatz), außer der gesamten Zeichenfolge selbst, die aus 64 Zeichen besteht.

Formal gesprochen, die Komplexität einer Zeichenfolge die Länge der kürzesten Beschreibung dieser Zeichenfolge in einer beliebigen gegebenen Universal-Beschreibungssprache. Wichtig ist die Sensibilität der Komplexität in Bezug auf die Wahl der Beschreibungssprache. Es kann gezeigt werden, dass die Kolmogorov-Komplexität eines Strings nicht viel größer sein kann als die Länge dieses Strings selbst. Strings, deren Kolmogorov-Komplexität im Verhältnis zur Größe des Strings klein ist, werden nicht als komplex betrachtet. Der Begriff der Kolmogorov-Komplexität geht überraschend tief und kann verwendet werden, um Unmöglichkeitsergebnisse zu berechnen, die ähnlich sind wie Unvollständigkeitssätze von Gödel und Stoppproblem von Turing zu setzen und zu beweisen.