path: root/LP3/LP3.tex

\documentclass[ngerman]{scrartcl}

\usepackage{standalone}
\usepackage{subcaption}
\usepackage{rotating}
\usepackage{todonotes}
\usepackage[backend=biber]{biblatex}
\addbibresource{../literatur.bib}
\usepackage{hyperref}
\usepackage{pdfpages}
\usepackage{pdflscape}
\usepackage{afterpage}
\usepackage{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsthm,amsmath}
\usepackage{gensymb}
\usepackage{mathtools}
\usepackage{ifthen}
\usepackage{graphicx}
\usepackage[most]{tcolorbox}
\usepackage{lmodern}
\usepackage[ngerman]{babel}
\usepackage{csquotes}
\MakeOuterQuote{"}

\usepackage{cleveref}
\usepackage{setspace}
\usepackage{array}
\usepackage{booktabs}
\usepackage{float}
\usepackage{wrapfig}
\usepackage{caption}
\usepackage[parfill]{parskip}
\usepackage{tikz}
\usetikzlibrary{arrows.meta, babel, graphs, calc, positioning, quotes}
\usepackage{siunitx}
\usepackage[shortlabels]{enumitem}
\usepackage[table]{xcolor}

\usetikzlibrary{decorations.pathmorphing}
\newtcolorbox{pseudocode}{
  coltitle=white,
  colbacktitle=gray!30!black,
  colframe=gray!30!black,
  enhanced,
  title=\bfseries {\large P}SEUDOCODE,
  attach boxed title to top right={yshift=-0.28cm, xshift=-5mm},
  frame code={
    \draw[
      decorate,
      decoration={random steps, segment length=5mm, amplitude=0.6pt},
      draw=gray!30!black
    ] (frame.north east) rectangle (frame.south west);
  },
}
\newcommand\textvtt[1]{{\normalfont\fontfamily{cmvtt}\selectfont #1}}
\newcommand\revealtexton[3]{#1}
\usepackage{changepage}

\newcommand\boldred[1]{\textcolor{red}{\textbf{#1}}}

\usepackage{ragged2e}
\DeclareCaptionFormat{myformat}{#1#2#3}
\captionsetup[wrapfigure]{justification=RaggedRight, format=myformat}

\author{StRef Florian Fischer}
\title{3. Prüfungslehrprobe\\
\date{21. Oktober 2024}
\Large Dijkstra Algorithmus}

\usepackage[acronym, automake, nomain]{glossaries}
\makeglossaries

\newacronym{SoS}{SoS}{Schüler oder Schülerinnen}
\newacronym{SuS}{SuS}{Schüler und Schülerinnen}
\newacronym{DC}{DC}{Dokumentenkamera}
\newacronym{BE}{BE}{Beamer}
\newacronym{AB}{AB}{Arbeitsblatt}
\newacronym{UG}{UG}{Unterrichtsgespräch}
\newacronym{IDW}{IDW}{Ich Du Wir}
\newacronym{PA}{PA}{Partnerarbeit}
\newacronym{EA}{EA}{Einzelarbeit}
\newacronym{LV}{LV}{Lehrervortrag}

\begin{document}
\maketitle

{
\renewcommand*{\arraystretch}{1.5}
\noindent\begin{tabular}{p{5cm} l}
Fach:   & Informatik \\
Klasse: & 11C \\
Datum:  & 21. Oktober 2024 \\
Zeit:   & 11:30 Uhr bis 12:15 Uhr (5. Unterrichtsstunde) \\
Ort:    & Hans-Sachs-Gymnasium Nürnberg, Raum rU07\_PC \\
\end{tabular}
\vspace{2cm}

\noindent\begin{tabular}{p{5cm} l}
\textbf{Prüfungskommission} & \\
Vorsitzender:   & StD W. Schweiger \\
Seminarlehrer Informatik: & StD M. Donat \\
Seminarlehrerin Mathematik: & StRin K. Kreß \\
Betreuungslehrer: & StR F. Berger
\end{tabular}
}

\newpage

\tableofcontents
\newpage

\section{Rahmenbedingungen}

Seit Beginn des Schuljahres unterrichte ich die Klasse 11C im Fach Informatik mit zwei Unterrichtsstunden die Woche.

Die wöchentliche Doppelstunde findet am Montag in der fünften  und sechsten Stunde statt.

In der Klasse 11C befinden sich regulär 27 \gls{SuS}, davon sind 7 weiblich und 20 männlich.
Aktuell befindet sich Daniela Delins Austauschpartnerin mit im Computerraum.
Sie nimmt jedoch meist eher passiv am Unterricht teil.
Ein Faktor dafür ist, dass sie keinen eigenen Computerzugang hat.
Da in diesem Schuljahr oft Rechner durch zu oft vergebliche Passworteingabe gesperrt sind, gibt es nicht immer genug PC-Arbeitsplätze für alle \gls{SuS}.

In der Klasse herrscht meist eine produktive Lernatmosphäre und -bereitschaft.
Nur dem Thema Programmierung in Java steht die Klasse fast geschlossen negativ und mit Angst gegenüber.
Bei einer Umfrage zu Schuljahresbeginn, was die \gls{SuS} sich vom Informatikunterricht wünschen, wurden unabhängig und mehrfach Antworten in Richtung "mehr Geduld", "kein Programmieren", und "keine Angst haben zu müssen" gegeben.

Als Wiederholung der Vorstunden und zur Aktivierung des nötigen Vorwissens starten wir gewöhnlich den Unterricht mit einer Phase, in der die SuS mit unterschiedlichen fachlichen Aussagen konfrontiert sind, über die sie sich zu zweit austauschen sollen und anschließend Stellung beziehen.

In der Klasse sind einige sehr starke \gls{SuS}, die das Unterrichtsgespräch mit guten Beiträgen und ihrer aufmerksamen Mitarbeit bereichern.
Vor allem stechen die Schüler, Mehemmed, Carlo, und Gagik aus der rechten vorderen Ecke (aus Sicht der Prüfungskommission) durch ihre aufmerksame und durchdachte Teilnahme am Unterricht heraus.
Ebenfalls bereichern Malte und Jakob den Unterricht vorallem durch ihre Programmierkenntnisse. 
Die meisten Schülerinnen der Klasse sind eher verhalten und werden nur aktiv, wenn sie sich sicher fühlen.
Lediglich Hannah und Vicky beteiligen sich bereitwillig am Unterrichtsgespräch.

Ungefähr die Hälfte der \gls{SuS} arbeiten ausschließlich analog auf Papier.
In der Lehrprobe sind alle \gls{SuS} angehalten auf dem Arbeitsblatt mitzuarbeiten, damit durch die Aufteilung in Vorder- und Rückseite, die Lösung zu einer späteren Aufgabe nicht direkt bekannt ist.

Die im Unterricht verwendeten Folien werden den \gls{SuS} zur potentiellen Nachbereitung zur Verfügung gestellt.

Nachdem noch zu keiner Stunde die Klasse vollständig war und die Verfügbarkeit der PCs variiert, existiert kein eindeutiger Sitzplan der Klasse.

\section{Didaktische Überlegungen}
\subsection{Einordnung in den Lehrplan und in den Unterrichtsverlauf}

Die Stunde fällt in den Lernbereich \textbf{1 Graphen}~\cite{LPP-GY-Inf-11-NTG} des naturwissenschaftlich technischen Gymnasiums, welcher 10 Stunden umfasst und somit ca. ein Fünftel der 11. Jahrgangsstufe ausmacht.

Das Thema der Lehrprobe \textit{der Dijkstra-Algorithmus} folgt logisch der vorangegangenen Betrachtung der Breitensuche als systematisches Vorgehen zur Traversierung eines Graphens und schließt den Lernbereich ab.

Aufgrund der Schwierigkeiten mit der Java Programmierung wurde die Implementierung der Breitensuche nach die Herbstferien verschoben.

Die Unterrichtssequenz um die Lehrprobe ist wie folgt gestaltet:

\begin{itemize}
\item \textbf{Vorstunde}: 
Die \gls{SuS} entwickelten Algorithmen, wie in der eingeführten Java-Implementierung eines Graphens dessen Eigenschaften überprüft werden können.
Dabei wiederholten sie die in der 10. Jahrgangsstufe erworbene Kompetenz im Umgang mit Arrays.
Alle abstrakten Fragestellungen wurden mithilfe des Minotaurus "Manfred", der in einem Labyrinth lebt und gerne mehr über potentiell andere Labyrinthe erfahren möchte, konkretisiert.

Dabei hatten die \gls{SuS} große Schwierigkeiten, ihre entworfenen Algorithmen in Java-Code zu übertragen.

Anschließend, haben die \gls{SuS}, am Beispiel eines Wasserrohrbruchs in Manfreds Labyrinth, schrittweise den Algorithmus der Breitensuche durchgeführt und den Pseudocode erarbeitet.

\item \textbf{Vorstunde}: 
Die \gls{SuS} haben um für Manfred den Ausgang des Labyrinths zu finden, die Breitensuche selbstständig durchgeführt.
Mithilfe einer Visualisierung der Breitensuche haben sich die \gls{SuS} selbstständig die Funktionsweise der dabei eingesetzten Warteschlange hergeleitet und den Pseudocode des Algorithmus aufgestellt.
Anschließend haben die \gls{SuS} eine graphische Anleitung der Breitensuche im Stile einer IKEA Anleitung kommentiert und die Bezüge zum Pseudocode hergestellt.

\item \textbf{Lehrprobenstunde}: 
In der Lehrprobenstunde erarbeiten die \gls{SuS} aufbauend auf ihren Kenntnissen zur Breitensuche, anhand eines geeigneten und bekannten Beispiels, sowie einer erklärten Visualisierung schrittweise den Dijkstra-Algorithmus.
Die \gls{SuS} formulieren die Dringlichkeit des kürzesten Pfades in realen Anwendungen und führen den Dijkstra-Algorithmus an einem Beispiel aus ihrer Alltagswelt durch.

\item \textbf{Folgestunde}: 
In der Stunde nach der Lehrprobe setzen die \gls{SuS} den Breitensuche-Algorithmus in einem geeigneten Java-Projekt um.
\end{itemize}

\newpage
\subsection{Vergleich verschiedener Zugänge}

Die beiden untersuchten Schulbücher erarbeiten den Dijkstra-Algorithmus immer am Beispiel der Routenplanung einer Fahrradtour oder Wanderung.

Das verwendete Schulbuch \citetitle{cornelsen2023informatik5} beschreibt das Vorgehen des Dijkstra-Algorithmus an einem relativ großen Beispielgraphen ohne weitere Bedeutung (vgl. \cite[34]{cornelsen2023informatik5}), wohingegen \citetitle{buchner2024informatik11} das Einstiegsproblem aufgreift und in Einzelschritten an einem überschaubaren Graphen das Vorgehen jedes Schritts erklärt~\cite{buchner2024informatik11}.

Das Buch \citetitle{gallenbacher2008abenteuer} erklärt den Dijkstra-Algorithmus mit Ameisen, die alle gleichzeitig potentielle Wege ablaufen, und somit immer die Ameisen, die den kürzesten Weg zu einem Knoten verfolgten, dort als erste ankommen und diesen markieren~\cite[13ff]{gallenbacher2008abenteuer}.

Im Internet existieren viele verschiedene Visualisierungen des Dijkstra-Algorithmus.
Oft handelt es sich dabei um Angebote privater Programmierer, die eine rein graphische Visualisierung des Algorithmus veröffentlichen.

Aber auch Universitäten bieten vor allem für ihre Studierende Visualisierungen des Dijkstra-Algorithmus an.
Im Folgenden stelle ich kurz drei Varianten und meine Entscheidung für eine Visualisierung vor:

Die Webseite der University of San Francisco~\cite{usfcaAlgo} bietet keine Möglichkeit einen eigenen Graphen zu verwenden.
Die Darstellungsmöglichkeit als Adjazenzmatrix ist sehr gut geeignet, um die Implementierung zu unterstützen, da aber keine Implementierung des Dijkstra-Algorithmus vom Lehrplan verlangt wird~\cite{LPP-GY-Inf-11-NTG}, ist diese Darstellung für den Informatikunterricht irrelevant.
Die Konstruktion der kürzesten Pfade ist in der Animation schlecht begründet beziehungsweise nicht offensichtlich dargestellt.
Auch werden keine Erklärungen in textueller Form zu den einzelnen Schritten angezeigt.

Visualgo.net eine Webseite der Universität Singapur~\cite{visualgoAlgo} ist eher für ihre Studierende gedacht und zeigt automatisch den sehr mathematischen und formalen Pseudocode des Algorithmus während des Durchlaufs an.
Leider ist die Webseite nicht auf Deutsch verfügbar und somit sind die vorhandenen Erklärungen rund um die Problemstellung ungeeignet für den Informatikunterricht.

Keine der betrachteten Visualisierungen erfüllt die Kriterien so wie die Webseite der TU München~\cite{tumAlgo}.
Bei dieser Visualisierung ist es möglich, einen eigenen Graphen hochzuladen, ohne ihn per Hand jedes mal selbst zusammenzuklicken.
Dadurch können alle \gls{SuS} den Algorithmus an dem gleichen bereits bekannten Graphen ausführen ohne große Verzögerungen in der Stunde.
Zusätzlich bietet die TU München deutsche Erklärungen zu jedem Schritt und eine anschließende Erklärung des gesamten Algorithmus.
% Außerdem sind Forschungsfragen enthalten, die das Verständnis des Algorithmus überprüfen.

\subsection{Sachanalyse}

\subsubsection{Graphen}

Ein Graph ist eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert. 

Die Objekte werden als \emph{Knoten} bezeichnet und die zwischen Knoten bestehenden Verbindungen als \emph{Kanten}.
Eine Möglichkeit einen solchen Graphen darzustellen ist, ihn als die zwei Mengen $V$, die Menge aller Knoten (englisch \boldred{v}ertices) und $E$, die Menge aller Kanten (englisch \boldred{e}dges) anzugeben.
Der in \cref{fig:simple-graph} gezeigte Graph kann demnach in Mengenschreibweise wie folgt dargestellt werden:
\[(\{v1,v2,v3,v4\}, \{(v1,v2), (v2,v1), (v1,v3), (v3,v1), (v1,v4), (v4,v1), (v2,v4)\})\]

Meist werden Graphen allerdings zur Visualisierung für Menschen graphisch dargestellt.
Dabei werden Knoten mit ihrer Bezeichnung in einem Kreis und Kanten als einfache Linien zwischen Knoten dargestellt.
\Cref{fig:simple-graph} zeigt einen Graphen mit vier Knoten und drei ungerichteten und einer gerichteten Kante.

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1.4]
  \node[draw, circle] (1) at (0, 0) {v1};
  \node[draw, circle] (2) at (1, 0) {v2};
  \node[draw, circle] (3) at (1, -1) {v3};
  \node[draw, circle] (4) at (0, 1) {v4};
  \graph {
    (1) -- (2),
    (1) -- (3),
    (1) -- (4),
    (2) -> (4),
  };
\end{tikzpicture}
\end{center}
\caption{Graphische Darstellung eines Graphens.
Zwischen den Knoten v1 und den Anderen existiert eine Kante.
Außerdem ist v2 über eine \emph{gerichtete} Kante mit v4 verbunden.}
\label{fig:simple-graph}
\end{figure}

Kanten zwischen zwei Knoten können ein spezifisches \emph{Gewicht} aufweisen.
Graphen mit \emph{gewichteten} Kanten nennt man \emph{gewichtet}.
Kanten haben grundsätzlich eine Richtung, das heißt einen Start und einen Zielknoten.
Die Richtung einer Kante wird mit einer Pfeilspitze symbolisiert.
Verläuft eine Kante in beide Richtungen können die Pfeilspitzen weggelassen werden und man spricht von einer \emph{ungerichteten} Kante.
Besteht ein Graph nur aus \emph{ungerichteten} Kanten, so handelt es sich um einen \emph{ungerichteten} Graphen.
Graphen, in denen jeder Knoten durch einen Pfad, eine beliebige Folge von Kanten, mit jedem anderen Knoten verbunden ist, nennt man \emph{zusammenhängend}.
Ein Spezialfall von \emph{zusammenhängenden} Graphen sind die \emph{vollständigen} Graphen, bei denen von jedem Knoten zu jedem anderen Knoten eine direkte \emph{Kante} existiert.

Eine weitere Möglichkeit Graphen darzustellen, sind Adjazenzmatrizen.
Eine Adjazenzmatrix entspricht einer $n \times n$ Tabelle die alle möglichen Kanten eines Graphen mit $n$ Knoten erfassen kann (siehe \Cref{fig:adjmtrx}).
In \emph{ungewichteten} Graphen werden Kanten gewöhnlich mit Einträgen von $1$, es existiert eine Kante, oder $0$, es existiert keine Kante, vermerkt.
In \emph{gewichteten} Graphen werden Kanten mit ihrem Kantengewicht oder $-1$ dargestellt.
Nachdem jeder \emph{ungewichtete} Graph auch als \emph{gewichtet} mit impliziten Gewichten von $1$ aufgefasst werden kann, wurde zur Implementierung die allgemeinere Darstellung ($Kantengewicht$ / $-1$) gewählt.

Die Adjazenzmatrix ist eine beliebte Darstellung, da sie sich einfach mit einer zweidimensionalen Datenstruktur in den meisten Programmiersprachen implementieren lässt, und schnellen und gezielten Zugriff auf einzelne oder alle Kanten erlaubt.

Gewöhnlich ist die Diagonale leer, da ein Knoten im verwendeten Graphenmodell keine Kante zu sich selbst haben kann.

Ein reales Problem von Adjazenzmatrizen ist ihre Speicherplatzverschwendung für Graphen mit sehr vielen Knoten aber wenig Kanten.

\begin{figure}
\begin{center}
\begin{tabular}{c | c | c | c | c}
\rowcolor{gray!30} \cellcolor{gray} & v1 & v2 & v3 & v4 \\
\hline
\cellcolor{gray!30} v1 & \cellcolor{gray!30} & 1 & 1 & 1 \\
\hline
\cellcolor{gray!30} v2 & 1 & \cellcolor{gray!30} & & 1 \\
\hline
\cellcolor{gray!30} v3 & 1 & & \cellcolor{gray!30} & \\
\hline
\cellcolor{gray!30} v4 & 1 & & & \cellcolor{gray!30} \\
\hline
\end{tabular}
\end{center}
\caption{Die Adjazenzmatrix des in \Cref{fig:simple-graph} dargestellten Graphens.
Die Adjazenzmatrix ist nicht achsensymmetrisch zu ihrer Diagonalen aufgrund der \emph{gerichteten} Kante von v2 zu v4.
Einträge mit $0$ wurden zur besser Übersicht weg gelassen.}
\label{fig:adjmtrx}
\end{figure}

\subsubsection{Breitensuche}

Die Breitensuche ist ein Algorithmus zur strategischen Traverisierung eines Graphens, dem Besuchen aller erreichbaren Knoten von einem Startpunkt aus.
Dabei werden alle Knoten, die den gleichen Abstand zum Startknoten haben und somit in einer "Ebene" liegen, besucht, bevor die Knoten in der nächsten Ebene betrachtet werden.

Als Datenstruktur, um die zu besuchenden Knoten zu verwalten, kommt eine Warteschlange zum Einsatz.
Bei einer Warteschlange wird der erste eingefügte Knoten auch wieder als Erstes entfernt.

Um Knoten nicht mehrfach zu besuchen und somit Fortschritt bei der Traversierung zu garantieren, wird für jeden Knoten vermerkt, ob er bereits betrachtet wurde.

Diese Eigenschaft erlaubt es, nur aktuell noch unbekannte Knoten in die Warteschlange aufzunehmen.

\begin{figure}
\input{bfs-pseudocode.tex}
\caption{Pseudocode der Breitensuche.}
\label{fig:bfs-pseudocode}
\end{figure}

Die Breitensuche kann genutzt werden, um zu bestimmen, ob ein Graph zusammenhängend ist.
Sind am Ende eines Durchlaufs alle Knoten markiert worden, ist der Graph zusammenhängend.

Jeder durch Breitensuche bestimmte Pfad, hat in einem ungewichteten Graphen den kürzesten Abstand zum Startknoten.

\subsubsection{Dijkstra-Algorithmus}

\begin{figure}
\begin{center}
\begin{tikzpicture}[
  graph vertex/.style={draw, circle, inner sep=3pt},
  edge label/.style={fill=white},
  marked/.style={fill=blue!40},
  active/.style={draw=red, fill=red!40},
  bad/.style={draw=red, thick},
  better/.style={draw=green!70!black, thick}
]
  \node[graph vertex, active] (1) {v1};
  \node[graph vertex, marked] (2) at (2, 0) {v2};
  \node[graph vertex, marked] (3) at (0, -2) {v3};
  \node[graph vertex] (4) at (2, -2) {v4};

  \graph[edge quotes mid] {
    (1) -> ["5" edge label, bad] (2),
    (1) -> ["1" edge label, better] (3),
    (3) -> ["1" edge label, better] (4),
    (4) -> ["1" edge label, better] (2),
  };
\end{tikzpicture}
\end{center}
\caption{Gerichteter Graph, in dem der durch Breitensuche vom Startpunkt $v1$ zu $v2$ gefundene Pfad $v1/v2$ länger ist als der Pfad $v1/v3/v4/v2$.}
\label{fig:directed-graph-bfs}
\end{figure}

In gerichteten Graphen kann es Pfade geben, die trotz größerer Anzahl an Kanten eine kleine Länge aufweisen, da die Kantengewichte aufsummiert werden.

Der Dijkstra Algorithmus erweitert die Breitensuche, um die kürzesten Pfade in einem gewichteten Graphen zu finden.

Dies wird erreicht, indem immer der aktuell kürzeste Pfad verlängert wird.
Um dies zu erreichen werden die bereits gefundenen aber noch zu betrachtenden Knoten in einer Prioritätswarteschlange nach ihrer Pfadlänge zum Startknoten aufsteigend sortiert.
Um nach einem Durchlauf den kürzesten Pfad zwischen einem Knoten und dem Startknoten konstruieren zu können, wird für jeden Knoten der Vorgänger vermerkt.
Sollte für einen noch nicht markierten Knoten ein kürzerer Weg gefunden werden, wird die gespeicherte Distanz sowie der Vorgängerknoten aktualisiert und die Warteschlange gegebenenfalls neu sortiert.

\begin{figure}
\input{lesson/topic/pseudocode.tex}
\caption{Pseudocode des Dijkstra-Algorithmus.}
\label{fig:bfs-pseudocode}
\end{figure}

Der Dijkstra-Algorithmus ist eine Lösung für das \emph{Single-Source Shortest Path} Problem, bei dem ausgehend von einem Knoten der kürzeste Pfad zu einem oder allen anderen Knoten gefunden werden soll.
\newpage

\section{Planung der Stunde}

\subsection{Lernziele und tabellarischer Stundenverlauf}
\textbf{Stundenziel}: Die \gls{SuS} analysieren und erläutern die Funktionsweise des Dijkstra-Algorithmus und wenden diesen an einem konkreten Beispiel an.

\textbf{Feinziele}: \vspace{2mm}\\
\begin{tabular}{l p{0.8\textwidth}}
1. & \acrshort{SuS} analysieren den Dijkstra-Algorithmus anhand einer Visualisierung dessen Ablaufs an einem ihnen bekannten Graphen. \\
2. & \acrshort{SuS} erklären den Ablauf des Dijkstra-Algorithmus und sortieren dessen Schritte in Pseudocode. \\
3. & \acrshort{SuS} reflektieren ihnen bekannte Situationen, in denen der Dijkstra-Algorithmus eingesetzt werden könnte. \\
4. & \acrshort{SuS} wenden den Dijkstra-Algorithmus an einem geeigneten Beispiel an. \\
\end{tabular}

\makebox[\textwidth][c]{
\renewcommand*{\arraystretch}{1.5}
\begin{tabular}{l p{0.55\textwidth} c c c}
Phase & Unterrichtsgeschehen & Ziel & Methode & Medien \\
\toprule
Wiederholung & \emph{Turn and Talk} \newline Warteschlange LIFO oder FIFO \newline Markierung $\rightarrow$ Speichern \newline BFS kürzeste Pfade gewichtet vs. ungewichtet\newline & \acrshort{PA}/\acrshort{UG} & \acrshort{BE} \\
Motivation  & LK stellt Problem vor: Manfred muss auf die Toilette & \acrshort{LV} & \acrshort{BE} \\
Erarbeitung & \gls{SuS} analysieren mit einer Visualisierung den Dijkstra-Algorithmus an einem geeigneten Graphen & \acrshort{PA} & PC \\
Erarbeitung & \gls{SuS} überprüfen ihr Verständnis des Dijkstra-Algorithmus anhand eines Lückentexts & \acrshort{PA} & PC \\
Sicherung   & \gls{SuS} übertragen die Lücken auf ihr Arbeitsblatt & \acrshort{UG}/\acrshort{EA} & \acrshort{AB} \\
Erarbeitung & \gls{SuS} sortieren den Dijkstra-Algorithmus in Pseudocode & \acrshort{PA} & PC \\
Sicherung   & \gls{SuS} füllen die Lücken im Pseudocode auf der Rückseite ihres Arbeitsblattes & \acrshort{UG}/\acrshort{EA} & \acrshort{AB} \\
Übung       & \gls{SuS} bestimmen den kürzesten Weg für Manfred auf eine Toilette mit der Visualisierung & \acrshort{EA}/\acrshort{UG} & \acrshort{AB}, PC \\
Vertiefung  & \gls{SuS} verallgemeinern die Anwendbarkeit des Dijkstra-Algorithmus auf die Navigation in Beispielen aus ihrer Alltagswelt & \acrshort{UG} & \acrshort{BE} \\
Übung       & \gls{SuS} wenden den Dijkstra-Algorithmus an, um eine Alpenüberquerung mit dem Rad zu planen & \acrshort{UG}/\acrshort{EA}/\acrshort{PA} & \acrshort{AB}, \acrshort{BE} \\
Puffer      & \gls{SuS} reflektieren die Einsetzbarkeit des Algorithmus oder Bearbeiten die Hausaufgabe & \acrshort{UG}/\acrshort{EA}/\acrshort{PA} & \acrshort{AB} \\
\toprule
Hausaufgabe & \gls{SuS} führen den Dijkstra-Algorithmus an dem Teilgraph von Manfreds Labyrinth per Hand durch und füllen dabei die Tabelle auf ihrem Arbeitsblatt & & \acrshort{AB} \\
\hline
\end{tabular}
} \\[0.2cm]
{\footnotesize \acrfull{PA}, \acrfull{UG}, \acrfull{EA}, \acrfull{BE}, \acrfull{AB}}

\subsection{Stundenverlauf}

% Hausaufgabe fakultativ und individuell via Teams.

Die Stunde beginnt wie gewohnt mit dem Diskutieren präsentierter Aussagen zur Aktivierung der \gls{SuS}, Wiederholung der Vorstunde und den in der Stunde benötigten Kenntnissen zu den Eigenschaften von Graphen.
Es werden drei Aussagen präsentiert.
Für jede Aussage haben die \gls{SuS} ca. eine Minute Zeit, sie zu zweit zu besprechen.
Im Anschluss wird die Aussage im Plenum thematisiert.

Anschließend stelle ich das die Stunde motivierende Problem vor.
Der bereits in den Vorstunden verwendete Minotaurus namens "Manfred" braucht erneut Hilfe in seinem Labyrinth.

\begin{wrapfigure}[19]{r}{4cm}
\includegraphics[keepaspectratio, width=4cm]{lesson/topic/img/manfred_cut_out_autum.png}
\caption{Manfred in seinem Herbstoutfit.}
\label{fig:manfred_autum}
\end{wrapfigure}

Nachdem die in den Vorstunden thematisierten Wasserrohrbrüche in Manfreds Wohnung repariert sind, entspannt Manfred in seinem Heimkino (Raum 13).
Als er nachts aufwacht, muss er dringend auf die Toilette, leider wohnt er in einem Labyrinth und weiß deshalb nicht, was der kürzeste Weg zu einer Toilette ist.
Er hat allerdings die Strecken in seinem Labyrinth mit einer Stoppuhr vermessen.
Allerdings sind es zu viele Wege, um sie alle einzeln auszuprobieren.

Die \gls{SuS} schätzen die Anzahl der Wege (257), und begründen somit die Notwendigkeit für einen neuen Algorithmus (vgl. \cite[26]{gallenbacher2008abenteuer}).

Dieses Problem lösen die \gls{SuS} anschließend für Manfred mithilfe des Dijkstra-Algorithmus zunächst an einem Teilgraph seines Labyrinthes.
Dazu verwenden die \gls{SuS} die Visualisierung der TU München~\cite{tumAlgo} und einen dafür vorbereiteten gerichteten Teilgraph von Manfreds Labyrinth.
Die Visualisierung ist an den Computer-Arbeitsplätzen bereits geöffnet, sodass das Hochladen des Graphs und dabei potentiell auftretende Schwierigkeiten entfallen.

Währenddessen wird das Arbeitsblatt, das der Sicherung dient und den Rest der Stunde begleitet, von mir leise ausgeteilt.

Nachdem die \gls{SuS} die Visualisierung nachvollzogen haben, überprüfen sie ihr allgemeines Verständnis über den soeben analysierten Algorithmus mit einer interaktiven H5P-Anwendung, bei der sie vorbereitete Lücken ausfüllen und entsprechendes Feedback erhalten.
Die Lücken sichern sie anschließend selbstständig auf ihrem Arbeitsblatt und stellen ihre Erkenntnisse im Plenum vor.

Anschließend sortieren die \gls{SuS} die Schritte des Dijkstra-Algorithmus in Pseudocode in einer zweiten H5P-Anwendung.
Mit einem korrekt sortiertem Pseudocode, drehen die \gls{SuS} ihr Arbeitsblatt um, auf dessen Rückseite der Pseudocode und die darin enthaltenen Lücken ergänzt werden.
Die Tatsache, dass der Pseudocode zur Sicherung auf dem Arbeitsblatt abgedruckt ist, ist der Grund, dass alle \gls{SuS} auf Papier mitarbeiten sollen, um den Effekt des Umdrehens des Arbeitsblattes zu ermöglichen.

Mit den gewonnenen Erkenntnissen zum Dijkstra-Algorithmus lösen die \gls{SuS} die Eingangsproblematik und bestimmen für Manfreds komplettes Labyrinth den kürzesten Weg zu einer Toilette.
Dazu verwenden sie erneut die bereits auf den Computern vorbereitete Visualisierung in einem zweiten Tab mit dem kompletten Graphen des Labyrinths.
Der komplette Graph enthält dabei Kanten in beide Richtungen, da das zugrunde liegende Labyrinth ungerichtet ist.
Der Start der Visualisierung und die Eigenschaft des Graphens werden im Plenum besprochen, bevor die \gls{SuS} selbst den Rest der Visualisierung ablaufen lassen.
Dabei kommt zum Tragen, dass der Dijkstra-Algorithmus in einem Durchlauf den kürzesten Weg vom Start zu jedem erreichbaren Knoten bestimmt.
Zusätzlich notieren die \gls{SuS} auch die Besuchsreihenfolge der Räume, sodass schnellere \gls{SuS} reflektieren können, dass die Besuchsreihenfolge den Pfadlängen der Räume in aufsteigend sortierter Ordnung entspricht.

\begin{wrapfigure}[19]{l}{6.2cm}
\includegraphics[keepaspectratio, width=6cm]{lesson/topic/img/manfreds_labyrinth_toilets.png}
\caption{Manfreds Labyrinth mit den beiden eingezeichneten Toiletten (Raum 2 und 14). Das Heimkino befindet sich in Raum 13.}
\label{fig:labyrinth_toilets}
\end{wrapfigure}

Anschließend verallgemeinern die \gls{SuS} die Anwendbarkeit des Dijkstra-Algorithmus auf ihre Alltagswelt.
Wobei, falls es nicht bereits erwähnt wurde, das zur Einführung von Graphen benutzte Beispiel der Fahrradtour wieder aufgegriffen wird.

Die \gls{SuS} planen eine Radtour durch die Alpen von Traunstein nach Venedig mit dem Dijkstra-Algorithmus unter Zuhilfenahme einer Tabelle.
Die ersten Einträge beim Ausfüllen der Tabelle werden gemeinsam erarbeitet und danach füllen die \gls{SuS} die Tabelle selbstständig aus.
Anhand der ausgefüllten Tabelle bestimmen die \gls{SuS} den kürzesten Weg von Traunstein nach Venedig.
An dieser Stelle reflektieren schnelle \gls{SuS} die Anwendbarkeit des Dijkstra-Algorithmus in realen Navigationssystemen.
Ein Problem des Dijkstra-Algorithmus ist, dass er erst terminiert, nachdem alle Knoten besucht wurden.
Außerdem wird nur das Kantengewicht, hier am Beispiel die Strecke, berücksichtigt und nicht potentielle andere Faktoren wie die Art der Strecke oder die Steigung.

\subsection{Didaktisch-methodische Analyse des Lehrprobeninhalts}
Ich habe mich für den gewohnten Einstieg entschieden, da so leicht benötigtes Vorwissen aktiviert werden kann und durch die Gewohnheit potentielle Hemmungen aufgrund der Lehrproben-Situation vermieden werden. 
Außerdem wird dadurch die Kompetenz, über fachliche Zusammenhänge zu kommunizieren, bei allen gefordert und gefördert.

Die erste Aussage behandelt die in der Breitensuche neu eingeführte Datenstruktur der FIFO-Warteschlange und grenzt diese von dem anderen aus dem Alltag bekannten Prinzip eines Stapels (LIFO) ab.
Da die Warteschlange zu einer nach Pfadlänge sortierten Warteschlange erweitert wird, war es mir wichtig, allen noch einmal die Funktionsweise einer Warteschlange in Erinnerung zu rufen.

Aussage zwei verbindet die bisher hauptsächlich theoretisch behandelten Algorithmen mit einer potentiellen Implementierung und stellt für die \gls{SuS} den Bezug zu Computern als "Alleinstellungsmerkmal" des Informatikunterrichts her.

Die letzte Aussage legt den Grundstein für einen weiteren Algorithmus, da die Breitensuche in gerichteten Graphen gegebenenfalls nicht die optimale Lösung findet.

Die anschließende Motivation mit Manfreds Labyrinth ist anschaulich und dringlich genug, damit die \gls{SuS} eine Vorstellung davon haben, was es zu lösen gilt.

Die selbstständige Erarbeitung des Algorithmus in Partnerarbeit mithilfe einer Visualisierung erfüllt die im Lehrplan geforderte \emph{Analyse} des Dijkstra-Algorithmus~\cite{LPP-GY-Inf-11-NTG}.
Die Partnerarbeit ist in dem beengten und unflexiblen Computerraum, die unkomplizierteste und oft einzig praktikable Möglichkeit freiere Arbeitsphasen umzusetzen.

Die Erkenntnisse der \gls{SuS} können sie anschließend selbstständig auf ihrem Arbeitsblatt mit Feedback durch die beiden eingesetzten H5P-Anwendungen vornehmen.
Diese eigenständige Erarbeitung und Sicherung sorgt für eine hohe Aktivierung der \gls{SuS} und die Möglichkeit als Lehrkraft individuell zu unterstützten.

Um alle mitzunehmen, werden die Ergebnisse der Sicherungen vor jeder weiteren Phase im Plenum besprochen.

Anschließend wird mit dem erarbeiteten Verständnis des Dijkstra-Algorithmus das Toiletten-Problem von Manfred gelöst.
Dabei werden die Eigenheiten der Visualisierung des kompletten Graphens im Plenum thematisiert, bevor jeder selbst den kürzesten Weg und die Besuchsreihenfolge der Räume nachvollziehen soll.

Nachdem das sehr fantastische Thema des Labyrinths des Minotauren gelöst ist, übertragen die \gls{SuS} die Anwendbarkeit des Dijkstra-Algorithmus auf ihre Alltagswelt und die alltäglich gegenwärtige Thematik der Navigation.

Dabei sollen sie eine Radreise planen und führen, wie im Lehrplan gefordert, mit Hilfe einer Tabelle den Dijkstra-Algorithmus an einem geeigneten Beispiel durch~\cite{LPP-GY-Inf-11-NTG}.
Dabei werden die ersten Schritte beim Ausfüllen der Tabelle gemeinsam erarbeitet.
Der kürzeste Weg wird anschließend gemeinsam aus der Tabelle abgelesen.

Als Hausaufgabe mit Blick auf potentielle Anwendbarkeit in der anstehenden Kurzarbeit, sollen alle \gls{SuS} die Tabelle zum Teilgraph von Manfreds Labyrinth nach dem selben Verfahren ausfüllen, dazu steht ihnen bei Bedarf ein Lernvideo zur Verfügung.

\section{Literaturnachweise}

\printbibliography

\section{Abkürzungsverzeichnis}

\printglossary[type=\acronymtype]

\section{Erklärung}

Ich versichere, dass ich den Lehrprobenentwurf in allen Teilen selbstständig angefertigt und keine anderen als die angegebenen Hilfsmittel benutzt habe.

\vspace{2cm}
Erlangen, den \today{} \hfil \begin{minipage}{3cm}
\underline{\Large \phantom{Florian Fischer}} \\
\hfil Florian Fischer
\end{minipage}

\section{Anhang}
\phantomsection
\addcontentsline{toc}{subsection}{Folien}
\includepdf[landscape,pages=-, nup=2x2]{lesson/topic/slides.pdf}
\phantomsection
\addcontentsline{toc}{subsection}{Arbeitsblatt unausgefüllt}
\includepdf{lesson/topic/AB_Dijkstra.pdf}

\phantomsection
\addcontentsline{toc}{subsection}{Arbeitsblatt ausgefüllt}
\includepdf{lesson/topic/AB_Dijkstra_Lsg.pdf}

\newgeometry{margin=1cm,top=1cm}
\afterpage{\restoregeometry}
\pagestyle{empty}
\begin{landscape}
\resizebox{28cm}{!}{
\phantomsection
\addcontentsline{toc}{subsection}{Sitzplan}
\input{sitzplan.tikz}
}
\end{landscape}

\end{document}