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.