Kontakt
Themen
Modellierung, Implementierung, Analyse und Beurteilung von Such- und Sortierverfahren unterschiedlicher Komplexitätsklassen in kontextbezogenen Problemstellungen
Leitfrage: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: 20 Stunden
Sequenzierung des Unterrichtsvorhabens:
|
Unterrichtssequenzen |
Zu entwickelnde Kompetenzen |
Beispiele, Medien, Materialien |
|
1. Suchen von Daten in Listen und Arrays (d) Lineare Suche in Listen und in Arrays (e) Binäre Suche in Arrays als Beispiel für rekursives Problemlösen (f) Untersuchung der beiden Suchverfahren hinsichtlich ihrer Effizienz (Speicherbedarf, Anzahl der Vergleiche) |
Die Schülerinnen und Schüler
|
Beispiel: Benutzerverwaltung für einen Fotokopierer Benutzerinnen und Benutzer des Kopierers geben eine vierstellige Ziffernkombination an, um sich zu legitimieren. Über diesen PIN-Code soll auch die Benutzerinnen und Benutzer des Kopierers identifizierbar sein, um auf sein Konto den Kopierverbrauch zu buchen. Die Benutzungsdaten werden in linearen Strukturen verwaltet, die nach den PIN-Nummern sortiert vorliegen. Materialien: Ergänzungsmaterialien zum Lehrplannavigator Unterrichtsvorhaben Q1.III - Suchen und Sortieren |
|
2. Sortieren in Listen und Arrays - Entwicklung und Implementierung von iterativen und rekursiven Sortierverfahren (d) Entwicklung und Implementierung eines einfachen Sortierverfahrens für eine Liste (e) Implementierung eines einfachen Sortierverfahrens für ein Feld (f) Entwicklung eines rekursiven Sortierverfahren für ein Feld (z.B. Sortieren durch Mischen) |
Beispiel: Benutzerverwaltung für einen Fotokopierer (s.o.) Die Benutzungsdaten sollen nach den Kriterien Kopierverbrauch, Namen und PIN-Nummern geordnet ausgegeben werden können. Material: Ergänzungsmaterialien zum Lehrplannavigator Unterrichtsvorhaben Q1.III - Suchen und Sortieren |
|
|
3. Untersuchung der Effizienz der Sortierverfahren „Sortieren durch direktes Einfügen“ und „Quicksort“ auf linearen Listen (d) Grafische Veranschaulichung der Sortierverfahren (e) Untersuchung der Anzahl der Vergleichsoperationen bei beiden Sortierverfahren (f) Beurteilung der Effizienz der beiden Sortierverfahren, untere Schranke für die Laufzeit von Sortieralgorithmen |
Beispiel:Test- und Analyseumgebung für Sortieralgorithmen Listen mit unterschiedlich vielen Listenelementen und unterschiedlicher Vorsortierung werden bezüglich der Anzahl der Vergleiche von Listenelementen analysiert. Die untere Schranke für die Laufzeit wird bestimmt. Materialien: Ergänzungsmaterialien zum Lehrplannavigator Unterrichtsvorhaben Q1.III - Suchen und Sortieren |