Algorithmus - Schleifeninvariante

11.11.2008, 18:34

prinzschleifer

Auf diesen Beitrag antworten »

Algorithmus - Schleifeninvariante

Da ich es irgendwie nicht hinbekomme mich beim Informatik Board anzumelden, post ich hier mal eine Aufgabe:

So, die Aufgabe befindet sich im Anhang.

Nun müssen wir erstmal rausfinden, das dieser Algorithmus macht. Dazu hab ich einfach mal Beispielwerte genommen, es kommt bei mir aber nichts sinnvolles für $\begin{eqnarray*} P_n \end{eqnarray*}$ raus.

Hier meine Eingaben: a = 6 und b = 9

Bei einer Wertetabelle für jeden Schleifendurchlauf hab ich sowas bekommen

$\begin{eqnarray*} i - P_i - X_0 - Y_0 - x_0 \end{eqnarray*}$ (minus als seperator)
0 1 6 9 0
1 1 3 81 1
2 81 1 9^4 0
3 81 0 9^6 0

Nunja, das Ergebnis soll nun 81 sein. Leider finde ich keine Verbindung zwischen den beiden?

Brauche dringend Hilfe!

11.11.2008, 18:49

Reksilat

Auf diesen Beitrag antworten »

RE: Algorithmus - Schleifeninvariante
Eigentlich sollte ja laut Algorithmus $\begin{eqnarray*} Y_3=Y_2^2 \end{eqnarray*}$ sein, das stimmt aber mit Deiner Tabell nicht überein.

Wenn man eine Vermutung über den Zusammenhang von Eingabewerten und Ausgabewert finden will, benötigt man außerdem mehr als ein Beispiel.

Edit: Und $\begin{eqnarray*} x_2 \end{eqnarray*}$ wurde auch falsch berechnet, die Lösung lautet dann 9^4+9^2.

Tipp: Schau Dir mal die Binärdarstellung von a an.

11.11.2008, 19:25

prinzschleifer

Auf diesen Beitrag antworten »

Ah okay, also ich bin auch grade auf meine Fehlergestoßen.

Ich hab das ganze jetzt mit a=3 und b=9 gemacht, weil mich die alten Werte irgendwie genervt haben. geschockt

geschockt

So, was ich rausgefunden habe ist das 1 mod 2 = 1 ergibt, da 2x0 + 1 = 1 ist. Nunja, und dann noch die Potenzregeln, dass $\begin{eqnarray*} (a^m)^n = a^{m*n} \end{eqnarray*}$ ist.

So, nun schau ich mir mal die Binärschreibweise von a an, diese wäre für a=3
$\begin{eqnarray*} a = 3 = 11_b \end{eqnarray*}$

Mit den obigen Parametern hab ichs nochmal durchgerechnet und bin auf folgende Tabelle gekommen, die hoffentlich richtig ist.

$\begin{eqnarray*} i - P_i - X_0 - Y_0 - x_0 \end{eqnarray*}$
0 1 3 9 1
1 9 1 9^2 1
2 9^3 0 9^4 0

Also kommt für $\begin{eqnarray*} P_3 = 729 \end{eqnarray*}$ raus, was wiederum im Binärschreibweise folgendes wär: $\begin{eqnarray*} P_3 = 729 = 1011011001_b \end{eqnarray*}$

Idee: Könnte es vielleicht $\begin{eqnarray*} b^a \end{eqnarray*}$ sein?

Ich glaube schon. Weiter testen.

11.11.2008, 19:50

Reksilat

Auf diesen Beitrag antworten »

Deine Idee ist richtig.

$\begin{eqnarray*} 9^6=(0\cdot 9^8)\cdot (1\cdot 9^4)\cdot (1\cdot 9^2)\cdot(0\cdot 9^1) \end{eqnarray*}$ , denn $\begin{eqnarray*} 6=0\cdot8 + 1\cdot 4+ 1\cdot 2+0 \cdot 1 \end{eqnarray*}$

11.11.2008, 21:10

prinzschleifer

Auf diesen Beitrag antworten »

Gut, dazu sollen wir dann noch eine Schleifeninvariante angeben. Dies ist relativ einfach, da man lediglich einen Zusammenhang erkennen muss. Dazu schaut man in die Tabelle und findet folgenden Zusammenhang:

$\begin{eqnarray*} A_i = P_i * Y_i^{X_i} = b^a \end{eqnarray*}$

$\begin{eqnarray*} A_i \end{eqnarray*}$ sei eine Aussage, die ich jetzt durch vollständige Induktion beweisen soll muss.

Also I.A. :
Siehe Initalisierung: $\begin{eqnarray*} A_0 = P_0 * Y_0^{X_0} = b^a \checkmark \end{eqnarray*}$

I.S: Zeige: i => i+1
$\begin{eqnarray*} A_{i+1} = P_{i+1} * Y_{i+1}^{X_ {i+1}} = b^a \end{eqnarray*}$

