0 Daumen
115 Aufrufe

Frage: Vollständige Induktion, Korrektheitsbeweis: Wie kommt man auf den Schluss n - 1 auf n?

Hallo, ich verstehe nicht ganz wieso man beim Beweis von n – 1 auf n schließt und generell erschließt mir nicht wirklich wieso der untenstehende Beweis nun aussreicht/ bzw. alles zeigt. Das hier ist eine Musterlösung. Es soll die Korrektheit vom Algorithmus Fakultät-Rekursiv(n) gezeigt werden.  

Induktionsanfang für n = 0: Die Bedingung n = 0 bei Aufruf Fakultät-Rekursiv(0) wird wahr und f → 1 ausgeführt. Der Funktionsaufruf ¨ bricht ab und es gilt Fakultät-Rekursiv(0) = f = 1 = 0!
Induktionsvoraussetzung: Fakultät-Rekursiv(n) = n! für n ≥ 0
Induktionsschluss von n − 1 auf n für n > 0. Bei Aufruf Fakultät-Rekursiv(n) wird der else-Zweig ausgeführt, da n > 0 gilt. f bekommt den Wert des Ausdrucks n * Fakultät-Rekursiv(n-1) zugewiesen. Mit Hilfe der Induktionsbehauptung für n − 1 ≥ 0 folgt f = n · (n − 1)! = n!.

Erläuterung/ Eigene Überlegung:
Induktionsanfang und Terminierung ist mir klar. Induktionsvoraussetzung denke ich auch. Denn wir nehmen ja an, dass das was wir behaupten schon stimmt und schließen dann von n auf das nächst größere. Eigentlich. Hier ist auch meine Frage: Induktionsschluss von n-1 auf n.
Müsste man nicht normalerweise von n auf n + 1 schließen, da n bereits die Eingabe ist für die wir annehmen, dass die Behauptung Fakultät-Rekursiv(n) = n! für n >= 0 gilt?
Oder wählen wir absichtlich von n - 1 auf n, da wir so folgende Gültigkeit haben: n > 0 bzw. n >= 1
Da man n >= 0 hat und dies auch für n – 1 gelten muss: n - 1 >= 0
Da wir dann vom Schluss von n – 1 auf n praktisch durch Addition von 1 auf n >= 1 kommen (bzw. n > 0) ist das die richtige Erklärung warum hier in der Musterlösung steht: „von n − 1 auf n für n > 0“ ?

Die Überlegung eines Freundes warum wir nicht von n auf n + 1 wählen war Folgende:
Man hat wieder n >= 0 und das soll auch für n + 1 gelten
n + 1 >= 0 | mit – 1 muss n >= -1 gelten und -1 kann bei Fakultät-Rekursiv(n) keine gültige Eingabe sein.

Kommt das irgendwie so hin? Ich glaube das kann man nicht so erklären. Uns verwirrt wieso ausdrücklich n – 1 auf n und nicht n auf n + 1 gewählt wurde. Denn eigentlich ist doch der Sinn von vollständiger Induktion, dass man die Behauptung annimmt und für das nächst größere diese Behauptung als Voraussetzung nimmt und dadurch dann die Gültigkeit beweist.


Meine erste Vermutung war diese: n auf n + 1

