Algorithmen und Datenstrukturen at Universität Erlangen-Nürnberg

• Endlichkeit:

  • Die Beschreibung ist endlich lang.

• Terminierung:

  • Nach Durchführung endlich vieler Operationen kommt das Verfahren zum Stillstand.

• eindeutige Reihenfolge:

  • Die Reihenfolge, in der Operationen anzuwenden sind, ist festgelegt.

• eindeutige Wirkung:

  • Die Wirkung jeder Anweisung der Anweisungsfolge und damit der gesamten Folge ist eindeutig festgelegt.

• Hinweis: die Eigenschaft der Terminierung wird manchmal auch weggelassen, um auch z. B. auch nicht abbrechende Server- Prozesse zu umfassen

Übersetzungszeit = bei der Übersetzung;

Laufzeit = Während das Programm läuft;

- Muss deklariert werden

- Hat Namen und Datentyp

- Verweist bei Objekt nur auf Objektreferenz

O(1)

- O(n)

- Iteration mit jeweils Merken des kleinsten Elements

- Schlüsselwort final

- nur lesender Zugriff

- Konvention: Groß geschrieben

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 𝑛∈ℕ