Algorithmus

Unter einem Algorithmus versteht man allgemein eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen in endlich vielen Schritten.

Im täglichen Leben lassen sich leicht Beispiele für Algorithmen finden: Zum Beispiel ist ein Kochrezept ein Algorithmus – zumindest dann, wenn alle Angaben genau genug sind und es für alle Teilaufgaben, wie beispielsweise Braten oder Rühren, ebenfalls Algorithmen gibt. Auch Reparatur- und Bedienungsanleitungenen oder Hilfen zum Ausfüllen von Formular sind in der Regel Algorithmen. Ein weiteres, etwas präziseres Beispiel sind Waschmaschinenprogramme.

Algorithmen können in Programmablaufplänen nach DIN 66001 oder ISO 5807 grafisch dargestellt werden.

Wortgeschichte

Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens von Muhammed Al Chwarizmi (* ca. 783; † ca. 850), dessen arabisches Lehrbuch Über das Rechnen mit indischen Ziffern (um 825) in der mittelalterlichen lateinischen Übersetzung begann mit den Worten Dixit Algorismi („Algorismi hat gesagt“). Im Mittelalter wurde daraus lat. algorismus (mit lat. Varianten wie alchorismus, algoarismus, altfranzösisch algorisme, argorisme, mittel-englisch augrim, augrym) als Bezeichnung für die Kunst des Rechnens mit den arabischen Ziffern und als Titel für Schriften über diese Kunst.

Die lateinischen Autoren pflegten zu erklären, dass das Wort 'algorismus' aus dem Namen des Erfinders dieser Kunst, eines Philosophen namens Algus, und dem griechischen Wort rismus (arhithmós) für 'Zahl' zusammengesetzt sei. Dabei wurde Algus von einigen als Araber, von anderen als Grieche oder zumindest griechisch schreibender Autor, gelegentlich auch als 'König von Kastilien' (Johannes von Norfolk) betrachtet. In der volkssprachlichen Tradition erscheint dieser 'Meister Algus' dann zuweilen in einer Reihe mit großen antiken Denkern wie Platon, Aristoteles und Euklid, so im altfranzösischen Roman de la Rose, während das altitalienische Gedicht Il Fiore ihn sogar als Erbauer des Schiffes Argo ausgibt, mit dem Jason sich auf die Suche nach dem Goldenen Vlies begab.

Durch Gräzisierung der Schreibweise des vermeintlich griechischen Wortbestandteiles rismus hat sich dann in der lateinischen Wissenschaftssprache die Schreibung 'algorithmus' ergeben; in dieser Form hat sich das Wort später als Fachterminus für geregelte Prozeduren zur Lösung definierter Probleme eingebürgert.

Informatik und Mathematik

Vor allem aber sind Algorithmen eines der zentralen Themen der Informatik und Mathematik. Sie sind Gegenstand einiger Spezialgebiete der Theoretischen Informatik, wie der Algorithmentheorie, der Komplexitätstheorie und der Berechenbarkeitstheorie. In Form von Computerprogrammen und elektronischen Schaltkreisen steuern sie Computer und andere Maschinen.

Algorithmus und Programme

Für Algorithmen gibt es unterschiedliche formale Repräsentationen. Diese reichen vom Algorithmus als abstraktes Gegenstück zum konkret auf eine Maschine zugeschnittenen Programm (d. h., die Abstraktion erfolgt hier im Weglassen der Details der realen Maschine, das Programm ist eine konkrete Form des Algorithmus, angepasst an die Notwendigkeiten und Möglichkeiten der realen Maschine) bis zur Ansicht, Algorithmen seien gerade die Maschinenprogramme von Turingmaschinen (wobei hier die Abstraktion in der Verwendung der Turingmaschine an sich erfolgt, d. h., einer idealen mathematischen Maschine).

Erster Computeralgorithmus

Der erste für einen Computer gedachte Algorithmus wurde 1842 von Ada Lovelaces in ihren Notizen zu Charles Babbage Analytical Engine, festgehalten. Sie gilt deshalb als die erste Programmiererin. Weil Charles Babbage seine Analytical Engine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert.

Definition

Turingmaschinen und Algorithmusbegriff

Die mangelnde mathematische Genauigkeit des Begriffs Algorithmus störte viele Mathematiker und Logiker des 19 und 20. Jahrhunderts, weswegen in der ersten Hälfte des 20. Jahrhunderts eine ganze Reihe von Ansätzen entwickelt wurde, die zu einer genauen Definition führen sollten. Formalisierungen des Berechenbarkeitsbegriffs sind die Turing-Maschine (Alan Turing), der Lambda-Kalkül (Alonzo Church), rekursive Funktionen, Chomsky-Grammatiken und Markow-Algorithmen.

