path: root/Info/11/MUG_SWG_SG/1/Pfade/slides.md

---
header-includes: |
    \usepackage{booktabs}
    \newcommand{\graph}{
      \begin{tikzpicture}
      \node[fill=red, circle, minimum size=0.2cm] (ts) {};
      \node[above=0.1cm of ts] {Traunstein};
      
      \node[fill=red, circle, minimum size=0.2cm] (ib) at (-2, -1) {};
      \node[xshift=-0.3cm, above=0.1cm of ib] {Innsbruck};
      
      \node[fill=red, circle, minimum size=0.2cm] (ms) at (1, -2) {};
      \node[right=0.1cm of ms] {Millstadt};
      
      \draw (ts) -- node[fill=yellow!30] {138} (ib);
      \draw (ts) -- node[fill=yellow!30] {211} (ms);
      
      \node[fill=red, circle, minimum size=0.2cm] (ic) at (-1, -2.5) {};
      \node[left=0cm of ic, yshift=-0.2cm] {Innichen};
      
      \draw (ib) -- node[fill=yellow!30] {139} (ic);
      \draw (ms) -- node[fill=yellow!30] {120} (ic);
      
      \node[fill=red, circle, minimum size=0.2cm] (vd) at (0, -4) {};
      \node[right=0.1cm of vd] {Venedig};
      \draw (ic) -- node[fill=yellow!30] {197} (vd);
      \draw (ms) -- node[fill=yellow!30] {278} (vd);
      \end{tikzpicture}
    }
---

## Wdh - Sortieren {.standout}

Sortieren

## Wdh - Sortieren

Beschreibe einen Algorithmus damit ich 5 Spielkarten der Größe nach sortieren kann.

\pause
### Algorithmen (Auswahl)

