Hallo hat geschrieben:
Bei dem Induktionsschritt, denke ich mal ich soll da immer sagen, wie der Alogrithmus unmittelbar nach dem 1. rekursiven Schritt weitergeht.
In der Vorlesung und darüber hinaus hatte ich öfters versucht, folgendes zu kommunizieren: Gehen Sie beim Verstehen und bei der Analyse von rekursiven Methoden am Besten einfach von dem Code aus und vergessen Sie den zeitlichen Ablauf der Rekursion. Im Code muss es eine Fallunterscheidung geben mit mindestens einem Fall (meist auch nur ein Fall), in dem die Methode nicht rekursiv aufgerufen wird. Im Induktionsanfang argumentieren Sie, warum die Invariante in diesen Fällen eingehalten wird. Im Induktionsschritt argumentieren Sie, warum die Invariante in den anderen Fällen eingehalten wird, wobei Sie prüfen müssen, ob die Inputs der rekursiven Aufrufe der Input-Spezifikation entsprechen, und dann von der Annahme ausgehen dürfen, dass die rekursiven Aufrufe den korrekten Output für ihren Input liefern (diese Annahme ist die Induktionshypothese).
Hallo hat geschrieben:
Ich verstehe jedoch nicht, was sie mit Zusatzargumente meinen. :
Wir unterscheiden ja häufig zwischen der eigentlichen Methode, die dann nicht selbst rekursiv ist, und einer rekursiven Hilfsmethode mit leicht erweiterter Parameterliste. Zum Beispiel Ihre Parameter l und r würden ja nicht zum Input der eigentlichen Suchmethode gehören, sondern erst zum Input der rekursiven Hilfsmethode.
Häufig werden in der eigentlichen Methode aber darüber hinaus noch weitere Operationen durchgeführt, die natürlich auch korrekt sein müssen. Beispiele dafür müssten Sie in den Übungsaufgaben finden. Die Argumente zur Korrektheit dieser Operationen sind Zusatzargumente über die Rekursion hinaus.
Hallo hat geschrieben:
Wohldefiniertheit:
NullPointerException kann nicht sein,da es keine Zuweisungen gibt, die auf null zugreifen könnten.
ArithmeticException kann nicht sein, da die berechneten Variablen maximal so groß sind wie die Länge des Arrays, und somit kein Überlauf auftreten kann.
Im Fall, dass der Input ein Array ist und Sie auf etwas komplizierte Weise darauf arbeiten, ist natürlich IndexOutOfBoundsException besonders interessant.
Hallo hat geschrieben:
Variante:
j-i wird in jedem Rekursionssaufruf echt kleiner, somit verändert sich in jede Rekursion die Position der Variable m.
Ihr erster Halbsatz ist die Variante, ok. Ihr zweiter Halbsatz scheint mir keinen ernsthaften Erkenntnisgewinn im Hinblick auf Korrektheit zu bringen?
Disclaimer für das folgende: Kann sein, dass ich mich mit i, j, l und r hier und da um 1 vertun werde, prüfe ich jetzt nicht nach.
Hallo hat geschrieben:
Terminierung:
Aufgrund der Variante wird die Abbruchbedingung a[m]==x oder j-i==0 (= Teilarray mit 1 Element) nach endlich vielen Rekursionsschritte erreicht.
Ich stimme zu.
Hallo hat geschrieben:
Invariante:
Unmittelbar nach einen rekursiven Schritt gilt, das falls der gesuchte Element im Array enthalten ist, so ist er im Teilarray l+1( l = i = linke Grenze des Intervalls) bis r-1 (l = j = rechte Grenze des Intervalls) zu finden.
Ich stimme zu, wobei mir nicht klar ist, wieso wir i und l bzw. j und r gleichzeitig haben sollten, jeweils eine der beiden Notationen reicht doch, oder?
Hallo hat geschrieben:
Induktionsanfang:
Die Rekursion bricht im Fall von l-r=0 oder a[m] = x, und liefert -1 bzw die Position des gesuchten Wertes x.
Ich denke, die eigentlich spannende Frage lassen Sie aus: Warum ist das Ergebnis in beiden Fällen korrekt. Der eine Fall ist a[m]==x, in diesem Fall ist x gefunden und daher das Ergebnis offensichtlich korrekt. Der andere Fall ist r<l, und in diesem Fall folgt Korrektheit von -1 aus der Invariante: Wenn x nicht innerhalb des Intervalls l..r zu finden ist, sofern x überhaupt im Array ist, das Intervall l..r aber leer ist, dann kann x nicht im Array sein, und die Rückgabe ist wieder korrekt.
Hallo hat geschrieben:
Induktionsschritt:
Nach Induktionsvoraussetzung gilt, das falls x im Array enthalten ist, so ist er zwischen dem Intervall r+1 bis i-1 zu finden. Somit ergibt sich, das falls die mittlere Variable nicht auf den gesuchten Wert zuweist, und r-l ungleich 0 sind, eine Fallunterscheidung passiert:
Ist a[m] kleiner als x, so ruft sich die Methode wieder mit r als m+1 auf, also die 1. Hälfte des Arrays wird vernachlässigt.
Ist a[m] größer x so ruft sich die Methode mit gleichem r, jedoch l-1 wieder auf.
Sie beschreiben, was die Methode macht, aber nicht, warum die Invariante eingehalten wird.
Ich würde es vielleicht so formulieren: Ist a[m] kleiner als x, dann folgt aus der aufsteigenden Sortierung des Arrays, dass x nicht im Intervall m..r sein kann. Daraus folgt: Falls x in l..r ist, dann ist x in l..m-1. Die Induktionsvoraussetzung besagt: Falls x im Array ist, ist es in l..r. Beides zusammen ergibt transitiv: Falls x im Array ist, ist x in l..m-1, was zu zeigen war. Der Fall, dass x größer a[m] ist, ist natürlich analog.
Die Induktionsvoraussetzung und die Voraussetzung, dass das Array aufsteigend sortiert sind, müssen ja irgendwo in die Argumentation eingehen. Es ist immer sinnvoll, sich für jede Voraussetzung klarzumachen, an welcher Stelle sie eingeht, und dort auch explizit mit ihr zu arbeiten, so wie ich das im vorherigen Absatz gemacht habe. Die Stelle ist im Prinzip leicht zu finden: da, wo die Methode falsch laufen würde, wenn die Voraussetzung nicht erfüllt wäre.
Hallo hat geschrieben:
Korrektheit:
Gilt der Algorithmus für den allerersten Rekursionsaufruf, so liefert er nach endlich vielen Rekursionsschritten das korrekte Ergebnis.
"Gelten" ist kein Verb, das auf Algorithmen anwendbar ist, oder? Was meinen Sie wirklich?
KW
