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:
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.
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.
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.
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.
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.