Es wurde – unter maßgeblicher Beteiligung von Alan Turing selbst – gezeigt, dass all diese Methoden gleich leistungsfähig (gleich mächtig) sind. Sie können durch eine Turing-Maschine emuliert werden, und sie können umgekehrt eine Turing-Maschine emulieren.

Mit Hilfe des Begriffs der Turing-Maschine kann folgende formale Definition des Begriffs formuliert werden:

Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt.

Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar:

1. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
2. Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein (Ausführbarkeit).
3. Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, siehe Platzkomplexität).
4. Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung, siehe auch Zeitkomplexität).

Darüber hinaus wird der Begriff Algorithmus in praktischen Bereichen oft auf die folgenden Eigenschaften eingeschränkt:

1. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
2. Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).

Church-Turing-These

Die Church-Turing-These lautet: „Jedes intuitiv berechenbare Problem kann durch eine Turingmaschine gelöst werden.“ Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen, zu einer Turing-Maschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer Programmiersprache – die von Church verlangte Terminiertheit ist dadurch allerdings noch nicht gegeben.

Der Begriff der Berechenbarkeit ist dadurch dann so definiert, dass ein Problem genau dann berechenbar ist, wenn es einen (terminierenden) Algorithmus zu dem Problem gibt, d. h. wenn eine entsprechend programmierte Turing-Maschine das Problem in endlicher Zeit lösen könnte.

Abstrakte Automaten

Turingmaschinen harmonieren sehr gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen, reale Probleme sind jedoch ungleich komplexer, daher wurden andere Maschinen vorgeschlagen.

Diese Maschinen weichen z. B. in der Mächtigkeit der Befehle ab; anstatt den einfachen Operationen der Turingmaschine können sie z. T. mächtige Operationen, wie z. B. Fouriertransformationen, in einem Rechenschritt ausführen.

Oder sie beschränken sich nicht auf eine Operation pro Rechenschritt, sondern ermöglichen sehr parallele Operationen, wie z. B. die Addition zweier Vektorenen in einem Schritt.

Ein Modell einer realeren Maschine ist die Sequential Abstract State Machine (seq. ASM) mit folgenden Eigenschaften:

Ein Algorithmus einer seq. ASM soll

• durch einen endlichen Programmtext spezifiziert werden können
• schrittweise ausgeführt werden können
• für bestimmte Zustände terminieren, muss aber nicht immer terminieren (sinnvolle Gegenbeispiele für die Forderung, dass immer terminiert werden muss, wären z. B. ein Programm, das fortgesetzt Primzahlen findet, oder ein Betriebssystem)
• nur begrenzt viele Zustände pro Schritt ändern können (Begrenzung der Parallelität)
• nur begrenzt viele Zustände pro Schritt inspizieren können (Begrenzung der Exploration).

Eigenschaften

Determiniertheit

Ein Algorithmus ist determiniert, wenn dieser bei jeder Ausführung mit gleichen Startbedingungen und Eingaben gleiche Ergebnisse liefert.

Determinismus

Ein Algorithmus ist deterministisch, wenn zu jedem Zeitpunkt der Algorithmusausführung der nächste Handlungsschritt eindeutig definiert ist. Beispiele für deterministische Algorithmen sind Bubblesort und der Euklidische Algorithmus. Dabei gilt, dass jeder deterministische Algorithmus determiniert, während aber nicht jeder determinierte Algorithmus deterministisch ist. So ist Quicksort mit zufälliger Wahl des Pivotelements ein Beispiel für einen determinierten, aber nicht deterministischen Algorithmus, da sein Ergebnis bei gleicher Eingabe und eindeutiger Sortierung immer dasselbe ist, der Weg dorthin jedoch zufällig erfolgt.

In der theoretischen Informatik gibt es neben dem Determinismus auch den Nichtdeterminismusn, der aber mit keiner realen Maschine (auch nicht mit Quantencomputer) direkt umgesetzt werden kann.

Finitheit (Ausführbarkeit)

Statische Finitheit

Die Beschreibung des Algorithmus' besitzt eine endliche Länge, der Quelltext muss also aus einer begrenzten Anzahl von Zeilen bestehen.

Dynamische Finitheit

Ein Algorithmus darf zu jedem Zeitpunkt seiner Ausführung nur begrenzt viel Speicherplatz benötigen.

Terminierung

Terminiertheit heißt: Ein Algorithmus hält nach endlich vielen Schritten an (bricht kontrolliert ab). Dies gilt für jede mögliche Eingabe. Würde ein Algorithmus nicht terminieren (und somit zu keinem Ergebnis kommen), wäre die Folge eine so genannte Endlosschleife.

