Algorithmus

Begriff und Bedeutung

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Er besteht aus endlich vielen wohldefinierten Einzelschritten und überführt bei der Problemlösung eine bestimmte Eingabe in eine bestimmte Ausgabe. Algorithmen können als Computerprogramm umgesetzt, aber auch in menschlicher Sprache formuliert werden.

In Informatik und Mathematik sind Algorithmen zentral. Als Programme oder elektronische Schaltungen steuern sie Computer und andere Maschinen. Sie werden unter anderem in der Berechenbarkeitstheorie, Komplexitätstheorie und Algorithmik beziehungsweise Algorithmentheorie untersucht.

Formale Modelle und Berechenbarkeit

Für eine mathematisch strenge Definition braucht man ein Berechenbarkeitsmodell: ein Modell dafür, wie eine Funktion Eingaben in Ausgaben umwandelt. Das Referenzmodell ist die Turingmaschine von Alan Turing. Weitere Formalisierungen sind Registermaschinen, der Lambda-Kalkül von Alonzo Church, rekursive Funktionen, Chomsky-Grammatiken und Markow-Algorithmen.

Diese Methoden besitzen dieselbe Berechnungsstärke: Sie können durch eine Turingmaschine emuliert werden und umgekehrt eine Turingmaschine emulieren. Formal heißt eine Berechnungsvorschrift genau dann Algorithmus, wenn eine äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt.

Die Church-Turing-These besagt, dass jedes intuitiv berechenbare Problem durch eine Turingmaschine lösbar ist. Sie ist nicht mathematisch beweisbar, weil „intuitiv berechenbares Problem“ nicht eindeutig formal definiert ist. Denkbar wären daher intuitiv berechenbare Probleme, die nicht als berechenbar gelten; ein solches Problem wurde bisher nicht gefunden. Ein Problem heißt berechenbar, wenn ein terminierender Algorithmus es lösen kann, also eine passend programmierte Turingmaschine es in endlicher Zeit lösen könnte.

Neben Turingmaschinen gibt es abstrakte Maschinenmodelle für komplexere reale Probleme. Sie können etwa mächtigere Operationen wie Fourier-Transformationen in einem Rechenschritt oder parallele Operationen wie die Addition zweier Vektoren erlauben. Eine Sequential Abstract State Machine (seq. ASM) soll durch einen endlichen Programmtext festgelegt und schrittweise ausführbar sein. Sie muss für bestimmte Zustände terminieren, aber nicht stets; außerdem darf sie pro Schritt nur begrenzt viele Zustände ändern und inspizieren.

Wichtige Eigenschaften

Finitheit bedeutet erstens statische Finitheit: Die Beschreibung oder der Quelltext hat endliche Länge und besteht aus einer begrenzten Zahl von Zeichen. Zweitens bedeutet dynamische Finitheit: Während der Ausführung wird zu jedem Zeitpunkt nur begrenzt viel Speicherplatz benötigt.

Ausführbarkeit oder Effektivität verlangt, dass jeder Schritt tatsächlich ausführbar ist und der Effekt jeder Anweisung eindeutig festgelegt ist. Terminierung bedeutet, dass ein Algorithmus für jede mögliche Eingabe nach endlich vielen Schritten anhält oder kontrolliert abbricht. Bei manchen Eingaben kann ein nicht terminierendes Verfahren in eine Endlosschleife geraten. Nicht terminierendes Verhalten kann aber gewünscht sein, etwa bei Steuerungssystemen, Betriebssystemen oder interaktiven Programmen. Donald E. Knuth schlägt dafür die Bezeichnung rechnergestützte Methoden (Computational Methods) vor. Ob ein beliebiger Algorithmus mit einer beliebigen Eingabe terminiert, ist wegen des Halteproblems nicht durch einen Algorithmus entscheidbar.