- Insertionsort - [wikipedia.org/wiki/Insertionsort](https://de.wikipedia.org/wiki/Insertionsort)
- Selectionsort - [wikipedia.org/wiki/Selectionsort](https://de.wikipedia.org/wiki/Selectionsort)
- [Simplesort]{.underline} - [wikipedia.org/wiki/Simplesort](https://de.wikipedia.org/wiki/Simplesort)
- Bubblesort - [wikipedia.org/wiki/Bubblesort](https://de.wikipedia.org/wiki/Bubblesort)
- Mergesort - [wikipedia.org/wiki/Mergesort](https://de.wikipedia.org/wiki/Mergesort)
- Quicksort - [wikipedia.org/wiki/Quicksort](https://de.wikipedia.org/wiki/Quicksort)
- Bogosort - [wikipedia.org/wiki/Bogosort](https://de.wikipedia.org/wiki/Bogosort)
- ...  - [wikipedia.org/wiki/Sortierverfahren](https://de.wikipedia.org/wiki/Sortierverfahren)

## Wdh - Simplesort

Vereinfachung des Selectionsorts.

\pause
### **Algortihmus**

```
Wiederhole für jeden Index → zielIndex
  // KOMMENTAR: Suche kleinere Elemente im nachfolgenden, noch unsortieren Bereich:
  Wiederhole für jeden größeren Index → pruefIndex
    Falls Eintrag an preufIndex < Eintrag an zielIndex
      Vertausche Eintrag an pruefIndex mit dem Eintrag an zielIndex
```

\pause
### \faIcon{desktop} Arbeitsauftrag - Simplesort in `Snap!`

Implementiere den Simplesort Algorithmus in einer Snap! Methode

## \faIcon{chalkboard-teacher} Lösung - Simplesort in `Snap!`

![](img/simplesort_snap.png){.center height=85%}

## Radtour nach Venedig

::: columns
:::: {.column width=50%}
Für die kommenden Sommerferien plant ihr eine Radtour durch die Alpen nach \boldred{Venedig}.
\vspace{1cm}

\pause

Als Startpunkt habt ihr euch \boldred{Traunstein} ausgesucht.
::::

:::: {.column width=50%}
\graph
::::
:::

## Radtour nach Venedig

::: columns
:::: {.column width=50%}
\vspace{2cm}
Wie finden wir den kürzesten Weg von Traunstein nach Venedig?
::::

:::: {.column width=50%}
\graph
::::
:::

## Dijkstra Algortihmus

Eine Möglichkeit \boldred{effizient} den kürzesten Weg zwischen zwei Punkten zu finden ist der Algorithmus des niederländischen Informatikers Dijkstra.

Dazu benötigen wir zu erst eine Tabelle aller Orte mit den vier Spalten:  
**Ort, kommt von, Distanz zum Start, bearbeitet**

::: columns
:::: {.column width=60%}
\begin{tabular}{l | l | l | l}
Ort & kommt von & Distanz zum Start & bearbeitet \\
\toprule
Traunstein & & 0 & \\
\hline
Innsbruck & & $\infty$ & \\
\hline
Innichen & & $\infty$ & \\
\hline
Millstatt & & $\infty$ & \\
\hline
Venedig & & $\infty$ & \\
\end{tabular}
::::

:::: {.column width=40%}
\hspace{0.3cm} \scalebox{0.8}{\graph}
::::
:::


## Dijkstra Algortihmus Start

Zuerst tragen wir alle benachbarten Orte vom Start und ihre Distanzen ein und vermerken den Start als \textbf{bearbeitet}.

::: columns
:::: {.column width=60%}
\begin{tabularx}{\textwidth}{X | X | X | X}
Ort & kommt von & Distanz zum Start & bearbeitet \\
\toprule
Traunstein & & 0 & \cellcolor{green!20} X \\
\hline
\rowcolor{blue!10} Innsbruck & Traunstein & 138 & \\
\hline
Innichen & & $\infty$ & \\
\hline
\rowcolor{blue!10} Millstatt & Traunstein & 211 & \\
\hline
Venedig & & $\infty$ & \\
\end{tabularx}
::::

:::: {.column width=40%}
\hspace{0.3cm} \scalebox{0.8}{\graph}
::::
:::

## Dijkstra Algortihmus Fortsetzung

Wir wählen den \boldred{nicht bearbeiteten} Ort mit der \boldred{kürzesten} Distanz zum Start.  

\only<1>{\phantom{Setzen in auf \textbf{bearbeitet}.}}
\only<2->{Setzen in auf \textbf{bearbeitet}.}

\only<-2>{\phantom{Von dem gewählten Ort bestimmen wir alle Distanzen zum Start und aktualisieren Einträge für die wir einen kürzeren Weg gefunden haben.}}
\only<3->{Von dem gewählten Ort bestimmen wir alle Distanzen zum Start und aktualisieren Einträge für die wir einen kürzeren Weg gefunden haben.}

::: columns
:::: {.column width=60%}
\only<-5>{
\begin{tabularx}{\textwidth}{X | X | X | X}
Ort & kommt von & Distanz zum Start & bearbeitet \\
\toprule
Traunstein & & 0 & X \\
\hline
\rowcolor{red!20} Innsbruck & Traunstein & 138 & \only<2->{\cellcolor{green!20}} \only<2->{X} \only<-2>{\\ \hline}
\only<3->{\\ \hline \rowcolor{blue!10}} Innichen & \only<4->{Innsbruck} & \only<-3>{$\infty$}\only<4->{277} & \\
\hline
Millstatt & Traunstein & 211 & \\
\hline
Venedig & & $\infty$ & \\
\end{tabularx}
}
\only<6-8>{
\begin{tabularx}{\textwidth}{X | X | X | X}
Ort & kommt von & Distanz zum Start & bearbeitet \\
\toprule
Traunstein & & 0 & X \\
\hline
Innsbruck & Traunstein & 138 & X \\
\hline
Innichen & Innsbruck & \only<-3>{$\infty$}\only<4->{277} & \\
\hline
\rowcolor{red!20} Millstatt & Traunstein & 211 & \only<7->{\cellcolor{green!20}} \only<7->{X} \only<-7>{\\ \hline}
\only<8->{\\ \hline \rowcolor{blue!10}} Venedig & \only<8->{Millstadt} & \only<-7>{$\infty$}\only<8>{498} & \\
\end{tabularx}
}
\only<9-10>{
\begin{tabularx}{\textwidth}{X | X | X | X}
Ort & kommt von & Distanz zum Start & bearbeitet \\
\toprule
Traunstein & & 0 & X \\
\hline
Innsbruck & Traunstein & 138 & X \\
\hline
\rowcolor{red!20} Innichen & Innsbruck & 277 & \only<7->{\cellcolor{green!20} X} \\
\hline
Millstatt & Traunstein & 211 & X \only<-9>{\\ \hline}
\only<10->{\\ \hline \rowcolor{blue!10}} Venedig & \only<9->{Innichen} & \only<-9>{498}\only<10>{\textbf{474}} & \\
\end{tabularx}
}
\only<11->{
\begin{tabularx}{\textwidth}{X | X | X | X}
Ort & kommt von & Distanz zum Start & bearbeitet \\
\toprule
Traunstein & & 0 & X \\
\hline
Innsbruck & Traunstein & 138 & X \\
\hline
Innichen & Innsbruck & 277 & X \\
\hline
Millstatt & Traunstein & 211 & X \\
\hline
\rowcolor{red!20} Venedig & Innichen & 474 & \only<11->{\cellcolor{green!20} X}\\
\end{tabularx}
}
::::

:::: {.column width=40%}
\hspace{0.3cm} \scalebox{0.8}{\graph}
::::
:::

## Dijkstra Algortihmus Ende

Der kürzeste Weg zu einem Ort wurde gefunden sobald dieser als bearbeitet markiert ist.
\begin{tabularx}{\textwidth}{X | X | X | X}
Ort & kommt von & Distanz zum Start & bearbeitet \\
\toprule
Traunstein & & 0 & X \\
\hline
Innsbruck & Traunstein & 138 & X \\
\hline
Innichen & Innsbruck & 277 & X \\
\hline
Millstatt & Traunstein & 211 & X \\
\hline
\rowcolor{red!20} Venedig & Innichen & 474 & X\\
\end{tabularx}

Der Weg nach Venedig lässt sich aus der Tabelle ablesen:  
**Venedig < Innichen < Innsbruck < Traunstein**

## \faIcon{pencil-alt} Arbeitsauftrag - Dijkstra

::: columns
:::: {.column width=70%}
\begin{enumerate}[a)]
\item Ermittle alle möglichen Wege von A nach D mit ihren Längen.
\item Ermittle den kürzesten Weg von A nach D mit dem Dijkstra-Algortihmus.
\item Vergleiche den Aufwand von \textbf{a)} und \textbf{b)}. Warum wird der Dijkstra-Algortihmus erst bei vielen Knoten überlegen sein?
\end{enumerate}
::::

:::: {.column width=30%}
\begin{tikzpicture}
\node[circle, fill=blue!10] (a) {A};
\node[circle, fill=blue!10, yshift=1cm, right=1cm of a] (b) {B};
\node[circle, fill=blue!10, right=2cm of a] (d) {D};
\node[circle, fill=blue!10, yshift=-1cm, right=1cm of a] (c) {C};

\draw (a) -- node[fill=bg] {3} (b);
\draw (b) -- node[fill=bg] {2} (d);
\draw (d) -- node[fill=bg] {5} (c);
\draw (c) -- node[fill=bg] {1} (a);
\draw (c) -- node[fill=bg, above] {3} (b);
\draw (a) -- node[fill=bg] {7} (d);
\end{tikzpicture}
::::
:::