Einführung

Definition von Algorithmen

Es gibt viele Definitionen von Algorithmen. Hier sind die Ergebnisse einer Google-Suche auf englisch und auf deutsch. Die Grundidee ist aber immer gleich:

Ein Algorithmus ist eine Problemlösung durch endlich viele, elementare Schritte. Die Elemente der Definition bedürfen näherer Erläuterung:

Problemlösung

Ein Algorithmus hat die Aufgabe, ein Problem (oder genauer: eine Menge von gleichartigen Problemen) zu lösen. Dazu ist es notwendig, dass das Problem zunächst definiert (spezifiziert) wird. Die Spezifikation beschreibt, was der Algorithmus erreichen soll, sagt aber nichts über das wie. Der Algorithmus selbst repräsentiert einen bestimmten Lösungsweg für das Problem. Mit Hilfe der Spezifikation muss man danach prüfen, dass der Algorithmus tasächlich eine Lösung des gegebenen Problems darstellt. Diese Frage untersuchen wir im Kapitel [Korrektheit].

Endlich viele Schritte

Die Forderung von endlich vielen Schritten unterstellt, dass jeder einzelne Schritt eine gewisse Zeit benötigt, also nicht unendlich schnell ausgeführt werden kann. Damit ist diese Forderung äquivalent zu der Forderung, dass der Algorithmus in endlicher Zeit zum Ergebnis kommen muss. Der Sinn einer solchen Forderung leuchtet aus praktischer Sicht unmittelbar ein. Interessant ist darüber hinaus die Frage, wie man mit möglichst wenigen Schritten, also möglichst schnell, zur Lösung kommt. Diese Frage untersuchen wir im Kapitel [Effizienz].

Elementare Schritte

Im allgemeinsten Sinne sind elementare Schritte