Algorithmus

Ein Algorithmus ist eine wohldefinierte Methode oder Prozedur, um ein Problem zu lösen. Üblicherweise geht es dabei um Probleme der Mathematik oder der Informatik. Typischerweise wird ein Algorithmus durch eine Folge von Anweisungen beschrieben, die nacheinander ausgeführt und oft in festgelegter Weise wiederholt werden. Dadurch besteht die Möglichkeit, dass ein Algorithmus niemals beendet wird. Manchmal werden solche Algorithmen als ungültig betrachtet. Algorithmen werden meistens als Computerprogramm implementiert. Möglich ist aber auch die Implementierung als elektronischer Schaltkreis oder die (händische) Ausführung durch Menschen.

Geschichte

Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens al-Khwarizmi (ca. 780 - ca. 850), des Autors des Buchs "Kitab al-jabr w'al-muqabala" (825, Regeln zur Wiederherstellung und Reduktion), durch das die Algebra im Westen verbreitet wurde. Das Wort Algebra stammt ebenfalls (al-Jabr) aus dem Titel des Buchs. Ursprünglich stand das Wort Algorism nur für die Regeln zur Arithmetik mit arabischen Ziffern. Heute steht es für alle geregelten Prozeduren, mit denen Probleme aller Art gelöst werden können.

Die mangelnde mathematische Genauigkeit in der gängigen Definition eines Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts. Dieses Problem wurde erst einigermaßen befriedigend durch Alan Turing gelöst. Dieser führte die sogenannte Turing-Maschine als ein abstraktes Modell eines Computers ein und zeigte, dass alle gängigen Methoden, "wohldefinierte Prozeduren" zu formulieren durch eine Turing-Maschine emuliert werden können. Diese Behauptung ist bekannt als Church-Turing-These. Heute kann man als formales Kriterium für einen Algorithmus die Implementierbarkeit in einem beliebigen zu einer Turing-Maschine äquivalenten Formalismus heranziehen (also den meisten Programmiersprachen).

Beispiel

Als Beispiel für einen Algorithmus eignet sich besonders gut der Euklidische Algorithmus zur Ermittlung des größten gemeinsamen Teilers zweier natürlicher Zahlen A und B:

1. Sei A die größere der beiden Zahlen A und B (entsprechend vertauschen)
2. Setze A = A - B
3. Wiederhole die Schritte 1 und 2 solange, bis A und B gleich sind. Diese Zahl ist der größte gemeinsame Teiler.

Analyse

Das Verhalten von Algorithmen bezüglich Ressourcenbedarf wie Rechenzeit und Speicherbedarf wird in der Komplexitätstheorie behandelt. Das Verhalten bezüglich Terminierung (d.h. ob der Algorithmus überhaupt jemals erfolgreich beendet werden kann) wird in der Berechenbarkeitstheorie behandelt.

Siehe auch:

• Liste von Algorithmen
• MMIX (virtuelle Maschine zur Darstellung von Algorithmen)

Literatur

• Donald Knuth: The Art of Computer Programming, Vol 1-3, Addison Wesley 1998. (Das ist der Standard in dem Bereich; Übersetzung existiert leider nicht - Juli 2000).