Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Kolmogorov-Komplexität (http://www.informatikerboard.de/board/thread.php?threadid=386)

Geschrieben von donvito am 14.03.2008 um 15:50:

  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.


Geschrieben von Tobias am 14.03.2008 um 18:10:

 

Kannst du uns erklären, was eine "unäre Menge" ist?


Geschrieben von donvito am 14.03.2008 um 18:15:

 

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

11, 111, 11111, ...


Geschrieben von Tobias am 14.03.2008 um 18:30:

 

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?


Geschrieben von donvito am 14.03.2008 um 18:44:

 

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?


Geschrieben von Tobias am 14.03.2008 um 18:57:

 

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.


Geschrieben von donvito am 14.03.2008 um 20:32:

 

Aber die Bitlänge weiß ich doch nicht... Kapier das nicht so recht...


Geschrieben von Tobias am 14.03.2008 um 20:52:

 

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?


Geschrieben von donvito am 15.03.2008 um 11:43:

 

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.


Geschrieben von Tobias am 15.03.2008 um 12:13:

 

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?


Geschrieben von donvito am 15.03.2008 um 12:43:

 

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


Geschrieben von Tobias am 15.03.2008 um 13:03:

 

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.


Forensoftware: Burning Board, entwickelt von WoltLab GmbH