Definition: Algorithmus
Ein Algorithmus ist eine eindeutige, ausführbare Folge von Anweisungen endlicher Länge zur Lösung eines Problems. Ein Algorithmus besteht aus einem Deklarationsteil (Was wird benötigt?) und einem Anweisungsteil (Wie wird das Problem gelöst?).
Eigenschaften eines Algorithmus
Ein Algorithmus erfüllt zwingend die folgenden Eigenschaften:
Allgemeinheit
Ein Algorithmus ist allgemeingültig, d. h. er löst eine Vielzahl von Problemen (der gleichen Art). Die Auswahl eines einzelnen konkreten Problems erfolgt über Eingabedaten oder Parameter. Ein Algorithmus zum Lösen quadratischer Gleichungen löst alle quadratische Gleichungen.
Eindeutigkeit
An jeder Stelle des Algorithmus muss eindeutig festgelegt sein, was zu tun ist und welcher Schritt der nächste ist. Dafür muss jede Anweisung unmissverständlich formuliert sein. Beim Wechseln der Reifen eines Autos sollten die Einzelschritte in der vorgeschriebenen Folge abgearbeitet werden.
Ausführbarkeit
Jede einzelne Anweisung eines Algorithmus muss vom Computer (vom Mensch) ausführbar sein. Aus mathematischer Sicht dürfte der Algorithmus z. B. keine Division durch 0 enthalten.
Endlichkeit (Finitheit)
Die Beschreibung eines Algorithmus besitzt eine endliche Länge, d. h. er besteht aus einer begrenzten Anzahl von Anweisungen mit begrenzter Länge. Zudem darf ein Algorithmus zu jedem Zeitpunkt für seine Daten nur endlich viel Platz belegen. (Wichtig für diese Eigenschaft ist die Abgrenzung zur Laufzeitlänge. Der Algorithmus des Heron-Verfahrens zum Berechnen einer Quadratwurzel ist sehr wohl endlich, kann jedoch für bestimmte Werte eine unendlich lange Laufzeit haben.
Schön wären für die Praxis noch die Eigenschaften:
Determiniertheit
Wird ein Algorithmus mit den gleichen Eingabewerten und Startbedingungen wiederholt, so liefert er stets das gleiche Ergebnis.
Terminierung
Der Algorithmus ist nach endlich vielen Schritten beendet, d. h. er liefert ein Ergebnis oder hält an.
Beispiele für Algorithmen
- Vorschriften zum Addieren, Subtrahieren oder Multiplizieren von Zahlen
- euklidischer Algorithmus zur Berechnung des ggT zweier Zahlen
- (gute) Bastelanleitungen
- Spielregeln und alltägliche Vorschriften (sind aber leider nur selten exakt ausformuliert und enthalten Teile, die unterschiedlich interpretiert werden können)
- Spielen einer Melodie
- Bedienung eines Handys
Genauigkeit der Definition
Die obige intuitive Definition für den Begriff des Algorithmus ist zwar verständlich, aber mathematisch ungenau. In der kürzeren Geschichte der Mathematik und der theoretischen Informatik (zu Beginn des 20. Jahrhunderts) wurden eine Reihe von Ansätzen entwickelt, die zu einer genauen Definition führen sollten. Die gefundenen Methoden waren letztlich alle gleich leistungsfähig. So kann man z. B. mit Hilfe der Turing-Maschine (Church-Turing-These) den Begriff des Algorithmus wesentlich präziser formulieren.