Algorithmus

Definition

Ein Algorithmus ist eine eindeutig formulierte, aus einzelnen Verarbeitungsschritten zusammengesetzte Vorschrift zur Lösung einer Aufgabe. Algorithmen werden in einer formalen Sprache oder in sog. Pseudo-Code abgefasst. Sie sollen in einer von einer konkrekten Implementation in einer spezifischen Programmiersprache unabhängigen Weise die Lösungsschritte darstellen. Der selbe Algorithmus kann demnach durch verschiedene Programme, die in verschiednenen Programmierpsprachen geschrieben sind, implementiert (oder instantiiert) werden. Die Abarbeitung eines Algorithmus erfolgt durch einen abstrakten Automaten) mit einem endlichen Vorrat von elementaren Verarbeitungsschritten (Operationen, Befehlen), etwa durch die abstrakte Maschine, die durch die Elementaroperationen einer höheren Programmiersprache gegeben ist. Wichtige Qualitätsmerkmale eines Algorithmus sind die Präzision seiner Beschreibung, seine Korrektheit und seine Effizienz.

Die meisten Algorithmen sind determiniert), d.h., sie liefern bei gleichen Eingaben stets das gleiche Ergebnis. Ein Algorithmus heisst nicht-deterministisch, wenn (an einer Stelle) eine beliebige Auswahlmöglichkeit zwischen verschiedenen Verarbeitungsschritten besteht; das Ergebnis kann dennoch das gleiche sein. Auch nicht terminierende Algorithmen können sinnvoll sein, wenn sie eine Folge von Zwischenergebnissen liefern, etwa die Approximationswerte nach endlich vielen Schritten einer Reihenentwicklung oder die Berechnung der Zahl "pi" mit endlich vielen Nachkommastellen.

Man unterscheidet ausserdem zwischen sequentiellen und parallelen Algorithmen. In einem sequentiellen Algorithmus werden alle Verarbeitungsschritte in der festgelegten Reihenfolge nacheinander abgearbeitet. In einem parallelen Algorithmus können bestimmte Verarbeitungsschritte gleichzeitig abgearbeitet werden, beispielsweise von verschiedenen Prozessoren eines Parallelrechners. Erfolgt die Abarbeitung eines parallelen Algorithmus auf verschiedenen Rechnern eines Netzes, so spricht man auch von einer verteilten Verarbeitung bzw. von einnicht-deterministischem verteilten Algorithmus.

Ursprung

• Bezeichnung nach dem Mathematiker Al Chwarism (um 825)