Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- curricula:oberstufe:uv_q2-i [2014/08/08 13:47] – [Leitfragen] Sven Biermann
+++ curricula:oberstufe:uv_q2-i [2014/09/04 07:46] (aktuell) – [Konkretisierung Q2-I] Sven Biermann
@@ Zeile 1: / Zeile 1: @@
 ====== Konkretisierung Q2-I ======
+{{indexmenu_n>31}}
 ====== Modellierung und Implementierung von Anwendungen mit dynamischen, nichtlinearen Datenstrukturen ======
 ===== Leitfragen =====
 //Wie können Daten im Anwendungskontext mit Hilfe binärer Baumstrukturen verwaltet werden? Wie kann dabei der rekursive Aufbau der Baumstruktur genutzt werden? Welche Vor- und Nachteile haben Suchbäume für die geordnete Verwaltung von Daten?//
 ===== Vorhabenbezogene Konkretisierung =====
-Das erste Unterrichtsvorhaben stellt eine allgemeine Einführung in das Fach Informatik dar. Dabei ist zu berücksichtigen, dass für manche Schülerinnen und Schüler in der Einführungsphase der erste Kontakt mit dem Unterrichtsfach Informatik stattfindet, so dass zu Beginn Grundlagen des Fachs behandelt werden müssen.
+Anhand von Beispielen für Baumstrukturen werden grundlegende Begriffe eingeführt und der rekursive Aufbau binärer Bäume dargestellt.
-Zunächst wird auf den Begriff der Information eingegangen und die Möglichkeit der Kodierung in Form von Daten thematisiert. Anschließend wird auf die Übertragung von Daten im Sinne des Sender-Empfänger-Modells eingegangen. Dabei wird eine überblickartige Vorstellung der Kommunikation von Rechnern in Netzwerken erarbeitet.
+Anschließend werden für eine Problemstellung in einem der Anwendungskontexte Klassen modelliert und implementiert. Dabei werden die Operationen der Datenstruktur Binärbaum thematisiert und die entsprechende Klasse BinaryTree (der Materialien für das Zentralabitur in NRW) der Vorgaben für das Zentralabitur NRW verwendet. Klassen und ihre Beziehungen werden in Entwurfs- und Implementationsdiagrammen dargestellt. Die Funktionsweise von Methoden wird anhand grafischer Darstellungen von Binärbäumen erläutert.
-Des Weiteren soll der grundlegende Aufbau eines Rechnersystems im Sinne der Von-Neumann-Architektur erarbeitet werden und mit dem grundlegenden Prinzip der Datenverarbeitung (Eingabe-Verarbeitung-Ausgabe) in Beziehung gesetzt werden.
+Unter anderem sollen die verschiedenen Baumtraversierungen (Pre-, Post- und Inorder) implementiert werden. Unterschiede bezüglich der Möglichkeit, den Baum anhand der Ausgabe der Bauminhalte via Pre-, In- oder Postorder-Traversierung zu rekonstruieren, werden dabei ebenfalls angesprochen, indem die fehlende Umkehrbarbeit der Zuordnung Binärbaum à Inorder-Ausgabe an einem Beispiel verdeutlicht wird.
-Bei der Beschäftigung mit Datenkodierung, Datenübermittlung und Datenverarbeitung ist jeweils ein Bezug zur konkreten Nutzung der informatischen Ausstattung der Schule herzustellen. So wird in die verantwortungsvolle Nutzung dieser Systeme eingeführt.
+Eine Tiefensuche wird verwendet, um einen in der Baumstruktur gespeicherten Inhalt zu suchen.
+Zu einer Problemstellung in einem entsprechenden Anwendungskontext werden die Operationen der Datenstruktur Suchbaum thematisiert und unter der Verwendung der Klasse BinarySearchTree (der Materialien für das Zentralabitur in NRW) weitere Klassen oder Methoden in diesem Anwendungskontext modelliert und implementiert. Auch in diesem Kontext werden grafische Darstellungen der Bäume verwendet.
+Die Verwendung von binären Bäumen und Suchbäumen wird anhand weiterer Problemstellungen oder anderen Kontexten weiter geübt.
 ===== Zeitbedarf =====
  Stunden
 ===== Sequenzierung des Unterrichtsvorhabens =====
