3.3.1.2 Datenstrukturen  |
3.3.1.2 Datenstrukturen
Ausgehend von Beispielen aus dem Alltag lernen die Schülerinnen und Schüler unterschiedliche Ansätze kennen, Daten
mithilfe von Arrays, Listen, Bäumen und Graphen systematisch zu strukturieren. Je nach Codierungsform einer Datenstruktur existieren
unterschiedliche Möglichkeiten, auf dieser zu navigieren, Elemente hinzuzufügen oder zu entfernen. Diese Möglichkeiten
werden dann von Algorithmen auf Datenstrukturen zur Lösung komplexerer Problemstellungen genutzt.
Abstrakte Datentypen (ADT) kapseln ihre interne Datenstruktur und sind damit unabhängig von einer konkreten Implementierung. Die
Schülerinnen und Schüler lernen mit dem Stack einen ADT kennen, der unter anderem zur Auflösung von Rekursion und
Realisierung von Unterprogrammaufrufen Anwendung findet. Der ADT Queue eignet sich insbesondere, um Alltagssituationen zu modellieren, in
denen Warteschlangen auftreten.
Die Schülerinnen und Schüler können
(1)
zweidimensionale Arrays in ihrer Implementierung verwenden
|
|
|
BP2016BW_ALLG_GYM_INF_PK_02_09, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_03_06
|
|
|
(2)
einfach verkettete Listen als Beispiel einer linearen Struktur und Grundoperationen (zum Beispiel Einfügen, Löschen)
implementieren
|
|
|
BP2016BW_ALLG_GYM_INF_PK_02_09, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_01
|
|
|
(3)
Binärbäume als Beispiel einer Baumstruktur implementieren
|
|
|
BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_04, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_03, BP2016BW_ALLG_GYM_INF_PK_02_09
|
|
|
(4)
Graphen in den Repräsentationsformen Adjazenzmatrix und Adjazenzliste beschreiben
|
|
|
BP2016BW_ALLG_GYM_INF_PK_03_01
|
|
|
(5)
Begriffe aus der Graphentheorie (unter anderem Knoten, Kanten, Knotengrad, Kreis/Zyklus) und
Eigenschaften von Graphen (unter anderem gerichtet/ungerichtet, gewichtet/ungewichtet,
zyklisch/azyklisch) verwenden
|
|
|
BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_09, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_10
|
|
|
(6)
erläutern, dass Bäume spezielle Graphen sind (Begriffe: Wurzel, innerer Knoten,
Blatt)
|
|
|
BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_09, BP2016BW_ALLG_GYM_INF_PK_03_02, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_02_10
|
|
|
(7)
das Konzept des Abstrakten Datentyps (unter anderem anhand von Set) erläutern
|
|
|
BP2016BW_ALLG_GYM_INF_PK_03_02, BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_01_15
|
|
|
(8)
den Abstrakten Datentyp (ADT) Stack mit den Operationen isEmpty, push, pop und top
beschreiben (LIFO-Prinzip) und mithilfe einer geeigneten Datenstruktur implementieren
|
|
|
BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_01_15, BP2016BW_ALLG_GYM_INF_PK_04_03
|
|
|
(9)
den Abstrakten Datentyp (ADT) Queue mit den Operationen isEmpty, enqueue, dequeue und front
beschreiben (FIFO-Prinzip) und mithilfe einer geeigneten Datenstruktur implementieren
|
|
|
BP2016BW_ALLG_GYM_INF_IK_11-12-LF_02_01_15, BP2016BW_ALLG_GYM_INF_PK_04_03
|
|
|
(10)
Datenstrukturen zur Modellierung und Lösung ausgewählter Anwendungsfälle (zum Beispiel Straßennetz, Geldflüsse,
Freundschaftsbeziehungen in sozialen Netzwerken, Organigramm, To-do-Liste, Klammerausdrücke, Rangierbahnhof) nutzen
|
|
|
BP2016BW_ALLG_GYM_INF_PK_04_02
|
|
|
(11)
einen Algorithmus auf Graphen implementieren (unter Verwendung geeigneter Bibliotheken oder Frameworks)
|
|
|
BP2016BW_ALLG_GYM_INF_PK_02, BP2016BW_ALLG_GYM_INF_PK_02_09, BP2016BW_ALLG_GYM_INF_PK_02_06, BP2016BW_ALLG_GYM_INF_PK_03_04
|
|
|
|
|
