Algorithmen

Ein Algorithmus ist eine endliche Folge von eindeutig definierten Schritten, die der Reihe nach ausgeführt wird, um ein Problem zu lösen oder eine Berechnung durchzuführen. Er nimmt Eingaben entgegen, produziert Ausgaben und terminiert nach einer endlichen Anzahl von Schritten. Er kann in verschiedenen Formen vorliegen, etwa als Flussdiagramm, Pseudocode oder Programm in einer Programmiersprache.

Zu den zentralen Eigenschaften gehören Eindeutigkeit der Anweisungen, Determinismus (bei gleichen Eingaben liefert er dieselben Ergebnisse), Endlichkeit, Effektivität und Generalität. Der Algorithmus endet bei jeder zulässigen Eingabe nach endlich vielen Schritten und lässt sich unabhängig von der konkreten Implementierung verstehen.

Historisch reichen die Ursprünge der Algorithmen bis in die Antike: Der Euclidsche Algorithmus zur Bestimmung des größten gemeinsamen Teilers ist eines der frühesten bekannten Beispiele. Der Begriff Algorithmus leitet sich vom Namen des persischen Mathematikers al-Chwarizmi ab, dessen Werke im 9. Jahrhundert die Grundlage für das formale Verständnis von Berechnungen legten.

Zur Bewertung der Leistungsfähigkeit eines Algorithmus dienen Zeit- und Speicherbedarf. Die Komplexität wird oft mit der sogenannten Big-O-Notation beschrieben, die das Wachstum des Ressourcenverbrauchs in Abhängigkeit von der Eingabemenge angibt.

Algorithmen lassen sich klassifizieren als deterministisch oder nichtdeterministisch; rekursiv oder iterativ; außerdem als heuristisch, probabilistisch oder randomisiert.

Wichtige Beispiele sind Sortieralgorithmen (Quicksort, Mergesort), Suchalgorithmen (Binärsuche), Graphalgorithmen (Dijkstra, Bellman-Ford) und Techniken der dynamischen Programmierung.

Nicht alle Probleme sind berechenbar oder lösbar. Der Halteproblem beweist, dass es unmöglich ist, für jedes Programm zu entscheiden, ob es terminiert. Solche Grenzen bestimmen das Feld der theoretischen Informatik und der Formalsprachen.