Ein Algorithmus ist eine eindeutig beschriebene Folge von Regeln, die Eingaben verarbeitet und daraus ein Ergebnis erzeugt. Das NIST-Glossar beschreibt ihn als klar festgelegten mathematischen Prozess beziehungsweise als Regelwerk, das bei korrekter Ausführung zu einem vorgesehenen Ergebnis führt.
Algorithmen stecken in Suchfunktionen, Navigation, Datenkompression, Bildverarbeitung, Sortierung, Verschlüsselung und zahlreichen alltäglichen Softwarefunktionen. Sie sind keine eigenständigen Programme, sondern die darin umgesetzten Verfahren.
Eingabe, Verarbeitung und Ausgabe
Ein Algorithmus erhält eine Eingabe, führt definierte Verarbeitungsschritte aus und liefert eine Ausgabe. Ein Sortierverfahren übernimmt beispielsweise eine ungeordnete Liste und gibt dieselben Elemente in einer festgelegten Reihenfolge zurück.
Damit das Ergebnis überprüfbar bleibt, müssen Bedeutung und zulässiger Bereich der Eingaben bekannt sein. Ein Verfahren kann mathematisch korrekt sein und trotzdem ungeeignete Ergebnisse liefern, wenn seine Eingaben unvollständig, falsch skaliert oder missverständlich definiert sind.
Deterministische Algorithmen
Ein deterministischer Algorithmus erzeugt bei demselben Ausgangszustand und denselben Eingaben dieselbe Ausgabe. Das erleichtert Tests, Fehlersuche und reproduzierbare Berechnungen.
Auch ein Pseudozufallszahlengenerator arbeitet deterministisch. Seine Zahlen wirken ungeordnet, werden aber aus einem Anfangswert berechnet. Dieser Seed bestimmt die erzeugte Folge.
Heuristische und probabilistische Verfahren
Nicht jede Aufgabe lässt sich mit vertretbarem Aufwand exakt lösen. Heuristische Verfahren suchen deshalb nach einer brauchbaren Lösung, ohne für jeden Fall das bestmögliche Ergebnis zu garantieren. Routenplanung, Optimierung und Mustererkennung verwenden häufig solche Annäherungen.
Probabilistische Algorithmen beziehen Zufallswerte in ihren Ablauf ein. Ihr Verhalten kann zwischen Durchläufen variieren. Der Algorithmus bleibt dennoch definiert: Festgelegt sind die Schritte, die Verwendung der Zufallsquelle und die Bedingungen, unter denen ein Ergebnis akzeptiert wird.
Algorithmus und Implementierung sind nicht dasselbe
Ein Verfahren kann in verschiedenen Programmiersprachen und Programmen umgesetzt werden. Fehler entstehen dabei nicht nur im Algorithmus selbst, sondern auch in seiner Implementierung, in Datentypen, Nebenläufigkeit, Plattformgrenzen oder der Behandlung ungültiger Eingaben.
Ein fachlich passender Algorithmus garantiert deshalb noch keine zuverlässige Software. Tests müssen sowohl das Verfahren als auch seine konkrete Umsetzung prüfen.
Aufwand und Skalierung
Zwei Algorithmen können dasselbe Ergebnis liefern und dennoch sehr unterschiedlich viel Zeit oder Speicher benötigen. Bei kleinen Datenmengen fällt dieser Unterschied kaum auf. Mit wachsendem Bestand kann ein ungeeignetes Verfahren jedoch so langsam oder speicherintensiv werden, dass es praktisch unbrauchbar ist.
Die Komplexitätsanalyse beschreibt, wie der Aufwand mit der Grösse der Eingabe wächst. Sie liefert keine exakte Laufzeit für jedes Gerät, macht aber Verfahren unabhängig von einer einzelnen Messung vergleichbar.
Algorithmen tragen Annahmen
Ein Algorithmus verarbeitet die Welt nicht voraussetzungslos. Kategorien, Grenzwerte, Gewichtungen und Abbruchbedingungen legen fest, welche Unterschiede zählen und welche ignoriert werden. Diese Entscheidungen können technische, wirtschaftliche oder gesellschaftliche Folgen haben.
Bei sicherheitsrelevanten Verfahren kommen weitere Anforderungen hinzu. Ein kryptografischer Algorithmus muss nicht nur funktionieren, sondern bekannten Angriffen widerstehen, korrekt implementiert und mit geeigneten Schlüsseln betrieben werden. Seine Sicherheit hängt damit auch von Zufallsquellen, Schlüsselverwaltung und dem umgebenden System ab.
Merksatz
Ein Algorithmus beschreibt ein Verfahren. Ob daraus ein verlässliches Ergebnis entsteht, hängt zusätzlich von Eingaben, Annahmen, Implementierung und Prüfung ab.