Wir haben n >= 0 und schließen durch +1 auf n + 1 >= 1 was ja das gleiche ist wie n + 1 > 0
Und dann die gleiche Erklärung wie oben, „da n > 0 gilt, wird der else-Zweig durchgeführt und man kriegt den Ausdruck:    n *  Fakultät-Rekursiv(n-1) und ruft damit die Funktion mit um eins verringerten Wert n auf und das wiederholt sich solange bis n = 0 ist (was aufgrund der Terminierung zwangsweise eintreten muss, da n bei jedem rekursivem Aufruf um 1 reduziert wird.
Durch die Induktionsbehauptung für n + 1 >= 1 folgt: f = (n + 1) * n! = (n + 1)!


Zumindest kenne ich das aus Mathe so. Oder muss hier bei Algorithmen ausdrücklich die Behauptung die wir beweisen wollen am Ende im Induktionsschluss stehen? Das finde ich irgendwie widersprüchlich.


Mit freundlichen Grüßen

von

1 Antwort

0 Daumen
 
Beste Antwort

Hallo, ob du bei der vollständigen Induktion entweder mit \(n-1\) auf \(n\) schließt oder von \(n\) auf \(n+1\), ist im Prinzip nicht wichtig. Du nimmst ja in der Induktionsvoraussetzung an, dass deine Aussage für eine beliebige, aber fest, gewählte natürliche Zahl gelte. Und aus designtechnischen Gründen nimmt man da zb \(n-1\), weil eben bei eurer Fakultätsfunktion rekursiv der Wert berechnet wird, also man eben \(\text{Fakultät-Rekursiv}(n-1)\) ( das entspricht hier der Induktionsannahme ) aufruft. Am Ende muss man ja im Induktionsschritt zeigen, dass man mithilfe der Induktionsvoraussetzung auf den Nachfolger schließen kann, hier n. Würde das nicht klappen, dann kann man sich auch den Induktionsbeweis schenken, da man dadurch sehen würde, dass die Behauptung wohl nicht für alle natürlichen Zahlen (ab einem Startindex) wahr ist. Es macht also keinen Unterschied, n zu wählen, um damit auf n+1 zu schließen. Es macht aber die Rechnungen vielleicht etwas übersichtlicher.

Oder muss hier bei Algorithmen ausdrücklich die Behauptung die wir beweisen wollen am Ende im Induktionsschluss stehen? Das finde ich irgendwie widersprüchlich.

Nunja, es wird ja behauptet, dass eure Funktion Fakultät-Rekursiv(n) die Werte \(n!\) für alle \(n\in \mathbb{N}\) zu berechnen. Es muss auch im Induktionsschritt mithilfe des aufgestellten Algortihmuses aufgezeigt werden, dass dieser auch für die Eingabe \(n\) terminiert und mittels rekursiver Aufrufe tatsächlich das Ergebnis \(n!\) ausgibt.

von

Ah okay vielen dank!

Also wäre meine erste Vermutung nicht wirklich falsch gewesen, außer das man anders als In Mathe nicht einfach ein nächst höheres wählen kann, sondern die genau verlangte Ausgabe erzeugen soll und damit n "schlau" auswählen.

Eine Frage hätte ich noch. Ist dies dann so korrekt wie man auf die n > 0 kommt?

Da man n >= 0 hat und dies auch für n – 1 gelten muss: n - 1 >= 0
Da wir dann vom Schluss von n – 1 auf n praktisch durch Addition von 1 auf n >= 1 kommen (bzw. n > 0)

Es wird im Induktionsschritt \(n>0\) betrachtet, womit \(n-1\geq 0\) gilt. Also ist damit auch \(n\geq 1\). Damit wird der else-Zweig betrachtet und dort das Ergebnis \(n\cdot \text{Fakultät-Rekursiv}(n-1)\) zurückgegeben.

Der Fall \(n=0\) wurde schon im Induktionsanfang betrachtet, wo die Korrektheit und die Terminierung vom Algorithmus verifiziert worden ist. Nun wird aber das Aufrufargument für eure Funktion \(\text{Fakultät-Rekursiv}\) in jeder Rekursion um Eins vermindert. Das zu betrachten, ist aber per Algorithmus nur für \(n>0\) sinnvoll, da ihr ja nach \(n\) Rekursionen auf euren Rekursionsanker kommt, wo also \(n=0\) (als Eingabe-Argument) gilt und euch der Induktionsanfang die Korrektheit garantiert.

Ja, aber wie kommt man auf die n > 0

Durchdem man annimmt das n >= 0 (I.V) auch für n - 1 gilt und dann: +1 macht um "von n - 1 auf n zu schließen" wodurch man n >= 1 bzw. n > 0 erhält.

Darf man sich das so merken?

Nein, das hat nichts mit dem Sachverhalt zu tun. Dein Algorithmus fragt doch in jedem Aufruf, wie groß die Eingabe ist. Ist diese \(n=0\) ist man mit dem Induktionsanfang bereits fertig. Ist diese \(n>0\), dann wird im else-Zweig der Wert \(n\cdot \text{Fakultät-Rekursiv}(n-1)\) zurückgegeben. Hier kommt dann die Induktionsvoraussetzung ins Spiel, die sagt, dass bereits für die Zahl/Eingabe \(n-1\) die Funktion Fakultät-Rekursiv korrekt arbeitet.

Okay danke. Ich glaube ich habe es verstanden.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community