Algorithmieren

Algorithmieren

Alles wär nicht halb so schwer, wenn das Wörtchen wenn nicht wär.
– Otto Reutter

Algorithmus

Ein Algorithmus¹ ist im weitesten Sinne eine ausführbare Vorschrift, deren einzelne Schritte in ihrer Reihenfolge genau festgelegt sind. Algorithmen müssen folgende Bedingungen erfüllen:

1. Sie müssen aus zweifelsfrei aufeinanderfolgenden Anweisungen bestehen (eindeutig sein).
2. Jede der Anweisungen muss ausführbar sein.
3. Die Zahl der Anweisungen muss endlich sein.
4. Sie müssen zu einem Ergebnis führen (effektiv sein).

Für praktikable Algorithmen folgen einige Einschränkungen bzw. wünschenswerte Eigenschaften:

1. Das Programm darf nicht in einer Endlosschleife hängenbleiben.
2. Bestimmte Algorithmen übersteigen in Speicherbedarf und/oder Rechenzeitbedarf die Grenzen verfügbarer Rechner oder auch des Universums, obwohl sie in beiden Forderungen endlich sind.
3. Sie sollten zum richtigen Ergebnis führen (korrekt sein).
4. Gleiche Eingaben (Startwerte) sollten nachvollziehbar zum selben Ergebnis führen. Ansonsten ist das Verhalten nicht deterministisch.
5. Einschränkungen hinsichtlich der Startwerte sollten klar dokumentiert sein. Der Start mit ungültigen Werten sollte unmöglich gemacht oder wenigstens mit einer Fehlermeldung versehen werden.
6. Sie sollten das Ergebnis mit möglichst geringem Aufwand (an Rechenzeit und Speicherbedarf) erreichen (effizient sein).

Ebenfalls wünschenswert ist, dass ein Algorithmus eine ganze Klasse von gleichartigen Aufgaben löst (allgemeingültig ist). Algorithmen für spezielle Aufgaben sind vielfach schneller ausführbar als allgemeinere, denn sie können bestimmte zusätzliche Eigenschaften der zu bearbeitenden Aufgabe für Abkürzungen ausnutzen, sind manchmal aber gerade deshalb schwerer verständlich.

Der Korrektheitsnachweis für Algorithmen ist selbst nicht algorithmisierbar. Das ist eine Folge einer fundamentalen mathematischen Aussage, des Gödelschen Unvollständigkeitssatzes. Praktisch bedeutet das: Ein Computer findet nicht alle Fehler, da er Programme nicht verstehen, sondern nur abarbeiten kann. Die Bedeutung eines Programms oder Quelltextes ist der Maschine unzugänglich. So können z. B. Endlosschleifen unerkannt bleiben. Ein allgemein gehaltenes Testprogramm kann nur bejahen, dass eine Schleife zum Ende kommt, indem es sie durchläuft und das Ende erreicht. In Endlosschleifen bleibt es hängen und kommt deshalb nie zum Ergebnis. In der Informatik wird das als Halteproblem bezeichnet.

So bleiben Testläufe als Hilfsmittel. Um wirklich sicher zu gehen, müsste ein Algorithmus mit allen möglichen Startwerten getestet werden. Das ist offensichtlich aus Zeitgründen meist unmöglich.

Algorithmen und Tests lassen sich automatisieren. Dazu müssen Algorithmen und Tests in einer bestimmten, von der Maschine ausführbaren Form niedergeschrieben werden: als Programm oder als übersetzbarer Quelltext für ein Programm. Der Weg dahin ist steinig und erfordert Übung und Erfahrung.

Als Mensch abarbeiten

Eine Aufgabe und deren vielleicht noch unbekannten Lösungsweg zu verstehen, beginnt häufig mit dem Abarbeiten von Beispielen. Welche Schritte führe ich nacheinander aus, um zur Lösung zu gelangen? Kann ich meine Handlungen in meiner Sprache so formulieren, dass ein anderer Mensch dies versteht und beim Ausführen zu demselben Ergebnis gelangt? Gelingt dies nicht, können wir die Aufgabe auch keiner Maschine übertragen.

Eine mathematische, zugegebenermaßen nicht sehr praxistaugliche Aufgabe soll zur Veranschaulichung dienen. Wir bestimmen die Länge einer Collatzfolge:

