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 legt fest, was der Algorithmus erreichen soll, sagt aber nichts über das wie. Die Spezifikation beschreibt somit relevante Eigenschaften des Systemzustands vor und nach der Ausführung des Algorithmus (sogenannte Vor- und Nachbedingungen), während der Algorithmus einen bestimmten Lösungsweg repräsentiert. Mit Hilfe der Spezifikation kann 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 denen der Algorithmus ausgeführt werden soll, also z.B. durch die Hardware oder die Programmiersprache. 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 und den Hilfsmitteln zu ihrer Lösung 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 die Einleitung begann mit den Worten „Dixit Algorismi“ (Al Chwarizmi hat gesagt). Ab etwa 1200 wurden die neuen Rechenmethoden als „Algorismus de integris“ bzw. „Algorismus vulgaris“ (Rechnen mit ganzen Zahlen, d.h. Grundrechenarten und Wurzelziehen) sowie „Algorismus de minutiis“ (Bruchrechnung) zum festen Bestandteil der mathematischen Ausbildung im Rahmen der sieben freien Künste. Dabei diente der Begriff Algorithmus unrsprünglich 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. Durch die steigenden Anforderungen des kaufmännischen Rechnens und der Navigation verbreitete sich die algorithmische Denkweise ab etwa 1500 rasch. 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 wohl auf Alonso Church's 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.

Die selben Bits können somit völlig verschiedene Bedeutungen annehmen, ja nachdem in welcher Datenstruktur sie sich befinden. 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 Gruppen werden als nicht-negative Binärzahlen gelesen, wobei die erste Gruppe das Vorzeichen s der Gleitkommazahl ist (0 bedeutet "+", 1 bedeutet "-"), die zweite ist ihr Exponent exp und die dritte die Mantisse m (Hier gilt s = 1, exp = 248 und m = 6448494). Die Umrechnung in eine Gleitkommazahl erfolgt, gemäß IEEE Standard, nach folgender Formel:
z = (1 - 2*s) * 2^exp-127 * (1 + m * 2^-23).
In Dezimaldarstellung ist dies rund -4.7020653*10³⁶.

Im Sinne einer hierarchischen Gruppierung können wir jetzt z.B. eine Datenstruktur "Farbbild" definieren, indem wir viele RGBA-Werte zu einem 2-dimensionalen Array zusammenfassen. Eine Datenstruktur "komplexe Zahl" wird durch ein geordnetes Paar von Gleitkommazahlen gebildet, eine "Meßreihe" als Liste von ganzen Zahlen oder Gleitkommawerten (je nach Art der Messung), usw.

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. Programmiersprachen, die ausgereifte Mechanismen zur Definition von Klassen bieten, werden als objekt-orientiert bezeichnet. Sprachen heißen streng typisiert, wenn der Compiler bzw. Interpreter der Sprache sicherstellt, dass auf jeder Datenstruktur nur die jeweils explizit erlaubten Operationen ausgeführt werden (jeder Versuch, eine illegale Operation auszuführen, wird hier als Fehler signalisiert). Erfolgt diese Prüfung während der Compilierung (also während der Übersetzung des Quellcodes in eine Maschinensprache), spricht man von einer statisch typisierten Sprache. Wird die Prüfung hingegen während der Ausführung des Programms durchgeführt, handelt es sich um eine dynamisch typisierte Sprache. Python ist eine dynamisch-typisierte, objekt-orientierte Sprache. Streng typisiert ist sie allerdings nur für die vordefinierten Klassen. Bei benutzerdefinierten Klassen gibt es (wie bei den meisten anderen Programmiersprachen auch) Möglichkeiten, die erlaubten Operationen zu umgehen. Dies sollte man allerdings nur dann tun, wenn es einen wichtigen Grund gibt. Solange man sich nämlich auf die erlaubten Operationen beschränkt, ist eine große Menge von Fehlerquellen von vornherein ausgeschlossen.

Ein bestimmter Speicherbereich, der den Anforderungen an eine Klasse genügt (wo also die Bits in entsprechender Weise gruppiert und interpretiert werden), wird als Objekt dieser Klasse oder als Instanz bezeichnet. Jede Instanz hat eine eindeutige Identität, einen Schlüssel. Innerhalb eines Programms wird dafür gewöhnlich die Speicheradresse des ersten Bytes der Instanz (also der Index der ersten Speicherzelle) verwendet. Dies ist besonders effizient, weil die Speicheradresse für jedes Objekt eindeutig und leicht feststellbar ist. Ist das Objekt hingegen als Datei gespeichert, benötigt man einen expliziten Schlüssel, z.B. den Dateinamen oder die URL.

