Basiert der Algorithmus z. B. auf einem wiederholten Ausführen von Einzelanweisungen, so sprechen wir von einem „iterativen Algorithmus“.

Erlauben wir weiterhin, dass sich ein Algorithmus auch selbst aufrufen darf, so sprechen wir von einem „rekursiven Algorithmus“.

In der Informatik wird Induktion benutzt, um Eigenschaften von Schleifen und rekursiv definierten Algorithmen nachzuweisen.

Greedy-Algorithmen, oder gierige Algorithmen, bilden eine spezielle Klasse von Optimierungsalgorithmen, die in der Informatik auftreten.

Sie zeichnen sich dadurch aus, dass sie schrittweise den Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis (berechnet durch eine Bewertungsfunktion) verspricht z. B. Gradientenverfahren, so etwa die Berechnung von Wechselgeld oder des kürzesten Wegs.

Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal.

Eine Anwendung eines solchen Greedy-Algorithmus im täglichen Leben ist die beispielsweise die Herausgabe von Wechselgeld.

Die Vorgabe lautet: Nimm jeweils immer die größte Münze unter dem Zielwert und ziehe sie von diesem ab. Verfahre derart bis Zielwert gleich null.

Will man beispielsweise 79 Cent zurückgeben, fängt der Algorithmus sofort mit dem höchsten Münzwert an und macht weiter, bis er den niedrigsten Münzwert erreicht hat, falls das nötig ist: 79 = 50 + 20 + 5 + 2 +2.

Beispiele für Greedy-Algorithmen sind:

• Dijkstra-Algorithmus: Suche nach einem minimalen Weg in einem Graphen,

• Kruskal-Algorithmus: Suche nach einem minimalen Spannbaum,

• Prim-Algorithmus: Suche nach einem minimalen Spannbaum.

Wenn wir es im Alltag mit einem komplexen und zunächst kaum überwindbaren Problem zu tun haben, erweist es sich meist als vorteilhaft, das zunächst unlösbar erscheinende Problem in kleinere Teilprobleme zu zerlegen und diese dann individuell für sich isoliert betrachtet zu lösen.

Nach Abschluss und erfolgreichem Lösen der Teilprobleme werden diese Teillösungen dann wieder zu einer Lösung kombiniert.

Dieses Vorgehen wird dabei auch als „teile und beherrsche“ bzw. „divide and conquer“ bezeichnet.

Als Extremfall des Teile-und-beherrsche-Vorgehens kann die dynamische Programmierung verstanden werden.

Dynamische Programmierung ist eine Methode zum algorithmischen Lösen eines Optimierungsproblems durch Aufteilung in Teilprobleme und systematische Speicherung von Zwischenresultaten.

Nach dem Greedy-Algorithmus würde so ausgehend von dem Startpunkt A immer eine Verbindung zu demjenigen Knoten erfolgen, welcher dem gerade besuchten am nächsten liegt.

Die Konsequenz daraus wäre, dass das Vorgehen nach Greedy dabei zu dem Pfad A-D-G-B führt und Gesamtkosten von 15 zur Folge hätte. Die dynamische Programmierung geht hierbei in ihrer Grundidee so vor, dass sie das globale Problem insgesamt betrachtet und sich nicht auf lokale Effekte beschränkt (wie Greedy).

Weiterhin wird eine optimale Lösung des kleineren Problems bestimmt, das aus den verbleibenden Entscheidungen besteht. Mit diesem weitreichenderen Ansatz findet sich im Städtegraphen damit ein Pfad der Länge 13, was effizienter ausfällt, als vom Greedy-Algorithmus bestimmt.

Die Besonderheit eines Greedy-Algorithmus besteht darin, dass dieser zu jedem Zustand seines Ablaufs versucht,

den momentan besten nächsten Schritt zu wählen,

und damit eine lokale Optimierungsstrategie erreicht.

Fehlerquellen, die die Korrektheit eines Algorithmus beeinflussen, ergeben sich z. B. durch (Harel/Feldman 2006, S. 119f.):

• Sprach- oder Syntaxfehler: Diese ergeben sich beispielsweise durch die Verwendung einer falschen Syntax einer Programmiersprache wie for Y from 1 until N do statt der korrekten Schreibweise for Y from 1 to N do.

