Diskussion:Kolmogorow-Komplexität

Schewek? Wo hast Du dass den her? Ich würde mit Algorithmischer Komplexität die Komplexität von Berechnungsproblemen bezeichnen. Was hier steht, scheint mir recht wirres Zeugs zu sein. Wenn der Artikel so bleiben soll, würde ich ihn lieber unter dem Titel Kolmogorov Komplexität sehen wollen. Aber überarbeitet werden muss der in jedem Fall. Ich versteh hier nur Bahnhof. --Coma 19:17, 6. Jan 2003 (CET)

Erstmal hat du recht: Kolmogorov Komplexität ist wohl der gebräuchlichere Begriff. Weiterhin hast du recht: Der Artikel ist schlecht, und ich hatte wohl ein paar Dinge falsch verstanden. Ich hatte unter http://www.cwi.nl/~paulv/papers/020608isb.pdf nachgeschaut. -- Schewek

Gut, dann verschieb ich ihn erstmal und schau mal nach, ob ich bessere Infos finde... --Coma 19:43, 6. Jan 2003 (CET)

Hab nur eine sehr theoretische Abhandlung gefunden, die wohl auch vorkenntnisse erfordert. und ich hab auch keine Lust und Zeit selbst zu lesen... --Coma 20:07, 6. Jan 2003 (CET)

Dann werde ich mich nochmal schlaumachen, und morgen einen neuen Versuch machen. -- Schewek

Wenn ich es richtig verstanden habe, geht es um eine Beschreibungskomplexität. Eine Bitfolge läßt sich oft kürzer darstellen. Beispielsweise kann man 1000 Nullen auch durch die Zahl 1000 (in Binärform) ersetzen, was dann nur 10 Bit benötigt. Natürlich muss man dazu noch sagen, wie die neue Folge zu interpretieren ist, was durch ein Berechnungsprogramm geschehen kann, welches dann die ursprüngliche Folge wieder herstellt. Das braucht dann auch Speicher, aber für verschiedene Sprachen nur konstant viel zusätzlichen Speicher. (Ein Programm kann immer als Zahl kodiert werden). Die Zahl muss dann also auch immer noch mit angegeben werden. In der Sprache der beliebig langen Folgen von Nullen läßt sich ein Wort der Sprache also durch die Angabe der Anzahl von Nullen angeben. Zur Interpretation der Zahl benötigt man dann noch das Programm oder besser die Programmnummer, die aber für jedes Wort der Sprache konstant ist. Die Sprache der konstanten Folgen von Nullen besitzt dann logarithmische Komplexität, weil die Länge der Worte logarithmisch kodiert werden können, wobei noch die additven Kontante (für das Programm) dazukommt, welche aber nicht ins Gewicht fällt. Wenn das jemand so bestätigen oder präzisieren könnte, kann man da schon fast einen Artikel draus machen. --Coma 20:21, 6. Jan 2003 (CET)

Als ich studiert hab war K der informationsgehalt, also die minimale information um etwas darzustellen. und keine grösse eines computerprogramms. Denn ein Computerprogramm das diese seite darstellt ist bestimmt grösser als die seite selbst...

Ich stimme hier meinem unbekannten Vorredner zu; ein Computerprogramm das irgendetwas ausgibt muss allein schon durch die entsprechenden Ausgaberoutinen eine bestimmte Größe haben. Diese Größe würde entsprechend des verwendeten Systems auch noch variieren. Die Kolmogorow-Komplexität ist jedoch eine theoretische Größe, die bewusst unabhängig von real existierenden Maschinen und Sprachen gehalten wurde. Davon unabhängig habe ich hier folgende Definition: "Die Kolmogorov-Komplexität einer 0-1-Folge ist die Länge eines kürzesten Programms für eine fest vorgegebene universelle Maschine, die gegebene Folge zu erzeugen." Mit "fest vorgegebene universelle Maschine" ist imho wohl eine Turingmaschine gemeint. Vielleicht kann jemand das bestätigen und ändern?--Ente2k 15:52, 19. Jan. 2007 (CET)

Der Artikel enthält unten zwar eine hübsch anschauliche Darstellung, redet jedoch anfangs ausschließlich von 1000 Bits. Die Programmanweisung liegt aber nicht binär vor, sondern - solange nicht anders angegeben - als Bytes. Damit ist die Grafik irreführend. (nicht signierter Beitrag von 88.74.1.187 (Diskussion | Beiträge) 00:23, 16. Sep. 2009 (CEST))

Beschreibungskomplexität ist ein viel allgemeinerer Begriff (z.B. auch die Anzahl der Zustände, die ein bestimmter Typ endlicher Automaten benötigt, um eine Klasse von Sprachen zu entscheiden) --129.132.153.200 12:43, 28. Sep. 2009 (CEST)

Informationsgehalt <-> Datengehalt

Was mich hier stört ist die Aussage, dass je zufälliger eine Datenfolge ist, desto mehr Information würde sie enthalten. Das ist nämlich nicht unbedingt richtig!!!!

Eine vollständig deterministische Datenfolge wie 0101010101010101010101010101010101..... liefert sicher keine Information, weil ihre Fortsetzung bekannt ist und damit keine (neue) Information mehr mit sich bringt. Damit ist diese Folge zwar stark komprimierbar aber eben auch wenig informativ.

Das andere Extrem sind reine Zufallszahlen/Zufallsbuchtaben. Sie enthalten ein Maximum an - nicht komprimierbarer - DATEN, aber wie steht es mit dem Informationsgehalt?

Information im Sinne von Kommunikation ist mehr als eine Menge an empfangenen Daten. Insbesonders wenn ich diese Daten nicht verstehen kann, bringen sie nämlich nichts. Um Information zu übertragen braucht es eine Semantik wie in der Sprache typischerweise durch den Wortschatz vorgegeben.

Eine zufällige Aneinanderreihung von Wörtern vermittelt dem Empfäger aber mit Sicherheit nichts festgelegtes/definierbares.

Das heisst: Der Informationsgehalt eine Nachricht hat bei "mittlerer" Zufälligkeit der Datenteile ein Maximum und bei totaler Zufälligkeit ist die übertragene Information wieder minimal.

Hier muesste man deutlicher Unterschieden, was gemeint ist: Man kann natürlich einen Datenpacket so packen, dass es nicht weiter komprimmierbar ist. Dann muss aber separat die Information mitkommen, wie das zu entpacken ist und was man da überhaupt erhält.

In der Kommunikation wäre das Übertragen von Zufallszahlen analog zu statistischem Rauschen zu sehen. Und das enthält keine Information auch wenn man aus ihm jede Menge Daten gewinnen kann.

-- 192.54.144.229 14:57, 19. Nov. 2009 (CET) S.Koller