| Die letzten 10 Beiträge |
| 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]](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. |
| donvito |
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
|
| 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? |
| 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. |
| 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? |
| donvito |
Aber die Bitlänge weiß ich doch nicht... Kapier das nicht so recht... |
| 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. |
| donvito |
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? |
| 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? |
| 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, ... |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
