---
header-includes: |
    \usepackage{ulem}
    \usetikzlibrary{graphs}
    \usetikzlibrary{overlay-beamer-styles}
---

## {.standout}
Herzlich Willkommen!

Du kannst dich schon anmelden

\texttt{vorname.nachname}

und den Bildschirm ausschalten.

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Ungerichtete Graphen \hfill{} 1/3 {.t}

::: {.columns}
:::: {.column width=50%}
### Diskutiert die Aussage:

\vspace{0.1cm}

> Ungerichtete Graphen sind doch Quatsch in der Realität hat alles immer eine Richtung, oder eben zwei.
::::

:::: {.column width=50%}
![](img/Copyrighted/street.png){.center height=40%}
::::
:::

\pause

Die Kanten eines **ungerichteter** Graphens haben nicht **keine** Richtung, sondern sind in **beide** Richtungen gleich.

\pause
::: {.columns}
:::: {.column width=50%}
```{.graphviz dpi=150 height=2.8cm}
graph {
  bgcolor=transparent
  layout=circo
  node [shape=circle]
  nodesep=0.5
  v1 -- v2
  v2 -- v3
}
```
::::

:::: {.column width=50%}
```{.graphviz dpi=150 height=2.8cm}
digraph {
  bgcolor=transparent
  layout=circo
  node [shape=circle]
  nodesep=0.5
  v1 -> v2 [label=7]
  v2 -> v1 [label=7]
  v2 -> v3 [label=3]
  v3 -> v2 [label=3]
}
```
::::
:::

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Wieso Algorithmus? \hfill{} 2/3

### Diskutiert die Aussage:

\vspace{0.2cm}

> Ich muss mir keinen komplizierten Algorithmus merken, ich sehe doch gleich ob ein Graph zusammenhängend ist oder nicht.

::: {.columns align=center}
:::: {.column width=50%}
\pause
![](img/huge_labyrinth.png){.center height=65%}
::::

:::: {.column width=50%}
\pause
Bei sehr großen Graphen scheitern wir Menschen.
Der Computer hingegen kann sehr große Probleme lösen aber braucht ein festes Vorgehen, einen **Algorithmus**.
::::
:::

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Algorithmus \hfill{} 3/3

### Diskutiert die Aussage:

\vspace{0.3cm}

> Toll, aber wenn ich irgendwas farblich markiere auf meinem Blatt kann, dass der Computer ja nicht einfach so machen.

\pause

Sicher, aber der Computer kann die Information abspeichern.

## Manfred ist auf einer Labyrinthbesichtigung

\begin{tikzpicture}
\node {\includegraphics[keepaspectratio, width=\textwidth]{img/laboscout.png}};
\node at (-5, 0) {\includegraphics[keepaspectratio, height=\textheight]{img/manfred_cut_out.png}};
\end{tikzpicture}

## \faIcon{pencil-alt} Arbeitsauftrag: Manfred sucht den Ausgang

\begin{tikzpicture}
\node at (0, 0) {\includegraphics[keepaspectratio, height=\textheight]{img/manfred_cut_out.png}};
\node[scale=1.5] at (3, 2.5) {\bfseries\Large ?\Huge ?\Large ?};
\node at (8, 0.5) {\includegraphics[keepaspectratio, width=6cm]{img/labyrinth.png}};
\end{tikzpicture}

## \faIcon{desktop} Arbeitsauftrag: Visualisierung der Breitensuche \hfill 5 min

Öffne die Visualisierung der Breitensuche und lasse sie einmal durch klicken auf den Playknopf ablaufen.

