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 Bestimmung der Schachtel mit maximaler Goldmenge aus den vorangehenden Abschnitten.
lege eine Schachtel auf eine Waagschale
solange noch Schachteln vorhanden sind:
greife eine Schachtel heraus und
lege diese Schachtel auf die leere Waagschale
wenn die zuletzt auf die Waage gelegte Schachtel schwerer als die andere Schachtel ist:
lege die andere Schachtel in die Ablage
sonst:
lege die zuletzt auf die Waage gelegte Schachtel in die Ablage
die verbleibende Schachtel auf der Waage hat das größte Gewicht
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 Verfahrensbeschreibung benutzt die Anweisung "alle schachteln nach aufsteigenden Gewicht sortieren", die mit den Möglichkeiten der Waage nicht ausgeführt werden kann.
Sortiere die Schacheln nach aufsteigendem Gewicht. Die Schachtel mit dem größten Gewicht liegt dann ganz rechts.
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. An den Verzweigungsstellen ist nicht klar, welchen Pfad man beschreiten soll.
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 Verfahrensbeschreibung zeigt eine Situation, in der es Schwierigkeiten mit der Endlichkeit der Darstellung gibt. Die drei Punkte deuten jeweils an, dass es immer so weitergehen soll.
Lege Schachtel A und Schachtel B auf die Waagschalen.
Wenn Schachtel B leichter als Schachtel A ist, dann
lege Schachtel B in die Ablage und
lege Schachtel C auf die freie Waagschale
Wenn Schachtel C leichter als Schachtel A ist, dann
lege Schachtel C in die Ablage und
lege Schachtel D auf die freie Waagschale
Wenn Schachtel D leichter als Schachtel A ist, dann
lege Schachtel D in die Ablage und
lege Schachtel E auf die freie Waagschale
...
sonst
lege Schachtel A in die Ablage und
lege schachtel C auf die freie Waagschale
Wenn Schachtel C leichter als Schachtel B ist, dann
lege Schachtel C in die Ablage
lege Schachtel D auf die freie Waagschale
...
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.
Diese Verfahrensbeschreibung löst nur ein spezielles Problem (für 3 gegebene Schachteln).
Bei 3 Schachteln geht das so:
Lege Schachtel A und Schachtel B auf die Waagschalen.
Wenn Schachtel B leichter als Schachtel A ist, dann
lege Schachtel B in die Ablage und
lege schachtel C auf die freie Waagschale
Wenn Schachtel C leichter als Schachtel A ist, dann
Schachtel A ist die mit der größten Goldmenge
sonst
Schachtel C ist die mit der größten Goldmenge
sonst
lege Schachtel A in die Ablage und
lege schachtel C auf die freie Waagschale
Wenn Schachtel C leichter als Schachtel B ist, dann
Schachtel B ist die mit der größten Goldmenge
sonst
Schachtel C ist die mit der größten Goldmenge
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.
