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 weiteren Sinne verstehen wir unter einem elementaren Schritt ein Teilproblem, für das bereits ein Algorithmus bekannt ist. Im engeren Sinne ist die Menge der elementaren Schritte durch die Hilfsmittel vorgegeben, mit der der Algorithmus ausgeführt werden soll. Wir gehen darauf unten näher ein.

Zur Frage der elementaren Schritte

Welche Schritte als elementar angesehen werden können, hängt sehr stark vom Kontext der Aufgabe ab. Ein interesssantes Beispiel ist die Geometrie der alten Griechen, wo geometrische Probleme in der Ebene allein mit Zirkel und Lineal gelöst werden. In diesem Fall sind folgenden elementare Operationen erlaubt:

• das Markieren eines Punktes (beliebig in der Ebene oder als Schnittpunkt zwischen bereits gezeichneten Linien),
• das Zeichnen einer Geraden durch zwei Punkte,
• das Zeichnen eines Kreises um einen Punkt,
• das Abgreifen des Abstands zwischen zwei Punkten mit dem Zirkel.

Auf der Basis dieser Operationen kann zum Beispiel kein Algorithmus für die Dreiteilung eines Winkels definiert werden, während der Algorithmus für die Zweiteilung ganz einfach ist.

Eine völlig andere Menge von elementaren Operationen ergibt sich für arithmetische Berechnungen mit Hilfe des Abacus (Rechenbrett), der seit der Römerzeit in Europa weit verbreitet war. Hier werden Zahlen durch die Position und Berechnungen durch das Verschieben von Perlen auf Rillen oder Drähten dargestellt. Eine ausführliche Beschreibung der wichtigsten Abacus-Algorithmen findet sich unter The Bead Unbuffled von Totton Heffelfinger und Gary Flom.

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. Im 12. Jahrhundert wurde das Buch ins Lateinische übersetzt. Es begann mit den Worten „Dixit Algorismi“ (Al Chwarizmi hat gesagt) bzw. „Algoritmi de numero Indorum“ (Al Chwarizmi über die indischen Zahlen). Ursprünglich diente der Begriff zur Abgrenzung des schriftlichen Rechnens mit indischen (arabischen) Zahlen, wie wir es noch heute in der Schule erlernen, vom traditionellen mechanischen Rechnen mit dem Abacus, das bis ins 15. Jahrhundert in Europa vorherrschend blieb. Aber auch die allgemeinere Bedeutung des Wortes Algorithmus als systematische Rechenvorschrift war schon früh gebräuchlich. Dies zeigt zum Beispiel der Titel des Buches „Algorismus proportionum“ (Rechnenkunst mit Proportionen, ca. 1350) von Nicole Oresme, wo erstmals die Rechenregeln für Potenzen mit rationalen Exponenten beschrieben werden. Die algorithmische Denkweise verbreitete sich besonders im 16. Jahrhundert durch die Anforderungen des kaufmännischen Rechnens und der Navigation. Werke wie Adam Rieses „Rechnen auf der linihen und federn“ (1522) machten Rechenalgorithmen erstmals einem breiten Bevölkerungskreis bekannt. Umfangreiche Tafelwerke, z.B. der „Canon“ von G.J. Rhaeticus (1551), der bis zu siebenstellige Tabellen der trigonometrischen Funktionen enthält, erlaubten es, komplizierte Berechnungen auf einfache Schritte (Addition, Subtraktion sowie Nachschlagen in der Tabelle) zurückzuführen. Die heutige Verwendung des Begriffs geht auf Alonso Churchs Aufsatz „An Unsolvable Problem of Elementary Number Theory“ (1936) zurück, wo die Berechenbarkeit einer Funktion durch die Existenz eines terminierenden Berechnungsalgorithmus definiert wird.

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.