::: {.columns align=center}
:::: {.column width=60%}
`\centering`{=latex}
[**https://bycs.link/HMEG2U**](https://bycs.link/HMEG2U)
::::

:::: {.column width=40%}
![](img/bfs-visualisierung-qrcode.png){.center width=4cm}
::::
:::

### Achte dabei auf folgende Fragen:

1. Wann wird ein Knoten in die Warteschlange aufgenommen?
2. Wann wird ein Knoten aus der Warteschlange entfernt?

## \faIcon{desktop} Arbeitsauftrag: Ordne den Pseudocode \hfill 5min

::: {.columns align=center}
:::: {.column width=60%}
Öffne die Webseite

\vspace{0.5cm}
[**https://schule.muhq.space/bfs**](https://schule.muhq.space/bfs)

\vspace{0.5cm}
und bringe die einzelnen Schritte der Breitensuche in die richtige Reihenfolge.
::::

:::: {.column width=40%}
![](img/bfs-pseudocode-qrcode.png){.center width=4cm}
::::
:::


## \faIcon{pencil-alt} Arbeitsauftrag: Breitensuche made by IDEA

\begin{tikzpicture}
\node {\includegraphics[keepaspectratio, height=0.9\textheight]{img/idea-bfs-alpha.png}};
\node[text width=7cm] at (4, -1) {Kommentiere die einzelnen Schritte der graphische Darstellung der Breitensuche.};
\end{tikzpicture}


## \faIcon{comment} Arbeitsauftrag: Breitensuche für den Computer{.t}

Der Computer hat mit unserem menschlichen Vorgehen noch Probleme, denn er sieht nicht wie wir den ganzen Graphen auf einmal:
\vspace{0.3cm}

\pause
> Wie kann sich der Computer merken welche Knoten markiert sind?

\pause
### Lösungen \faIcon[regular]{lightbulb}

> * Ein neues Attribut `markiert` der Klasse `Knoten`
> * oder ein neues Array um die Markierungen zu speichern

::: {.columns align=center}
:::: {.column width=40%}
\only<3->{
\begin{tikzpicture}
 \begin{object}[text width=4cm]{Knoten}{0,0}
  \attribute{String bezeichnung}
  \attribute{boolean markiert}
 \end{object}
\end{tikzpicture}
}
::::

:::: {.column width=50%}
\only<4->{
\resizebox{\textwidth}{!}{
\begin{tikzpicture}
  \node at (-3.5, 5) {\textbf{Knotenarray}};
  \node at (.5, 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=4.7cm]{hbf: Knoten}{-6, 4.5}
    \attribute{name = "Hauptbahnhof"}
  \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=4.7cm]{ww: Knoten}{-6, 3}
    \attribute{name = "Wöhrder Wiese"}
  \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=4.7cm]{rp: Knoten}{-6, 1.5}
    \attribute{name = "Rathenauplatz"}
  \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{comment} Arbeitsauftrag: Breitensuche für den Computer{.t}

> Wie kann der Computer sicherstellen, dass die Knoten in der richtigen Reihenfolge markiert werden?

\pause

Wir brauchen eine \boldred{Warteschlange} der zu bearbeitenden Knoten!

### \faIcon[regular]{lightbulb} Arten von Warteschlangen
\vspace{0.1cm}

::: {.columns align=center}
:::: {.column width=50%}
\pause
**Warteschlange**

\pause
![](img/Copyrighted/people-queue.png){.center width=80%}

\pause
"Hinten rein, vorne raus" (FIFO)
::::

:::: {.column width=50%}
\pause
**Stapel**

\pause
![](img/Copyrighted/book-stack.png){.center height=25%}

\pause
"Oben drauf, oben runter" (LIFO)
::::
:::

## \faIcon{pencil-alt}\faIcon{hands-helping} Arbeitsauftrag: Münchner S-Bahn Netz.

::: {.columns align=center}
:::: {.column width=50%}
Ermittelt wie viele Stationen auf dem Weg mindestens erreicht werden.
Eine Person führt die Suche durch die andere kontrolliert und stoppt bei Fehlern.
\vspace{0.1cm}

1. Sendlinger Tor $\rightarrow$ Innsbrucker Ring
2. Sendlinger Tor $\rightarrow$ Moosach
::::

:::: {.column width=50%}
![](img/Copyrighted/Corneslen_S22_A2_graph.png)
::::
:::