Gegeben sei eine positive natürliche Zahl. Ist die Zahl eins, endet die Berechnung. Andernfalls gibt es zwei Möglichkeiten. Eine gerade Zahl wird halbiert, eine ungerade Zahl wird verdreifacht und um eins erhöht. Danach beginne von vorn. Wie oft müssen diese Anweisungen bis zum Erreichen der Zahl eins durchlaufen werden?

Hier sind die Anweisungen schon im Text vorgegeben. Starten wir zum Beispiel mit der Zahl n=3. Bei jedem Schritt wird in einer Wertverlaufstabelle notiert, welche Werte sich wie und warum ändern. Wir prüfen stets, ob der Endwert 1 erreicht wurde. Andernfalls entscheiden wir uns, ob die Zahl halbiert oder vergrößert werden muss. Jede Entscheidung lässt sich in der Tabelle nachvollziehen. Mit einem zähler führen wir Buch über die Zahl der wiederholten Durchläufe (Schleifen):

zähler	n	n = 1?	n gerade?
0	3	nein	nein
1	10	nein	ja
2	5	nein	nein
3	16	nein	ja
4	8	nein	ja
5	4	nein	ja
6	2	nein	ja
7	1	ja	$\leftarrow$ STOP
Am Ende interessiert nur die Anzahl der wiederholten Durchläufe. Der zähler liefert diese Zahl. Wir können die Ergebnisse für verschiedene Startwerte in einer Tabelle sammeln und für Testzwecke aufbewahren:

Startwert n	Folgewerte	Anzahl der Folgewerte
1	-	0
2	1	1
3	10, 5, 16, 8, 4, 2, 1	7
4	2, 1	2
…

Handlungen beschreiben

Wird ein Algorithmus von Menschen entworfen, stehen uns verschiedene Darstellungsformen zur Verfügung. Wir können den Algorithmus

• in Worten in unserer Muttersprache niederschreiben,
• als Pseudocode etwas formaler und übersichtlicher gestalten oder
• ihn als Struktogramm oder Programmablaufplan grafisch darstellen.

Gegeben ist eine positive Zahl n. Falls n gleich eins ist, endet das Verfahren. Anderenfalls wird wird ein gerades n halbiert, ein ungerades n wird jedoch durch 3n+1 ersetzt. Danach beginnt das Verfahren von vorn. Die Anzahl der Änderungen von n wird gezählt und stellt das Ergebnis dar.

Die Beschreibung in natürlicher Sprache ist oft zu verschwommen: Wann genau passiert das Zählen? Während des Durchlaufes oder nachdem alle Folgewerte notiert wurden? Beides wäre möglich. Insofern ist die Anforderung an einen Algorithmus nicht erfüllt, dass an jedem Punkt eindeutig klar sein muss, welches der nächste auszuführende, führbare Schritt ist. Der zähler wurde nirgends erwähnt. Die Beschreibung muss nachgebessert werden. Hilfreich sind Ausdrucksformen wie „wenn …, dann …, sonst …“ und „solange …, wiederhole …“. Wir schreiben zudem jede einzelne Anweisung auf eine einzelne Zeile. Rücken wir zusammengehörende Blöcke von Anweisungen noch entsprechend ein, gelangen wir zu Pseudocode. Hier der Algorithmus für die Länge der Collatzfolge als Struktogramm, Programmablaufplan und Pseudocode:

Struktogramm	Programmablaufplan

collatz(n):
-----------
	zähler = 0
	solange n ungleich 1
		erhöhe zähler um 1
		wenn n gerade
		dann 
			halbiere n
		sonst
			ersetze n durch 3n+1
	Rückgabe zähler

Der Programmablaufplan, auch Flussdiagramm genannt, gibt einen Weg vor, der abzulaufen ist und sich an manchen Stellen verzweigt. Einige Wege führen wieder zurück zu schon durchlaufenen Stellen, in einer Schleife. Leider tendieren komplexe Programmablaufpläne zu unübersichtlichen, verschlungenen Wegen, die wir als Spaghetticode bezeichnen. Spaghetti bilden ein dreidimensionales Labyrinth. Sprache und damit auch Quelltext ist jedoch linear, eindimensional. Programmablaufpläne verschleiern zudem den Unterschied von Verzweigungen und Schleifen.

Pseudocode und Struktogramm, nach den Erfindern als Nassi-Shneiderman-Diagramm bezeichnet, sind im Wesentlichen linear. Durch die einleitenden Wörter „wenn“ und „solange“ wird deutlich zwischen Verzweigungen und Schleifen unterschieden.² Einrückungen dienen als optische Orientierungshilfe.

