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 beliebigen Winkels definiert werden, während der Algorithmus für die Zweiteilung sehr 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 Positionen von Perlen auf Rillen oder Drähten dargestellt und Berechnungen durch deren Verschiebung. Eine ausführliche Beschreibung der wichtigsten Abacus-Algorithmen findet sich unter The Bead Unbuffled von Totton Heffelfinger und Gary Flom.

Die moderne Auffassung von elementaren Operationen wird durch die Berechenbarkeitstheorie, einem Teilgebiet der theoretischen Informatik, bestimmt. Verschiedene Mathematiker (darunter die Pioniere Alan Turing, Alonso Church, Kurt Gödel, Stephen Kleene und Emil Post) haben seit den 1930er Jahren versucht, den intuitiven Begriff der Berechenbarkeit einer Funktion zu formalisieren und sind dabei auf völlig verschiedene Lösungen gekommen (z.B. Turingmaschine, Lambda-Kalkül, μ-Rekursion und WHILE-Programm). Interessanterweise stellte sich heraus, dass diese Lösungen alle die gleiche Mächtigkeit haben: Obwohl die elementaren Operationen jeweils ganz verschieden definiert sind, ist die Menge der damit berechenbaren Funktionen immer gleich. Die Church-Turing-These besagt, dass es prinzipiell unmöglich ist, eine mächtigere Definition von elementaren Operationen zu finden, aber dies ist unbewiesen. Am bequemsten für die Praxis sind die elementaren Operationen eines WHILE-Programms (in erweiterter Backus-Naur Notation):

P ::= x[i] = x[j] + c
      P; P
      WHILE x[i] != 0 DO P DONE

wobei c ein beliebiges ganzahliges Literal (eine ausgeschriebene ganze Zahl) und x[i] die Speicherzelle i bezeichnet. Alle Speicherzellen können ganze Zahlen aufnehmen und sind anfangs mit Null belegt. Darüber hinaus wird vorausgesetzt, dass mindestens soviele Speicherzellen vorhanden sind, wie der gegebene Algorithmus benötigt, und jede Speicherzelle groß genug ist, um die größte auftretende Zahl aufzunehmen. Beide Annahmen sind in der Praxis nicht immer erfüllt.

Die Zerlegung jedes Problems in Form eines WHILE-Programms (oder eines äquivalenten Formalismus der Berechenbarkeitstheorie) ist für unsere Zwecke aber zu feinkörnig: Sie würde bedeuten, dass alle Algorithmen auf einem sehr einfachen Prozessor in Assembler programmiert werden müssten. Statt dessen definiert man höhere Programmiersprachen, die wichtige Algorithmen wie z.B. die arithmetischen Operationen mit ganzen Zahlen und Gleitkomma-Zahlen bereits als elementare Operationen anbieten. Weitere nicht ganz so wichtige Funktionen wie die Wurzel oder der Logarithmus werden in Programmbibliotheken angeboten, die standardmäßig mitgeliefert werden. In der Praxis betrachtet man eine Operation deshalb als elementar, wenn sie von einer typischen Programmiersprache oder einer typischen Standardbibliothek unterstützt wird. In dieser Vorlesung wählen wir die Operationen und Bibliotheken der Programmiersprache Python. Wenn ein Algorithmus Anforderungen stellt, die nicht selbstverständlich sind, müssen sie als Requirements explizit angegeben werden. Wir werden darauf im Kapitel Generizität zurückkommen.

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 dieses Buch ins Lateinische übersetzt. Die Übersetzungen begannen 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“ (Rechenkunst 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.

Man betrachte z.B. die Folge von 32 Bits:

11111100011000100110010101101110

Wenn wir sie in vier Gruppen von 8 Bit gruppieren, und die Gruppen als Zeichencodes im Latin-1 Zeichensatz interpretieren, erhalten wir:

11111100 01100010 01100101 01101110 => üben

Interpretieren wir dieselben Gruppen hingegen als Farbe im RGBA System, erhalten wir ein halbtransparentes Rosa (Rot: 252, Grün: 98, Blau: 101, Alpha: 110). Alternativ können wir die gesamte Folge von 32 Bits als positive ganze Zahl in Binärdarstellung (unsigned integer) interpretieren, dies ergibt die Dezimalzahl 4234306926. Eine weitere Interpretation ist die als vorzeichenbehaftete ganze Zahl in Zweierkomplement-Darstellung (signed integer): -60660370. Gruppiert man hingegen so