Das Bitmuster selbst bzw. die daraus folgende Interpretation wird als Zustand oder Wert der Instanz bezeichnet. Daraus folgt, dass verschiedene Instanzen einer Klasse dennoch gleiche Werte haben können. Die Menge aller legalen Werte bilden den Wertebereich der Klasse. Werden Instanzen ausschließlich mit den explizit erlaubten Operationen ihrer Klasse manipuliert, können niemals illegale Werte entstehen. Es liegt auf der Hand, dass illegale Werte schwerwiegende Programmfehler darstellen, die man auf diese Weise vermeidet. [Computerviren tun genau das Gegenteil: Sie verwenden absichtlich verbotene Operationen, um dass Programm in einen illegalen, vom Angreifer gewünschten Zustand zu bringen. Dies ist möglich, weil nicht alle verbotenen Operationen automatisch als Fehler erkannt werden, siehe oben.]

Die meisten Programmiersprachen haben einen oder mehrere spezielle Typen für das Speichern von Objektschlüsseln. Die gebräuchlichsten Namen für diese Typen sind Zeiger (pointer), Referenz (reference) und Handle. Wir verwenden das Wort Referenz. Ein Objekt der Klasse Referenz enthält also den Schlüssel eines anderen Objekts. Man sagt, dass die Referenz auf das andere Objekt verweist. Diese Art der Indirektion ist uns heutzutage durch das Internet bestens vertraut: Jede WWW-Seite ist ein Objekt, und seine URL ist der dazugehörige Schlüssel. Hyperlinks und Lesezeichen (bookmarks) hingegen sind Refernzen, die mittels der URL auf andere Seiten verweisen.

Aus der Unterscheidung von Werten und Referenzen ergibt sich die wichtige Unterscheidung von Wertsemantik und Referenzsemantik. Wird nämlich ein Objekt an eine Variable zugewiesen

x = anObject

so hängt die korrkte Verwendung der Variablen x davon ab, ob sie das Objekt in Form eines Wertes oder einer Referenz speichert. Im ersten Fall wird das Objekt selbst kopiert, und es entsteht ein neues Objekt mit neuer Identität, aber gleichem Zustand. Im andern Fall wird nur der Schlüssel kopiert, und die Referenz verweist nach wie vor auf das ursprüngliche Objekt. Ist x ein Wert, so verändert eine Manipulation von x nur das neue Objekt (das ursprüngliche bleibt erhalten). Ist x hingegen eine Referenz, wird immer das ürsprüngliche Objekt manipuliert (denn es gibt ja keine Kopie). Ob eine Variable einen Wert oder eine Referenz enthält, wird in jeder Programmiersprache anderes festgelegt. In Python gilt

• Zahlen (Typen bool, int, und float) werden immer als Werte gespeichert und kopiert.
• Alle anderen Typen werden als Referenzen gespeichert und kopiert.
• Für alle Typen kann Wertsemantik mit Hilfe des Python-Moduls copy erzwungen werden.

Das Verständnis von Werten und Referenzen wird in der 1. Übung vertieft.

Der Entwurf von Datentypen wird uns im Laufe der Vorlesung immer wieder beschäftigen.

Fundamentale Algorithmen