• Logische oder semantische Fehler: Diese Art von Fehlern ergibt sich durch die logisch falsche Verwendung beispielsweise der Semantik eines Ausdrucks. So erhalten wir durch Verwendung der Aussage „Ich habe einen Geldbetrag von EUR 346.24 auf meinem Konto und bin reich. Ziemlich beachtlich, wenn man mein Talent zum Geldsparen beachtet“ (Harel/Feldman 2016, S. 120). Versuchen wir nun, diese zwei Sätze nach der Anzahl der Sätze mit dem Ausdruck „Geld.“ zu durchsuchen. Ein Algorithmus würde dabei zunächst nach der Zeichenkette „Geld“ suchen, gefolgt von dem Zeichenmuster „.“, welches das Ende eines Satzes kennzeichnet. Die Ausgabe wäre in diesem Fall der Satz Nummer 1, da nur im zweiten Satz die Zeichenkette „Geld“ isoliert vorkommt. Nehmen wir abweichend an, ein Satzende würde durch „.“ gekennzeichnet werden. Dieser Algorithmus würde bei Anwendung auf den oben diskutierten Satz die Ausgabe 2 erzeugen, da die Zeichenkette „Geld“ sowohl in „Geld“ als auch im zweiten Satz als „Geld“ zu finden ist. Der Algorithmus lässt sich dabei künstlich durch den Punkt als Trennzeichen im Geldbetrag täuschen. Dies ist das Konzept eines logischen Fehlers. Weiterführend können sich logische Fehler durch eine nicht adäquat formulierte Entscheidungskette in If-else-Unterscheidungen ergeben.

• Endlosschleifen: Diese nicht-terminierenden Schleifen ergeben sich z. B. durch eine unpräzise oder fehlerhafte Definition des Abbruchkriteriums einer Schleife. Formulieren wir beispielsweise eine Schleife in der Form

  
  

Unter der Verifikation eines Algorithmus wird ein Testumfeld verstanden, bei dem geprüft wird, ob ein Algorithmus bei einer vordefinierten Eingabe stets zu einer deterministischen und reproduzierbaren Ausgabe führt.

Diese nicht-terminierenden Schleifen ergeben sich z. B. durch eine unpräzise oder fehlerhafte Definition des Abbruchkriteriums einer Schleife.

Da sie aufgrund der fehlenden Anweisung zur Erhöhung der Schleifenvariablen i nie die Abbruchbedingung der While-Schleife erreichen wird.

Dies zeigt einen Selection Sort Algorythmus.

Betrachten wir im Folgenden ein Beispiel, für das nicht automatisch klar ist, ob der Algorithmus für jede Eingabe terminiert. Dieses Beispiel ist auch als die „Collatz-Vermutung“ bekannt, welche vermutet, dass der Algorithmus für jede Eingabe n € ℕ terminiert

Partiell korrekt= wenn die gelieferten Ergebnisse für alle Eingabewerte korrekt sind, der Algorithmus aber nicht notwendigerweise für jede zulässige Eingabe terminiert.

total korrekt = Fordern wir, dass ein korrekter Algorithmus für alle zulässigen Eingaben auch terminiert, so bezeichnen wir diesen als „total korrekt“.

Die Laufzeitbestimmung eines Algorithmus hat zum Ziel, eine obere asymptotische Grenze zu finden, der sich die Laufzeit des Algorithmus in Abhängigkeit der zur Berechnung notwendigen Rechenschritte annähert.

log(log(n)) = doppelt logarithmisch

log(n) = logarithmisch

n = linear

n · log(n) = quasi-linear

n2 = quadratisch

2n = exponentiell

Wenn für die Laufzeit des Algorithmus O(n^k) gilt.

Wenn es zur Lösung des Problems einen nichtdeterministischen Algorithmus gibt, welcher eine polynominelle Laufzeit aufweist.

Die Grundidee der Turingmaschine.

Turingmaschinen werden vor allem für Entscheidungsprobleme verwendet, also insbesondere Fragen die mit „ja/nein“ beantwortet werden können.