Inf12 - Lernbereich 3: Bäume (ca. 16 Std.)

Zurück zur Übersicht >>> LehrplanPLUS G9 - Informatik

Lehrplantext

Kompetenzerwartungen: Die Schülerinnen und Schüler ...

• modellieren geordnete Binärbäume zu verschiedenen Problemstellungen ihres Erfahrungsbereiches (z. B. digitales Wörterbuch), in denen eine effiziente Datenhaltung wichtig ist. Sie nutzen dabei das Konzept der Trennung von Struktur und Daten sowie das Entwurfsmuster Kompositum und erkennen die Wiederverwendbarkeit eines Entwurfsmusters.
• entwickeln rekursive Algorithmen zur Verwaltung der Daten, die in einem Binärbaum gespeichert sind, insbesondere zur Traversierung eines Binärbaums sowie zum Einfügen und Suchen in einem geordneten Binärbaum, und wenden diese Algorithmen an konkreten Beispielen an.
• implementieren auf der Grundlage gegebener Modelle geordnete Binärbäume mithilfe einer objektorientierten Programmiersprache.
• vergleichen und bewerten geordnete Binärbäume und einfach verkettete Listen hinsichtlich der Anzahl der Schlüsselvergleiche bei Suchanfragen. Dabei wird ihnen bewusst, dass die Effizienz einer Suche insbesondere von der Struktur des geordneten Binärbaums abhängig ist.
• nutzen bei der Bearbeitung von alltagsnahen Anwendungssituationen (z. B. Speicherung und Verarbeitung von Personendaten) eine bereits implementierte Version eines geordneten Binärbaums und passen diese an die konkrete Aufgabenstellung an.
• erläutern an konkreten Beispielen, wie Bäume, die keine geordneten Binärbaume sind, zur Lösung praxisrelevanter Aufgaben verwendet werden, z. B. Huffman-Baum zur Umsetzung einer Textkompression, Quad-Tree zur Flächenindizierung oder Hash-Baum zur Sicherstellung der Integrität von Daten.

Inhalte zu den Kompetenzen:

• Baum: Wurzel, Knoten, Kante, Blatt, Pfad, Höhe, Ebene
• Binärbaum; Spezialfälle: vollständig, balanciert, entartet
• geordneter Binärbaum: Definition, Einfügen und Suchen von Elementen
• Trennung von Struktur und Daten bzw. Inhalt
• Entwurfsmuster Kompositum
• Traversierungsstrategien im Binärbaum: Preorder, Inorder, Postorder