Entwurf einfacher Graphalgorithmen

Die konstruktive Induktion ist eine Methode zur systematischen Entwicklung von Algorithmen. Die Kernidee ist, eine Lösung für Probleminstanzen der Grösse n auf Instanzen der Grösse n+1 zu erweitern. Dadurch ergeben sich in natürlicher Weise rekursive Algorithmen.

In dieser Unterrichtssequenz entwickeln wir Algorithmen, bei denen die konstruktive Induktion zu Lösungen führen kann, die nicht für alle Probleminstanzen korrekt sind. Dies ist vor allem dann der Fall, wenn die Induktion nicht wohlfundiert ist. Wir nutzen diese Erkenntnis, um die entworfenen Algorithmen so zu erweitern, dass sie für alle Probleminstanzen funktionieren.

Wir studieren zu diesem Zweck zwei einfache Graphalgorithmen. Bei diesen funktionieren naive rekursive Implementierungen nur für azyklische Graphen, terminieren aber möglicherweise nicht für zyklische Graphen. Um eine Anbindung an frühere Unterrichtseinheiten zum Programmieren mit Python zu schaffen, motivieren wir die ausgewählten Graphalgorithmen über die Speicherbereinigung (Garbage Collection) moderner Programmiersprachen.