2A02:8071:8188:CF60:5AC1:988D:556B:D147: Grammatik korrigiert

2025-06-21T18:24:04Z

Grammatik korrigiert

Neue Seite

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 Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt somit eine beste [[Datenkompression|Komprimierung]] der Zeichenkette an, ohne dass Information verloren geht.

Wenn die Kolmogorow-Komplexität einer Zeichenkette mindestens so groß ist wie die Zeichenkette selbst, 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 '[[Zufall|zufälliger]]' ist die Zeichenkette (und desto mehr Information enthält sie).

Das Prinzip der Kolmogorow-Komplexität wurde unabhängig im Jahre 1964 von [[Ray Solomonoff]], im Jahre 1965 von [[Andrei Nikolajewitsch Kolmogorow|Andrei Kolmogorow]] und 1969 von [[Gregory Chaitin]] entwickelt und hat Bezüge zur [[Claude Shannon|Shannonschen]] [[Informationstheorie]].

Die Kolmogorow-Komplexität wird manchmal auch '''Algorithmische Komplexität''' oder '''Beschreibungskomplexität''' genannt, darf aber nicht mit der [[Komplexität (Informatik)|Zeit- oder Raumkomplexität von Algorithmen]] verwechselt werden. Etwas präziser ist die Bezeichnung '''Algorithmischer Informationsgehalt''', die auch die Verbindung zu dem Begriff des [[Informationsgehalt]]s 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 [[Andrei Nikolajewitsch Kolmogorow|Kolmogorows]] in Bezug auf das [[Maschinenmodell]]. [[Jorma Rissanen]] beschreibt mit der [[Minimum Description Length]] ein ähnliches Konzept, das aber auf [[Datenkompression|Komprimierung]] der Daten aufbaut.

== Beispiel ==
Ein Beispiel zur Erzeugung einer Folge von 1000 Nullen mag die Kompression veranschaulichen:
Die Zahl 1000 lässt sich (in [[Dualsystem|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:
Program Nullfolge (n)
begin
for i:= 1 to n // im Beispiel n = 1000
print "0"
end
Das obige Programm kann mit einer konstanten Anzahl an Bits kodiert werden, z. B. als [[Maschinencode]] oder als einfache [[Textdatei]]. Die Kodierung der Zahl ''n'' benötigt ''log(n)'' Bits. Die gesamte Kodierung benötigt also zusammengerechnet "Konstante + log(n)" Bits und damit für große ''n'' wesentlich weniger als ''n'' Bits. Daher ist die Nullfolge komprimierbar.

Die folgende Darstellung verdeutlicht die Komprimierbarkeit:
Program Nullfolge (n)00000000000000000000000000000
0begin00000000000000000000000000000000000000000000
00for i:= 1 to n0000000000000000000000000000000000
000print "0"00000000000000000000000000000000000000
0end0000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
Das Programm, das die Folge mit 1000 Nullen erzeugt, nimmt kaum mehr als 5 % der Folge selber ein.

== Zufall oder Ordnung? ==
Es gibt allerdings (in diesem Sinne) auch nur scheinbar zufällige [[Zahlenfolge]]n.
Beispielsweise gibt es ein kurzes Programm, welches die [[Dezimalentwicklung]] der Kreiszahl [[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 ==
Die Kolmogorow-Komplexität ist nicht berechenbar, sie ist allerdings von oben [[rekursiv aufzählbar]].

== 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

== Literatur ==
* [[Ming Li]], [[Paul Vitányi]]: ''An Introduction to Kolmogorov Complexity and Its Applications.'' 3. Auflage. Springer-Verlag, New York 2008, ISBN 978-0-387-33998-6, {{DOI|10.1007/978-0-387-49820-1}}
* [[Juraj Hromkovič|Juraj Hromkovic]]: ''Theoretische Informatik. Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie.'' 3. überarbeitete und erweiterte Auflage. Teubner Verlag, Wiesbaden 2007, ISBN 978-3-8351-0043-5 (''Leitfäden der Informatik'').

== Weblinks ==
* [https://homepages.cwi.nl/~paulv/kolmogorov.html Paul Vitanyis Webpräsenz zur Kolmogorow-Komplexität]

{{SORTIERUNG:Kolmogorowkomplexitat}}
[[Kategorie:Theoretische Informatik]]
[[Kategorie:Berechenbarkeitstheorie]]

Kolmogorow-Komplexität - Versionsgeschichte

2A02:8071:8188:CF60:5AC1:988D:556B:D147: Grammatik korrigiert