Exkurs – Algorithmisches Problemlösen
Orientierung
Es ist manchmal gar nicht so einfach, einen Algorithmus zur Lösung eines Problems zu entwickeln –
insbesondere dann, wenn das Problem komplizierter ist.
Am Beispiel Kleeblatt suchen
sollen die wesentlichen Schritte im Folgenden noch einmal
kurz zusammengestellt werden.
Das Problem: Kleeblatt suchen
Hier noch einmal eine Beschreibung des zu lösenden Problems.
Kara ist auf der Suche nach einem Kleeblatt. Kara soll hierzu geradeaus weiterlaufen, bis sie/er ein Kleeblatt gefunden hat. Aber, es befinden sich manchmal Baumstümpfe im Weg. Kara muss diese Hindernisse dann umlaufen.
Aufgabe 1: Das Problem beschreiben
Probleme lassen sich (nicht nur) in PythonKara sehr gut durch Abbildungen einer Vorher-Nachher-Beschreibung der Kara-Welt darstellen.
(a) Erkläre, warum die folgende Abbildung nicht gut geeignet ist, um das Problem zu beschreiben.
(b) Ist dieses Beispiel besser geeignet, um das Problem zu beschreiben? Finde Argumente für und gegen dieses Beispiel.
(c) Erzeuge selbst eine Kara-Welt (vorher und nachher), die gut geeignet ist, um das Problem darzustellen.
Ideen suchen
Algorithmen bzw. Programme kann man oft nicht gleich hinschreiben. Zunächst muss man nach geeigneten Ideen suchen.
Aufgabe 2: Die Ideensuche
Die folgenden Überlegungen und Handlungen können alle bei der Ideensuche auftreten. Bringe sie in die richtige Reihenfolge.
T: Ich überlege mir, welche grobe Struktur vorliegt: Welche Teilaufgaben (z.B. Baumreihe umlaufen) sind zu erledigen? (Diese Teilaufgaben muss ich noch nicht im Detail ausführen.) Gibt es eine wichtige äußere Schleife? Was wäre die entsprechende Schleifenbedingung?
U: Ich suche Gemeinsamkeiten in meinen eigenen Lösungsabläufen. Passiert etwas immer zu Beginn oder immer am Ende?
A: Ich spiele selbst Kara und löse das Problem für verschiedene Ausgangszustände.
O: Ich teste mein überlegtes grobes Vorgehen an verschiedenen möglichst unterschiedlichen Ausgangszuständen. Kann man es überall anwenden oder gibt es Sonderfälle, die noch nicht berücksichtigt sind? In diesem Fall müsste ich nachbessern.
Algorithmus entwickeln und formulieren
Erste Ideen sind nicht präzise genug, dass sie von einer Maschine bearbeitet werden können; sie stellen also keinen Algorithmus dar. Wir müssen das Verfahren deshalb noch präziser formulieren.
Beispiel: Bei der Ideensuche könnte man notiert haben: „WENN man vor einem Baum steht, dann muss man den Baum / die Baumreihe umlaufen“. Nun wäre es an der Zeit, klarzumachen, wie man eine Baumreihe bzw. einen Baum umläuft.
Bei dieser Präzisierung bieten sich für kleinere Probleme Flussdiagramme an. Bei größeren Problemen haben sich Struktogramme bewährt.
Ein mögliches Ergebnis der Präzisierung ist dieses Struktogramm.
Aufgabe 3: Warum nicht gleich programmieren?
Begründe, warum man nach der Ideensuche nicht direkt mit dem Programmieren beginnen sollte, sondern stattdessen erst einmal den Algorithmus in einer anderen Form (z.B. als Struktogramm) entwickelt.
Algorithmus implementieren
Der letzte Schritt zur Entwicklung einer lauffähigen Problemlösung besteht darin, den Algorithmus in eine vom Ausführsystem vorgegebene Sprache zu übersetzen und zu testen. In unserem Kara-System ist das die Programmiersprache Python.
while not kara.onLeaf():
if kara.treeFront():
kara.turnLeft()
kara.move()
kara.turnRight()
kara.move()
while kara.treeRight():
kara.move()
kara.turnRight()
kara.move()
kara.turnLeft()
else:
kara.move()
kara.removeLeaf()
Hierbei muss man dann natürlich die Besonderheiten der vorgegebenen Sprache beachten.
Aufgabe 4: Was heißt eigentlich „Programmieren“?
Nimm Stellung zu folgendem Zitat: „Some of the best programming is done on paper, really. Putting it into the computer is just a minor detail.“ (Max Kanat-Alexander: Code Simplicity: The Fundamentals of Software, Sebastopol: O'Reilly (2012))
Das Wichtigste notieren
Aufgabe 5: Ein Wissensspeicher für das Algorithmische Problemlösen
Die vier Schritte, mit denen wir dieses Problem gelöst haben, sind so wichtig, dass wir sie notieren sollten. Im Wissensspeicher sind die vier Schritte vorgegeben. Beschreibe jeden der Schritte. Gib an, welche Hilfsmittel (Sprache, Diagramme, ...) genutzt werden. Lass ggf. etwas Platz, um später noch Punkte zu ergänzen. Den unteren Bereich zu den Fehlertypen kannst du erst einmal freilassen.
