Aufgabe 6.2

[Kubik-Rubik]

Hier kommen Fragen und Antworten zur Aufgabe 6.2 rein!

[Rob]

Hat schon wer ein guter Ansatz zu 6.2 e)? Ich habe zwar eine Idee, aber ich bin mir noch nicht ganz sicher wie ich sie richtig ausdrucken werde...

[Patric]

Also ich würde das Induktiv Beweisen, also über die länge des encodierten Wortes, das man daraus immer genau ein Wort decodieren kann.
Also habs jetzt noch nich getestet geht aber sicherlich irgendwie in die richtung.
Und wenn man das nich induktiv Beweist, wär es das erste GBI Blatt ohne induktiven Beweis ;P

[salami]

Hallo, hab mal ne Frage.

Die a) verwirrt mich ein bisschen.

001000001, das müsste man ja eigentlich so sehen: 00 10 00 00 1. Dann ist aber die "1" nicht definiert. (Stichwort: Präfixfrei/nicht präfixfrei)
Muss man dann also das Wort so aufteilen, dass es passt (00 10 00 001), oder ist 1=10, oder ist die Antwort, dass man dieses Wort nicht decodieren kann?

[Christian S.]

Hallo, hab mal ne Frage.

Die a) verwirrt mich ein bisschen.

001000001, das müsste man ja eigentlich so sehen: 00 10 00 00 1. Dann ist aber die "1" nicht definiert. (Stichwort: Präfixfrei/nicht präfixfrei)
Muss man dann also das Wort so aufteilen, dass es passt (00 10 00 001), oder ist 1=10, oder ist die Antwort, dass man dieses Wort nicht decodieren kann?

Es darf keinen Rest geben, also ist die Aufteilung richtig, die keinen Rest ergibt - wenn es denn eine solche Aufteilung gibt. Schau am besten einfach auf welcher Seite du ein "kritisches" Element hast - in diesem Fall ja rechts die eins. Soll es also per diesem Code kodiert sein, müsste am Ende ja die 1 aus einem 001 sein.

[Chrisor]

jemand schon nen vernünftigen ansatz zur e)?

[|silent]

jemand schon nen vernünftigen ansatz zur e)?

Also ich würde das Induktiv Beweisen, also über die länge des encodierten Wortes, das man daraus immer genau ein Wort decodieren kann.
Also habs jetzt noch nich getestet geht aber sicherlich irgendwie in die richtung.
Und wenn man das nich induktiv Beweist, wär es das erste GBI Blatt ohne induktiven Beweis ;P

Also ich dachte mir das ähnlich. Induktiv ist defintiv klar würd ich sagen. Könnte mir vll. jemand von euch erklären wie man den induktiven Beweis aus folgendem Ansatz am saubersten (PROPER!) schreibt?

Mein Ansatz:
z.z.: keine zwei versch. Wörter w_1 und w_2 werden in das gleiche Wort w übersetzt. Wobei w_1, w_2 € {a,b,c}* und w € {0,1}*.

Behauptung:
Aus w_1, w_2 => je ein kodiertes neues Wort, dass
C(w_1) != C(w_2), wenn w_1 != w_2 und
C(w_1) == C(w_2), wenn w_1 == w_2.

Beweis durch Induktion:
I.A.:
Für n=1 => w_1 = {a,b,c}^1 = a | b | c ==(daraus folgt per Def.)==>
w = C(a) = 00
w = C(b) = 001
w = C(c) = 10

I.S.:
Es gelte w_n = {a,b,c}^n (I.V.)

Für n -> n+1:
w_n+1 = {a,b,c}^n+1 = {a,b,c} {a,b,c}^n = {a,b,c}^2 (für n=1)
=> w_2 = aa | ab | ac | ba | bb | bc | ca | cb | cc ==(daraus folgt per Def.)==>
w = C(a) C(a) = 00 00
w = C(a) C(b) = 00 001
...

Schluss:
Da w_1 != w_2 => C(w_1) != C(w_2) q.e.d.

Kann mir da jmd. helfen, ich hab noch so meine Probleme mit der vollständigen Induktion, gerne helfe ich bei Programmieren

[localhorst]

sowas wie C(aa) dürfte nicht 100%ig korrekt sein da ja C: {a,b,c} -> {0,1}, nicht C: {a,b,c}* -> {0,1}

[|silent]

sowas wie C(aa) dürfte nicht 100%ig korrekt sein da ja C: {a,b,c} -> {0,1}, nicht C: {a,b,c}* -> {0,1}

oh, stimmt hab' ich gar nicht gesehn danke. aber sonst noch was?

[JTex]

zur a) man geht immer von rechts nach links vor