Induktionsschritt #2b

studenthoch80
Neuling
Neuling
Beiträge: 9
Registriert: 15. Mai 2017 16:16

Induktionsschritt #2b

Beitrag von studenthoch80 » 12. Jun 2017 15:50

Hallo,

ich habe eine Frage zum Induktionsschritt eines rekursiven Korrektheitsbeweises.

Ich verstehe, dass die Induktionsvoraussetzung im Induktionsschritt immer angenommen wird, d.h. dass z.B. der Induktionsparameter |C\V| - 1 angenommen wird, und man muss nun zeigen, dass das auch für |C\V| gelten muss. (Bsp. ColoringCanvasInBackgroundColor2Recursive)

Und man muss nun anhand der IV immer zeigen, dass das dann auch für das letzte Element der Menge gilt? In dem genannten Bsp.: Weil die IV die Menge V einschließt, und der aktuelle Pixel zusammen mit den Elementen aus V, die ja schon in der IV bewiesen wurden, rekursiv behandelt wurde, ist das Element somit auch bewiesen? D.h. die IV wird erneut angewandt, wobei es das letzte, noch zu beweisende Element, dann mit einschließt?

Habe ich das richtig verstanden?

Danke & Gruß

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Induktionsschritt #2b

Beitrag von invariant » 12. Jun 2017 17:47

Hallo,

Ich bin mir nicht ganz sicher ob ich Ihre Frage korrekt verstehe.


Das letzte Element der Menge? Das erschließt sich mir gerade nicht ganz.

Im Induktionsschritt zeigen Sie, dass mit Hilfe Ihrer IV (h-1 bzw. hier |C\V|-1) ihre Invariante auch für h bzw. hier |C\V| gilt. Dazu müssen Sie normalerweise am Code "entlanghangeln" und die IV an der bzw. den passenden Stellen nutzen.

Hat das Ihre Frage beantwortet? Ansonsten könnten Sie sie vielleicht nochmal umformulieren?

Gruß

studenthoch80
Neuling
Neuling
Beiträge: 9
Registriert: 15. Mai 2017 16:16

Re: Induktionsschritt #2b

Beitrag von studenthoch80 » 12. Jun 2017 17:59

Ja, ich meinte bei einem Induktionsparameter h wird anhand der IV, die für h-1 angenommen wird, gezeigt, dass die Aussage auch für h gilt. h ist hier der letzte Knoten des Baumes zum Beispiel.

Und der "Trick" an dem Induktionsschritt ist dann der, dass ich, wie Sie bereits gesagt haben, die IV so einsetze, dass diese auch für h gilt. Da war ich mir nicht so sicher. Dieses Prozedere gilt dann sicher auch für iterative Beweise. An dieser Stelle kam ich immer ins Wanken.

Grüße

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Induktionsschritt #2b

Beitrag von invariant » 12. Jun 2017 18:19

Hallo,
dieses Beispiel, dass es der letzte Knoten im Baum ist - vorsichtig damit, ich kann daran nicht ganz einschätzen ob Sie es verstanden haben.
Die Höhe h ist beliebig und das ist wichtig. Dass wir häufig die Wurzel des aktuellen Teilbaumes der Höhe h im Schritt direkt behandeln - also keinen weiteren Rekursionsschritt brauchen - ist häufig richtig.

sie wollen im Induktionsschritt die IV so einsetzen, dass die Invariante bzw. Induktionsbehauptung für h gilt.
Die IV ist an dieser Stelle, dass die Induktionsbehauptung für h-1 gilt.
Das ganze Prozedere gilt natürlich auch für iterative Beweise:

Beliebige Iteration h-1 als IV und dann zeigen, dass im h-ten Schritt aufbauend auf der IV die Invariante weiter gilt.

Gruß

Antworten

Zurück zu „Archiv“