1.5    Algorithmenbegriffe

Mit Algorithmen sind Sie seit der Schulzeit vertraut, möglicherweise ohne dass Sie diesen Begriff benutzt oder gekannt haben. Das war z. B. der Fall, als wir das schriftliche Multiplizieren oder Dividieren gelernt haben: Um richtige Ergebnisse zu erhalten, mussten wir genau vorgeschriebene Rechenschritte als Handlungsanweisungen befolgen. Diese Schritte machen einen Algorithmus aus.

Da es in diesem Buch darum gehen soll, Algorithmen zu entwickeln und als Python-Quelltext zu implementieren, ist es zunächst sinnvoll, sich genauer anzuschauen, wie der Begriff Algorithmus in der Fachliteratur definiert wird:

1. »Algorithmen sind eindeutige und endliche Handlungsvorschriften.« [Oldenburg: 1]

2. »Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems.« [Gumm: 91]

3. »Ein Algorithmus ist ein automatisierbares Verfahren, das einen Input zu einem Output verarbeitet. Diese Verarbeitung geschieht

   1. in endlich vielen Schritten, von denen jeder in endlicher Zeit zu einem Abschluss kommt, ... und

   2. so, dass jeder Schritt aus einer präzisen, unmissverständlichen und unzweideutig formulierten Anweisung besteht.« [Barth: 8]

4. »Der Begriff Algorithmus wird in der Informatik verwendet, um ein Verfahren zur Lösung eines Problems zu beschreiben, das für die Realisierung in Form eines Programms geeignet ist.« [Sedgewick: 22]

In der ersten Definition wird die Eindeutigkeit und Endlichkeit betont. Dass ein Algorithmus nicht die Bedingung der Endlichkeit erfüllt, kommt z. B. bei einer fehlerhaft programmierten while-Schleife vor.

Die zweite Definition hebt den schrittweisen Charakter der Problemlösung hervor. Das komplexe Ganze sollte in übersichtliche Teilprobleme zerlegt werden.

Die dritte Definition betont die Automatisierbarkeit. Das Problem muss so formuliert und beschrieben werden, dass es von einem Computer auch gelöst werden kann. Die Eingaben (Input) müssen immer die gewünschten Ausgaben (Output) erzeugen.

Die vierte Definition verweist auf die Programmierbarkeit des Problems. Der Algorithmus muss so beschrieben werden, dass er sich auch als Programm implementieren lässt. Der Quelltext eines Programms ist dann die formulierte Endversion des Algorithmus.

Anforderungen an einen mathematischen Algorithmus

An einen mathematischen Algorithmus werden folgende Anforderungen gestellt:

• Er sollte stabil sein. Diese Anforderung scheint selbstverständlich zu sein. Die Berechnung des Differenzenquotienten erfüllt diese Anforderung aber nicht (Kapitel 9, »Numerische Differenziation«).

• Er sollte möglichst schnell konvergieren. Diese Anforderung erfüllt z. B. das Newton-Verfahren zur Nullstellensuche (Kapitel 8, »Nullstellen berechnen«).

• Er sollte eine möglichst kurze Laufzeit haben. Bei der Multiplikation von Matrizen steigt die Laufzeit mit der 3. Potenz der Anzahl der Elemente. Der Strassen-Algorithmus kann die Laufzeit zwar verkürzen, seine Implementierung verlangt aber einen höheren Aufwand.

• Er sollte möglichst wenig Speicherplatz belegen. Dieser Aspekt ist für die in diesem Buch behandelten Algorithmen nicht relevant.

Entwicklungsschritte

Algorithmen werden durch schrittweise Verfeinerung entwickelt. Zuerst wird das Problem ausführlich analysiert und beschrieben. Dann wird eine Grobstruktur festgelegt. Hierbei wird häufig Pseudocode verwendet. Unter Pseudocode versteht man eine knappe Beschreibung eines Problems mit reduzierten Sprachelementen, die unabhängig von der Syntax einer Programmiersprache gewählt werden, sich aber an deren Grundelementen orientieren. Pseudocode ist ein guter erster Schritt, um die eigenen Gedanken zu sortieren.

In einem letzten Schritt wird der Quelltext in einen Editor eingegeben, und anschließend wird das Programm, je nach Programmiersprache, mit einem Compiler oder Interpreter in Maschinensprache übersetzt, die von der Hardware des Computers ausgeführt werden kann. Ein Compiler erzeugt direkt ein ausführbares Programm, das unter Windows an der Dateiendung .exe erkennbar ist.

Ein Interpreter übersetzt den Quelltext Zeile für Zeile. Wenn Sie das Python-Programm test.py im Terminal ausführen wollen, dann müssen Sie den Befehl python test.py eingeben. Die Ausgabe erscheint dann im Terminal. Für das Erlernen des Programmierens sind interpretierende Programmiersprachen besser geeignet als Compilersprachen, weil die Entwicklungsumgebungen bei Programmierfehlern eine detaillierte Rückmeldung über die Art und den Ort des Fehlers schon während des Übersetzungsvorgangs im Konsolenfenster ausgeben.

Bei der Entwicklung von Algorithmen kommen grundsätzlich nur drei Strukturen vor: Sequenz, Verzweigung und Wiederholung – darauf werde ich in Kapitel 3, »Programmstrukturen«, eingehen. Es ist schon erstaunlich, dass mit nur drei Programmstrukturen alle lösbaren Probleme gelöst werden können.

Die Effizienz eines Algorithmus wird durch den Speicherplatzbedarf und die Laufzeitkomplexität (siehe Abschnitt 3.9) beschrieben. An der Anzahl der ineinander verschachtelten Schleifen kann schon die Komplexitätsklasse erkannt werden. Einfache Sortieralgorithmen bestehen immer aus zwei ineinander verschachtelten Schleifen. Sie haben deshalb eine quadratische Laufzeitkomplexität von O(n²). Das heißt: Wenn sich die Anzahl der zu sortierenden Elemente verdoppelt, vervierfacht sich die Laufzeit.

Viele Menschen bevorzugen ein Vorgehen, das durch Versuch und Irrtum geleitet ist. Scherzhaft wurde dieses Vorgehen auch als VHIT (vom Hirn ins Terminal) beschrieben. Ein ideales Vorgehen sollte aber immer aus einer ausführlichen Planung bestehen, die konservativ mit Papier und Bleistift beginnt.

Bevor Sie mit den Planungsschritten beginnen können, müssen Sie jedoch wissen, welche Datentypen und Datenstrukturen Python zur Verfügung stellt (siehe Kapitel 2, »Datentypen und Datenstrukturen«).