add past info lesson

6 files changed, 320 insertions, 0 deletions

diff --git a/Info/24_25/11/04/11C/BFS b/Info/24_25/11/04/11C/BFS
new file mode 120000
index 00000000..9a80621a
--- /dev/null
+++ b/Info/24_25/11/04/11C/BFS
@@ -0,0 +1 @@
+../../../../11/NTG/1/Breitensuche/
\ No newline at end of file
diff --git a/Info/24_25/11/04/11C/Dijkstra b/Info/24_25/11/04/11C/Dijkstra
new file mode 120000
index 00000000..74065ebd
--- /dev/null
+++ b/Info/24_25/11/04/11C/Dijkstra
@@ -0,0 +1 @@
+../../../../11/NTG/1/Dijkstra/
\ No newline at end of file
diff --git a/Info/24_25/11/04/11C/img/biber.png b/Info/24_25/11/04/11C/img/biber.png
new file mode 100644
index 00000000..f981e2b1
--- /dev/null
+++ b/Info/24_25/11/04/11C/img/biber.png
diff --git a/Info/24_25/11/04/11C/img/bike.png b/Info/24_25/11/04/11C/img/bike.png
new file mode 100644
index 00000000..8eb55c15
--- /dev/null
+++ b/Info/24_25/11/04/11C/img/bike.png
diff --git a/Info/24_25/11/04/11C/schedule.md b/Info/24_25/11/04/11C/schedule.md
new file mode 100644
index 00000000..616c0299
--- /dev/null
+++ b/Info/24_25/11/04/11C/schedule.md
@@ -0,0 +1,30 @@
+---
+lang: de
+geometry: margin=2cm
+---
+# Impl Breitensuche / Bieber
+
+* **Klasse**: 11C
+* **Datum**: 04.11
+
+## Lernziele
+
+## Verlaufplan
+
+---------------------------------------------------------------------------------------------------
+Zeit  Phase           Unterrichtsgeschehen                         Ziel        Methode    Medien
+----- --------------- -------------------------------------------- ----------- ---------- ---------
+5     Orga
+
+5     Wdh             Dijkstra
+
+5     Wdh             Dijkstra Fahrrad
+
+5     Wdh             Dijkstra Manfred
+
+20    Erarbeitung     BS Code
+
+5     Sicherung       BS Code
+
+45    Bieber
+---------------------------------------------------------------------------------------------------
diff --git a/Info/24_25/11/04/11C/slides.md b/Info/24_25/11/04/11C/slides.md
new file mode 100644
index 00000000..d32f0c23
--- /dev/null
+++ b/Info/24_25/11/04/11C/slides.md
@@ -0,0 +1,288 @@
+---
+header-includes: |
+    \makeatletter
+    \beamer@ignorenonframefalse
+    \makeatother
+    \usetikzlibrary{graphs, shapes, quotes}
+    \usetikzlibrary{overlay-beamer-styles}
+    \usepackage{changepage}
+    \usepackage{adjustbox}
+    \newcommand\revealtexton[3]{\textbf{\only<-#2>{\textcolor{bg}{#1}}\only<#3->{\textcolor{red}{#1}}}}
+    \newcommand\textvtt[1]{{\normalfont\fontfamily{cmvtt}\selectfont #1}}
+---
+
+## {.standout}
+Herzlich Willkommen!
+
+Du kannst dich schon anmelden
+
+\texttt{vorname.nachname}
+
+und den Bildschirm ausschalten.
+
+## Wo ist der Zusammenhang?
+
+::: {.columns}
+:::: {.column width=50%}
+![](img/bike.png)
+::::
+
+:::: {.column width=50%}
+![](Dijkstra/img/Edsger_Wybe_Dijkstra_cutout.png)
+::::
+:::
+
+## \faIcon{chalkboard-teacher} Wir Planen unsere Radreise
+::: {.columns align=center}
+:::: {.column width=70%}
+\resizebox{\textwidth}{!}{
+\newcolumntype{C}{ >{\centering\arraybackslash} m{1.5cm} }
+\newcolumntype{D}{ >{\centering\arraybackslash} m{1.4cm} }
+ \renewcommand{\arraystretch}{1.5}% Spread rows out...
+\begin{tabular}{c|C|D|D|D|D|D|D|c}
+Ort & Traunstein \newline (Tra) & Innsbruck \newline (Is) & Millstatt \newline (M) & Trient \newline (Tri) & Innichen \newline (Ic) & Treviso \newline (Tre) & Venedig \newline (V) & Warteschlange\\
+\hline
+- & \only<2->{$0/-$ & $\infty/-$ & $\infty/-$ & $\infty/-$ & $\infty/-$ & $\infty/-$ & $\infty/-$ & Tra}\only<1>{&&&&&&&} \\
+\hline
+\only<3->{Tra} & \only<3->{\cellcolor{red!30}$0/-$} & \only<3->{$138/$Tra} & \only<3->{$211/$Tra} & & & & & \only<3->{Is, M} \\
+\hline
+\only<4->{Is} & & \only<4->{\cellcolor{red!30}$138/$Tra} & & \only<4->{$327/$Is} & \only<4->{$277/$Is} & & & \only<4->{M, Ic, Tri} \\
+\hline
+\only<5->{M} & & & \only<5->{\cellcolor{red!30}$211/$Tra} & & & & \only<5->{$489/$M} & \only<5->{Ic, Tri, V} \\
+\hline
+\only<6->{Ic} & & & & & \only<6->{\cellcolor{red!30}$277/$Is} & \only<6->{$434/$Ic} & & \only<6->{Tri, Tre, V} \\
+\hline
+\only<7->{Tri} & & & & \only<7->{\cellcolor{red!30}$327/$Is} & & & & \only<7->{Tre, V} \\
+\hline
+\only<8->{Tre} & & & & & & \only<8->{\cellcolor{red!30}$434/$Ic} & \only<8->{$472/$Tre} & \only<8->{V} \\
+\hline
+\only<9->{V} & & & & & & & \only<9->{\cellcolor{red!30}$472/$Tre} & \\
+\hline
+\end{tabular}
+}
+\begin{tikzpicture}[overlay, remember picture]
+\only<12->{\draw[-Triangle, red, line width=1pt] (6.9, 0.2) -- (6.6, 0.4);}
+\only<13->{\draw[-Triangle, red, line width=1pt] (6, 0.8) -- (5.5, 1.45);}
+\only<14->{\draw[-Triangle, red, line width=1pt] (5, 1.75) -| (2.5, 2.3);}
+\only<15->{\draw[-Triangle, red, line width=1pt] (2, 2.8) -- (1.8, 3);}
+\end{tikzpicture}
+::::
+
+:::: {.column width=30%}
+\resizebox{\textwidth}{!}{
+\begin{tikzpicture}[
+  graph vertex/.style={draw, ellipse, inner xsep=1pt, inner ysep=1mm},
+  edge label/.style={fill=yellow!30},
+  marked/.style={fill=blue!40},
+  marked on/.style={alt=####1{marked}{}},
+  active/.style={fill=red!40},
+  active on/.style={alt=####1{active}{}},
+]
+\node[graph vertex, marked on=<3->, active on=<3>] (ts) {Traunstein};
+\node[graph vertex, marked on=<4->, active on=<4>] (ib) at (-2.5, -2) {Innsbruck};
+\node[graph vertex, marked on=<5->, active on=<5>] (ms) at (1.5, -2.5) {Millstatt};
+\node[graph vertex, marked on=<6->, active on=<6>] (ic) at (-1, -3.5) {Innichen};
+\node[graph vertex, marked on=<7->, active on=<7>] (tr) at (-3.5, -4) {Trient};
+\node[graph vertex, marked on=<8->, active on=<8>] (tv) at (-2, -5.25) {Treviso};
+\node[graph vertex, marked on=<9->, active on=<9>] (vd) at (0.5, -6) {Venedig};
+
+\graph[edge quotes mid] {
+  (ts) -- ["138" edge label] (ib),
+  (ts) -- ["138" edge label] (ib),
+  (ts) -- ["211" edge label] (ms),
+  (ib) -- ["139" edge label] (ic),
+  (ib) -- ["189" edge label] (tr),
+  (ms) -- ["120" edge label] (ic),
+  (tr) -- ["136" edge label] (tv),
+  (ic) -- ["157" edge label] (tv),
+  (ms) -- ["278" edge label] (vd),
+  (tv) -- ["38" edge label] (vd),
+};
+\end{tikzpicture}
+}
+::::
+:::
+
+\only<10->{Kürzester Weg:} \only<15->{\textbf{Tra/Is/Ic/Tre/V}}
+
+
+## \faIcon{pencil-alt} Arbeitsauftrag: Ausbessern
+
+\small
+\begin{adjustbox}{center=-1.2cm}
+\begin{minipage}{1.1\textwidth}
+\begin{pseudocode}
+\textvtt{Weise allen Knoten die beiden Eigenschaften „Distanz“ und „Vorgänger“ zu.}
+\vspace{0.1cm}
+
+\textvtt{Initialisiere die Distanz des Startknoten mit 0 und die der anderen Knoten mit $\infty$.}
+\vspace{0.1cm}
+
+\textvtt{Füge den Startknoten der Warteschlange hinzu.}
+\vspace{0.1cm}
+
+\textvtt{Solange die Warteschlange nicht leer ist ...}
+\vspace{0.1cm}
+
+\begin{adjustwidth}{0.5cm}{}
+\textvtt{Nimm den Knoten mit minimaler (aufsummierter) Distanz aus der Warteschlange.}
+\vspace{0.1cm}
+
+\textvtt{Markiere diesen Knoten.}
+\vspace{0.1cm}
+
+\textvtt{Berechne für alle unmarkierten Nachbarn die Gesamtdistanz des Pfades zum Startknoten ($\text{Kantengewicht} + \text{Distanz des aktuellen Knotens}$) \revealtexton{und füge sie der Warteschlange hinzu}{1}{2}.}
+\vspace{0.1cm}
+
+\textvtt{Ist dieser Wert kleiner als die für diesen Nachbarn gespeicherte Distanz, aktualisiere sie und speichere den aktuellen Knoten als Vorgänger.}
+\end{adjustwidth}
+\end{pseudocode}
+\end{minipage}
+\end{adjustbox}
+
+## \faIcon{pencil-alt} AB: Dijkstra in Manfreds Labyrinth {.t}
+
+Fülle die Tabelle zu dem Teilgraph von Manfreds Labyrinth auf deinem Arbeitsblatt.
+
+::: {.columns}
+:::: {.column width=70%}
+\resizebox{\textwidth}{!}{
+\renewcommand{\arraystretch}{1.5}% Spread rows out...
+\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c}
+Raum & 2 & 4 & 7 & 9 & 10 & 11 & 12 & 13 & WS \\ \hline
+& {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & {\small D|V} & \\[-0.1cm] \hline \only<-1>{&&&&&&&&&}\only<2->{- & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $0|-$ & 13} \\\hline 
+\only<-2>{&&&&&&&&&}\only<3->{13 & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $5|9$  & $\infty|-$ & $4|9$ & \cellcolor{red!30}$0|-$ & 12, 10} \\\hline 
+\only<-3>{&&&&&&&&&}\only<4->{12 & $\infty|-$ & $\infty|-$ & $\infty|-$ & $\infty|-$ & $5|9$ & $9|12$ & \cellcolor{red!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 10, 11} \\\hline 
+\only<-4>{&&&&&&&&&}\only<5->{10 & $\infty|-$ & $\infty|-$ & $\infty|-$ & $10|10$ & \cellcolor{red!30} $5|9$ & $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 11, 9} \\\hline 
+\only<-5>{&&&&&&&&&}\only<6->{11 & $\infty|-$ & $\infty|-$ & $15|11$ &  $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{red!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 9, 7} \\\hline 
+\only<-6>{&&&&&&&&&}\only<7->{9 & $\infty|-$ & $14|9$ & $15|11$ & \cellcolor{red!30} $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{gray!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 4, 7} \\\hline 
+\only<-7>{\phantom{4} & \phantom{$20|4$} & \phantom{$14|9$} & \phantom{$15|11$} & \phantom{$10|10$} & \phantom{$5|9$} & \phantom{$9|12$} & \phantom{$4|9$} & \phantom{$0|-$} & \phantom{7, 2}}\only<8->{4 & $20|4$ & \cellcolor{red!30} $14|9$ & $15|11$ & \cellcolor{gray!30} $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{gray!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 7, 2} \\\hline 
+\only<-8>{&&&&&&&&&}\only<9->{7 & $19|7$ & \cellcolor{gray!30} $14|9$ & \cellcolor{red!30} $15|11$ & \cellcolor{gray!30} $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{gray!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ & 2 } \\\hline 
+\only<-9>{&&&&&&&&&}\only<10->{2 & \cellcolor{red!30} $19|7$  & \cellcolor{gray!30} $14|9$ & \cellcolor{gray!30} $15|11$ & \cellcolor{gray!30} $10|10$ & \cellcolor{gray!30} $5|9$ & \cellcolor{gray!30} $9|12$ & \cellcolor{gray!30} $4|9$ & \cellcolor{gray!30} $0|-$ &} \\
+\end{tabular}
+}
+::::
+
+:::: {.column width=30%}
+\resizebox{\textwidth}{!}{
+\begin{tikzpicture}[
+  graph vertex/.style={draw, circle, minimum size=0.55cm, inner sep =0pt},
+  edge label/.style={inner sep=0pt, circle, fill=white},
+  marked/.style={fill=blue!40},
+  marked on/.style={alt=####1{marked}{}},
+  active/.style={fill=red!40},
+  active on/.style={alt=####1{active}{}},
+  toilet/.style={fill=teal!30},
+  start/.style={draw=red, thick},
+  start on/.style={alt=####1{start}{}},
+]
+\node[graph vertex, toilet, marked on=<10->, active on=<10>] (v2) at (2.50, 5.00) {2};
+\node[graph vertex, marked on=<9->, active on=<9>] (v4) at (4.00, 4.15) {4};
+\node[graph vertex, marked on=<8->, active on=<8>] (v7) at (2.80, 3.00) {7};
+\node[graph vertex, marked on=<7->, active on=<7>] (v9) at (4.00, 2.55) {9};
+\node[graph vertex, marked on=<5->, active on=<5>] (v10) at (5.50, 2.20) {10};
+\node[graph vertex, marked on=<6->, active on=<6>] (v11) at (2.90, 1.50) {11};
+\node[graph vertex, marked on=<4->, active on=<4>] (v12) at (4.20, 1.1) {12};
+\node[graph vertex, start on=<1>, marked on=<3->, active on=<3>] (v13) at (5.50, .80) {13};
+
+\graph[edge quotes mid] {
+  (v2) --["6" edge label] (v4),
+  (v4) --["4" edge label] (v9),
+  (v2) --["4" edge label] (v7),
+  (v7) --["5" edge label] (v9),
+  (v7) --["6" edge label] (v11),
+  (v9) --["8" edge label] (v11),
+  (v9) --["5" edge label] (v10),
+  (v10) --["9" edge label] (v11),
+  (v11) --["5" edge label] (v12),
+  (v12) --["4" edge label] (v13),
+  (v10) --["5" edge label] (v13),
+};
+\end{tikzpicture}
+}
+::::
+:::
+
+## Einen Schritt zurück: Breitensuche implementieren
+
+::: {.columns}
+:::: {.column width=50%}
+![](BFS/img/idea-bfs-alpha.png)
+::::
+
+:::: {.column width=50%}
+\pause
+\resizebox{\textwidth}{!}{
+\begin{tikzpicture}
+  \node at (-2.25, 4.5) {\textbf{Knotenfeld}};
+  \node at (.5, 4.5) {\textbf{Markierungen}};
+
+  \node[anchor=south west, minimum size=1cm, fill=gray!30] at (-3, 0) {};
+
+  \foreach \y in {0,...,3} {
+    \node[anchor=south west, minimum size=1cm, draw] at (-3, \y) {};
+  }
+
+  \foreach \y in {0,...,3} {
+    \node at (-1.75, 3.5 - \y) {\textbf \y};
+  }
+
+  \begin{object}[text width=3cm]{v1: Knoten}{-5.15, 4.5}
+    \attribute{name = "v1"}
+  \end{object}
+  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 3.5) {};
+  \draw[-Triangle, thick] (-2.5, 3.5) -- (-3.5, 4);
+
+  \begin{object}[text width=3cm]{v2: Knoten}{-5.15, 3}
+    \attribute{name = "v2"}
+  \end{object}
+  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 2.5) {};
+  \draw[-Triangle, thick] (-2.5, 2.5) -- (-3.5, 2.5);
+
+  \begin{object}[text width=3cm]{v3: Knoten}{-5.15, 1.5}
+    \attribute{name = "v3"}
+  \end{object}
+  \node[draw, circle, fill, inner sep=1pt] at (-2.5, 1.5) {};
+  \draw[-Triangle, thick] (-2.5, 1.5) -- (-3.5, 1);
+
+  \node[] at (-5.8, -0.25) {\textbf{anzKnoten = 3}};
+
+  \foreach \y in {0,...,3} {
+    \node at (-0.25, 3.5 - \y) {\textbf \y};
+  }
+
+  \node[anchor=south west, minimum size=1cm, fill=gray!30] at (0, 0) {};
+  \foreach \y in {0,...,3} {
+    \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {};
+  }
+
+  \draw[Triangle-Triangle, thick, dashed] (-1.6, 3.5) -- (-0.4, 3.5);
+  \node at (-1.75, 3.5) {\boldred{0}};
+  \node at (-0.25, 3.5) {\textbf{\textcolor{magenta}{0}}};
+\end{tikzpicture}
+}
+::::
+:::
+
+
+## \faIcon{desktop} Arbeitsauftrag: Breitensuche implementieren - 15min
+
+Logge dich in der Online-IDE [https://online-ide.de](https://online-ide.de) ein und öffne das Projekt **Breitensuche**.
+
+1. Implementiere die ersten beiden Schritte der Breitensuche
+2. Implementiere das Einfügen und Markieren aller \underline{unmarkierter Nachbarknoten}
+3. Implementiere eine Methode die prüft, ob der Graph zusammenhängend ist.
+
+## Biber Wettbewerb
+
+::: {.columns align=center}
+:::: {.column width=50%}
+1. Einloggen unter [https://ib.bwinf.de](https://ib.bwinf.de)
+2. (Team-Mitglieder einloggen)
+3. **Wir starten gemeinsam**!!
+::::
+
+:::: {.column width=50%}
+![](img/biber.png)
+::::
+:::