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 im nächsten Abschnitt 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 interessantes 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 folgende 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 (ein 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 zu völlig verschiedenen Lösungen gelangt (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 anders 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 WHILE-Programme, da sie sich direkt auf die heute gebräuchliche Hardware-Architektur abbilden lassen. Die elementaren Operationen eines WHILE-Programms lauten in erweiterter Backus-Naur Notation:

P ::= x[i] = x[j] + c
    | 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 enthalten. 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 und war nach 1200 fester Bestandteil der mathematischen Ausbildung im Rahmen der sieben freien Künste. Die Übersetzungen begannen mit den Worten „Dixit Algorismi“ (Al Chwarizmi hat gesagt) oder „Algoritmi de numero Indorum“ (Al Chwarizmi über die indischen Zahlen), später setzten sich die Bezeichnungen "Algorismus de integris" bzw. "Algorismus vulgaris" (Rechnen mit ganzen Zahlen, d.h. Grundrechenarten und Wurzelziehen) sowie "Algorismus de minutiis" (Bruchrechnung) durch. Ursprünglich diente der Begriff Algorithmus vor allem zur Abgrenzung des schriftlichen Rechnens mit indischen/arabischen Zahlen (wie wir es noch heute in der Schule lernen) vom traditionellen mechanischen Rechnen mit Abacus und römischen Zahlen, das noch bis ca. 1500 in Europa vorherrschend blieb. Die allgemeinere Bedeutung des Wortes Algorithmus als systematische Rechenvorschrift war jedoch ebenfalls 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. Der Buchdruck machte mit Werken wie Adam Ries' „Rechenung auff der linihen und federn“ (d.h. mit Abacus und mit indischen/arabischen Zahlen, zuerst 1522) die grundlegenden Rechenalgorithmen einem breiten Bevölkerungskreis bekannt. Umfangreiche gedruckte Tafelwerke, z.B. der „Canon“ von G.J. Rhaeticus (1551) mit bis zu siebenstelligen Tabellen der trigonometrischen Funktionen, erlaubten es, komplizierte Berechnungen auf einfache Schritte (Addition, Subtraktion sowie Nachschlagen in der Tabelle) zurückzuführen. Unsere heutige Verwendung des Begriffs geht auf Alonso Churchs Aufsatz „An Unsolvable Problem of Elementary Number Theory“ (1936) zurück, wo die Berechenbarkeit einer Funktion mit der Existenz eines terminierenden Berechnungsalgorithmus gleichgesetzt 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 fortgesetzt werden.

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

11111100011000100110010101101110

Wenn wir diese Folge als eine einzige Gruppe betrachten und als positive ganze Zahl in Binärdarstellung (unsigned integer) interpretieren, ergibt sich die Dezimalzahl 4234306926. Interpretieren wir dieselbe Gruppe als vorzeichenbehaftete ganze Zahl in Zweierkomplement-Darstellung (signed integer), ergibt sich statt dessen die Dezimalzahl -60660370.
Alternativ können wir die Folge in vier Gruppen zu 8 Bit gruppieren, und die Gruppen als Zeichencodes im Latin-1 Zeichensatz interpretieren. Wir erhalten die Zeichenkette "üben":

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).
Eine weitere Interpretation ist diejenige als 32-Bit Gleitkommazahl gemäß IEEE Standard 754 (float). Dabei wird die Folge in Gruppen zu 1 Bit, 8 Bit und 23 Bit eingeteilt:

1 11111000 11000100110010101101110

Die erste Gruppe wird als Vorzeichen s (0 bedeutet "+", 1 bedeutet "-"), die zweite als Exponent exp und die dritte als Mantisse m der Zahl gedeutet. Die Gruppen werden als nicht-negative ganze Zahlen gedeutet, wir haben also s == 1, exp == 248 und m == 6448494. Die Umrechnung in eine Gleitkommazehl erfolgt, gemäß IEEE Standard, nach folgender Fromel:
(1 - 2*s)*2^(exp-127)*(1 + m*2^-23).
In Dezimaldarstellung ist dies rund -4.7020653*10³⁶.

Die Bedeutung der einzelnen Gruppen ist dem Computer normalerweise nicht explizit bekannt. Vielmehr wird sie implizit durch die Menge der darauf ausführbaren Operationen definiert. Man bezeichnet die Verbindung einer Datenrepräsentation mit einer Menge von erlaubten Operationen als (Daten-)Typ oder als Klasse.