\documentclass[reversion,bibBibtex]{schuleub}
\usepackage[utf8]{inputenc}
\usepackage{schulinf}

% Dieses Dokument ist in der Zusammenarbeit von Informatikreferendaren und
% ehemaligen Informatikreferendaren der Studienseminare (heute ZfsL) Arnsberg,
% Hamm und Solingen entstanden.
%
% Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0
% http://creativecommons.org/licenses/by-nc-sa/4.0/deed.de
%
% Nach dieser Lizenz darf das Dokument beliebig kopiert und bearbeitet werden,
% sofern das Folgeprodukt wiederum unter gleichen Lizenzbedingungen vertrieben
% und auf die ursprünglichen Urheber verwiesen wird.
% Eine kommerzielle Nutzung ist ausdrücklich ausgeschlossen.
%
% Die Namensnennung durch einen Verweis und die Lizenzangabe der ursprünglichen
% Urheber auf den Materialien für Schülerinnen und Schüler ist erforderlich.
%
% Die Sammlung der Dokumente steht unter
% http://ddi.uni-wuppertal.de/material/materialsammlung/
% zur Verfügung.
%
% Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht
% unter  http://www.ctan.org/pkg/schule
% zur Verfügung.

\hypersetup{pdfauthor={Referendare der Informatikfachseminare Arnsberg, Hamm und Solingen}}
\includexmp{lizenz}
\cclizenz{byncsaeu}
\footerQRLink{materialsammlung_qr_url.pdf}

\svnid{$Id: ub_01_sortieren.tex 1467 2016-03-25 10:56:54Z pieper $}

\lehrer{-, StR}

\schuladresse{Gymnasium\\
-\\
-}
\ort{-}

\besuchtitel{Unterrichtsbesuch im Fach Informatik}

\lerngruppe{Grundkurs IF Q1}
\datum{-}
\zeit{09:40}{10:25}
\stunde{3}
\raum{Informatikraum}
\schulleiter{-, OStD}

\thema{Entwicklung eines eigenen Algorithmus zur alphabetischen Sortierung einer Namensliste}
 
\weiblich{0}
\maennlich{23}

\begin{document}

\section{Thematischer Zusammenhang}
Das Sortieren ist ein Vorgang, den wir an vielen Stellen auch ohne Computer einsetzen, wie z.\,B. beim Kartenspielen. Dieser uns geläufige Vorgang wird in einem Computeralgorithmus wesentlich komplexer, da es hier eine sehr wichtige Einschränkung gibt: Es können immer maximal zwei Elemente miteinander verglichen werden. Auch zusätzliche Hilfen können nicht angewandt werden, wie die Kenntnis darüber, in welchem Bereich sich hohe oder niedrige Zahlen im bereits sortierten Feld befinden.

Besonders beim Sortieren großer Datenmengen lassen sich schon deutliche Unterschiede bei der benötigten Zeit zwischen schnellen und langsamen Verfahren feststellen. Daher ist es neben dem Vorgehen beim Sortieren auch wichtig, Kenntnisse über die Laufzeit des Algorithmus zu besitzen. 

\subsection{Lehrplanbezug}
Die Behandlung von Sortieralgorithmen ist im Hauscurriculum Informatik in der Qualifikationsphase 1 als Thema vorgeschrieben. Im neuen Kernlehrplan Informatik für die Sekundarstufe II, der mit dem Beginn der Einführungsphase zum 1. August 2014 Gültigkeit erlangt, ist das Sortieren im Inhaltsbereich 2 Algorithmen aufgeführt \cite[S. 22]{KLP_Informatik_S2_NW2013}.

\subsection{Struktur der Unterrichtsreihe}\label{struktur}
Die Stunde ist im Themenbereich Datenstrukturen und Algorithmen angesiedelt. Die derzeitige Unterrichtsreihe beinhaltet das Suchen und Sortieren in und von Daten sowie die Analyse der Laufzeit- und Speicherplatzkomplexität. In den vorherigen Stunden wurde die Suche bei einer sortierten Datenmenge angewandt und analysiert. Speziell wurden dabei die Unterschiede zwischen einem Computer und einem Menschen bei der Suche hervorgehoben und die binäre Suche in einem kleinen Programm implementiert.

