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 Teile der Definition bedürfen näherer Erläuterung:

Problemlösung

Damit ein Algorithmus ein Problem (genauer: eine Menge von gleichartigen Problemen) lösen kann, muss das Problem zunächst definiert (spezifiziert) werden. Die Spezifikation beschreibt, was der Algorithmus erreichen soll, sagt aber nichts über das wie. Der Algorithmus repräsentiert dann einen bestimmten Lösungsweg. Mit Hilfe der Spezifikation muss gezeigt werden, dass der Algorithmus tatsächlich eine Lösung des gestellten Problems liefert. Diese Frage untersuchen wir im Kapitel Korrektheit.

Endlich viele Schritte

Die Forderung nach 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 verstehen wir unter einem elementaren Schritt ein Teilproblem, für das bereits ein Algorithmus bekannt ist. Was dies genau bedeutet, hängt vom Kontext ab. Im Zusammenhang mit Computern kann der Begriff stets auf die Berechenbarkeitstheorie zurückgeführt werden. Schritte gelten demnach als elementar, wenn sie Grundoperationen einer Turingmaschine (oder einer äquivalenten Formalisierung, wie beispielsweise Lambda-Kalkül, μ-Rekursion oder WHILE-Programm) sind. Dies ist Gegenstand der theoretischen Informatik. Für uns ist diese Problemzerlegung aber zu feinkörnig. Eine geeignetere Definition besagt, dass Operationen elementar sind, wenn sie von einer typischen Programmiersprache und einer typischen Bibliothek von Unterprogrammen unterstützt werden. In unserem Falle sind das die Operationen und Bibliotheken der Programmiersprache Python.

Zur Geschichte

Algorithmen wurden bereits im Altertum verwendet. Besonders die alten Griechen haben Pionierarbeit geleistet, z.B. auf dem Gebiet der Arithmetik (Euklidischer Algorithmus für den größten gemeinsamen Teiler von zwei Zahlen, Sieb des Eratosthenes zur Bestimmung von Primzahlen) und der Geometrie (Teilung einer Strecke oder eines Winkels nur mit Zirkel und Lineal). Der Begriff Algorithmus ist vom Namen des arabischen Gelehrten Muhammed Al Chwarizmi (ca. 783-850) abgeleitet, der in seinem Werk „Über das Rechnen mit indischen Ziffern“ (um 825) grundlegende Verfahren für das Rechnen im dekadischen Positionssystem beschrieben hat. In der mittelalterlichen lateinischen Übersetzung begann dieses Buch mit den Worten Dixit Algorismi („Algorismi hat gesagt“). Seine leicht verständlichen, schrittweisen Anleitungen haben sich im Laufe der Zeit so verbreitet, dass Problemlösungen in elementaren Schritten generell als Algorithmen (griechische Schreibweise des Namens) bezeichnet wurden.

Standbild Al Chwarizmis in Teheran

Definition von Datenstrukturen

Der Speicher eines Computers enthält eine Folge von Zeichen aus einem gegebenen Alphabet. Bei fast allen heutigen Computern ist dies eine Folge von Bits aus dem Alphabet {0,1}. Eine Datenstruktur ordnet eine Bitfolge in Gruppen und gibt jeder Gruppe eine Bedeutung. Der Gruppierungsprozess kann dann hierarchisch wiederholt werden.