Algorithmus

Ein Algorithmus ist eine wohldefinierte Methode oder Prozedur, um ein Problem zu lösen. Typischerweise wird ein Algorithmus durch eine Folge von Anweisungen beschrieben, die nacheinander ausgeführt und oft in festgelegter Weise wiederholt werden. 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. Die lateinische Fassung beginnt mit:"Dixit Algorithmi...", womit der Autor gemeint war. Das Wort Algebra stammt ebenfalls (al-Jabr "Einrenkung") 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 so genannte 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).

Grundprinzip eines Algorithmus

Ein Algorithmus basiert auf zwei Grundelementen, der (Rechen-)Anweisung und dem bedingten Sprung. Ein bedingter Sprung zeigt an, an welcher Stelle im Algorithmus fortgefahren werden soll, wenn eine bestimmte Bedingung erfüllt ist (z.B. die, dass zwei Werte gleich sein müssen), und an welcher fortgefahren werden soll, wenn diese Bedingung nicht erfüllt ist (wenn im Beispiel also die Werte nicht gleich sind).

Definition des Algorithmus

Ein Algorithmus ist eine Menge von Regeln für ein Verfahren, um aus gewissen Eingabegrössen bestimme Ausgabegrössen herzuleiten. Dabei müssen folgende Bedingungen erfüllt sein: - Das Verfahren muss in einem endlichen Text beschreibbar sein - Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein - Der Ablauf des Verfahrens ist zu jedem Zeitpunkt eindeutig definiert - Das Verfahren muss in endlich vielen Schritten zum Ende gelangen.

Beispiel

Für eine Übersicht von Artikeln zu Algorithmen siehe unter Liste von Algorithmen.

Als Beispiel für einen Algorithmus eignet sich beispielweise 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. Wenn A und B ungleich sind, dann fahre fort mit Schritt 1, wenn sie gleich sind, dann beende den Algorithmus: 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:

• Datenstruktur
• Optimierungsproblem/Entscheidungsproblem
• Probabilistischer Algorithmus
• Approximationsalgorithmus
• Genetischer Algorithmus
• MMIX (virtuelle Maschine zur Darstellung von Algorithmen)
• Denken und Problemlösen
• Problemlösungsprozess
• Kreativitätstechnik

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).