Ein Algorithmus ist eine genau definierte Verarbeitungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen. Typischerweise wird ein Algorithmus durch eine endliche Folge von Anweisungen beschrieben, die nacheinander ausgeführt und oft in festgelegter Weise wiederholt werden.

Im täglichen Leben kommen Algorithmen sehr häufig vor. Zum Beispiel ist ein Kochrezept ein Algorithmus. Auch Reparatur- und Bedienungsanleitungen oder Hilfen zum Ausfüllen von Formularen sind in der Regel Algorithmen. Sehr verbreitet sind Algorithmen in der Informatik: Dort steuern sie, in der Form von Computerprogrammen oder elektronischen Schaltkreisen, Rechner und Maschinen.

Die Theoretische Informatik beschäftigt sich u.a. mit der Frage, welche Problemstellungen algorithmisch, d.h. mittels genau definierter Handlungsanweisungen, gelöst werden können und wie rechenaufwendig Lösungen gegebener Probleme mindestens sind.

Ein Beispiel: der Euklidische Algorithmus

Der Euklidische Algorithmus, der bereits um 300 v. Chr. beschrieben wurde, dient zur Ermittlung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen A und B:

1. Sei A die größere der beiden Zahlen A und B (entsprechend vertauschen, falls dies nicht bereits so ist)
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.

Beispiel:

Es soll der größte gemeinsame Teiler der Zahlen 14 und 8 berechnet werden. Hierzu wird der euklidische Algorithmus verwendet:

Das Ergebnis ist also 2.

Geschichte

Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens Muhammad ibn Musa al-Chwarizmi (* ca. 783, ? ca. 850), des Autors des Buchs Hisab al-dschabr wa-l-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.

Erster Computeralgorithmus

Der erste für einen Computer gedachte Algorithmus wurde 1842 von Ada Lovelace, in ihren Notizen zu Charles Babbage's 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.

Exaktere Definitionen

Die mangelnde mathematische Genauigkeit in der gängigen Definition eines Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts. Insbesondere steht die natürliche Sprache mit ihren Unschärfen und Widersprüchlichkeiten der Forderung nach Eindeutigkeit und Widerspruchsfreiheit im Wege.

In der ersten Hälfte des 20. Jahrhunderts wurden eine ganze Reihe von Ansätzen entwickelt, um zu einer genauen Definition zu kommen. Der bekannteste ist wohl Alan Turings Konzept der Turing-Maschine als abstraktes Modell eines Computers.

Andere gängige Konzepte sind beispielsweise rekursive Funktionen, insbesondere der Lambda-Kalkül, Zeichen-Ersetzungssysteme wie Markov-Algorithmen oder Chomsky-Grammatiken oder verallgemeinerte abstrakte Programmiersprachen mit den Grundelementen Sequenz, Auswahl und Wiederholung.

Church-Turing These

Um die Mitte des 20. Jahrhunderts konnte, unter maßgeblicher Beteiligung von Alan Turing selbst, gezeigt werden, dass all diese Methoden ebenso leistungsfähig sind wie eine Turing-Maschine: Sie können durch eine Turing-Maschine emuliert werden, und sie können umgekehrt eine Turing-Maschine emulieren.

Aus diesem Grunde ist heutzutage die Church-Turing-These: "Jeder Algorithmus kann durch eine Turingmaschine ausgeführt werden" allgemein akzeptiert. 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.

Formale Definition und Eigenschaften

Formal ist ein Algorithmus eine Beschreibung eines Verfahrens zur Lösung einer bestimmten Klasse von Problemen. Dabei müssen folgende Bedingungen erfüllt sein:

1. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
2. Der Ablauf des Verfahrens ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).
3. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
4. Das Verfahren darf zum Ausführen nicht unendlich viel Speicherplatz benötigen (Dynamische Finitheit).
5. Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein. (Ausführbarkeit)
6. Der Algorithmus darf nur endlich viele Schritte benötigen. Jeder einzelne Schritt muss in endlicher Zeit ausführbar sein. (Terminierung)

Eine Ausnahme bilden stochastische Algorithmen, bei denen der jeweils nächste Verfahrensschritt von einer Wahrscheinlichkeitsregel abhängen kann.

Determiniertheit

kurz: wenn gleiche Startwerte vorhanden sind, muss das gleiche Ergebnis raus kommen

Algorithmen sind determiniert: Werden sie mit gleichen Parametern und Startwerten aufgerufen, liefern sie stets das gleiche Resultat. Ausnahme bilden randomisierte und stochastische Algorithmen, bei denen das Ergebnis zu einem gewissen Grad auf Zufall beruht.

Determinismus

kurz: es darf nur immer eine Möglichkeit vorhanden sein (--> sonst stochastisch)

Deterministisch heißen alle Algorithmen, bei denen zu jedem Zeitpunkt der Ausführung maximal eine Möglichkeit der Programmfortsetzung besteht. Gibt es mehrere Möglichkeiten der Programmfortsetzung und lassen sich diesen Wahrscheinlichkeiten zuweisen, so spricht man von stochastischen, randomisierten oder probabilistischen Algorithmen. In der theoretischen Informatik gibt es neben dem Determinismus auch den Nichtdeterminismus, der aber in praktischen Algorithmen nicht vorkommen kann.

Finitheit

Statische Finitheit

kurz: die Beschreibung ist endlich

Die Beschreibung eines Algorithmus ist nicht unendlich groß. Als statische Finitheit wird die Endlichkeit des Quelltextes bezeichnet. Der Quelltext darf nur begrenzten, wenn auch bei Bedarf sehr viel Speicherplatz in Anspruch nehmen.

Dynamische Finitheit

kurz: Fülle an Datenstrukturen und Zwischenspeicherungen sind zu jeder Zeit endlich

Zu jedem Zeitpunkt der Ausführung darf der von einem Algorithmus benötigte Speicherbedarf nur endlich groß sein. Andernfalls wäre der Algorithmus nicht ausführbar. Dies wird als dynamische Finitheit bezeichnet.

Terminierung

kurz: bricht nach absehbarer Zeit kontrolliert ab (Ausnahme z.B. Betriebssystem)

Algorithmen sind terminierend, sie kommen nach einer endlichen Zahl von Schritten zu einem Ergebnis. Die tatsächliche Zahl der Schritte kann jedoch willkürlich groß sein. Steuerungssysteme und Betriebssysteme erfüllen diese Eigenschaft nicht. Donald Knuth schlägt vor nicht terminierende Algorithmen als rechnergestützte Methoden ("Computational Methods") zu bezeichnen.

Algorithmenanalyse

Die Erforschung und Analyse von Algorithmen ist Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in einer 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 theoretischen Pseudosprachen (Pseudocode) geschrieben und 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, d.h. die angegebene Komplexität hängt davon ab, wie groß die Zahlen sind, deren ggT gesucht wird, oder wie viele Elemente sortiert werden müssen etc.

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

Beispiele

Algorithmen in der Wikipedia

In einzelnen Wikipedia-Artikeln gibt es zahlreiche Algorithmen-Beschreibungen, etwa den euklidischen Algorithmus und Quicksort. Eine Übersicht gibt die Liste von Algorithmen.

Algorithmen im Alltag

Auch im Alltag begegnen uns Algorithmen in Form von Handlungsanweisungen oder Rezepten:

Prozess	Ausführender	Algorithmus	Typische Anweisung
Kuchenbacken	Bäcker	Rezept	nimm 1 Pfund Mehl / rolle Teig aus
Spielen einer Klaviersonate	Pianist	Partitur
Bedienung eines Handys	Anrufer	Bedienungsanleitung	drücke die # Taste
Bau eines Radios	Radiobastler	Schaltplan und Montageanleitung	verbinde Transistor T1 mit T5
Kassieren im Supermarkt	Kassiererin an Registrierkasse	Bedienungsanleitung für Registrierkasse, Funktionsplan der Registrierkasse	Eintasten von 17,82 +

Siehe auch

• Approximationsalgorithmus
• Datenstruktur
• Determinierter Algorithmus
• Deterministischer Algorithmus
• Entscheidungsproblem
• Genetischer Algorithmus
• Greedy Algorithmus "gieriger" Algorithmus, z.B. zur Zerlegung von Brüchen in Summen von Stammbrüchen
• Komplexitätsklassen
• MMIX (virtuelle Maschine von Donald E. Knuth zur Darstellung von Algorithmen)
• Online-Algorithmus
• Optimierungsproblem
• Probabilistischer Algorithmus
• randomisierter Algorithmus
• Sortierverfahren
• Stochastischer Algorithmus
• Suchverfahren

Literatur

• Donald Knuth: The Art of Computer Programming, Vol 1?3, Addison Wesley 1998. (Das ist der Standard in dem Bereich; Übersetzung existiert nicht ? Juli 2000), ISBN 0201485419
• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2nd edition 2001, ISBN 0262531968
• Thomas Ottmann und Peter Widmayer: Algorithmen und Datenstrukturen, Spektrum Akademisher Verlag, 4. Auflage 2002, ISBN 3827410280

Weblinks

• Dictionary of Algorithms and Data Structures (http://www.nist.gov/dads/) des NIST (englisch)
• http://www.ads.tuwien.ac.at/