zurück zur Liste

Eigenschaften von Algorithmen

Abstraktion

Durch einen Algorithmus wird ein Problemlösungsprozess auf einem bestimmten Abstraktionsniveau beschrieben, das durch die elementaren Algorithmen, die elementaren Objekte und den verwendeten Formalismus festgelegt wird.
Eine der wichtigsten Möglichkeiten der Abstraktion besteht darin, (Teil-) Algorithmen einen Namen zu geben und diesen Namen dann stellvertretend für die detaillierte Realisierung des Algorithmus zu verwenden.

Diskretheit

Ein diskreter Algorithmus arbeitet schrittweise das Problem ab, d.h. er ist aus elementaren Operationen zusammengesetzt.

Finitheit (= Endlichkeit)

Statische Finitheit: Die Beschreibung eines Algorithmus besitzt nur eine endliche Länge.
Ein Dynamische Finitheit: Ein Algorithmus nimmt während seiner Ausführung nur endlich viel Platz zur Speicherung von Zwischenresultaten in Anspruch.

Terminierung

Einen Algorithmus nennt man terminierend, wenn er bei jeder Anwendung nach endlich vielen Verarbeitungsschritten anhält und ein Resultat liefert.

Finitheit vs. Terminierung

Das Terminieren einen Algorithmus darf nicht mit seiner Finitheit verwechslet werden. Es ist durchaus möglich, durch eine endliche Beschreibung (finit) einen Prozeß (z.B. mit Endlosschleife) zu definieren, der nicht nach endlicher Zeit beendet wird, also nicht terminiert.
Es gibt sogar Algorithmen mit praktischem Nutzen, die (potentiell) "endlos laufen", z.B. Algorithmen zur Steuerung "nichtabbrechender" Vorgänge (z.B. in chemischen Produktionsstätten) oder das zentrale Steuerungsprogramm (Betriebssystem) einen Computers, der Tag und Nacht in Verwendung steht.

Determinismus

Einen Algorithmus nennt man deterministisch, wenn zu jedem Zeitpunkt seiner Ausführung höchstens eine Möglichkeit der Fortsetzung besteht, also der Folgeschritt eindeutig bestimmt ist. Besteht keine Möglichkeit zur Fortsetzung der Ausführung, so vereinbart man, daß der Algorithmus terminiert.
Hat ein Algorithmus an mindestens einer Stelle zwei oder mehr Möglichkeiten der Fortsetzung, von denen eine nach belieben ausgewählt werden kann, so heißt er nicht-deterministisch.
Enthält ein Algorithmus also elementare Anweisungen, deren Ergebnis durch einen Zufallsmechanismus beeinflußt wird, so heißt dieser Algorithmus nicht-deterministisch. Liefert er bei der gleichen Eingabe immer die gleiche Ausgabe, so heißt er deterministisch.

Determiniertheit

Ein Algorithmus heißt determiniert, wenn er mit den gleichen Parametern und Startbedingungen stets das gleiche Ergebnis liefert.

Determinismus vs. Determiniertheit

Determinismus und Determiniertheit sind auseinanderzuhalten: Determinismus kennzeichnet einen Algorithmus, bei dem der gesamte Ablauf eindeutig bestimmt ist. Determiniertheit bezieht sich nur auf die eindeutige Bestimmtheit des Resultats. Deterministische Algorithmen haben durch ihren eindeutigen Ablauf auch ein eindeutiges Resultat, sie sind daher stets determiniert. Die Umkehrung gilt jedoch nicht. Es gibt nicht-deterministische Algorithmen, die über verschiedene Wege stets zum gleichen Ziel kommen, also determiniert sind.