Klausur 11.08.2011
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Induktion
Kann mir jemand bei Aufgabe 6 der Klausur vom 11.08.2011 (Formale Verifikation) weiterhelfen?
Beim Induktionsanfang bin ich mir relativ sicher:
C0 := (0+2) * 2^0-1 = 1 = cpRec(0)
C1 := (1+2) * 2^1-1 = 3 = cpRec(1)
Aber der Induktionsschluss ist mir noch unklar. Ich habe versucht
C N-2 := ((n-2) + 2) * 2^(n-2)-1 mit 4cpRec((n-2) - 1) - 4cpRec((n-2)-2) gleichzusetzen,
aber meine Vermutung ist, dass der rechte Teil der Gleichung nicht vollständig ist. Außerdem kommt nichts wirklich brauchbares raus, wenn man es ausrechnet. Nachdem man für diese Rechnungen nur wenig Platz hat, vermute ich es ist in Wirklichkeit viel einfacher!
Du hast noch 2 Induktionsvoraussetzungen gegeben, von denen du als gegeben ausgehen darfst.
IV(n-2): cpRec(n-2) = n*2^(n-3)
IV(n-1): cpRec(n-1) = (n+1) * 2^(n-2)
=>
cpRec(n) = 4cpRec(n-1) - 4cpRec(n-2)
I.V. = 4*(n+1)2^(n-2) - 4 n2^(n-3) =
[color=orange]
[i]// da 4 = 22 ist, wird die Eigenschaft verwendet um die 2er Potenz um 2 zu erhöhen[/i][/color]
= (n+1) * 2^n - n*2^(n-1) =
= n * 2^(n) + 2^n - n*2^(n-1) =
[color=orange]
// Eine Zweierpotenz aus dem ersten Element entfernen führt zu[/color]
= 2 * n * 2^(n-1) + 2^n - n * 2^(n-1) =
// 2a + b - a → a + b (wobei a = n2^(n-1))
= n * 2^(n-1) + 2^(n) =
= (n+2) * 2^(n-1) = Cn q.e.d
Danke vielmals! In dem Fall habe ich mich von den Angaben (die eigentlich als Hilfestellung gedacht waren) verwirren lassen!
ab hier kann ich nicht mehr folgen…was machst du da?
Danke vielmals! 
Vorher hatten wir
4 * (n+1) * 2^(n-2)
2^(n-2) ist 22222… und zwar n-2 zweier. Wenn wir da jetzt noch 22 (nämlich die 4) dranhängen haben wir n zweier → 2^n
Das gleiche mahchen wir rechts vom minus, dann bleibt:
//Die beiden vierer wurden wie eben beschrieben zu jeweils 2 zweiern und sind in die Potenz mit eingegangen.
= (n+1) 2^n - n2^(n-1) =
Jetzt einfach das vordere Glied ausmultiplizieren
= n * 2^n + 1 * 2^n - n*2^(n-1)
ok, vielen Dank!
ich stehe jetzt noch beim letzten Schritt:
wie komme ich von n*2^(n-1) + 2^n auf (n+2)*2^(n-1)?
Vielen Dank!!
einmal 2^(n-1) ausklammern, dann stehts da
Teilaufgabe d)
Servus, ich komm nicht so richtig mit dem folgenden Teil vom Lösungsvorschlag zur Teilaufgabe d) klar:
Ich hätte das ungefähr wie folgt gelöst:
{I ∧ b}=
(p = 2^(n - k - 1) ∧ k ≥ 0) ∧ (k > 0)
= (p = 2^(n - k - 1) ∧ k ≥ 1)
wp(A, I) = … = wp(A, I) = wp(p * 2 = 2^(n - k) ∧ k ≥ 1) = wp(p = 2^(n-k-1) ∧ k ≥ 1 )
{I ∧ b} => wp(A, I) == (p = 2^(n-k-1) ∧ k ≥ 1) => (p = 2^(n-k-1) ∧ k ≥ 1)
Jemand ne Meinung dazu, ob das so durchgeht?