 Kolmogorov-Komplexität |
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
 |
|
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.
__________________
Meine Moviebase
|
|
14.03.2008 15:50 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Kannst du uns erklären, was eine "unäre Menge" ist?
|
|
|
14.03.2008 18:10 |
|
|
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
|
|
Ja, das bezieht sich darauf, dass nur die 1 enthalten ist. Es werden Wörter unterschiedlicher Länge aus 1ern gebildet:
11, 111, 11111, ...
__________________
Meine Moviebase
|
|
|
14.03.2008 18:15 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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?
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 14.03.2008 18:32.
|
|
|
14.03.2008 18:30 |
|
|
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
|
|
unär ist der Gegensatz zu BINÄR, Bi = zwei (O, 1) und uno = 1 (0 oder 1) 
Was ist |P(n)|? Die Anzahl der Zeilen des Programms, oder was?
__________________
Meine Moviebase
|
|
|
14.03.2008 18:44 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
| 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 18:57 |
|
|
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
|
|
Aber die Bitlänge weiß ich doch nicht... Kapier das nicht so recht...
__________________
Meine Moviebase
|
|
|
14.03.2008 20:32 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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?
|
|
|
14.03.2008 20:52 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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:13 |
|
|
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
|
|
Ja stimmt wohl, mir fehlte da nur irgendwie die Bedingung was passiert wenn w nicht in L ist. 
Also man bräuchte im schlimmsten Fall natürlich n Zeichen.
Jetzt habe ich es verstanden 
Hoffentlich kommt das dran
__________________
Meine Moviebase
|
|
|
15.03.2008 12:43 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?K(x_n) \leq c + \lceil \log_b(n) \rceil) , wenn wir n im Zahlensystem zur Basis b abspeichern.
Viel Glück bei deiner Klausur.
|
|
|
15.03.2008 13:03 |
|
|
|