In dieser Stunde sollen mit dem Einstieg die Vorteile einer sortierten Menge hervorgehoben werden und darauf aufbauend die dazugehörigen Mittel erarbeitet werden. Dazu sind die \SuS aufgerufen, selbst einen Sortieralgorithmus zu entwickeln, der entsprechend analysiert wird. Sehr wahrscheinlich werden dabei nur Algorithmen mit einer quadratischen Laufzeit entwickelt. Daher wird sich daran die Analyse von schnelleren Sortieralgorithmen anschließen, bis hin zu den Spezialfällen, in denen eine lineare Laufzeit erreicht werden kann. Ähnlich wie beim Suchen steht außerdem auch die Implementierung eines der Sortieralgorithmen an.

\subsection{Thema der Unterrichtsstunde}
\Thema{}.

\subsection{Lernziele der Unterrichtsstunde}
\minisec{Hauptlernziel:} 
\begin{smallitemize}
	\item Die \SuS sollen strukturiert eine Liste von Namen sortieren indem sie jeweils nur zwei Elemente vergleichen und dieses Vorgehen in einen schriftlichen Algorithmus überführen.
\end{smallitemize}

\minisec{Weitere Lernziele und Kompetenzen:}
Die zugrunde liegenden Kompetenzanforderungen des Kernlehrplans \cite[S. 22]{KLP_Informatik_S2_NW2013} sind durch Angabe des Kürzels gekennzeichnet.
\begin{smallitemize}
	\item Die \SuS erweitern ihre Kompetenzen bei der umgangssprachlichen Darstellung eines Algorithmus in Pseudocodeschreibweise [E2/3].

	\item Die \SuS erweitern ihre Kompetenzen bei dem Entwurf eines eigenen Algorithmus zum Sortieren von Namen nach der alphabetischen Reihenfolge [E2/7].

	\item Die \SuS erweitern ihre Kompetenzen bei der Beurteilung eines Algorithmus hinsichtlich des Zeitaufwands durch die Abschätzung der Arbeitsschritte ihres eigenen Algorithmus [E2/8].
\end{smallitemize}

\section{Hausaufgaben zur Stunde}
Die Lernenden haben die Aufgabe bekommen, ihre Implementation der binären Suche abzuschließen, soweit dieses nicht bereits geschehen ist. Die Ergebnisse werden in der Stunde nicht aufgegriffen, da bereits in der vorherigen Stunde Beispiele von einigen \SuSn vorgestellt wurden.

\section{Geplanter Unterrichtsverlauf}

\begin{stundenverlauf}

Einstieg & Eine Gästeliste für die Abendkasse einer Party wird als Folie mit vielen unsortierten Namen aufgelegt. Als Hilfe werden zusätzliche Hinweise zur Gästeliste bereit gehalten. & UG & Folie \\

\hline 

Leitfrage & Wie kann die Gästeliste durch den Computer alphabetisch sortiert werden? & UG & Tafel \\

\hline 

Erarbeitungs\-vorbe\-rei\-tung & Die SuS bekommen den Arbeitsauftrag auf einem AB, sowie eine Erinnerung an die Anforderungen an den Sortieralgorithmus. & LB & AB  \\
 
\hline

Erarbeitung  & Die SuS erarbeiten sich eine eigene Strategie zum Sortieren von Namen. & EA & AB \\

 & In einem zweiten Schritt präsentieren sich zwei Partner gegenseitig ihre Strategie. Sie entscheiden sich für eine und schreiben diese in Pseudocodeschreibweise für eine Präsentation auf Folie. & PA & AB, Folie \\

 & Als Zusatzaufgabe machen Sie sich Gedanken über die Laufzeitkomplexität ihres Sortieralgorithmus. & PA & AB \\

\hline

Zusammentragen & Einzelne Paare stellen ihren Algorithmus vor und wenden ihn auf eine Beispielmenge an. & SB & Folie \\

\hline

Sicherung & Die vorgetragenen Algorithmen werden verglichen und mit einer Kurzzusammenfassung sowie dem Originalnamen aufgeschrieben. & UG & Tafel \\

\hline

\end{stundenverlauf}

