Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten.[1] Somit können sie zur Ausführung in einem Computerprogramm implementiert, aber auch in menschlicher Sprache formuliert werden. Bei der Problemlösung wird eine bestimmte Eingabe in eine bestimmte Ausgabe überführt.[2]
Der Übergang zwischen Algorithmus und Heuristik ist fließend. Werner Stangl greift ihn folgend: Ein Algorithmus bezeichnet eine systematische, logische Regel oder Vorgehensweise, die zur Lösung eines vorliegenden Problems führt. Im Gegensatz dazu steht dabei die schnellere, aber auch fehleranfälligere Heuristik.[3]
Das Wort Algorithmus geht zurück auf das Arabische und ist eine Abwandlung oder Verballhornung des Namens von Abu Dscha'far Muhammad ibn Musa al-Chwarizmi, dessen Namensbestandteil (Nisba) al-Chwarizmi „der Choresmier“ bedeutet und auf die Herkunft des Trägers aus Choresmien verweist. Als dessen Lehrbuch Über die indischen Ziffern (verfasst um 825 in Bagdad) im 12. Jahrhundert aus dem Arabischen ins Lateinische übersetzt und hierdurch in der westlichen Welt zur wichtigsten Quelle für die Ausbreitung der Kenntnis der indischen (heute meist als 'arabische' bezeichneten) Ziffern und des schriftlichen Rechnens mit diesen Ziffern wurde, wurde auch der Name des Verfassers in Anlehnung an die Anfangsworte der ältesten Fassung dieser Übersetzung (Dixit Algorismi „Algorismi hat gesagt“) in der Form Algorismus latinisiert und in der Folgezeit mit Varianten wie alchorismus, algoarismus und mit Entlehnungen in die Volkssprachen (altfranzösisch algorisme, argorisme, mittelenglisch augrim, augrym) zu einer allgemeinen Bezeichnung für die von al-Chwarizmi gelehrte Kunst des Rechnens mit solchen Ziffern, desgleichen zu einem gebräuchlichen Werktitel für mittelalterliche Schriften über diese Kunst.
Der englische Dichter Geoffrey Chaucer beschreibt Ende des 14. Jahrhunderts in seinen Canterbury Tales einen Astrologen, der Steine zum Rechnen („augrym stones“) am Kopfende seines Betts aufbewahrt:
In der mittelalterlichen Überlieferung wurde das Wort bald als erklärungsbedürftig empfunden und dann seit dem 13. Jahrhundert zumeist als Zusammensetzung aus einem Personennamen Algus und aus einem aus dem griechischen ῥυσμός (Nebenform von ῥυθμός) in der Bedeutung „Zahl“ entlehnten Wortbestandteil -rismus interpretiert. Algus, der vermutete Erfinder dieser Rechenkunst, wurde hierbei 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 mit dem Erbauer des Schiffes Argo gleichsetzt, mit dem Jason sich auf die Suche nach dem Goldenen Vlies begab.
Auf der para-etymologischen Zurückführung des zweiten Bestandteils -rismus auf griech. ῥυσμός, ῥυθμός beruht dann auch die gräzisierende lateinische Wortform algorithmus, die seit der Frühen Neuzeit, anfangs auch mit der Schreibvariante algorythmus, größere Verbreitung erlangte und zuletzt die heute übliche Wortbedeutung als Fachterminus für geregelte Prozeduren zur Lösung definierter Probleme annahm.
Algorithmen sind eines der zentralen Themen der Informatik und Mathematik. Sie sind Gegenstand einiger Spezialgebiete der Theoretischen Informatik, der Komplexitätstheorie und der Berechenbarkeitstheorie, mitunter ist ihnen ein eigener Fachbereich Algorithmik oder Algorithmentheorie gewidmet. In Form von Computerprogrammen und elektronischen Schaltkreisen steuern Algorithmen Computer und andere Maschinen.
Für Algorithmen gibt es unterschiedliche formale Repräsentationen. Diese reichen vom Algorithmus als abstraktem Gegenstück zum konkret auf eine Maschine zugeschnittenen Programm (das heißt, 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, das heißt, einer idealen mathematischen Maschine).
Algorithmen können in Programmablaufplänen nach DIN 66001 oder ISO 5807 grafisch dargestellt werden.
Der erste für einen Computer gedachte Algorithmus (zur Berechnung von Bernoullizahlen) wurde 1843 von Ada Lovelace in ihren Notizen zu Charles Babbages 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.
Algorithmen für Computer sind heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz im KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von Algorithmen. Als Ideen und Grundsätze, die einem Computerprogramm zugrunde liegen, wird einem Algorithmus in der Regel urheberrechtlicher Schutz versagt.[4] Je nach nationaler Ausgestaltung der Immaterialgüterrechte sind Algorithmen der Informatik jedoch dem Patentschutz zugänglich, so dass urheberrechtlich freie individuelle Werke, als Ergebnis eigener geistiger Schöpfung, wirtschaftlich trotzdem nicht immer frei verwertet werden können. Dies betrifft oder betraf z. B. Algorithmen, die auf der Mathematik der Hough-Transformation (Jahrzehnte alt, aber mehrfach aktualisiertes Konzept mit Neu-Anmeldung) aufbauen, Programme, die das Bildformat GIF lesen und schreiben wollten oder auch Programme im Bereich der Audio- und Video-Verarbeitung, da die zugehörigen Algorithmen, wie sie in den zugehörigen Codecs umgesetzt sind, oftmals nicht frei verfügbar sind. Die entsprechenden Einsparpotentiale für alle Anwender weltweit (für den Rete-Algorithmus wurde einst 1 Million USD auf DEC XCON genannt) dürften heute problemlos die Grenze von einer Milliarde USD im Jahr um ein zigfaches überschreiten.
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 Turingmaschine (Alan Turing), Registermaschinen, 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 die gleiche Berechnungsstärke besitzen (gleich mächtig sind). Sie können durch eine Turingmaschine emuliert werden, und sie können umgekehrt eine Turingmaschine emulieren.
Mit Hilfe des Begriffs der Turingmaschine 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:
Darüber hinaus wird der Begriff Algorithmus in praktischen Bereichen oft auf die folgenden Eigenschaften eingeschränkt:
Die Church-Turing-These besagt, dass jedes intuitiv berechenbare Problem durch eine Turingmaschine gelöst werden kann. Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen, zu einer Turingmaschine ä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, das heißt, wenn eine entsprechend programmierte Turingmaschine das Problem in endlicher Zeit lösen könnte.
Turingmaschinen harmonieren gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen, reale Probleme sind jedoch ungleich komplexer, daher wurden andere Maschinen vorgeschlagen.
Diese Maschinen weichen etwa in der Mächtigkeit der Befehle ab; statt der einfachen Operationen der Turingmaschine können sie teilweise mächtige Operationen, wie etwa Fourier-Transformationen, in einem Rechenschritt ausführen.
Oder sie beschränken sich nicht auf eine Operation pro Rechenschritt, sondern ermöglichen parallele Operationen, wie etwa die Addition zweier Vektoren in einem Schritt.
Ein Modell einer echten Maschine ist die Sequential Abstract State Machine (kurz seq. ASM)[5] mit folgenden Eigenschaften:
Ein Algorithmus einer seq. ASM soll
Ein Algorithmus ist determiniert, wenn dieser bei jeder Ausführung mit gleichen Startbedingungen und Eingaben gleiche Ergebnisse liefert.
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 Nichtdeterminismus, der aber mit keiner realen Maschine (auch nicht mit Quantencomputern) direkt umgesetzt werden kann.
Die Beschreibung des Algorithmus besitzt eine endliche Länge, der Quelltext muss also aus einer begrenzten Anzahl von Zeichen bestehen.
Ein Algorithmus darf zu jedem Zeitpunkt seiner Ausführung nur begrenzt viel Speicherplatz benötigen.
Ein Algorithmus ‚terminiert überall‘ oder ‚ist terminierend‘, wenn er nach endlich vielen Schritten anhält (oder kontrolliert abbricht) – für jede mögliche Eingabe. Ein nicht-terminierender Algorithmus (somit zu keinem Ergebnis kommend) gerät (für manche Eingaben) in eine so genannte Endlosschleife.
Für manche Abläufe ist ein nicht-terminierendes Verhalten gewünscht: Z. B. Steuerungssysteme, Betriebssysteme und Programme, die auf Interaktion mit dem Benutzer aufbauen. Solange der Benutzer keinen Befehl zum Beenden eingibt, laufen diese Programme beabsichtigt endlos weiter. Donald E. Knuth schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden (Computational Methods) zu bezeichnen.
Darüber hinaus ist die Terminierung eines Algorithmus (das Halteproblem) nicht entscheidbar. Das heißt, das Problem, festzustellen, ob ein (beliebiger) Algorithmus mit einer beliebigen Eingabe terminiert, ist nicht durch einen Algorithmus lösbar.
Der Effekt jeder Anweisung eines Algorithmus muss eindeutig festgelegt sein.
Einfache Grundoperation: „Öffne die Flasche Wein“ hierbei wird das Wissen um das Öffnen vorausgesetzt.
Sequentieller Algorithmus: „Bier auf Wein, lass das sein“ beiden Operationen ist eine Reihenfolge vorgegeben und diese sollte nicht verändert werden.
Nebenläufiger Algorithmus: „Schnaps und Bier“ Die Reihenfolge ist nicht vorgegeben und kann auch gleichzeitig erfolgen.
Parallele Ausführung: „Mit Sekt anstoßen“ Dies kann nur gleichzeitig (parallel) ausgeführt werden und nicht hintereinander (sequentiell).
Nichtdeterministischer/nichtdeterminierter Algorithmus: „Bier oder Wasser“ Das Ergebnis unterscheidet sich, je nachdem welches man wählt.
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ätstheorie behandelt; die Ergebnisse werden als asymptotische Laufzeiten angegeben. Der Ressourcenbedarf wird dabei in Abhängigkeit von der Länge der Eingabe ermittelt, das heißt, 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.
Der älteste bekannte nicht-triviale Algorithmus ist der euklidische Algorithmus. Spezielle Algorithmus-Typen sind der randomisierte Algorithmus (mit Zufallskomponente), der Approximationsalgorithmus (als Annäherungsverfahren), die evolutionären Algorithmen (nach biologischem Vorbild) und der Greedy-Algorithmus.
Eine weitere Übersicht gibt die Liste von Algorithmen und die Kategorie Algorithmus.
Obwohl der etymologische Ursprung des Wortes arabisch ist, entstanden die ersten Algorithmen im antiken Griechenland. Zu den wichtigsten Beispielen gehören das Sieb des Eratosthenes zum Auffinden von Primzahlen, welches im Buch Einführung in die Arithmetik von Nikomachos beschrieben wurde[6] und der euklidische Algorithmus zum Berechnen des größten gemeinsamen Teilers zweier natürlicher Zahlen aus dem Werk „die Elemente“.[7] Einer der ältesten Algorithmen, die sich mit einer reellen Zahl beschäftigen, ist der Algorithmus des Archimedes zur Approximation von [math]\pi[/math], was zugleich auch eines der ältesten numerischen Verfahren ist.[8]
Das Wort Algorithmus stammt aus dem 9. Jahrhundert von dem choresmischen Mathematiker Al-Chwarizmi, der auf der Arbeit des aus dem 7. Jahrhundert stammenden indischen Mathematikers Brahmagupta[9][10] aufbaute. In seiner ursprünglichen Bedeutung bezeichnete ein Algorithmus nur das Einhalten der arithmetischen Regeln unter Verwendung der indisch-arabischen Ziffern. Die ursprüngliche Definition entwickelte sich mit Übersetzung ins Lateinische weiter.[11]
Bedeutende Arbeit leisteten die Logiker des 19. Jahrhunderts. George Boole der in seiner Schrift The Mathematical Analysis of Logic den ersten algebraischen Logikkalkül erschuf, begründete damit die moderne mathematische Logik, die sich von der traditionellen philosophischen Logik durch eine konsequente Formalisierung abhebt.[12] Gottlob Frege entwickelte als erster eine formale Sprache und die daraus resultierenden formalen Beweise.[13] Giuseppe Peano reduzierte die Arithmetik auf eine Sequenz von Symbolen manipuliert von Symbolen. Er beschäftigte sich mit der Axiomatik der natürlichen Zahlen. Dabei entstanden die Peano-Axiome.[14]
Die Arbeit von Frege wurde stark von Alfred North Whitehead und Bertrand Russell in ihrem Werk Principia Mathematica weiter ausgearbeitet und vereinfacht.[15] Zuvor wurde von Bertrand Russell die berühmte russellsche Antinomie formuliert, was zum Einsturz der naiven Mengenlehre führte. Das Resultat führte auch zur Arbeit Kurt Gödels.
David Hilbert hat um 1928 das Entscheidungsproblem in seinem Forschungsprogramm präzise formuliert.[16] Alan Turing und Alonzo Church haben für das Problem 1936 festgestellt, dass es unlösbar ist.[17]