Aufgaben

1. Ergänze die Tabelle der zu erwartenden Ergebnisse für weitere Startwerte. Weil wir nicht die ersten Menschen sind, die sich mit dem “3x+1 problem” befassen, kannst Du Deine Ergebnisse mit dieser Zahlenfolge https://oeis.org/A006577 vergleichen.
2. Wie lang ist die Collatzfolge für die Startwerte 41 bzw. 77031? Wie groß werden die Zahlen zwischenzeitlich? Überschreiten sie den Wertebereich für Ganzzahlen in C++?
3. Das Collatzproblem ist ein offenes mathematisches Problem.³ Für kleine Zahlen endet das Collatzverfahren bei eins. Das beweist aber nicht, dass für jeden Startwert endet. Darf man dennoch von einem Algorithmus sprechen?

Algorithmische Grundstrukturen auffinden

Struktogramme und Pseudocode nutzen bestimmte Formen und besondere Wörter, welche das Auffinden der geeigneten Steuerstruktur in modernen Programmiersprachen erleichtern. Diese Grundstrukturen sind ineinander verschachtelt:

• Algorithmen bestehen aus einer Folge (Sequenz) von Anweisungen: „Tue erst dies, dann das.“
• Die Wiederholung (Iteration) von Anweisungen wird auch als Schleife bezeichnet: „Solange die Bedingung erfüllt ist, wiederhole dies.“
• Eine Entscheidung (Alternative) legt fest, ob eine bzw. welche von mehreren Anweisungen einmal auszuführen ist: „Wenn diese Bedingung erfüllt ist, tue dies, sonst jenes.“
• Manche Teile eines Algorithmus können als Unterprogramm ausgelagert werden. Gibt man Anweisungsfolgen einen (möglichst passenden) Namen, kann dieser Block von Anweisungen mehrfach genutzt werden.

Sequenz	Iteration	Alternative	Unterprogramm
Zwei Herangehensweisen führen zu komplexen Programmen:

• Eine große Aufgabe wird in kleinere Teilaufgaben zerlegt (Top-Down-Vorgehen).
• Teilaufgaben werden zu größeren Aufgaben verschmolzen (Bottom-Up-Vorgehen). Beide Vorgehensweisen ergänzen sich beim Programmieren. Daher ist es wichtig zu wissen, a) welche „Bausteine“ schon vorhanden sind und b) wie man sie zusammensetzt.

Im Zusammenwirken mit Steueranweisungen und Funktionen als Unterprogrammen kann das Collatzproblem für eine endliche Menge von Startwerten untersucht werden:

//> basics/collatz.cpp
import std;
 
bool ist_gerade(int n)
{
	return n % 2 == 0;
}
 
int collatz(int n)
{
	int zähler = 0;
	
	while (n != 1)
	{
		++zähler;
		if (ist_gerade(n))
		{
			n /= 2;	
		}
		else
		{
			n = 3*n + 1;
		}		
	}
	return zähler;	
}
 
int main()
{
	for (int n : {1, 2, 3, 4, 5, 6, 7, 8, 9, 41, 77031})
	{
		std::println("collatz({}) = {}", n, collatz(n));
	}
}

Aufgaben

1. Vollziehe das Programm für die kleinen Zahlen handschriftlich nach. Experimentiere. Lasse Zwischenwerte anzeigen. Stimmen diese mit deinen handschriftlichen Überlegungen überein?
2. Wie verhält sich die Funktion collatz(n) bei Zahlen n < 1? Warum?
3. Modifiziere die Funktion collatz(n) so, dass sie Zahlen n < 1 abfängt. Diskutiere mehrere mögliche Wege für diesen Fall.
4. Was würde geschehen, wenn die Anweisung n = 3*n + 1; den Wertebereich für Ganzzahlen übersteigt? Schlage mehrere Möglichkeiten vor, mit dieser Situation umzugehen.

Anmerkungen

1. benannt nach Abu Jafar Mohammed Ibn Musa al-Chwarizmi, der um 800 u.Z. zwei Rechenbücher über die indischen Zahlen schrieb. ↩

2. Es gibt keine if-Schleife. Anfänger vermengen Verzweigung und Schleife häufig, weil beide Anweisungen im Quelltext ähnlich aussehen. ↩

3. Richard K. Guy: Don’t try to solve these problems! American Mathematician Monthly 90, 35-41 (1983) oder wie George Pólya sagte: „Mathematics may not be ready for such problems.“ ↩