Kontakt
Themen
Modellierung und Implementierung von dynamischen nicht-linearen Datenstrukturen und von Anwendungen mit dynamischen nicht-linearen Datenstrukturen in kontextbezogenen Problemstellungen.
Leitfrage:Wie können Daten im Anwendungskontext mit Hilfe von Graphen und binärer Baumstrukturen verwaltet werden? Wie kann in einem Graphen ein beliebiger, alle oder der kürzeste Weg zwischen zwei Knoten effizient gefunden werden? Welche Kanten müssen in einem zusammenhängenden Graphen mindestens verbleiben, sodass dieser bei minimaler Summe der Kantengewichte weiterhin zusammenhängend ist. Wie kann ich mit einem Binärbaum Daten sortiert verwalten?
Vorhabenbezogene Konkretisierung:
Anhand von Beispielen für Graphen werden grundlegende Begriffe eingeführt und die beiden Darstellungsformen Adjazenzmatrix und Adjazenzliste erarbeitet. Die Funktionalität der Methoden der Klassen Graph, Vertex und Edge aus den Vorgaben für das Zentralabitur NRW wird erarbeitet. Die Fragestellung nach der Suche eines oder aller Wege zwischen zwei Knoten in einem Graphen motiviert die Erarbeitung von Algorithmen zur Tiefen- und Breitensuche, mit denen Graphen systematisch durchsucht werden können. Anschließend werden anhand von Anwendungskontexten Algorithmen für die Bestimmung kürzester Wege in einem Graphen sowie zur Konstruktion von minimalen Spannbäumen modelliert und zum Teil auch implementiert.
Die Datenstruktur Binärbaum mit den notwendigen Begrifflichkeiten wird als Spezialfall eines Graphen anhand von Anwendungskontexten erarbeitet. Die entsprechende Klasse BinaryTree <ContentType> der Vorgaben für das Zentralabitur NRW wird zur Modellierung und Implementierung verschiedener Problemstellungen verwendet. Unter anderem sollen die verschiedenen Baumtraversierungen (Pre-, Post- und In-Order) implementiert werden.
Mithilfe einer anwendungsorientierten Problemstellung werden die Operationen der Datenstruktur Suchbaum thematisiert und die Klasse BinarySearchTree <ContentType> (der Materialien für das Zentralabitur in NRW) modelliert und zumindest partiell implementiert.
Zeitbedarf: 40 Stunden
Sequenzierung des Unterrichtsvorhabens:
|
Unterrichtssequenzen |
Zu entwickelnde Kompetenzen |
Beispiele, Medien, Materialien |
|
1. Analyse von Graphen in verschiedenen Kontexten (a) Grundlegende Begriffe (Graph, gerichtet – ungerichtet, Knoten, Kanten, Kantengewicht) (b) Aufbau und Darstellung von Graphen anhand von Graphenstrukturen in verschiedenen Kontexten (Adjazenzmatrix, Adjazenzliste) |
Die Schülerinnen und Schüler
|
Beispiel: „Das Haus vom Nikolaus“ Das Haus vom Nikolaus ist das bekannteste Beispiel für einen Graphen, für den ein Eulerweg, aber kein Eulerkreis existiert. Anhand dieses Beispiels werden die Grundbegriffe der Graphentheorie sowie die Darstellung eines Graphen als Adjazenzmatrix eingeführt. Beispiel: Soziale Netzwerke Da es in dem Graph eines sozialen Netzwerks im Verhältnis zu den Knoten nur wenige Kanten gibt, bietet sich dieses Beispiel zur Einführung der Darstellung eines Graphen in Form von Adjazenzlisten an. Materialien: Ergänzungsmaterialien zum Lehrplannavigator Unterrichtsvorhaben LK-Q1.V |
|
2. Die Datenstruktur Graph im Anwendungskontext unter Nutzung der Klassen Graph, Vertex und Edge. (a) Erarbeitung der Klassen Graph, Vertex und Edge und beispielhafte Anwendung der Operationen (b) Bestimmung von Wegen in Graphen im Anwendungskontext (Tiefensuche, Breitensuche) (c) Bestimmung von kürzesten Wegen in Graphen im Anwendungskontext (Backtracking, Dijkstra). (d) Bestimmung von minimalen Spannbäumen eines Graphen im Anwendungskontext. |
Beispiel: Soziale Netzwerke Ausgehend von dem Problem der Berechnung der Dichte eines sozialen Netzwerkes werden die Funktionalitäten der Methoden der Klassen Graph, Vertex und Edge erarbeitet und erste Beispiele modelliert und implementiert:
Beispiel: Wegsuche Ausgehend von dem Problem der Suche eines beliebigen Weges zwischen zwei Knoten in einem Graphen wird der Backtracking-Algorithmus zur Tiefensuche erarbeitet. Durch Wegfall der Abbruchbedingung „Zielknoten gefunden“ lassen sich mit dem Algorithmus alle Wege zwischen Start und Zielknoten finden. Als Alternative wird der Algorithmus zur Breitensuche erarbeitet, der als Ergebnis eine Liste aller Knoten, die auf dem Weg vom Start- zum Zielknoten gefunden wurde, zurückgibt. Ausgehend vom Zielknoten kann durch Vorgängersuch in dieser Liste ein Weg vom Start- zum Zielknoten gefunden werden. Damit wird das Verfahren beim Dijkstra-Algorithmus vorbereitet. Beispiel: Kürzeste Wege Ausgehend vom Backtracking-Algorithmus zur Bestimmung aller Wege von einem Start- zu einem Zielknoten in einem Graphen wird ein Algorithmus zur Bestimmung des kürzesten Weges erarbeitet. Aufwandbetrachtungen führen zu der Frage nach einem effizienteren Algorithmus. Der Dijkstra-Algorithmus kann durch geschickte Aufgabenstellung, ggf. unter Einbeziehung des in den Materialien enthaltenen Programms GraphTool von der Lerngruppe selbstständig erarbeitet und auf mehrere Beispiele angewandt werden. Die Implementierung erfolgt in der Lerngruppe arbeitsteilig unter Vorgabe einer Benutzungsoberfläche. Der Vergleich der beiden Algorithmen unter Effizienzaspekten ist Bestandteil des Unterrichts. Beispiel: Versorgungsnetz Die Problemstellung, Verbraucher eines Dorfes möglichst kostengünstig an ein Versorgungsnetz (Kabel, Gas, Telefon) anzuschließen, motiviert die Behandlung des minimalen Spannbaumes eines Graphen. Die Definition eines Baumes und eines Spannbaumes als Spezialfälle von Graphen bereiten die nächste Unterrichtssequenz vor. Materialien: Ergänzungsmaterialien zum Lehrplannavigator Unterrichtsvorhaben LK-Q1.V |
|
|
3. Die Datenstruktur Binärbaum als Spezialfall eines Graphen im Anwendungskontext unter Nutzung der Klasse BinaryTree <ContentType> (a) Definition eines Binärbaums und grundlegende Begriffe (b) Erarbeitung der Klasse BinaryTree <ContentType> und beispielhafte Anwendung der Operationen (c) Implementierung der Traversierung eines Binärbaums im Pre-, In- und Postorderdurchlauf (d) Modellierung und Implementierung einer Anwendung unter Verwendung der Datenstruktur Binärbaum |
Beispiel: MorseBaum Morse hat Buchstaben als Folge von Punkten und Strichen codiert. Diese Codierungen können in einem Binärbaum dargestellt werden, sodass ein Übergang zum linken Teilbaum einem Punkt und ein Übergang zum rechten Teilbaum einem Strich entspricht. Anhand dieses Beispiels werden die Definition eines Binärbaums als Spezialfall eines Graphen und eine rekursive Definition erarbeitet. Die Methoden der generischen Klasse BinaryTree <ContentType> eingeführt und zur Implementation des Morsecodierers und dekodierers genutzt. Wenn man bei der Wurzel startet und durch Übergänge zu linken oder rechten Teilbäumen einen Pfad zum gewünschten Buchstaben sucht, erhält man den Morsecode des Buchstabens. Im Leistungskurs wird auch ein rekursiver Algorithmus zur Dekodierung von Morsezeichen entwickelt. Beispiel: Termbaum Arithmetische Ausdrücke werden in einem Binärbaum dargestellt. Mit den Traversierungsalgorithmen lassen sich die Terme in Pre, Post- und In-Order-Darstellung ausgeben. Gegebenenfalls kann ein Interpreter für einen arithmetischen Term mit den vier Grundrechenarten entwickelt werden. Im Unterrichtsvorhaben (Q2-III) kann das Beispiel unter dem Thema „Parsen eines einfachen Terms und die Erzeugung eines Termbaums“ wieder aufgegriffen werden. Beispiel: Infomatikerbaum als Binärbaum In einem binären Baum werden die Namen und die Geburtsdaten von Informatikern lexikographisch geordnet abgespeichert. Alle Namen, die nach dieser Ordnung vor dem Namen im aktuellen Teilbaum stehen, sind in dessen linkem Teilbaum, alle die nach dem Namen im aktuellen Teilbaum stehen, sind in dessen rechtem Teilbaum. (Dies gilt für alle Teilbäume.) Folgende Funktionalitäten werden benötigt:
Anhand des Beispiels werden die Eigenschaften und die Methoden eines binären Suchbaums entwickelt und implementiert. Materialien: Ergänzungsmaterialien zum Lehrplannavigator Unterrichtsvorhaben LK-Q1.V |
|
|
4. Erarbeitung, Implementierung und Verwendung der Datenstruktur binärer Suchbaum im Anwendungskontext (a) Erarbeitung der Eigenschaften eines binären Suchbaums im Anwendungskontext (b) Erarbeitung der Attribute und Methoden der generischen Klasse BinarySearchTree <ContentType> und des Interfaces ComparableContent (c) Implementierung des Konstruktors und der Methode search der Klasse BinarySearchTree <ContentType> (d) Implementierung eines Anwendungsbeispiels einschließlich der sortierten Ausgabe eines binären Suchbaumes |
Beispiel: Informatikerbaum binärer Suchbaum Das Beispiel wird wieder aufgegriffen und diesmal mit der Klasse BinarySearchTree <ContentType> implementiert. Durch Modifikation der implementierten Methoden des Interfaces ComparableContent wird der Suchbaum nach den Geburtsdaten der Informatiker sortiert. Beispiel: Buchindex Als weiteres Anwendungsbeispiel, das mehrere dynamische Datenstrukturen miteinander verknüpft, soll ein Programm modelliert und implementiert werden, das das Stichwortregister eines Buches verwaltet. Die Wörter werden in einem binären Suchbaum verwaltet, die zugehörigen Seitenzahlen als lineare Listen. Materialien: Ergänzungsmaterialien zum Lehrplannavigator Unterrichtsvorhaben LK-Q1.V |