i

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.

flussdiagramm

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.

Suche

v
2.1.1.3
inf-schule.de/algorithmen/grundlagen/algorithmusbegriff/konzept_algorithmus
inf-schule.de/2.1.1.3

Rückmeldung geben