Informatik am HHG Bottrop

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Konkretisierung Q1-III ======
{{indexmenu_n>23}}
====== Suchen und Sortieren auf linearen Datenstrukturen ======
===== Leitfragen =====
//Wie kann man gespeicherte Informationen günstig (wieder)finden?//

===== Vorhabenbezogene Konkretisierung =====
In einem Anwendungskontext werden zunächst Informationen in einer linearen Liste bzw. einem Feld gesucht. Hierzu werden Verfahren entwickelt und implementiert bzw. analysiert und erläutert, wobei neben einem iterativen auch ein rekursives Verfahren thematisiert wird und mindestens ein Verfahren selbst entwickelt und implementiert wird. Die verschiedenen Verfahren werden hinsichtlich Speicherbedarf und Zahl der Vergleichsoperationen miteinander verglichen.

Anschließend werden Sortierverfahren entwickelt und implementiert (ebenfalls für lineare Listen und Felder). Hierbei soll auch ein rekursives Sortierverfahren entwickelt werden. Die Implementationen von Quicksort sowie dem Sortieren durch Einfügen werden analysiert und erläutert. Falls diese Verfahren vorher schon entdeckt wurden, sollen sie hier wiedererkannt werden. Die rekursive Abarbeitung eines Methodenaufrufs von Quicksort wird grafisch dargestellt.

Abschließend werden verschiedene Sortierverfahren hinsichtlich der Anzahl der benötigten Vergleichsoperationen und des Speicherbedarfs beurteilt.
===== Zeitbedarf =====
16 Stunden

===== Sequenzierung des Unterrichtsvorhabens =====
|< 100% 33% 33%>|
^Unterrichtssequenzen ^zu entwickelnde Kompetenzen ^Beispiele, Medien, Materialien ^
|<WRAP center column 100%>
**1. Suchen von Daten in Listen und Arrays**

(a) Lineare Suche in Listen und in Arrays

(b) Binäre Suche in Arrays als Beispiel für rekursives Problemlösen

%%(c)%% Untersuchung der beiden Suchverfahren hinsichtlich ihrer Effizienz (Laufzeitverhalten, Speicherbedarf)
</WRAP>|<WRAP center column 100%>
Die Schülerinnen und Schüler
  * analysieren und erläutern Algorithmen und Programme (A),
  * beurteilen die syntaktische Korrektheit und die Funktionalität von Programmen (A),
  * beurteilen die Effizienz von Algorithmen unter Berücksichtigung des Speicherbedarfs und der Zahl der Operationen (A),
  * entwickeln iterative und rekursive Algorithmen unter Nutzung der Strategien „Modularisierung“ und „Teilen und Herrschen“ (M),
  * modifizieren Algorithmen und Programme (I),
  * implementieren iterative und rekursive Algorithmen auch unter Verwendung von dynamischen Datenstrukturen (I),
  * implementieren und erläutern iterative und rekursive Such- und Sortierverfahren (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 iterative und rekursive Algorithmen umgangssprachlich und grafisch dar (D).
</WRAP>|<WRAP center column 100%>
//Beispiel//: Karteiverwaltung

Für ein Adressverwaltungsprogramm soll eine Methode zum Suchen einer Adresse geschrieben werden.

oder

//Beispiel//: Bundesjugendspiele

Die Teilnehmer an Bundesjugendspielen nehmen an drei Disziplinen teil und erreichen dort Punktzahlen. Diese werden in einer Wettkampfkarte eingetragen und an das Wettkampfbüro gegeben. Zur Vereinfachung sollte sich das Modell auf die drei Disziplinen „Lauf”, „Sprung“ und „Wurf“ beschränken.

Im Wettkampfbüro wird das Ergebnis erstellt. Das Programm soll dafür zunächst den Besten einer Disziplin heraussuchen können und später das gesamte Ergebnis nach gewissen Kriterien sortieren können.
</WRAP> |
|<WRAP center column 100%>
**2. Sortieren in Listen und Arrays - Entwicklung und Implementierung von iterativen und rekursiven Sortierverfahren**

(a) Entwicklung und Implementierung eines einfachen Sortierverfahrens für eine Liste

(b) Implementierung eines einfachen Sortierverfahrens für ein Feld

%%(c)%% Entwicklung eines rekursiven Sortierverfahren für ein Feld (z.B. Sortieren durch Mischen)
</WRAP>|:::|<WRAP center column 100%>
//Beispiel//: Karteiverwaltung

(s.o.)

oder

//Beispiel//: Bundesjugendspiele

(s.o.)
</WRAP> |
|<WRAP center column 100%>
**3. Untersuchung der Effizienz der Sortierverfahren "Sortieren durch direktes Einfügen" und "Quicksort" auf linearen Listen**

(a) Grafische Veranschaulichung der Sortierverfahren

(b) Untersuchung der Anzahl der Vergleichsoperationen und des Speicherbedarf bei beiden Sortierverfahren

%%(c)%% Beurteilung der Effizienz der beiden Sortierverfahren
</WRAP>|:::|<WRAP center column 100%>
//Beispiel//: Karteiverwaltung

(s.o.)

oder

//Beispiel//: Bundesjugendspiele

(s.o.)
</WRAP> |