@@ Zeile 19: / Zeile 23: @@
 ^Unterrichtssequenzen ^zu entwickelnde Kompetenzen ^Beispiele, Medien, Materialien ^
 |<WRAP center column 100%>
-**1. Information, deren Kodierung und Speicherung**
+**1. Analyse von Baumstrukturen in verschiedenen Kontexten**
-(a) Informatik als Wissenschaft der Verarbeitung von Informationen
+(a) Grundlegende Begriffe (Grad, Tiefe, Höhe, Blatt, Inhalt, Teilbaum, Ebene, Vollständigkeit)
-(b) Darstellung von Informationen
+(b) Aufbau und Darstellung von binären Bäumen anhand von Baumstrukturen in verschiedenen Kontexten
 </WRAP>|<WRAP center column 100%>
 Die Schülerinnen und Schüler
-  * beschreiben und erläutern
+  * erläutern Operationen dynamischer (linearer oder nicht-linearer) Datenstrukturen (A),
-  * nutzen
+  * analysieren und erläutern Algorithmen und Programme (A),
+  * beurteilen die syntaktische Korrektheit und die Funktionalität von Programmen (A),
+  * ermitteln bei der Analyse von Problemstellungen Objekte, ihre Eigenschaften, ihre Operationen und ihre Beziehungen (M),
+  * ordnen Attributen, Parametern und Rückgaben von Methoden einfache Datentypen, Objekttypen sowie lineare und nichtlineare Datensammlungen zu (M),
+  * modellieren abstrakte und nicht abstrakte Klassen unter Verwendung von Vererbung durch Spezialisieren und Generalisieren (M),
+  * verwenden bei der Modellierung geeigneter Problemstellungen die Möglichkeiten der Polymorphie (M),
+  * entwickeln iterative und rekursive Algorithmen unter Nutzung der Konstruktionsstrategien "Modularisierung" und "Teilen und Herrschen" (M),
+  * implementieren iterative und rekursive Algorithmen auch unter Verwendung von dynamischen Datenstrukturen (I),
+  * modifizieren Algorithmen und Programme (I),
+  * nutzen die Syntax und Semantik einer Programmiersprache bei der Implementierung und zur Analyse von Programmen (I),
+  * interpretieren Fehlermeldungen und korrigieren den Quellcode (I),
+  * testen Programme systematisch anhand von Beispielen (I),
+  * stellen lineare und nichtlineare Strukturen grafisch dar und erläutern ihren Aufbau (D),
+  * stellen iterative und rekursive Algorithmen umgangssprachlich und grafisch dar (D).
 </WRAP>|<WRAP center column 100%>
-//Beispiel//: Textcodierung
+//Beispiel//: Termbaum
-Kodierung und Dekodierung
+Der Aufbau von Termen wird mit Hilfe von binären Baumstrukturen verdeutlicht.
+oder
+//Beispiel//: Ahnenbaum
+Die binäre Baumstruktur ergibt sich daraus, dass jede Person genau einen Vater und eine Mutter hat.
+Weitere Beispiele für Anwendungskontexte für binäre Bäume:
+//Beispiel//: Suchbäume (zur sortierten Speicherung von Daten)
+Alle Inhalte, die nach einer Ordnung vor dem Inhalt im aktuellen Teilbaum stehen, sind in dessen linkem Teilbaum, alle die nach dem Inhalt im aktuellen Teilbaum stehen, sind in dessen rechtem Teilbaum. (Dies gilt für alle Teilbäume.)
+oder
+//Beispiel//: Entscheidungsbäume
+Um eine Entscheidung zu treffen, werden mehrere Fragen mit ja oder nein beantwortet. Die Fragen, die möglich sind, wenn die Antwort auf eine Frage mit „ja“ beantwortet wird, befinden sich im linken Teilbaum, die Fragen, die möglich sind, wenn die Antwort „nein“ lautet, stehen im rechten Teilbaum.
+oder
+//Beispiel//: Codierungsbäume für Codierungen, deren Alphabet aus genau zwei Zeichen besteht
+Morse hat Buchstaben als Folge von Punkten und Strichen codiert. Diese Codierungen können in einem Binärbaum dargestellt werden, so dass ein Übergang zum linken Teilbaum einem Punkt und ein Übergang zum rechten Teilbaum einem Strich entspricht. Wenn man im Gesamtbaum startet und durch Übergänge zu linken oder rechten Teilbäumen einen Pfad zum gewünschten Buchstaben sucht, erhält man die Morsecodierung des Buchstabens.
 </WRAP> |
 |<WRAP center column 100%>