Ein Algorithmus ist determiniert, wenn gleiche Startbedingungen und Eingaben stets gleiche Ergebnisse liefern. Er ist deterministisch, wenn zu jedem Zeitpunkt der nächste Handlungsschritt eindeutig festgelegt ist. Jeder deterministische Algorithmus ist determiniert, aber nicht umgekehrt: Quicksort mit zufälliger Wahl des Pivotelements bleibt bei gleicher Eingabe und eindeutiger Sortierung im Ergebnis gleich, wählt aber zufällig seinen Weg. Bubblesort und der euklidische Algorithmus sind deterministisch. Nichtdeterministische Algorithmen lassen sich im Allgemeinen mit keiner realen Maschine, auch nicht mit Quantencomputern, direkt umsetzen.

Algorithmen, Programme und Anwendungen

Ein Algorithmus ist eine abstrakte Vorgehensweise; ein Programm ist eine konkrete, an Möglichkeiten und Anforderungen einer realen Maschine angepasste Form davon. Algorithmen zerlegen eine Aufgabe in Teilschritte, für die wiederum Algorithmen verwendet werden. Bei quadratischen Gleichungen gehören beispielsweise die Grundrechenarten dazu. Programme nutzen dafür eingebaute Operatoren oder Programmbibliotheken. Durch Modularisierung werden nebensächliche Details in Unterprogramme ausgelagert, sodass der eigentliche Algorithmus kompakt und nachvollziehbar bleibt. Programmablaufpläne können nach DIN 66001 oder ISO 5807 dargestellt werden.

Computer-Algorithmen reichen von elektronischen Steuergeräten im Kfz über Rechtschreib- und Satzbaukontrolle bis zur Analyse von Aktienmärkten. In werbefinanzierten Online-Angeboten bestimmen Algorithmen oft, welche Inhalte und Anzeigen angezeigt werden. Sie sollen Anwender möglichst lange auf einer Plattform halten und Anzeigen auswählen, bei denen ein Klick besonders wahrscheinlich ist. Der Begriff wird auch für komplexe, nicht transparente Entscheidungsregeln etwa von Suchmaschinen verwendet.

Künstliche Intelligenz verwendet ebenfalls Algorithmen zur Lösung vorgegebener Probleme. Im Allgemeinen spricht man davon, wenn zusätzlich zuvor erlerntes Wissen genutzt wird: In einer Lernphase werden charakteristische Muster identifiziert und eingeordnet. Mit einer passenden Wissensbasis können geeignete Algorithmen geschriebene und gesprochene natürliche Sprache verarbeiten, Gesichter oder Objekte identifizieren oder Texte formulieren.

Eine Heuristik ist eine Methode, die aus unvollständigen Eingangsdaten möglichst sinnvolle Ergebnisse gewinnen soll. Der Übergang zum Algorithmus ist fließend: Exakt definierte Heuristiken sind selbst Algorithmen. Wenn nicht für jeden Schritt festgelegt ist, wie vorzugehen ist, sondern der Anwender günstig raten muss, lässt sich die Heuristik nicht vollständig als Algorithmus formulieren.

Analyse und typische Beispiele

Die Algorithmenanalyse untersucht meist theoretisch statt anhand einer konkreten Programmiersprache die zugrunde liegenden Konzepte. Dafür werden Algorithmen stark formalisiert und mit formaler Semantik untersucht. Die Komplexitätstheorie betrachtet Ressourcen wie Rechenzeit und Speicherbedarf. Die Ergebnisse werden meist asymptotisch angegeben, beispielsweise als asymptotische Laufzeit, und hängen gewöhnlich von der Länge der Eingabe ab. Die Berechenbarkeitstheorie untersucht dagegen, ob ein Algorithmus überhaupt erfolgreich beendet werden kann.

Als ältester bekannter nicht-trivialer Algorithmus gilt der euklidische Algorithmus. Weitere Typen sind randomisierte Algorithmen mit Zufallskomponente, Approximationsalgorithmen als Annäherungsverfahren, evolutionäre Algorithmen nach biologischem Vorbild und Greedy-Algorithmen. Ein einfaches Beispiel ist die Lösung des Spiels Türme von Hanoi mit drei Spielsteinen. Als erster für einen Computer gedachter Algorithmus wurde 1843 Ada Lovelaces Verfahren zur Berechnung von Bernoullizahlen in ihren Notizen zu Charles Babbages Analytical Engine festgehalten; es wurde nicht implementiert, weil Babbage die Maschine nicht vollenden konnte.