Laut Algorumpf:
$\begin{eqnarray*} P_{i+1} = P_i * Y_i^{X_i} \end{eqnarray*}$

Also
$\begin{eqnarray*} P_{i+1} * Y_{i+1}^{X_ {i+1}} \end{eqnarray*}$
$\begin{eqnarray*} = P_i * Y_i^{X_i} * Y_{i+1}^{X_ {i+1}} \end{eqnarray*}$

Laut Algorumpf:
$\begin{eqnarray*} X_ {i+1} = X_i div 2 \end{eqnarray*}$
und
$\begin{eqnarray*} Y_{i+1} = (Y_i)^2 \end{eqnarray*}$

Also
$\begin{eqnarray*} P_i * Y_i^{X_i} * Y_{i+1}^{X_ {i+1}} \end{eqnarray*}$

$\begin{eqnarray*} = P_i * Y_i^{X_i} * Y_{i}^{2(X_i div 2)} \end{eqnarray*}$

Wenn $\begin{eqnarray*} 2(X_i div 2) = 0 \end{eqnarray*}$ wäre. Wäre meine Induktion fertig.
Ist meine Annahme den richtig, bzw. wo hab ich was falsch gemacht?

Laut Voraussetzung:
$\begin{eqnarray*} = b^a \end{eqnarray*}$

11.11.2008, 22:57

Reksilat

Auf diesen Beitrag antworten »

Funktioniert, aber es ist $\begin{eqnarray*} P_{i+1}=P_i\cdot y_i^{x_i} \end{eqnarray*}$ (kleines x!)

Danach braucht man nur noch, dass für alle z immer $\begin{eqnarray*} 2\cdot(z \,\rm{div} 2)+ (z \mod 2) =z \end{eqnarray*}$ gilt.

Anzeige

11.11.2008, 23:48

prinzschleifer

Auf diesen Beitrag antworten »

Gut, ich rechne nochmal den letzen Teil:

$\begin{eqnarray*} P_i + Y_i^{x_i}+Y_i^{2(X_{i+1})} \end{eqnarray*}$

$\begin{eqnarray*} P_i + Y_i^{x_i}+Y_i^{2(X_{i} div 2)} \end{eqnarray*}$

So jetzt hier ein kleines Problem:

Im Algorumpf steht nur:
$\begin{eqnarray*} x_{i+1} = X_{i+1} mod 2 \end{eqnarray*}$

heißt das automatisch dann:
$\begin{eqnarray*} x_{i} = X_{i} mod 2 \end{eqnarray*}$

Wenn das gilt steht da:

$\begin{eqnarray*} P_i + Y_i^{ X_{i} mod 2}+Y_i^{2(X_{i} div 2)} \end{eqnarray*}$

Da:
$\begin{eqnarray*} Y_i^{ X_{i} mod 2}+Y_i^{2(X_{i} div 2)} = Y_i^{ X_{i}} \end{eqnarray*}$
// Geht das denn überhaupt so, bei einer Addition darf man das ja nicht einfach so machen?

wegen:

$\begin{eqnarray*} 2\cdot(z \,\rm{div} 2)+ (z \mod 2) =z \end{eqnarray*}$

Also:
$\begin{eqnarray*} P_i + Y_i^{X_i} = b^a \end{eqnarray*}$
q.e.d

11.11.2008, 23:59

Reksilat

Auf diesen Beitrag antworten »

Zitat:

heißt das automatisch dann:
$\begin{eqnarray*} x_{i} = X_{i} mod 2 \end{eqnarray*}$

Ja, wurde ja gerade im vorherigen Schleifendurchlauf so definiert.

Zitat:

$\begin{eqnarray*} Y_i^{ X_{i} mod 2}+Y_i^{2(X_{i} div 2)} = Y_i^{ X_{i}} \end{eqnarray*}$
// Geht das denn überhaupt so, bei einer Addition darf man das ja nicht einfach so machen?

Deshalb ersetzen wir hier das Plus auch lieber durch ein Mal Big Laugh

Big Laugh

12.11.2008, 00:06

prinzschleifer

Auf diesen Beitrag antworten »

Ich Fisch!

Vielen, vielen, vielen Dank.

So nun die letzte Aufgabe - eine äußerst kleine.

Also: $\begin{eqnarray*} log_2^{a} \end{eqnarray*}$ wird ja auf die nächste ganze Zahl aufgerundet. Nun sollen wir argumentieren was passieren würde wenn die Zahl abgerundet werden würde.

Meine Antwort wär folgedens:
Unter Umständen könnte es passieren, dass der Algorithmus nicht zu einem korrekten Ergebnis kommen würde, da der Exponent $\begin{eqnarray*} X_0 \end{eqnarray*}$ noch nicht null erreicht hat, da es noch nicht genug Schleifen durchläufe gab.

???

12.11.2008, 00:10

Reksilat

Auf diesen Beitrag antworten »

