3.3.2.3 Rekursion  |
3.3.2.3 Rekursion
Die Schülerinnen und Schüler ergänzen ihre Problemlösestrategien um rekursive Algorithmen und erkennen deren
Relevanz, indem sie konkrete Problemstellungen (zum Beispiel Türme von Hanoi, Acht-Damen-Problem) lösen.
Die zahlreichen Teilgebiete, in denen rekursive Algorithmen Anwendung finden, zum Beispiel beim Traversieren, Suchen und Sortieren,
machen ihnen die übergeordnete Bedeutung dieser Algorithmenklasse deutlich.
Mithilfe von Beispielen erarbeiten die Schülerinnen und Schüler Kriterien, anhand derer sich der sinnvolle Einsatz von
rekursiven Algorithmen gegenüber iterativen Algorithmen bewerten lässt.
Sie verstehen, wie rekursive Algorithmen von Rechnern ausgeführt werden, indem sie Rekursionsabläufe darstellen.
Die Schülerinnen und Schüler können
(1)
zu geeigneten Problemstellungen (zum Beispiel Türme von Hanoi, Baumtraversierung) rekursive Algorithmen unter Angabe von
Rekursionsschritt und Rekursionsbasis entwerfen und von Hand durchführen
|
|
|
BP2016BW_ALLG_GYM_INF_PK_01_03, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_04, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_09, BP2016BW_ALLG_GYM_INF_PK_01_05, BP2016BW_ALLG_GYM_INF_PK_01_06, BP2016BW_ALLG_GYM_INF_PK_02_13, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_02, BP2016BW_ALLG_GYM_INF_PK_02_01, BP2016BW_ALLG_GYM_INF_PK_03_01, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_06
|
|
|
(2)
das Divide-and-Conquer-Prinzip an geeigneten Problemstellungen erläutern
|
|
|
BP2016BW_ALLG_GYM_INF_PK_01_06, BP2016BW_ALLG_GYM_INF_PK_02_04, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_06
|
|
|
(3)
rekursive Algorithmen zu unterschiedlichen Problemstellungen (zum Beispiel Fakultätsfunktion, Fibonacci-Zahlen, Kochsche
Schneeflocke) implementieren
|
|
|
BP2016BW_ALLG_GYM_INF_PK_02_09
|
|
|
(4)
Rekursionsabläufe darstellen (unter anderem am call stack, Baum)
|
|
|
BP2016BW_ALLG_GYM_INF_PK_01_03, BP2016BW_ALLG_GYM_INF_PK_03_02, BP2016BW_ALLG_GYM_INF_PK_03_01
|
|
|
(5)
iterative Algorithmen und rekursive Algorithmen zur Lösung derselben Problemstellung vergleichen (unter anderem
hinsichtlich Laufzeit) und bewerten
|
|
|
BP2016BW_ALLG_GYM_INF_PK_04_04, BP2016BW_ALLG_GYM_INF_PK_04_03
|
|
|
(6)
das Prinzip des Backtrackings anhand einer geeigneten Problemstellung (zum Beispiel Acht-Damen-Problem, Magische Quadrate,
Zyklensuche) erläutern
|
|
|
BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_04, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_09, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_01_02_01
|
|
|
|
|