\section{Geplante Hausaufgaben}
Da es sich bei dieser Stunde um den ersten Teil einer Doppelstunde handelt, werden keine Hausaufgaben gestellt. Im Falle einer Einzelstunde würde es sich anbieten, die Laufzeitanalyse in die Form der in der Informatik gebräuchlichen O-Notation zu überführen.

\section{Lehrsituation und didaktisch-methodische Begründungen}

\subsection{Lehrsituation}
Der Grundkurs Informatik besteht etwa zur Hälfte aus Lernenden, die in der Jahrgangsstufe 8 und 9 am Mathematik/Informatik-Unterricht (MIf) teilgenommen haben. Die Anderen sind erst mit Beginn der Oberstufe in die Informatik eingestiegen. Bei diesen hat etwa die Hälfte auch beim Programmieren mit den ehemaligen MIf-Schülerinnen und Schülern gleichgezogen. Die Anderen weisen gerade in diesem Bereich Defizite auf, die mit dem Formalismus rund um das Programmieren zu tun haben. Für diese stehen deshalb zur Erinnerung Schablonen auf Hilfekarten bereit, die bei der Erstellung von Pseudocode helfen können.

\subsection{Zu Themenwahl und themenbezogener Zielsetzung}\label{themenwahl}
Welche Datenmengen zu sortieren sind, ist für die Grundstruktur eines Algorithmus beliebig. Die Wahl fiel daher auf Namen, die unsortiert auf einer Gästeliste stehen, damit eine Situation geschaffen wird, in der sich einige \SuS bereits befunden haben oder in Zukunft befinden können. Die Umsetzung durch die \SuS erfolgt auf der Grundlage von Vorgehensweisen, die sie z.\,B. vom Kartenspielen her kennen. Dabei ist es aber wichtig zu beachten, dass es bei der Umsetzung Einschränkungen gibt, weil das Ziel ein implementierbarer Algorithmus ist. 

\subsection{Zum Aufbau der Unterrichtsstunde}
Die Stunde beginnt mit dem Auflegen der Folie, auf der eine fiktive Gästeliste zu sehen ist, bei der alle Namen unsortiert sind. Für den Fall, dass den Lernenden eine solche Gästeliste unbekannt ist und keiner ihre Bedeutung erklären kann, gibt es weitere Hinweisfolien. Diese können auch dazu genutzt werden, um den Fokus auf das Problem der Stunde zu lenken.

Für die Umsetzung der Lösung zur Problemfrage gibt es das Arbeitsblatt, auf dem die nötigen Schritte aufgeführt sind. Dabei sollen sich die \SuS zuerst allein Gedanken über ihr Vorgehen machen, bevor sie mit einem Partner zusammen arbeiten. Dadurch soll es ermöglicht werden, dass auch schwächere Lernende eine eigene Lösung finden und die damit vorhandenen Gedankengänge in die spätere Partnerarbeit einbringen können. Aus diesem Grunde wird auch auf die Hypothesenbildung im Plenum verzichtet. Da beide Partner auch unterschiedliche Lösungsansätze gefunden haben können, sollen sie sich diese gegenseitig vorstellen und ggf. auf einen der beiden Ansätze einigen, bevor sie diesen gemeinsam in Pseudocode niederschreiben. Für diese Arbeit stehen den \SuSn die ersten sechs Namen aus der Gästeliste zum direkten Ausprobieren auf Kärtchen zur Verfügung. Es wurden nur die ersten sechs gewählt, damit die \SuS die Anzahl auch von Hand sortieren und sich auf das Verfahren konzentrieren können. Nach dem Austeilen der Arbeitsblätter wird noch einmal auf die Besonderheit hingewiesen, dass durch die Architektur von Computern maximal zwei Namen direkt verglichen werden können und deshalb die Namenskarten umzudrehen sind. 

Bei den Lösungen wird davon ausgegangen, dass entweder das Insertionsort- oder das Selectionsort-Verfahren gewählt wird. Die gewünschte Aussage zur Laufzeit werden langsamere Paare wahrscheinlich nicht mehr tätigen können. Durch die geringe Zahl von wahrscheinlichen Varianten kann bei der Präsentation die Angabe zur Laufzeit in einem solchen Fall auch durch ein anderes Paar erfolgen. Bei dieser Präsentation soll neben der erarbeiteten Folie auch der Algorithmus an einem kleinen Beispiel an der Tafel vorgeführt werden. Zur Sicherung wird das Wesen der aufgezeigten Algorithmen zusammengefasst und sie mit ihrem in der Informatik geläufigen Namen benannt. 

