Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

Fachkonzept - Algorithmus

Was ist ein Algorithmus?

Algorithmen kommen immer dann ins Spiel, wenn Verarbeitungsvorgänge automatisiert durchgeführt werden sollen. Die Vorgänge müssen dann exakt beschrieben werden.

Ein Algorithmus ist eine Verarbeitungsvorschrift zur Lösung eines Problems, die so präzise formuliert ist, dass sie auch von einer Maschine abgearbeitet werden kann.

Als Beispiel betrachten wir einen Algorithmus zur Robotersteuerung.

drehe dich um 90° nach rechts
gehe einen Schritt vorwärts
drehe dich um 90° nach links
solange du vor einem Ziegel stehst, tue folgendes:
    hebe einen Ziegel auf
    drehe dich um 90° nach links
    gehe einen Schritt vorwärts
    gehe einen Schritt vorwärts
    drehe dich um 90° nach rechts
    lege den Ziegel hin
    drehe dich um 90° nach rechts
    gehe einen Schritt vorwärts
    gehe einen Schritt vorwärts
    drehe dich um 90° nach links
drehe dich um 90° nach links
gehe einen Schritt vorwärts
drehe dich um 90° nach rechts

Dieser Algorithmus löst das in der folgenden Abbildung dargestellte Transportproblem:

Welt - vorher Welt - nachher

Der Roboter soll hier einen Turm (mit beliebig vielen Ziegeln) zwei Felder in Richtung Süden transportieren.

Einen Algorithmus kann man auf unterschiedliche Weise formulieren. Dabei muss man auf die Präzision der Darstellung achten.

Oft ist es gar nicht so einfach zu entscheiden, ob eine Verfahrensbeschreibung als Algorithmus bezeichnet werden kann oder nicht. Die folgenden Anforderungen sollen als Orientierungshilfe dienen.

Anforderungen an Verfahrensbeschreibungen - Ausführbarkeit

Ausführbarkeit bedeutet, dass der Prozessor jeden Einzelschritt des Algorithmus ausführen kann. Beachte, dass die Ausführbarkeit eines Algorithmus immer von den Möglichkeiten des Prozessors abhängt.

Die folgende Abbildung zeigt eine Situation, in der es Schwierigkeiten mit der Ausführbarkeit gibt.

Ausführbarkeit

Anforderungen an Verfahrensbeschreibungen - Eindeutigkeit

Eindeutigkeit bedeutet, dass die Abfolge der einzelnen Schritte genau festgelegt ist.

Bei der Abarbeitung der Anweisungen eines Algorithmus muss also immer genau feststehen, wie es weitergeht. Hieraus ergibt sich, dass ein Algorithmus bei denselben Ausgangsdaten immer zum selben Ergebnis kommt. Beachte, dass wir im Rahmen der theoretischen Informatik auch eine Form der Mehrdeutigkeit bei Algorithmen zulassen.

Die folgende Abbildung zeigt eine Situation, in der es Schwierigkeiten mit der Eindeutigkeit gibt.

Eindeutigkeit

Anforderungen an Verfahrensbeschreibungen - Endlichkeit

Endlichkeit bedeutet, dass die Beschreibung aus einem Text endlicher Länge besteht. Die Endlichkeit der Darstellung ist eigentlich eine Selbstverständlichkeit, da eine unendlich lange Beschreibung in der Praxis nicht vorkommen kann.

Die folgende Abbildung zeigt eine Situation, in der es Schwierigkeiten mit der Endlichkeit der Darstellung gibt.

Endlichkeit

Anforderungen an Verfahrensbeschreibungen - Allgemeinheit

Allgemeinheit bedeutet, dass nicht nur ein singuläres Problem, sondern eine ganze Klasse von Problemen gelöst werden soll. Die Forderung nach der Allgemeinheit der Problemstellung lässt man natürlich fallen, wenn man nur an der Lösung eines Einzelfalls interessiert ist.

Die folgende Abbildung zeigt eine Situation, in der es Schwierigkeiten mit der Allgemeinheit gibt.

Allgemeinheit

Zur Herkunft des Algorithmusbegriffs

Die Bezeichnung "Algorithmus" leitet sich aus dem Namen Al-Khwarizmi ab. Abu Abd Allah Mohammed Ibn Musa Al-Khwarizmi - so der vollständige Name - war ein choresmischer Universalgelehrter und Mathematiker, der etwa von 780 bis 850 n. Chr. lebte. Al-Khwarizmi stammte aus Choresm (arab. Khwarizmi) - das ist eine Gegend, die heute Teil von Usbekistan und Turkmenistan ist und lebte und arbeitete in Bagdad. Al-Khwarizmi beschäftigte sich u. a. mit Verfahren zur Lösung von Gleichungen. Diese Verfahren können aus heutiger Sicht als Algorithmen bezeichnet werden. Das ist wohl der Grund, weshalb Al-Khwarizmi Pate für maschinell verarbeitbare Verfahren geworden ist.

X

Fehler melden

X

Suche