Was ist ein Algorithmus?

Um ein gemeinsames Vokabular und Verständnis aufzubauen, welches wir fortan in der Veranstaltung benutzen wollten, machten wir uns an diese Frage und kamen über anfänglich eher naive Ansätze einer geeigneten Definition immer näher:

Der Begriff „Algorithmus” ist scheinbar abstrakt genug, um ein oft genanntes Beispiel - den Vergleich mit einem Kochrezept - zu erlauben. Aber ist dem wirklich so? Bevor wir uns der Frage widmeten, konkretisierten wir erstmal unsere Beschreibungen. Meine Definition dazu: Ein Algorithmus ist die Beschreibung einer Methode zur Lösung einer Aufgabenstellung. Durch Iteration bzw. Rekursion wird das Problem schrittweise gelöst/das Ergebnis aufgebaut.

Ein Algorithmus setzt sich aus einzelnen Anweisungen zusammen. Dabei kann man die Instruktionen als Werkzeug ansehen, den gesamten Algorithmus hingegen als Automaten.

Welche Eigenschaften hat ein Algorithmus?

In unseren Annäherungen waren einige Begriffe dabei, die sich wiederholten: Schrittweise, genau und in endlichen Schritten durchführbar soll er sein. Besser definiert[1] bedeutet das:

Spezifikation

Die Anforderungen, welche der Algorithmus an die Eingabegrößen stellt und die Zusicherungen, welche er bezüglich der Ausgabe macht.

Eingabespezifikation
Es muss genau spezifiziert sein, welche Eingabegrößen erforderlich sind und welchen Anforderungen diese Größen genügen müssen, damit das Verfahren funktioniert.
Ausgabespezifikation
Es muss genau spezifiziert sein, welche Ausgabegrößen (Resultate) mit welchen Eigenschaften berechnet werden.
Durchführbarkeit

Das Verfahren muss von einer Maschine mechanisch ausgeführbar sein. Dabei müssen die gleichen Eingaben immer zum gleichen Ablauf und Ergebnis führen.

Endliche Beschreibung
Das Verfahren muss in einem endlichen Text vollständig beschreibbar sein.
Effektivität
Jeder Schritt des Verfahrens muss effektiv (d.h. tatsächlich) mechanisch ausführbar sein.
Determiniertheit
Der Verfahrensablauf ist zu jedem Zeitpunkt fest vorgeschrieben.
Korrektheit
partielle Korrektheit
Jedes berechnete Ergebnis genügt der Ausgabespezifikation, sofern die Eingabegrößen der Spezifikation genügt haben.
Terminierung
Der Algorithmus endet nach endlich vielen Schritten mit einem Ergebnis, sofern die Eingabegrößen der Spezifikation genügt haben.

Exakt, präzise, effektiv und endlich

Was sich überhaupt sagen lässt, lässt sich klar sagen, und wovon man nicht sprechen kann, darüber muss man schweigen. -- Ludwig Wittgenstein

Damit die Maschine mit unseren Anweisungen umgehen kann, müssen wir sie exakt, präzise, effektiv und endlich formulieren.

The computer will do anything within its abilities, but it will do absolutely nothing unless commanded to do so. A command must be issued clearly, in the strict format of a one-word action, followed by a set of descriptors which qualify the action. There is no need to add the formality of a „please” or even a „thank you”. A command should not be confused with a request; you can fully expect that it will be obeyed.[2]

Terminiert ein Algorithmus zwangsläufig?

Zur Terminierung sei angemerkt, dass die Beschreibung des Verfahrens zwar deterministisch (der nächste Schritt ist fest vorgegeben) seien kann, dies aber nicht zwangsläfig bedeutet, dass der Algorithmus zu einem Ende kommt.
Algorithmen, welche der Berechnung von Ergebnissen dienen, sollten natürlich die Anforderung erfüllen, mit der Rückgabe eines Ergebniswerts zu terminieren. Darüber hinaus gibt es allerdings auch Programme, deren eigentliche Leistung durch sogenannte Seiteneffekte erbracht wird, beispielsweise der Von-Neumann-Zyklus, welcher der ständigen Befehlsverarbeitung in der CPU dient.

Zweitens kann es vorkommen, daß ein effektives Verfahren zwar in der Lage ist, prinzipiell eine bestimmte Berechnung durchzuführen, dafür aber eine so lange Zeit braucht, daß das Verfahren praktisch wertlos ist. Nehmen wir beispielsweise das Schachspiel. Da es eine Regel gibt, nach der ein Schachspiel beendet ist, wenn es dreimal zur selben Stellung der Figuren gekommen ist, ist Schach sicherlich ein endliches Spiel. Deshalb ist es prinzipiell möglich, ein Verfahren zu formulieren, mit dem eine Liste aller Spiele - Zug um Zug - erstellt werden kann, die möglicherweise gespielt werden können. Aber diese Berechnung würden selbst auf den schnellsten Computern, die man sich vorstellen kann, Ewigkeiten dauern.[3]

Der Ablauf eines Algorithmus

Die Aufgabenlösung lässt sich iterativ oder rekursiv in folgenden Schritten durchführen:[4]

  1. Vorbereitung: Einführung von Hilfsgrößen
  2. Prüfung auf Trivialfall/Lösung: Wenn die Lösung vorliegt, dann beende mit Ergebnis
  3. Problemreduktion/Ergebnisaufbau: Reduziere die Problemstellung X auf eine einfachere Form X'
  4. Rekursion bzw. Iteration: Rufe zur Weiterverarbeitung den Algorithmus mit X' erneut auf (Rekursion) oder fahre mit X' anstelle von X bei Schritt 2 fort (Iteration).

Sind Kochrezepte Algorithmen?

Fasst man den Begriff allgemein und lässt auch Beschreibungen zur Aufgabenlösung durchgehen, welche nicht zwangsläufig in programmierbaren Funktionen enden müssen, so lassen sich im Alltag viele Formen davon finden: Beispielsweise das Abfertigen eines Kassiervorgangs im Supermarkt, das Spielen einer Melodie beim Musizieren oder eben auch beim Kochen nach einem Rezept.

Nach unserer Definition ist ein Kochrezept allerdings kein Algorithmus, da es ist beispielsweise nicht effektiv durchführbar ist: Beschreibungen wie „eine Prise Salz” oder ”man schmecke ab” sind nicht von einem Computer ausführbar, da sie zu ungenau sind.
Des Weiteren dürfte wohl auch jeder zustimmen, dass selbst wenn man nach einem Rezept kocht, das Ergebnis geschmacklich immer variieren wird (vom Problem der genauen Messbarkeit einmal abgesehen).

Wer diesem Umstand näher auf den Grund gehen möchte, der findet die ausführliche Beschreibung „Algorithmisches Kuchenbacken” in Juraj Hromkovics Buch „Sieben Wunder der Informatik”[5].

Schon gewusst?

Der erste für einen Computer gedachte Algorithmus wurde 1842 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.[6]

Quellen

  1. #kuech03">[Küch03, 72 f.]
  2. #maed99">[Maed99]
  3. #weiz78">[Weiz78, 98]
  4. #kuech03">[Küch03, 75]
  5. #hrom06">[Hrom06, 34 ff.]
  6. Wikipedia: Algorithmus. http://de.wikipedia.org/wiki/Algorithmus. Aufgerufen am 15.02.2007.