Einige Algorithmen werden praktisch bei jeder Klasse benötigt, unabhängig vom eigentlichem Verwendungszweck der Klasse. Es ist wichtig, diese fundamentalen Algorithmen zu kennen. Außerdem eignen sie sich gut zur Einführung der Grundprinzipien der Algorithmen-Spezifikation. In der Algorithmen-Spezifikation ist es üblich, den Zustand der Objekte nach dem Aufruf des Algorithmus (also die Nachbedingungen, Post-Conditions) durch gestrichene Variablen (x', y', z' usw.) und Prädikate über diesen Variablen zu bezeichnen, den Zustand vor Aufruf des Algorithmus (die Vorbedingungen, Pre-Conditions) durch Prädikate über die entsprechenden ungestrichenen Variablen (x, y, z).

Die wichtigste Gruppe von fundamentalen Funktionen sind die Konstruktoren, die einen vorher unbenutzten Speicherbereich in eine Datenstruktur mit einem wohldefinierten Anfangswert transformieren. In Python haben die Konstruktoren im allgemeinen den gleichen Namen wie die dazugehörige Klasse, also z.B.

i = int()   # erzeuge eine ganze Zahl mit Anfangswert 0
f = float() # erzeuge eine Gleitkommazahl mit Anfangswert 0
a = list()  # erzeuge ein leeres Array

usw. (Man beachte, dass das Python-Array den Klassennamen list hat. Dies hat nichts mit verketteten Listen zu tun.) Konstruktoren ohne Argumente bezeichnet man als Standard-Konstruktoren (default constructors). Ja nach Typ gibt es meist noch weitere Konstruktoren, die Objekte mit anderen Anfangswerten erzeugen, z.B.

i = int(2)     # erzeuge eine ganze Zahl mit Anfangswert 2
i = 2          # ebenso (abgekürzte Schreibweise)
f = float(1.5) # erzeuge eine Gleitkommazahl mit Anfangswert 1.5
f = 1.5        # ebenso (abgekürzte Schreibweise)
a = [i, f]     # erzeuge ein Array mit Kopien der Werte von i und f

(Das Array a enthält Kopien der Werte, weil Zahlen immer mit Wertsemantik zugewiesen werden.) Die allgemeine Spezifikation eines Standard-Konstruktors lautet

<math>\begin{array}{ll} \mathrm{Precondition: } & T \in \mathrm{Types}\\ \mathrm{Constructor: } & t = T() \\ \mathrm{Postcondition: } & t' \in T \end{array}</math>

Der Ausdruck <math>t' \in T</math> besagt, dass t nach Ausführung des Konstruktors eine legale Instanz des Typs T (oder eine Referenz auf einen solche Instanz) sein muss. In Pythonsyntax kann dies folgendermassen geschrieben werden

import inspect  # wir brauchen das inspect-Modul

if inspect.isclass(T):
     t = T()
assert isinstance(t, T)

Natürlich funktioniert der Code nur, wenn die Klasse T tatsächlich existiert und dafür ein Standardkonstruktor definiert wurde. Das Gegenstück zu Konstruktoren sind die Destruktoren, die den Speicher der Datenstruktur wieder frei geben. Da Python automatisches Speichermanagment unterstützt, werden die Destruktoren automatisch aufgerufen. Wir können sie deshalb hier übergehen.

Sehr wichtig sind auch die Vergleichsoperatoren. Wir müssen dabei unterscheiden, ob auf Gleichheit der Referenzen (identity) oder auf Gleichkeit der Werte (equality) geprüft werden soll. In Python werden dazu die Operatoren is bzw. == verwendet. Die Negation erhält man durch is not bzw. !=

a = [1, 2]
b = [1, 2]

a == b      # True  weil gleiche Werte
a != b      # False weil Negation
a is b      # False weil unterschiedliche Identität
a is not b  # True  weil Negation

(Beachte: beim Vergleich von Zahlen des gleichen Typs liefern is und == immer dasselbe Ergebnis.) Natürlich impliziert die Gleichheit der Schlüssel (Identität der Objekte) die Gleichheit der Werte.

Ebenso wichtig sind die Zuweisungen. Hier zeigt sich besonders der Unterschied zwischen Wert- und Referenzsemantik. Im Falle von Wertsemantik gilt

<math>\begin{array}{ll} \mathrm{Preconditions: } & s,t \in T \\

                        & s \mathrm{\ is\ not\ } t \\

\mathrm{Assign\ by\ value: } & s = t \\ \mathrm{Postconditions: } & t' \mathrm{\ is\ } t \\

                         & s' \mathrm{\ is\ not\ } t' \\
                         & s' == t' 

\end{array}</math>

Das heisst, t darf sich nicht verändern, und s hat nach der Zuweisung den gleichen Wert wie t. Bei Referenzsemantik gilt sogar

<math>\begin{array}{ll} \mathrm{Precondition: } & t \in T \\ \mathrm{Assign\ by\ reference: } & s = t \\ \mathrm{Postconditions: } & t' \mathrm{\ is\ } t \\

                         & s' \mathrm{\ is\ } t'

\end{array}</math>

Dies entspricht dem Pythoncode

x = y
assert x is y

Die Wertsemantik muss man in Python explizit erzwingen

import copy  # wir brauchen das copy-Modul
x = copy.deepcopy(y)
assert x == y
assert x is not y

Mit der Zuweisung eng verwandt ist die Funktion swap, die den Inhalt von zwei Variablen vertauscht:

<math>\begin{array}{ll} \mathrm{Precondition: } & t \in T, s \in S \\ \mathrm{Algorithmus\ swap: } & \mathrm{swap}(s, t) \\ \mathrm{Postconditions: } & t' \mathrm{\ is\ } s \\

                         & s' \mathrm{\ is\ } t

\end{array}</math>

Diese Funktion wird sich beim Sortieren als sehr nützlich erweisen, weil dort das Vertauschen von zwei Datenelementen eine Grundoperation ist. In Python kann man dies so implementieren:

t, s = s, t

Dabei macht man sich zunutze, dass Python mehrere Variablen in einem einzigen Statement zuweisen kann.