-**1. Information, deren Kodierung und Speicherung**
+**2. Die Datenstruktur Binärbaum im Anwendungskontext unter Nutzung der Klasse BinaryTree**
-(a) Informatik als Wissenschaft der Verarbeitung von Informationen
+(a) Analyse der Problemstellung, Ermittlung von Objekten, ihren Eigenschaften und Operationen im Anwendungskontext
-(b) Darstellung von Informationen
+(b) Modellierung eines Entwurfsdiagramms und Entwicklung eines Implementationsdiagramms
+%%(c)%% Erarbeitung der Klasse BinaryTree und beispielhafte Anwendung der Operationen
+(d) Implementierung der Anwendung oder von Teilen der Anwendung
+(e) Traversierung eines Binärbaums im Pre-, In- und Postorderdurchlauf
 </WRAP>|:::|<WRAP center column 100%>
-//Beispiel//: Textcodierung
+//Beispiel//: Informatikerbaum als binärer Baum
-Kodierung und Dekodierung
+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:
+  * Einfügen der Informatiker-Daten in den Baum
+  * Suchen nach einem Informatiker über den Schlüssel Name
+  * Ausgabe des kompletten Datenbestands in nach Namen sortierter Reihenfolge
 </WRAP> |
+|<WRAP center column 100%>
+**3. Die Datenstruktur binärer Suchbaum im Anwendungskontext unter Verwendung der Klasse BinarySearchTree**
+(a) Analyse der Problemstellung, Ermittlung von Objekten, ihren Eigenschaften und Operationen
+(b) Modellierung eines Entwurfsdiagramms und Entwicklung eines Implementationsdiagramm,
+grafische Darstellung eines binären Suchbaums und Erarbeitung der Struktureigenschaften
+%%(c)%% Erarbeitung der Klasse BinarySearchTree und Einführung des Interface Item zur Realisierung einer geeigneten Ordnungsrelation
+(d) Implementierung der Anwendung oder von Teilen der Anwendung inklusive einer sortierten Ausgabe des Baums
+</WRAP>|:::|<WRAP center column 100%>
+//Beispiel//: Informatikerbaum als Suchbaum
+In einem binären Suchbaum 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:
+  * Einfügen der Informatiker-Daten in den Baum
+  * Suchen nach einem Informatiker über den Schlüssel Name
+  * Ausgabe des kompletten Datenbestands in nach Namen sortierter Reihenfolge
+</WRAP> |
+|<WRAP center column 100%>
+**4. Übung und Vertiefungen der Verwendung von Binärbäumen oder binären Suchbäumen anhand weiterer Problemstellungen**
+</WRAP>|:::|<WRAP center column 100%>
+//Beispiel//: Codierungsbäume (s.o.) oder Huffman-Codierung
+oder
+//Beispiel//: Buchindex
+Es soll eine Anwendung entwickelt werden, die anhand von Stichworten und zugehörigen Seitenzahlen ein Stichwortregister erstellt.
+Da die Stichwörter bei der Analyse des Buches häufig gesucht werden müssen, werden sie in der Klasse Buchindex als Suchbaum (Objekt der Klasse BinarySearchTree) verwaltet.
+Alle Inhalte, die nach einer Ordnung vor dem Inhalt im aktuellen Teilbaum stehen, sind in dessen linkem Teilbaum, alle die nach dem Inhalt im aktuellen Teilbaum stehen, sind in dessen rechtem Teilbaum. (Dies gilt für alle Teilbäume.)
+oder
+//Beispiel//: Entscheidungsbäume (s.o.)
+oder
+//Beispiel//: Termbaum (s.o.)
+oder
+//Beispiel//: Ahnenbaum (s.o.)
+</WRAP> |