Definition „Algorithm“ Was ist ein Algorithmus?

Algorithmen finden sich in praktisch jedem Computerprogramm. Sie geben eine Art zielgerichtete Anleitung, nach der eine bestimmte Aufgabe Schritt für Schritt gelöst werden kann.

Ein Algorithmus ist, vereinfacht gesagt, eine fest definierte und endliche Vorgehensweise, mit der ein Problem gelöst werden kann. Er enthält Anweisungen, die Schritt für Schritt befolgt werden, um ein bestimmtes Ziel zu erreichen. Die einzelnen Schritte sind eindeutig definiert, sodass sie immer in der beabsichtigten Art und Reihenfolge ausgeführt werden.

Algorithmen gibt es in vielen Bereichen. Ein bekanntes Beispiel aus der Mathematik ist zum Beispiel der euklidische Algorithmus. Er beschreibt eine präzise Vorgehensweise, mit der man den größten gemeinsamen Teiler von zwei natürlichen Zahlen bestimmen kann. Aber auch alltägliche Dinge können Algorithmen sein: In festgelegten Einzelschritten kann man einen Zauberwürfel ausgehend von jeder beliebigen Startposition lösen.

Allgemeinheit von Algorithmen

Ein Algorithmus ist keine Handlungsvorschrift für ein spezifisches Problem, sondern soll allgemein eine bestimme Art von Problem lösen. Im euklidischen Algorithmus geht es beispielsweise nicht darum, das Problem „Was ist der größte gemeinsame Teiler von 12 und 4958?“ zu lösen.

Vielmehr soll dieser Algorithmus ganz allgemein das Problem lösen, den größten gemeinsamen Teiler zweier beliebiger natürlicher Zahlen zu finden. Der Algorithmus einer Suchmaschine ist nicht spezifisch für „Rote Gummistiefel in Größe 42“ gültig, sondern verarbeitet beliebige Eingaben auf abstrakter Ebene.

Finitheit

Ein Algorithmus muss sich mit einem endlichen Text vollständig beschreiben lassen (statische Finitheit) und darf zur Laufzeit nicht unbegrenzt Speicher mit Zwischenergebnissen belegen (dynamische Finitheit), wenn er nach endlicher Zeit ein Ergebnis liefern soll.

Determiniertheit und Determinismus

Ein Algorithmus muss zu jedem Zeitpunkt eine konkrete Anweisung für ein Zwischenergebnis liefern. Es muss also immer klar sein, was als nächstes mit einer Eingabe oder einem Zwischenergebnis zu tun ist. Wenn die Vorgehensweise eindeutig ist, also je Zwischenergebnis nur genau ein Folgeschritt ausgeführt werden kann, ist der Algorithmus deterministisch.

Es gibt auch nicht-deterministische Algorithmen. Sie beinhalten mindestens einen Schritt, in dem ein Zwischenergebnis auf mehreren gleichwertigen Pfaden weiterverarbeitet werden kann. Die Entscheidung, wie ein Zwischenergebnis behandelt wird, steht an dieser Stelle nicht fest, sondern wird zum Beispiel durch Zufall bestimmt.

Deterministische Algorithmen haben daher immer determinierte Ergebnisse, sprich eine bestimmte Eingabe endet immer im gleichen Ergebnis. Nicht-deterministische Algorithmen hingegen können bei unveränderter Eingabe unterschiedliche Ergebnisse liefern oder auf unterschiedlichen Wegen zu determinierten Ergebnissen kommen.

Terminiertheit

Ein Algorithmus soll Eingabewerte annehmen und ein dazu passendes Ergebnis liefern. Dazu gehört auch, dass die Verarbeitung bei ungültigen Zwischenergebnissen oder Eingaben abbricht und nicht in eine Endlosschleife einsteigt: Ein Algorithmus ist normalerweise terminierend, muss also nach endlicher Zeit ein Ergebnis liefern. Nicht terminierende Algorithmen existieren ebenfalls. Hier geht es meist um Vorgänge, die ganz explizit niemals von selbst abbrechen sollen, weil sie zum Beispiel auf unbestimmte Zeit eine Maschine steuern.

Algorithmen in der Informatik

Es gibt unzählige etablierte Algorithmen, die in der Softwareentwicklung für verschiedenste Zwecke genutzt werden:

• Komplexe Berechnungen, z. B. Zassenhaus-Algorithmus

• Sortierverfahren, z. B. Bubblesort, Quicksort

• Suchverfahren, z. B. Lineare Suche, A*-Suche

• Verschlüsselungsverfahren, z. B. RSA, Blowfish

• Kompression, z. B. Huffman-Kodierung

Algorithmen in Hardware

Ein Algorithmus kann in elektronischen Geräten auch per Hardware umgesetzt werden. Eine anwendungsspezifische integrierte Schaltung (ASIC) ist zum Beispiel ein Schaltkreis, der einen spezifischen Algorithmus abbilden kann. Wenn ein Gerät eine bestimmte Aufgabe übernimmt, die algorithmisch gelöst werden soll, ist ein solch spezialisierter Chip eine performante Alternative zur Verarbeitung per Software.

Bei einem ASIC ist der Algorithmus allerdings Hardware-seitig verankert bzw. abgebildet. Es gibt auch Field Programmable Gate Arrays (FPGA), mit denen man flexibel eigene Schaltungen konfigurieren und somit ganz nach Bedarf verschiedenste Algorithmen abbilden kann. Diese kommen aktuell vermehrt in Embedded Systems zum Einsatz.

(ID:45675222)