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 EF-III ======
{{indexmenu_n>13}}
====== Such- und Sortieralgorithmen anhand kontextbezogener Beispiele ======
===== Leitfragen =====
//Wie können Objekte bzw. Daten effizient sortiert werden, so dass eine schnelle Suche möglich wird?//
===== Vorhabenbezogene Konkretisierung =====
Dieses Unterrichtsvorhaben beschäftigt sich mit der Erarbeitung von Such- und Sortieralgorithmen. Der Schwerpunkt des Vorhabens liegt dabei auf den Algorithmen selbst und nicht auf deren Implementierung in einer Programmiersprache, auf die in diesem Vorhaben vollständig verzichtet werden soll.

Zunächst erarbeiten die Schülerinnen und Schüler mögliche Einsatzszenarien für Such- und Sortieralgorithmen, um sich der Bedeutung einer effizienten Lösung dieser Probleme bewusst zu werden. Anschließend werden Strategien zur Sortierung mit Hilfe eines explorativen Spiels von den Schülerinnen und Schülern selbst erarbeitet und hinsichtlich der Anzahl notwendiger Vergleiche auf ihre Effizienz untersucht.

Daran anschließend werden die erarbeiteten Strategien systematisiert und im Pseudocode notiert oder als Programmablaufplan (PAP) visualisiert. Die Schülerinnen und Schüler sollen auf diese Weise das //Sortieren durch Vertauschen//, das //Sortieren durch Auswählen// und mindestens einen weiteren Sortieralgorithmus kennen lernen.

Des Weiteren soll das Prinzip der //binären Suche// behandelt und nach Effizienzgesichtspunkten untersucht werden.
===== Zeitbedarf =====
9 Stunden

===== Sequenzierung des Unterrichtsvorhabens =====
|< 100% 33% 33%>|
^Unterrichtssequenzen ^zu entwickelnde Kompetenzen ^Beispiele, Medien, Materialien ^
|<WRAP center column 100%>
**1. Explorative Erarbeitung eines Sortierverfahrens**

(a) Sortierprobleme im Kontext informatischer Systeme und im Alltag (z.B. Dateisortierung, Tabellenkalkulation, Telefonbuch, Bundesligatabelle, usw.)

(b) Vergleich zweier Elemente als Grundlage eines Sortieralgorithmus

%%(c)%% Erarbeitung eines Sortieralgorithmus durch die Schülerinnen und Schüler
</WRAP>|<WRAP center column 100%>
Die Schülerinnen und Schüler
  * beurteilen die Effizienz von Algorithmen am Beispiel von Sortierverfahren hinsichtlich Zeit und Speicherplatzbedarf (A),
  * entwerfen einen weiteren Algorithmus zum Sortieren (M),
  * analysieren Such- und Sortieralgorithmen und wenden sie auf Beispiele an (D).
</WRAP>|<WRAP center column 100%>
//Beispiel//: Sortieren mit Waage

Die Schülerinnen und Schüler bekommen die Aufgabe, kleine, optisch identische Kunststoffbehälter aufsteigend nach ihrem Gewicht zu sortieren. Dazu steht ihnen eine Balkenwaage zur Verfügung, mit deren Hilfe sie das Gewicht zweier Behälter vergleichen können.

//Materialien//:

Computer science unplugged – Sorting Algorithms, URL:
[[http://www.csunplugged.org/sorting-algorithms|www.csunplugged.org/searching-algorithms]] (abgerufen: 30.03.2014)
</WRAP> |
|<WRAP center column 100%>
**2. Systematisierung von Algorithmen und Effizienzbetrachtungen**

(a) Formulierung (falls selbst gefunden) oder Erläuterung von mehreren Algorithmen im Pseudocode (auf jeden Fall: Sortieren durch Vertauschen, Sortieren durch Auswählen)

(b) Anwendung von Sortieralgorithmen auf verschiedene Beispiele

%%(c)%% Bewertung von Algorithmen anhand der Anzahl der nötigen Vergleiche

(d) Variante des Sortierens durch Auswählen (Nutzung eines einzigen oder zweier Felder bzw. lediglich eines einzigen zusätzlichen Ablageplatzes oder mehrerer neuer Ablageplätze)

(e) Effizienzbetrachtungen an einem konkreten Beispiel bezüglich der Rechenzeit und des Speicherplatzbedarfs

(f) Analyse des weiteren Sortieralgorithmus (sofern nicht in Sequenz 1 und 2 bereits geschehen)
</WRAP>|:::|<WRAP center column 100%>
//Beispiele//: Sortieren durch Auswählen,

Sortieren durch Vertauschen, Quicksort

Quicksort ist als Beispiel für einen Algorithmus nach dem Prinzip //Teile und Herrsche// gut zu behandeln. Kenntnisse in rekursiver Programmierung sind nicht erforderlich, da eine Implementierung nicht angestrebt wird.

//Materialien//:

Computer science unplugged – Sorting Algorithms, URL:
[[http://www.csunplugged.org/sorting-algorithms|www.csunplugged.org/searching-algorithms]] (abgerufen: 30.03.2014)
</WRAP> |
|<WRAP center column 100%>
**3. Binäre Suche auf sortierten Daten**

(a) Suchaufgaben im Alltag und im Kontext informatischer Systeme

(b) Evtl. Simulationsspiel zum effizienten Suchen mit binärer Suche

%%(c)%% Effizienzbetrachtungen zur binären Suche
</WRAP>|:::|<WRAP center column 100%>
//Beispiel//: Simulationsspiel zur binären Suche nach Tischtennisbällen

Mehrere Tischtennisbälle sind nummeriert, sortiert und unter Bechern verdeckt. Mit Hilfe der binären Suche kann sehr schnell ein bestimmter Tischtennisball gefunden werden.

//Materialien//:

Computer science unplugged – Searching Algorithms, URL:
[[http://www.csunplugged.org/searching-algorithms|www.csunplugged.org/searching-algorithms]] (abgerufen: 30.03.2014)
</WRAP> |