add missing traverse exercise

1 files changed, 126 insertions, 0 deletions

diff --git a/Info/11/NTG/1/Aufgaben/traversierung.tex b/Info/11/NTG/1/Aufgaben/traversierung.tex
new file mode 100644
index 00000000..e06ec87b
--- /dev/null
+++ b/Info/11/NTG/1/Aufgaben/traversierung.tex
@@ -0,0 +1,126 @@
+\renewcommand{\Verteilung}{6 + 3}% + 4}
+\begin{Aufg}[Traversierung von Graphen]
+\vspace{-1.15cm}
+\begin{enumerate}[a)]
+\item Führe den Dijkstra-Algorithmus mit Hilfe der Tabelle durch und bestimme den kürzesten Pfad und dessen Länge vom Startknoten zum Knoten F. \\[0.3cm]
+\iflehrer{}{
+\begin{tabular}{p{0.6\textwidth} p{0.4\textwidth}}
+\vspace{-5cm}
+\begin{tabular}{c | c | c | c | c | c | c | c}
+akt. & A & B & C & D & E & F & WS \\
+\hline
+- & $\infty$ & 0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & B \\
+\hline
+\solution{B} & \solution{2} & & \solution{3} & & \solution{5} & \solution{9} & \solution{A,C,E,F \PointSymbol} \\
+\hline
+\solution{A} & & & & & & & \solution{C,E,F \HalfpointSymbol} \\
+\hline
+\solution{C} & & & & \solution{4\HalfpointSymbol} & & & \solution{D,E,F \HalfpointSymbol} \\
+\hline
+\solution{D} & & & & & & \solution{7\HalfpointSymbol} & \solution{E,F \HalfpointSymbol} \\
+\hline
+\solution{E} & & & & & & & \solution{F \HalfpointSymbol} \\
+\hline
+\solution{F} & & & & & & & \solution{\HalfpointSymbol} \\
+\hline
+\end{tabular}
+&
+\begin{tikzpicture}[node/.style={draw, circle, inner sep=1pt, minimum size=0.7cm}]
+  \node[node] (a) {A};
+  \node[node, above=of a] (b) {B};
+  \node[node, left=of b] (c) {C};
+  \node[node, above=of c] (d) {D};
+  \node[node, right=of b] (e) {E};
+  \node[node, above=2cm of b] (f) {F};
+
+  \draw (a) edge node[right] {2} (b);
+  \draw (b) edge node[above] {3} (c);
+  \draw (b) edge node[above] {5} (e);
+  \draw (e) edge node[right] {7} (f);
+  \draw (c) edge node[left] {1} (d);
+  \draw (d) edge node[above] {3} (f);
+  \draw (b) edge node[right] {9} (f);
+\end{tikzpicture}
+\\
+\end{tabular} \\[0.1cm]
+\liniert{1}
+}
+\item Beschreibe knapp den Unterschied zwischen den Warteschlangen der Breitensuche und des Dijkstra-Algorithmus und deren Auswirkungen auf die Besuchsreihenfolge der Knoten.
+\iflehrer{}{\\[0.2cm] \kariert{16}}
+% \item In der folgenden unvollständigen Implementierung des Dijkstra-Algorithmus haben sich Fehler eingeschlichen. Gib die entsprechende Zeilennummern an und beschreibe die Fehler.
+% \begin{minted}[linenos, baselinestretch=1.2, fontsize=\small]{java}
+% int[] dijkstra(int start) {
+  % int[] distanzen; boolean[] besucht;
+  % // Die Distanzen und das besucht Feld wurden entsprechend initialisiert
+  % while(naechsterKnoten(distanzen, besucht) != -1) {
+    % int aktuellerKnoten = naechsterKnoten(distanzen, besucht);
+    % for (int i = 0; i < anzKnoten; i++) {
+      % if (adjazenzmatrix[aktuellerKnoten][i] == -1) {
+        % // Aktualisiere die Distanz aller Nachbarknoten
+        % int kantenGewicht = adjazenzmatrix[i][aktuellerKnoten];
+        % distanzen[i] = distanzen[aktuellerKnoten] + kantenGewicht;
+      % }
+    % }
+  % }
+  % return distanzen;
+% }
+% \end{minted}
+% \iflehrer{}{\kariert{18}}
+\end{enumerate}
+\end{Aufg}
+
+\begin{Lsg}
+\begin{enumerate}[a)]
+\item 
+\begin{tabular}{p{0.6\textwidth} p{0.4\textwidth}}
+\vspace{-3cm}
+\begin{tabular}{c | c | c | c | c | c | c | c}
+akt. & A & B & C & D & E & F & WS \\
+\hline
+- & $\infty$ & 0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & B \\
+\hline
+B & 2 & & 3 & & 5 & 9 & A,C,E,F \Point \\
+\hline
+A & & & & & & & C,E,F \Halfpoint \\
+\hline
+C & & & & 4 & & & D,E,F \Point \\
+\hline
+D & & & & & & 7 & E,F \Point \\
+\hline
+E & & & & & & & F \Halfpoint \\
+\hline
+F & & & & & & & \Halfpoint \\
+\hline
+\end{tabular}
+&
+\begin{tikzpicture}[node/.style={draw, circle, inner sep=1pt, minimum size=0.7cm}]
+  \node[node] (a) {A};
+  \node[node, above=of a] (b) {B};
+  \node[node, left=of b] (c) {C};
+  \node[node, above=of c] (d) {D};
+  \node[node, right=of b] (e) {E};
+  \node[node, above=2cm of b] (f) {F};
+
+  \draw (a) edge node[right] {2} (b);
+  \draw (b) edge node[above] {3} (c);
+  \draw (b) edge node[above] {5} (e);
+  \draw (e) edge node[right] {7} (f);
+  \draw (c) edge node[left] {1} (d);
+  \draw (d) edge node[above] {3} (f);
+  \draw (b) edge node[right] {9} (f);
+\end{tikzpicture}
+\\
+\end{tabular} \\[0.1cm]
+B/C/D/F\Point; 7\Halfpoint
+\item Die Warteschlange der Breitensuche verwaltet die Knoten nach ihrer Einfügereihenfolge,\Halfpoint die des Dijkstra-Algorithmus nach ihrer Distanz zum Startknoten.\Halfpoint
+Deshalb werden die Knoten in der Breitensuche in Ebenen (Anzahl der Kanten zum Startknoten), ausgehend vom Startknoten besucht. \Point
+Wohingegen der Dijkstra-Algorithmus immer den Knoten mit der kürzesten Distanz zum Startknoten besucht.\Point
+% \item
+  % \begin{itemize}
+  % \item Nach Zeile 6:\Halfpoint Der aktuelle Knoten muss als besucht vermerkt werden.\Halfpoint
+  % \item Zeile 8:\Halfpoint Die Bedingung müsste \texttt{!=} sein, um alle Nachbarknoten zu betrachten.\Halfpoint
+  % \item Zeile 10:\Halfpoint Die Indices für das Kantengewicht der ausgehenden Kante sind vertauscht.\Halfpoint
+  % \item Zeile 11:\Halfpoint Die Distanz darf nur aktualisiert werden, wenn sie kleiner als die aktuell gespeicherte ist.\Halfpoint
+  % \end{itemize}
+\end{enumerate}
+\end{Lsg}