Forum
 
Fragen
 
Suchen
 
Über Uns
 
 

Kolmogorov-Komplexität
Neue Frage »

14.03.2008, 15:50 Auf diesen Beitrag antworten »
donvito Kolmogorov-Komplexität

Mal wieder ne Frage:

Wie zeige ich, dass die KK des n-ten Elements einer rekursiven unären Mange A Teilmenge von 1* beschrieben wird durch
K(x_n) < n + c

Dürfte eigentlich nicht schwer sein, aber mir fehlt da die Übung.
Die Elemente sind der Größe nach sortiert, also z.B. 11, 1111, 11111, usw.

Die KK ist je gegeben durch die Länge des Kürzesten Programms, dass diese Zeichenkette erzeugt. Nur: Ich weiß ja garnicht wieviele 1er im n-ten Element stehen.
 
 
14.03.2008, 18:10 Auf diesen Beitrag antworten »
Tobias

Kannst du uns erklären, was eine "unäre Menge" ist?
14.03.2008, 18:15 Auf diesen Beitrag antworten »
donvito

Ja, das bezieht sich darauf, dass nur die 1 enthalten ist. Es werden Wörter unterschiedlicher Länge aus 1ern gebildet:

11, 111, 11111, ...
14.03.2008, 18:30 Auf diesen Beitrag antworten »
Tobias

Also jede Menge, die ne Teilmenge von 1* ist, ist unär?

Eine obere Schranke für KK kann man immer durch einen Algo angeben, der das Wort ausgibt.

A ist rekursiv, d.h. es gibt eine Turingmaschine M, die entscheidet, ob 1^i (1..1 mit Länge i) in A ist oder nicht. Sei die Notation dafür
M(w) = true <=> w ist in A

Wir können nun ein Programm P(n) schreiben, dass M benutzt und x_n ausgibt:
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

P(n):

count = 0;
i = -1;
while (count < n) {
   i = i+1;
   if (M(1^i) == true) count = count+1;
}
Output(1^i);

Wir prüfen also mittels M der Reihe nach Eps, 1, 11, 111, 1111, ... ob sie in A enthalten sind. Wenn dies so ist, erhöhen wir den Counter, bis er auf n steht. Sobald er auf n steht haben wir x_n gefunden.

Nun ist die Frage, wieso für dieses Programm gilt:
K(x_n) <= |P(n)| <= n + c

Siehst dus?
 Anzeige
 
14.03.2008, 18:44 Auf diesen Beitrag antworten »
donvito

unär ist der Gegensatz zu BINÄR, Bi = zwei (O, 1) und uno = 1 (0 oder 1) Augenzwinkern

Was ist |P(n)|? Die Anzahl der Zeilen des Programms, oder was?
14.03.2008, 18:57 Auf diesen Beitrag antworten »
Tobias

Zitat:
unär ist der Gegensatz zu BINÄR, Bi = zwei (O, 1) und uno = 1 (0 oder 1)

Jau, weiß ich. Aber "unäre Menge" ist damit nicht erklärt. Aber das ist ja nun geklärt.

|P(n)| soll die Größe (nach einem bestimmten Maß) des Programms sein. Ein Maß wäre z.B. die Bitlänge des Wortes, welches die Turingmaschine kodiert, die P(n) berechnet.
14.03.2008, 20:32 Auf diesen Beitrag antworten »
donvito

Aber die Bitlänge weiß ich doch nicht... Kapier das nicht so recht...
14.03.2008, 20:52 Auf diesen Beitrag antworten »
Tobias

Die Bitlänge genau zu wissen ist hier nebensächlich. Es geht darum zu erkennen, welche Teile des Programms in die Konstante c einfließen und warum die Größe n noch vorkommt. Sprich:

Welcher Teil des Programms ändert sich, wenn du statt x_n das Wort x_m ausgeben willst?
15.03.2008, 11:43 Auf diesen Beitrag antworten »
donvito

Dein Algo hat aber einen Fehler bzw. du hast was falsch verstanden. Es müssen NICHT alle Teilfolgen von 1* enthalten sein. Es kann zum Beispiel sein, dass 1, 111, 11111, ... enthalten sind, 11 und 1111 aber nicht. Es ist eben eine Teilmenge von 1*

Dein Algorithmus würde dann einfach aufhören zu zählen
So müsste es klappen:
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:

P(n):   
 count = 0; 
 i = -1;  
while (count < n) {     i = i+1;    
if (M(1^i) == true) count = count+1; 
else do_nothing(); 
 }  
Output(1^i);


Die Konstante c enthält also offenbar alles außer der Schleife. Setze ich einen höheren Wert für n ein, so läuft die Schleife entsprechend länger. Die Länge ihrer Beschreibung dürfte sich dadurch aber nur minimal ändern. Es ändert sich ja nur der "Grenzwert" bis zu dem count zählt.
15.03.2008, 12:13 Auf diesen Beitrag antworten »
Tobias

Das musst du mir aber erklären, was dein Algo nun anders macht als meiner. Ich sehe keinen Sinn darin, ein "do_nothing" einzufügen, schließlich fängt er einfach in der while-Schleife von vorne an!?
Dass nicht Wörter aller Längen 1, 2, 3, ... drin sein müssen ist doch offensichtlich, denn sonst bräuchte ich keine zwei verschiedenen Counter "count" und "i".

Zitat:
Die Konstante c enthält also offenbar alles außer der Schleife. Setze ich einen höheren Wert für n ein, so läuft die Schleife entsprechend länger. Die Länge ihrer Beschreibung dürfte sich dadurch aber nur minimal ändern. Es ändert sich ja nur der "Grenzwert" bis zu dem count zählt.

Ja, das ist fast richtig. In die Konstante c fließt alles ein bis auf die Zahl n im Schleifenkopf der while-Schleife. Und wieviele Zeichen braucht man im schlechtesten Fall um eine Zahl n zu kodieren?
15.03.2008, 12:43 Auf diesen Beitrag antworten »
donvito

Ja stimmt wohl, mir fehlte da nur irgendwie die Bedingung was passiert wenn w nicht in L ist. großes Grinsen

Also man bräuchte im schlimmsten Fall natürlich n Zeichen.

Jetzt habe ich es verstanden Tanzen

Hoffentlich kommt das dran großes Grinsen
15.03.2008, 13:03 Auf diesen Beitrag antworten »
Tobias

Genau, im worst-case kodieren wir die Zahl im unären System. Das bedeutet aber auch, dass sich die Komplexität drücken lässt auf
[latex]K(x_n) \leq c + \lceil \log_b(n) \rceil[/latex], wenn wir n im Zahlensystem zur Basis b abspeichern.

Viel Glück bei deiner Klausur.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


Informatiker Board » Themengebiete » Theoretische Informatik » Kolmogorov-Komplexität

 
© 2005-2019 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen