Definition des Algorithmus

Eine Anweisungsfolge zur Lösung eines Problems heißt Algorithmus.

Herkunft des Begriffes

Die Bezeichnung Algorithmus geht auf den arabischen Schriftsteller Abu Dshafar Muhammed Ibn Musa al-Khwarizmi zurück. Er lebte um 825 nach Christus in der Stadt Khiva im heutigen Usbekistan, die damals Khwarizm hieß und als Teil des Namens verwendet wurde. Er beschrieb die Erbschaftsverhältnisse, die sich ergaben, wenn ein wohlhabender Mann starb, der bis zu vier Frauen in unterschiedlichem Stand und eine Vielzahl von Kindern hatte. Dazu verwendete er algebraische Methoden und schrieb ein Lehrbuch mit dem Titel "Kitab al jabr w'almuqabalah' (Regeln zur Wiederherstellung und Reduktion), wobei die Übertragung von Gliedern einer Gleichung von der einen zur anderen Seite des Gleichheitszeichens gemeint ist.
Der Begriff Algebra leitet sich aus dem Titel des Lehrbuchs ab. Aus dem Namen des Schriftstellers wurde algorism und daraus Algorithmus.

Definition eines Algorithmus (vgl. auch Algorithmen bei ZUM)

Ein Algorithmus ist eine genaue, eindeutige und endliche Beschreibung eines endlichen Prozesses.
Diese Beschreibung erfolgt in einem beliebig wählbaren Formalismus (Notation, Schreibweise), in Termen anderer Algorithmen und, letztlich, in elementaren Algorithmen. (vgl. unten: Beispiel 1 und Beispiel 2)
Der Algorithmus muß von einem Prozessor (oder Ausführende - sei es ein Mensch oder ein Automat) ausführbar sein. Der Prozessor muß den Formalismus kennen und die elementaren Algorithmen beherrschen.
Der Algorithmus erlaubt es, über den Prozeß und sein Ergebnis Aussagen zu machen. Zu gleichen Eingabewerten liefert der Algorithmus stets die gleichen Ausgabewerte (Determinismus).
Ein Algorithmus kann sequentiell oder nicht-sequentiell sein. Ein sequentieller Algorithmus wird zeitlich nacheinander, d.h. seriell abgearbeitet. Bei einem nichtsequentiellen Algorithmus werden Teile zeitlich parallel ausgeführt.
Die Schritte eines Algorithmus können hintereinander, in Abhängigkeit von einer Bedingung (Auswahl, Verzweigung) oder wiederholt (Schleife) ausgeführt werden.

Wird ein Algorithmus in einen vom Computer, einer Maschine ausführbaren Formalismus umgesetzt, so nennt man dies ein Programm.

Der Begriff des Algorithmus ist immer wieder in leicht abgewandelter Form definiert worden - unten sind einige Beispiele angeführt.

Beispiele für Algorithmen

Vierfarbiger Ringelpullover für 3-4 Jahre

Material: ca. 250 g mittelschwere Wolle mit Dralon und Mohair, in den Farben Rosa, Weiß, Dunkelgrün und Hellgrün

Rippen: 1 M. rechts, 1 M. links im Wechsel
Glatt rechts: Hin-R. rechte M., Rück-R. linke Masche
Streifenmuster:
- * 4 R. Rosa, 4 R. Weiß, 4 R. Dunkelgrün, 4 R. Hellgrün, 2 R. Rosa, 2 R. Weiß, 2 R. Dunkelgrün, 2 R. Hellgrün.
- ab * dreimal wiederholen und enden mit 4 R. Rosa, 4 R. Weiß, 4 R. Dunkelgrün = 108 R.
Rückenteil: Mit Rosa 76 Maschen anschlagen. Im Streifenmuster arbeiten, zuerst 4 R. für den Bund und dann glatt rechts. Nach 21 cm ...

Mayonnaise

2 Eigelb, Salz, Pfeffer, 1/8 Liter Salatöl, ein Teelöffel Senf, ein Teelöffel Zitronensaft.
Wenn die Zutaten aus dem Kühlschrank kommen, müssen sie zuerst auf Zimmertemperatur erwärmt werden, damit die Mayonnaise beim Rühren nicht gerinnt.
Eigelb, Salz, Pfeffer, Senf und Zitronensaft solange kräftig mit einem Schneebesen schlagen, bis die Masse homogen ist. Danach tropfenweise, unter ständigem Rühren, die Hälfte des Öls hinzufügen. Der Rest des Öls kann dann rasch unter die steife Masse gerührt werden.

Weitere Definitionen von Algorithmen

In Knuth 1973 finden wir folgende Definition:

Ein Algorithmus muss nach endlich vielen Schritten enden.
Jeder Schritt eines Algorithmus muss exakt beschrieben sein; die in ihm verlangten Aktionen müssen präzise formuliert und in jedem Falle eindeutig interpretierbar sein.
Ein Algorithmus hat keine, eine oder mehrere Eingangsgrößen, d.h. Größen, die von ihm benutzt und deren Werte vor Beginn seiner Ausführung festgelegt werden müssen.
Ein Algorithmus hat eine oder mehrere Ergebnisgrößen, d.h. Größen, deren Werte in Abhängigkeit von den Eingangsgrößen während der Ausführung des Algorithmus berechnet werden.
Ein Algorithmus muss so geartet sein, dass die in ihm verlangten Aktionen im Prinzip von einem Menschen in endlicherZeit mit Papier und Bleistift ausgeführt werden können.

Aho, Hopcroft und Ullman geben folgende Definition an (vgl. Aho et al. 1975):

Ein Algorithmus ist eine endliche Folge von Instruktionen, die alle eindeutig interpretierbar und mit endlichem Aufwand in endlicher Zeit ausführbar sind.

Algorithmen enthalten Instruktionen zur Formulierung von (beliebig vielen) Wiederholungen anderer Instruktionen. Unabhängig von den Werten der Eingangsgrößen endet ein Algorithmus stets nach endlich vielen Instruktionsschritten. Ein Programm ist dann ein Algorithmus, wenn für alle möglichen Eingabewerte sichergestellt ist, dass keine Instruktion unendlich oft wiederholt wird.

In Kronsjö 1979 heißt es:

Ein Verfahren, beschrieben durch eine endliche Menge von eindeutig interpretierbaren Regeln, das eine endlich lange Folge von Operationen zur Lösung eines Problems oder einer speziellen Problemklasse beschreibt, wird Algorithmus genannt.

Bauer und Goos schreiben (vgl. Bauer u. Goos 1982):

Ein Algorithmus ist eine präzise, d.h. in einer festgelegten Sprache abgefasste, endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Verarbeitungs-) Schritte.

Und in Rechenberg 1974 finden wir die Definition:

Ein Algorithmus ist ein endliches schrittweises Verfahren zur Berechnung gesuchter aus gegebenen Größen, in dem jeder Schritt aus einer Anzahl ausführbarer eindeutiger Operationen und einer Angabe über den nächsten Schritt besteht.