+1 Daumen
3,1k Aufrufe

Ich habe folgenden Algorithmus (Pythoncode):

def f(n):
  w = 0                    # Anfangswert
  for i in range(n+1):    # i=0,...,(n+1)-1
      w = w+i             # w um i erhöhen
  return w                 # Nach Beendigung der for-Schleife w zurückgeben.

Dieser Berechnet die Summe aller Zahlen 0,...,n .

Ich habe dazu folgende Schleifeninvariante aufgestellt:

$$ w'=\sum_{i=0}^n i-\sum_{k=i+1}^n k=\frac{n\cdot (n+1)+(i-n)\cdot (n+i+1)}{2} $$

Nur leider geht mein Induktionsbeweis nicht auf, verstehe aber nicht wiso.

Induktionsanfang. Für i=0 ist beim ersten Schleifendurchlauf $$ w'=\sum_{i=0}^n i-\sum_{k=0+1}^n k=\sum_{i=0}^n i-\sum_{k=1}^n k=0=\frac{n\cdot (n+1)+(0-n)\cdot (n+0+1)}{2}. $$

Induktionsvoraussetzung. Angenommen, die Schleifeninvariante gelte für den ersten Schleifendurchlauf.

Induktionsschritt. Dann gilt diese auch für den nachfolgenden, also für die (i+1)-te Iteration, also:

$$ w'=\sum_{i=0}^n i-\sum_{k=(i+1)+1}^n k=\frac{n\cdot (n+1)+((i+1)-n)\cdot (n+(i+1)+1)}{2}\\=\sum_{i=0}^n i-\sum_{k=i+2}^n k=\frac{n\cdot (n+1)+(i+1-n)\cdot (n+i+2)}{2}=\underline{\frac{i^2+3\cdot i+2}{2}}  $$ Dies zeigt man so:

$$ w'=w+i\stackrel{(IV)}{=} \Bigg(\sum_{i=0}^n i-\sum_{k=i+1}^n k\Bigg)+i=\frac{n\cdot (n+1)+(i-n)\cdot (n+i+1)}{2}+i\\=\underline{\frac{i^2+3\cdot i}{2}} $$

Was mache ich falsch?

Avatar von
folgende Schleifeninvariante aufgestellt:


Es fällt auf, dass du in der Summenschreibweise von w' i für zwei verschiedene Dinge (Summationsindex und -grenze) verwendest.

Ist das Absicht?

Ja, das ist so gewollt. Ich will in jeder i-ten Iteration die restliche Summe von der (i+1) - ten Iteration bis n abziehen, damit ich die aktuelle Summe von w' bekomme. Hier ein Beispiel:

$$ n=5\\i=0\quad w'=15-15=0\\i=1\quad w'=15-14=1\\i=2\quad w'=15-12=3\\i=3\quad w'=15-9=6\\i=4\quad w'=15-5=10\\i=5\quad w'=15-0=15 $$

Ich vermute mal, dass du meinen Einwand zum i nicht verstanden hast. Denn: Es gilt Punkt- vor Strichrechnung. D.h. du müsstest eigentlich Klammern setzen.

w' = Σ ( i - Σ k )

In dieser Interpretation wäre dann am Schluss gar kein i im Resultat.

Die Umformung scheint diese Klammer nicht zu berücksichtigen.

Zum Programmcode für die Schleife soll sich jemand in der Stacklounge äussern.

Nein ich meinte das hier:

$$ w'=\Bigg(\sum_{i=0}^n i\Bigg)-\Bigg(\sum_{k=i+1}^n k\Bigg)$$

Das sehe ich. Aber da machst du dir das Leben zu schwer mit den beiden verschiedenen i.

$$ w'=\Bigg(\sum_{k=0}^n k\Bigg)-\Bigg(\sum_{k=i+1}^n k\Bigg)$$

$$ w'=\Bigg(\sum_{k=0}^i k\Bigg)$$

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Schleifeninvariante beweisen (Python)

Um zu überprüfen, wo der Fehler liegt, betrachten wir den gegebenen Python-Algorithmus und die vorgelegte Schleifeninvariante Schritt für Schritt. Der Algorithmus lautet:

python
def f(n):
    w = 0           # Anfangswert
    for i in range(n+1):  # i=0,...,n
        w = w + i        # w um i erhöhen
    return w           # Nach Beendigung der for-Schleife w zurückgeben.


Dieser Algorithmus berechnet die Summe aller ganzen Zahlen von 0 bis \(n\).

Die vorgeschlagene Schleifeninvariante ist:

\( w' = \sum_{i=0}^n i - \sum_{k=i+1}^n k = \frac{n \cdot (n+1) + (i-n) \cdot (n+i+1)}{2} \)

Analyse der Schleifeninvariante:

Zuerst ist es wichtig zu bemerken, dass die aufgestellte Schleifeninvariante nicht korrekt formuliert wurde, um die beobachtete Eigenschaft des Codes hinsichtlich des Akkumulators \(w\) direkt nach jedem Schleifendurchlauf zu beschreiben.

Für den Algorithmus wäre eine korrekte Schleifeninvariante zu formulieren als die Summe der Zahlen von 0 bis \(i\), wobei \(i\) den aktuellen Stand im Laufe der Iterationen der Schleife repräsentiert. Also:

\( w = \sum_{k=0}^i k \)

und zu zeigen wäre, dass nach jedem Durchlauf \(i\), dies gleich bleibt, bis \(i=n\).

Induktionsanfang:

Vor dem Beginn der Schleife, wenn \(i=0\), ist \(w=0\) offensichtlich wahr, da:
\( w = \sum_{k=0}^0 k = 0 \)

Induktionsvoraussetzung:

Wir nehmen an, dass nach \(i\) Durchläufen der Schleife die Invariante wahr ist, d.h. \(w = \sum_{k=0}^i k\).

Induktionsschritt:

Wir müssen nun zeigen, dass wenn die Invariante nach \(i\) Durchläufen wahr ist, sie auch nach \(i+1\) Durchläufen wahr bleibt.

\( w' = w + i+1 = \sum_{k=0}^i k + (i + 1) = \sum_{k=0}^{i+1} k \)

Daher bestätigt dies die Gültigkeit der Schleifeninvariante.

Korrektur der ursprünglichen Invariante:

Der Ausdruck, der ursprünglich als Invariante vorgeschlagen wurde, scheint Konfusion hinsichtlich des Zwecks der Invariante und der tatsächlichen Berechnung innerhalb des Algorithmus zu schaffen. Die ursprünglich vorgeschlagene Formel erscheint unnötig komplex in Bezug auf die direkte Berechnung, die im Algorithmus stattfindet. Eine Schleifeninvariante sollte ein einfacher Ausdruck sein, der die Eigenschaften der Variablen in jedem Schritt der Schleife beschreibt.

Fazit:

Für korrektes Beweisen von Schleifeninvarianten ist es wesentlich, eine direkte Verbindung zwischen der Logik des Algorithmus und der Formulierung der Invarianten herzustellen. Im gegebenen Beispiel war die korrekte Invariante einfacher und direkter im Zusammenhang mit der Summenformel, die der Schleifenstruktur des Algorithmus entspricht.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community