Einfach ausprobieren (vorzugsweise mit a als einer Zweipotenz, in den anderen Fällen sollte es klappen) Wink

Wink

12.11.2008, 00:29

prinzschleifer

Auf diesen Beitrag antworten »

Ja, wenn $\begin{eqnarray*} a = 2^n \end{eqnarray*}$ dann wird es keine Rundungsfehler geben, weil es ja dann automatisch eine ganze Zahl ist.

Wie hab ich das den zuverstehen, bedeuten die Striche nach unten, dass aus 2,64 = 2 wird?

Anders würde es keinen Sinn ergeben.

Also durch Test hab ich rausgefunden, dass $\begin{eqnarray*} X_i \end{eqnarray*}$ manchmal einfach nicht null wird und dadurch zwar die Schleifeninvariante erfüllt wird, $\begin{eqnarray*} P_i \end{eqnarray*}$ aber nicht das Ergebnis $\begin{eqnarray*} b^a \end{eqnarray*}$ hat. Ist das ein Argument?

12.11.2008, 01:05

Reksilat

Auf diesen Beitrag antworten »

War natürlich Unsinn was ich geschrieben habe, im Fall a=2^r ändert sich ja durch die Veränderung der Gaußklammer nichts. In allen anderen Fällen dagegen gibt es vielleicht Probleme:
Ansatz $\begin{eqnarray*} a=2^r+q \end{eqnarray*}$ , wobei $\begin{eqnarray*} 1\leq q <2^r \end{eqnarray*}$ , dann ist beim Abrunden $\begin{eqnarray*} n=1+[\log_2a]=r+1 \end{eqnarray*}$ .

Nun sieht es für mich so aus, als wenn am Ende trotzem immer $\begin{eqnarray*} X_n=x_n=0 \end{eqnarray*}$ gilt, der Algorithmus würde also weiterhin funktionieren. Du hast es doch implementiert... Ausprobieren!

Gute Nacht! Tanzen

Tanzen

12.11.2008, 01:58

prinzschleifer

Auf diesen Beitrag antworten »

Mein Prof hat irgendwas gemeint mit der Logarithmus für die Zahl 0 ist nicht definiert, aber a darf ja nach Vorraussetzung nicht die Null sein.

Also ist die Antwort auf die Frage, dass sich nichts verändert und dass der Exponent $\begin{eqnarray*} X_n=x_n=0 \end{eqnarray*}$ . Gibt es dafür eine logische Begründung. Warum dann überhaupt auf oder abrunden?

12.11.2008, 09:49

Reksilat

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \log_20=x \Leftrightarrow{} 2^x=0 \end{eqnarray*}$ dieser Logarithmus kann also gar nicht existieren.

Für $\begin{eqnarray*} X_n=x_n=0 \end{eqnarray*}$ gibt es natürlich eine logische Erklärung, denn es ist $\begin{eqnarray*} X_n=X_{n-1} \rm\,{div} 2 \end{eqnarray*}$ die rekursive Definition und mit dem obigen Ansatz sieht man auch warum man spätestens nahc n Schritten auf 0 kommt.

12.11.2008, 22:21

prinzschleifer

Auf diesen Beitrag antworten »

Gut, also zum letzen Mal zur Klarheit (will nunmal meine Punkte in dem Blatt):

Nach n Schritten ist der Exponent, also $\begin{eqnarray*} X_0 \end{eqnarray*}$ auf null reduziert worden, da
$\begin{eqnarray*} X_n=X_{n-1} \rm\,{div} 2 \end{eqnarray*}$ gilt. Deswegen hat das aufrunden (ceil) bzw. abrunden (floor) keine Auswirkung auf das Ergebnis des Algorithmus.

Erklärung so einleuchtend?

12.11.2008, 22:45

Reksilat

Auf diesen Beitrag antworten »

Ich kann Dir den Algorithmus erklären. Wie Du es dann verständlich aufschreibst ist Deine Sache. Wenn Du alles verstanden hast, solltest Du auch wissen, was alles zur Lösung dazugehört.
Ciao. Prost

Prost

13.11.2008, 14:31

JuliusSpringer

Auf diesen Beitrag antworten »

Der nette Herr wollte lediglich wissen ob seine Antwort richtig ist und ja, deine Antwort ist einleuchtend und richtig! Hammer

Hammer

13.11.2008, 19:44

Reksilat

Auf diesen Beitrag antworten »

@JuliusSpinner:
Lies Dir mal durch was in diesem Thread steht! Er wollte nicht wissen, ob seine Antwort richtig ist, denn dies haben wir ja schließlich zusammen erarbeitet, sondern ob das was er da geschrieben hat ausreicht.
Ich helfe gerne bei Fragen des Verständnis, aber wenn ich der Meinung bin, an einem Punkt angelangt zu sein, an dem prinzschleifer allein weiterarbeiten kann, so solltest Du dies akzeptieren. Gib Deinen Senf dazu, aber lass mich in Ruhe!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »