Ein paar Einsichten aus dem Repetitorium vom 17.9.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Ein paar Einsichten aus dem Repetitorium vom 17.9.

Beitrag von Prof. Karsten Weihe »

Hallo allerseits,

folgende Punkte sind mir in der Korrespondenz mit der Repetitoriumsleitung und bei der Durchsicht der Poster aufgefallen:

1. Es gab Fragen, ob man in den Klausuraufgaben nun explizit mit Induktionsvoraussetzung, Induktionsschritt, Gesamtkorrektheit usw. umgehen soll oder nur mit dem übergeordneten Schema Invariante + Variante + Abbruchbedingung. Meine Antwort: Das wird aus der Formulierung der Klausuraufgabe jeweils unzweideutig ersichtlich sein.

2. Unterscheiden Sie bitte Rekursionsschritt und Induktionsschritt - ersteres ist ein Ablauf im Algorithmus, letzteres ein Teil eines Textes, nämlich des Korrektheitsbeweises. Beide haben natürlich eng miteinander zu tun: Der Induktionsschritt beweist Korrektheit des Rekursionsschritts.

3. Oft wird eine Rekursion ja ausgelagert in eine Hilfsmethode. Zum Beispiel im Repetitorium wurde das bei Binary tree insert gemacht. Der Grund hier ist, dass der Fall, dass der gesamte Baum leer ist, nicht innerhalb der Rekursion behandelt werden kann. Der Punkt ist: Nur das, was in dieser Hilfemethode ist, gehört in die vollständige Induktion. Konkret beim Beispiel aus dem Repetitorium wird in der (nichtrekursiven) Hauptmethode der Fall root==null behandelt, in der rekursiven Hilfsmethode ist der Fall p==null der Rekursionsanker. Nur p==null gehört in den Induktionsanfang. Der Fall root==null kommt erst in der Gesamtkorrektheit des Algorithmus vor: Wenn der Baum leer ist, dass folgt Korrektheit aus dem, was in der Hauptmethode (ohne Aufruf der Hilfsmethode) passiert; wenn der Baum nicht leer ist, folgt Korrektheit aus der Invariante der Rekursion.

4. Wenn Sie einen Rekursionsschritt beschreiben oder den Induktiosschritt für die Invariante einer Rekursion formulieren/beweisen, dann erscheint es vielen von Ihnen natürlich zu beschreiben, wie die Rekursion immer weiter absteigt, bis der Rekursionsanker erreicht ist, und dann wieder zurückkommt. Das ist aber eine ungeeignete Sicht, die bei komplexeren rekursiven Algorithmen problematisch wird. Besser ist es, wie im Wiki und in der Vorlesung einfach den rekursiven Aufruf als "Black Box" zu betrachten, so wie man den (nichtrekursiven) Aufruf jeder anderen Methode ganz selbstverständlich als "Black Box" betrachten würde. Zum Beispiel Quicksort: Im Rekursionsschritt wird die Sequenz in drei Teilsequenzen zerlegt, die erste und die dritte Teilsequenz werden rekursiv sortiert (durch die Black Box!), und dann werden die drei Sequenzen wieder zu einer zusammengefügt. Abgesehen davon, dass ich ausgelassen habe, wie die Sequenz zerlegt wird, ist damit der Rekursionsschritt vollständig beschrieben - maximal einfach und maximal kurz.

KW

BluBlu
Erstie
Erstie
Beiträge: 19
Registriert: 17. Sep 2015 09:50

Re: Ein paar Einsichten aus dem Repetitorium vom 17.9.

Beitrag von BluBlu »

Dazu noch eine Frage zur im Repetitorium am 16.9. vorgestellten Musterlösung des iterativen Binary tree insert. Der Induktionsanfang lautete dort wie folgt:

"Für einen nicht existierenden Baum wird ein neuer Knoten angelegt und als der root des Baumes gesetzt."

Ist dies nicht ebenfalls nur eine Behandlung des Sonderfalls eines leeren Baums, welche eigentlich nicht zur Induktion gehört? Müsste der Induktionsanfang nicht das sein, was immer vor dem Einstieg in die Schleife sichergestellt ist, also in diesem Fall etwa:

"p wird auf root gesetzt, wodurch p auf einen Knoten zeigt, in dessen Range der einzufügende Knoten ist"

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Re: Ein paar Einsichten aus dem Repetitorium vom 17.9.

Beitrag von NonStop »

Prof. Karsten Weihe hat geschrieben: 2. Unterscheiden Sie bitte Rekursionsschritt und Induktionsschritt - ersteres ist ein Ablauf im Algorithmus, letzteres ein Teil eines Textes, nämlich des Korrektheitsbeweises.
Und wie sieht es bei iterativen Algorithmen aus?

In der wiki gibt es für jeden Algorithmus Induction basis und Induction step. Z.B. für B-Tree remove:
http://wiki.algo.informatik.tu-darmstad ... tion_Basis
http://wiki.algo.informatik.tu-darmstad ... ction_Step

Der Ablauf des Algorithmus wird nur da beschrieben, gleichzeitig beschreibt der Induktionsschritt aber auch die Korrektheit.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Ein paar Einsichten aus dem Repetitorium vom 17.9.

Beitrag von Prof. Karsten Weihe »

NonStop hat geschrieben: Der Ablauf des Algorithmus wird nur da beschrieben, gleichzeitig beschreibt der Induktionsschritt aber auch die Korrektheit.
Man kann einerseits sagen, der Induktionsschritt ist der Beweis der Korrektheit des Rekursionsschrittes / der Iteration. Andererseits kann man sagen, der Rekursionsschritt / die Iteration ist die Implementation des Induktionssxhrittes. Letzeres ist die Sicht, die im Wiki eingenommen wird.

Don't panic: Diese terminologische Feinheit spielt keine Rolle in der Klausur.

KW

Antworten

Zurück zu „Archiv“