Klausur 05.08.2010

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.

Klausur 05.08.2010
ich hätte da mal zwei fragen zum wp kalkül

  1. mir fehlt meistens der letzte schritt, wie lässt sich denn folgender ausdruck auswerten
    (a<=b && -b-a-1<0 )|| (a>b && -b-a-1<0) ?
  2. welche Invariante ist denn richtig ? ich hätte die 2. genommen (dh rechts oben), da ja k am anfang 1 ist und das kommt in der invariante rechts unten nicht vor- und da ja invarianten vor und nach dem schleifendurchlauf gelten müssen hätte ich mich für diese entschieden
    die untere ist auch deshalb rausgefallen da die summe ja von k=0 bis n-1 geht aber k ja wie gesagt 1 ist

wenn die invariante stimmt dann komme ich an dieser stelle nicht weiter:
kfs+kfk = (summe von i = 0 bis k) i! && kfk = k! && 1<=k<=n-1

der letzte teil müsste meiner meinung nach ja dann b sein


-b-a-1<0


und des andere kann ich einfach unter den tisch fallen lassen?


Wenn du sagt

dann ist das Wetter wohl oder übel egal

Deine Invariante ist richtig und das Ergebnis sieht auch richtig aus

An dieser stelle muss man ganz scharf in den Code schauen und erkennen, dass kf*k das gleiche ist wie k!

kfs = (summe von i = 0 bis k-1) i! && kf*k = k! && 1<=k<=n-1                  

ok seh ich ein
habt ihr dann auch eine lösung für die invariante am start?

-danke hab ich jetzt auch gesehn ^^


Deine Invariante ist schon mal die richtige. An der Stelle kannst du dann weiter machen mit:

kfs = (sum (i=0 to k) i!) - kf*k ^ kf=(k-1)! ^ 1<= k <= n-1

Jetzt würde ich die zweite Bedingung bei der ersten einsetzen, sodass sich ergibt:

kfs = (sum (i=0 to k) i! ) - (k-1)! * k ^....
kfs = (sum (i=0 to k) i! ) - k! ...
kfs = (sum (i=0 to k-1) i! ) ^kf = (k-1)! ^1 <= k <= n-1

Und dann steht letztlich wieder die Invariante da und k <= n-1, was ja Bedingung der Schleife ist und somit gilt :
I ^ b => wp( “In”, I)


Stimmt mit Einsetzen geht es genauso


ok danke


Die zweite Invariante müsste richtig sein. (Die andern 3 gelten imho nicht vor Betreten der Schleife, weiter hab ich nicht geschaut)

Schleifenbedingung ist, dass k <= n -1 ist. Da am Anfang der Schleife k = 1 initialisiert wird und k innerhalb der Schleife nur erhöht wird muss auch 1 <= k gelten. (Kein offzieller wp-Beweis, aber logisch).

Bei kf*k = k! teil doch einfach mal durch k :wink:
Dann kommt kf = (k-1)! raus, also ein Teil der Invariante

Die Summe wird etwas komplizierter (bin mir auch nicht sicher, ob man das in wp so machen darf):

kfs + kfk = sum(i = 0 bis k , i!)
kfs = sum(i = 0 bis k, i!) - kf
k
kfs = sum(i=0 bis k-1, i!) + k! - kf*k
kfs = sum(i=0 bis k-1,i!) + k((k-1)! - kf)
Wie wir von vorhin wissen gilt:
kf = (k-1)!
=> kfs = sum(i=0 bis k-1,i!) + k((k-1)! - (k-1)!)
kfs = sum(i=0 bis k-1,i!)
Womit wir wieder die Invariante vom Anfang haben.