Für diese Eigenschaft gibt es jedoch Ausnahmen: Steuerungssysteme, Betriebssysteme und viele weitere Programme, die auf Interaktion mit dem Benutzer aufbauen. Solange der Benutzer keinen Befehl zum Beenden eingibt, laufen diese Programme beabsichtigt endlos weiter. Donald Knuth schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden („Computational Methods“) zu bezeichnen.

Darüber hinaus lässt sich die Terminierung eines Algorithmus i.A. nicht entscheiden, d. h. es gibt keinen Algorithmus, der für einen beliebigen Algorithmus feststellt, ob er bei einer beliebigen, vorgegebenen Eingabe terminiert (siehe Halteproblem aus der Theoretischen Informatik).

Effektivität

Der Effekt jeder Anweisung eines Algorithmus muss eindeutig festgelegt sein.

Algorithmenanalyse

Die Erforschung und Analyse von Algorithmen ist eine Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in eine Programmiersprache) durchgeführt. Sie ähnelt somit dem Vorgehen in anderen mathematischen Gebieten, in denen die Analyse eher auf die zugrunde liegenden Konzepte als auf konkrete Umsetzungen ausgerichtet ist. Algorithmen werden zur Analyse in eine stark formalisierte Form gebracht und mit den Mitteln der formalen Semantik untersucht.

Die Analyse unterteilt sich in verschiedene Teilgebiete. Beispielsweise wird das Verhalten von Algorithmen bezüglich Ressourcenbedarf wie Rechenzeit und Speicherbedarf in der Komplexitätstheorieen behandelt; die Ergebnisse werden als asymptotische Laufzeit angegeben. Der Ressourcenbedarf wird dabei in Abhängigkeit von der Länge der Eingabe ermittelt, d. h. die angegebene Komplexität hängt davon ab, wie groß die Zahlen sind, deren größter gemeinsamer Teiler gesucht wird, oder wie viele Elemente sortiert werden müssen etc.

Das Verhalten bezüglich der Terminierung, ob also der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die Berechenbarkeitstheorie.

Typen und Beispiele

Der älteste bekannte nicht-triviale Algorithmus ist der euklidische Algorithmus. Spezielle Algorithmus-Typen sind der randomisierte Algorithmus (mit Zufallskomponente), der Approximationsalgorithmus (als Annäherungsverfahren), der genetische Algorithmus (mit evolutionärer Komponente) und der Greedy-Algorithmus.

Eine weitere Übersicht gibt die Liste von Algorithmen und die .

Algorithmen sind jedoch kein speziell mathematisches Phänomen, denn im Alltag werden die verschiedensten Algorithmen in Form von Handlungsanweisungen oder Rezepten eingesetzt:

Prozess	Ausführender	Algorithmus	Typische Anweisung
Kuchenbacken	Bäcker	Rezept	nimm 500 Gramm Mehl / rolle Teig aus
Spielen einer Melodie	Sänger, Instrumentalist	Tonfolge
Bedienung eines Handys	Anrufer	Bedienungsanleitung	drücke die Taste #
Bau eines Radios	Radiobauer	Schaltplan und Montageanleitung	verbinde die Basis von Transistor T1 mit dem Kollektor von T5
Kassieren im Supermarkt	Kassiererin an Registrierkasse	Bedienungsanleitung für Registrierkasse, Funktionsplan der Registrierkasse	Eintippen von 200,37 +

Siehe auch

• Ameisenalgorithmus
• Datenstruktur
• Entscheidungsproblem
• Heuristik
• Komplexitätsklassen
• MMIX (virtuelle Maschine von Donald E. Knuth zur Darstellung von Algorithmen)
• Optimierungsproblem
• Prozedur (Programmierung)
• Rezept, Anleitung, Vorschrift
• Sortierverfahren
• Suchverfahren

Literatur

• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8.
• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, Boston 2001, 2002, 2003. ISBN 0-262-53196-8. (engl. Orig.-Fass.)
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium, München 2002. ISBN 3-8273-7020-5.
• Donald E. Knuth: The Art of Computer Programming. Bd 1–3. Addison Wesley, Reading Mass. 1998, ISBN 0-201-48541-9.
• Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. 4. Auflage. Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-1029-0.

Weblinks

• Algorithmen anschaulich erklärt: Algorithmus der Woche (verschiedene Autoren, herausgegeben vom Fakultätentag Informatik)
• Algorithmen in der Informatik
• Dictionary of Algorithms and Data Structures des NIST (englisch)
• Facharbeit zum Thema „Die Definition des Algorithmusbegriffs und Darstellung der wesentlichen Merkmale eines Algorithmus an ausgesuchten Beispielen“ , Nils Adermann, 2005.