Sollte es zu Zeitproblem kommen, so wird auf die fertigen Folien zur Präsentation des Pseudocodes verzichtet und stattdessen die Funktionsweise alleine am Beispiel gezeigt. Die mögliche Hausaufgabe wäre dann, den Algorithmus zu verschriftlichen. Es ist davon auszugehen, dass durch die erneute Präsentation die Vorgehensweise so präsent wird, dass die \SuS in der Folgestunde ihr Verfahren noch präsent haben.

\section{Geplantes Tafelbild, Arbeitsblatt und Folie}

\subsection{Folie, Arbeitsblatt, Hilfekarten}
Die Folien, das Arbeitsblatt und die Hilfekarten befinden sich im Anhang. Die Namensliste wurde mit Hilfe eines entsprechenden Generators \cite[]{Fakename2013} erstellt.

\subsection{Tafel} \label{Tafel}

Möglicher Text auf der Tafel:\\
\begin{tikzpicture}
\node at (0,0) [text width=16cm, text depth=5cm, draw] {
	\underline{Sortieren einer Gästeliste}\\
	Wie kann die Gästeliste durch den Computer alphabetisch sortiert werden?

	\vspace{0.4cm}

	Selectionsort -- Das kleinste verbliebene Element wird ausgewählt und an die bereits sortierte Liste gehangen.

	Insertionsort -- Ein Element wird genommen und an passender Stelle in der bereits sortierten Liste eingefügt.
};

\end{tikzpicture}

\bibliography{../../../zusatz/projekt}

\clearpage

\section{Reflexion}
\begin{smallenumerate}
	\item Das Lernziel der Stunde wurde erreicht
	\begin{smallitemize}
		\item Alle \SuS haben einen eigenen Algorithmus entwickelt und diesen, zumindest in ihren Unterlagen verbalisiert.
		\item In der Präsentationsphase ließ sich deutlich erkennen, dass sich unterschiedliche Paare auch Gedanken zum Laufzeitverhalten gemacht haben.
	\end{smallitemize}
	\item Die Hilfsmittel der Stunde waren angemessen
	\begin{smallitemize}
		\item Die Einstiegsfolie war zielführend und die angedachten Hilfen waren nicht nötig. Dabei hilfreich war, dass die \SuS die unsortierte Liste ein Problem für das Suchen war. Der Bezug zur Lebenswelt, in Form der längeren Wartezeit, wurde aber nicht mehr deutlich hervorgehoben.
		\item Die Hilfekarten haben sich als sehr nützlich erweisen, da sich auf diese Weise viel \SuS an die bereits gelernte Arbeitsweise erinnert haben, auch wenn ihnen der Namen nicht mehr präsent war.
	\end{smallitemize}
	\item Zur Gestaltung der Präsentationsphase
	\begin{smallitemize}
		\item Die Präsentationsphase hätte etwas länger sein können, um den zweiten von den \SuS gefundenen Algorithmus (Bubble-Sort) zu präsentieren. Dieser war aber auf der Folie gesichert und konnte in der nächsten Stunde nach ähnlichem Verfahren präsentiert werden.
		\item Das Insertionsort wurde ausführlich von zwei Unterschiedlichen Gruppen mit verschiedenen Ansätzen präsentiert und dabei die zur Verfügung stehenden Mittel genutzt.
		\item Mit der Zusammenfassung des Wesens der beiden Algorithmen ist dieser Algorithmus auch komplett abgeschlossen worden. Dieses wurde der halbfertigen Vorstellung von zwei unterschiedlichen Algorithmen vorgezogen.
	\end{smallitemize}
	\item Allgemeine Verhaltensweise des Lehrers
	\begin{smallitemize}
		\item Es wurde in der Präsentationsphase viel Verantwortung an die \SuS abgegeben.
		\item Auch Fragen und Impulse wurden mit der nötigen Zeit zum Nachdenken versehen und nicht direkt nach einer richtigen Antwort weiter gemacht.
	\end{smallitemize}
\end{smallenumerate}


\end{document}
