Bäume und Backtracking

Dieses Leitprogramm führt in das Thema von Bäumen und Backtracking ein und richtet sich an Gymnasialschülerinnen und -schüler im letzten Schuljahr vor der Matur. Die folgenden Voraussetzungen müssen gegeben sein:

• Es wird auf der Baumsichtweise aufgebaut, wie sie in der Wahrscheinlichkeitsrechnung gebraucht wird. In das Thema der Wahrscheinlichkeitsrechnung sollte im Mathematikunterricht deshalb schon eingeführt worden sein.
• Der Begriff des ungerichteten Graphen sollte bekannt sein. Eine Zusammenfassung dieses Themas ist im Anhang gegeben.
• Die Lernenden benötigen Kenntnisse in einer Programmiersprache. (Der Code in diesem Leitprogramm ist in Processing angegeben, nähere Informationen dazu unter www.processing.org). Neben den Grundlagen muss auch die rekursive Programmierung verstanden worden sein.