AuD at Universität Erlangen-Nürnberg

In der rekursiven Methode muss ein Rekursionsschritt und einen Basisfall.

• Nicht direkt lösbare Teilprobleme müssen dem Ausgangsproblem ähnlich sein (Selbstähnlichkeit)
• Teilprobleme werden bei jedem weiteren rekursiven Aufruf bzgl. einer Ordnung kleiner (Monotonieeigenschaft)
• Größe der Teilprobleme ist nach unten beschränkt (Beschränktheit)

• Testansatz: 
  • möglich: für jede Eingabe kann das zugehörige Ergebnis durch schrittweises Ausführen ermittelt werden
  • letzte Unsicherheit bleibt bzgl. der übrigen Eingaben
• Variante 2: Korrektheitsbeweis
  • mit geeigneten Beweismethoden den Nachweis erbringen, dass die Methode für jede beliebige Eingabe immer das korrekte Ergebnis bzgl. der Spezifikation berechnet
  • im Zusammenhang mit rekursiven Methoden kommt dabei o

Induktionsanfang

Induktionsschluss (oder: -schritt)

• Basisform der Induktion (Variante 1: „+1“)
• Basisform der Induktion (Variante 2: „-1“)
• k-Anfangsform der Induktion (Variante 1: „+k“)
• k-Anfangsform der Induktion (Variante 2: „-k“)
• strenge Induktion
• Zweierpotenz-Induktion
• Rückwärtsinduktion
• strukturelle Induktion

• Bedingungen (zu beweisen):
  •  𝐴(1) ist wahr
  • Für jedes 𝑛 > 1 gilt: 𝐴(𝑛 − 1) ⇒ 𝐴(𝑛)
• Dann gilt 𝐴(𝑛) für alle 𝑛.
  • hier: 𝑘 Anfangswerte 𝐴(1) , … , 𝐴(𝑘) gegeben
• Strategie nun: „k parallele Pfade durch ℕ, die ℕ ganz überdecken“
• Ziel: Nachweis der Gültigkeit einer Aussage 𝐴(𝑛) für alle 𝑛∈ℕ

Durch den fehlenden Basisfall, entsteht eine Endlosrekursion die zu einem StackOverflow führt

Terminierungsbeweis

Testansatz (für Auswahl von Eingaben)

Endrekursivierung

• Elegante, intuitive, übersichtliche Problemlösungen.
• Programmtext ist im Allg. lesbarer und weniger fehleranfällig.
• Besonders geeignet für Algorithmen, die auf induktiv definierten Daten arbeiten, wodurch das Problem leicht in kleinere selbstähnliche Teilprobleme zerfällt.
• Beweise von Eigenschaften, wie Übereinstimmung mit Spezifikation und Terminierung, sind oft nahe liegend per vollständiger Induktion.

Eine Elementaroperation entspricht genau einer Instruktion des zugrunde liegenden Von-Neumann-Rechners und hat das Kostenmaß 1.

1. Schritt: Beschreibung der Nutzer und ihrer Anforderungen

2.Schritt: Klassenkandidaten identifizieren

3. Schritt: Klassenkarten entwerfen