add tomorrow's test for 11b

3 files changed, 130 insertions, 2 deletions

diff --git a/Info/11/NTG/1/Aufgaben/adjazenzmatrix.tex b/Info/11/NTG/1/Aufgaben/adjazenzmatrix.tex
new file mode 100644
index 00000000..e458c40e
--- /dev/null
+++ b/Info/11/NTG/1/Aufgaben/adjazenzmatrix.tex
@@ -0,0 +1,91 @@
+\renewcommand{\Verteilung}{2 + 3 + 3}
+\begin{Aufg}[Adjazenzmatrix]
+\iflehrer{}{\vspace{-1cm}}
+\begin{enumerate}[a)]
+\item Vervollständige die Adjazenzmatrix zu folgendem Graphen. \\
+  \begin{tabularx}{\textwidth}{X X}
+  \vspace{0pt}
+  \begin{tikzpicture}[node/.style={circle, thick, draw, inner sep=1pt}]
+    \node[node] (v1) at (3,2) {V1};
+    \node[node] (v2) at (0,2) {V2};
+    \node[node] (v3) at (-1,1) {V3};
+    \node[node] (v4) at (1,0) {V4};
+    \node[node] (v5) at (-1,-1) {V5};
+
+    \draw[-] (v1) -- (v2);
+    \draw[-] (v1) -- (v4);
+    \draw[-] (v2) -- (v3);
+    \draw[-] (v3) -- (v4);
+    \draw[-Triangle] (v2) -- (v4);
+  \end{tikzpicture} &
+  \vspace{0pt}
+  \iflehrer{
+  \begin{tabular}{c | c | c | c | c | c |}
+  & v1 & v2 & v3 & v4 & v5 \\ \hline
+  v1 & & 1 & & & \\ \hline
+  v2 & 1 &  & 1 & 1 & \\ \hline
+  v3 & & 1 & & & \\ \hline
+  v4 & 1 & & 1 & & \\ \hline
+  v5 & & & & & \\ \hline
+  \end{tabular}
+  }{
+  \begin{tabular}{c | c | c | c | c | c |}
+  & v1 & v2 & v3 & v4 & v5 \\ \hline
+  v1 & & & & & \\ \hline
+  v2 & & & & & \\ \hline
+  v3 & & & & & \\ \hline
+  v4 & & & & & \\ \hline
+  v5 & & & & & \\ \hline
+  \end{tabular}
+  }
+ \\
+  \end{tabularx}
+\iflehrer{}{\vspace{2cm}}
+\item Zeichne den zur folgenden Adjazenzmatrix zugehörigen Graphen. \\
+  \begin{tabularx}{\textwidth}{X X}
+  \vspace{0pt}
+  \iflehrer{
+  \begin{tikzpicture}[node/.style={circle, thick, draw, inner sep=1pt}]
+    \node[node] (v1) at (3,2) {V1};
+    \node[node] (v2) at (0,2) {V2};
+    \node[node] (v3) at (-1,-1) {V3};
+    \node[node] (v4) at (-2,2) {V4};
+    
+    \draw (v1) edge[above] node {3} (v2);
+    \draw[-Triangle] (v2) edge[left, bend right] node {1} (v3);
+    \draw[-Triangle] (v3) edge[below] node {1} (v1);
+    \draw[-Triangle] (v3) edge[right, bend right] node {2} (v2);
+    \draw[-Triangle] (v4) edge[above] node {7} (v2);
+  \end{tikzpicture}
+  }{\vspace{4cm}} &
+  \vspace{0pt}
+  \begin{tabular}{c | c | c | c | c | }
+  & v1 & v2 & v3 & v4 \\ \hline
+  v1 & & 3 & & \\ \hline
+  v2 & 3 & & 1 & \\ \hline
+  v3 & 1 & 2 & & \\ \hline
+  v4 & & 7 & & \\ \hline
+  \end{tabular}
+ \\
+  \end{tabularx}
+  \iflehrer{}{\newpage}
+  \item Nimm Stellung zu den folgenden Aussagen.
+  \begin{enumerate}[1)]
+    \item Der Graph aus Teilaufgabe a) ist ungerichtet.
+    \item Jeder vollständige Graph ist auch zusammenhängend.
+    \item Es gibt keinen Knoten im Graphen aus Teilaufgabe b), von dem ausgehend die Breitensuche alle Knoten besucht.
+  \end{enumerate}
+\end{enumerate}
+\end{Aufg}
+
+\begin{Lsg}
+\begin{enumerate}[a)]
+\item \BE{2} Abzug bei Fehlern
+\item \BE{3}. 0.5 BE pro Kante
+\item \begin{itemize}
+  \item Falsch.\Halfpoint Die Kante von v2 zu v4 ist gerichtet und somit ist der Graph gerichtet.\Halfpoint.
+  \item Korrekt.\Halfpoint In einem vollständiger Graph existiert eine Kante von jedem Knoten zu jedem anderen.\Halfpoint
+  \item Falsch.\Halfpoint Beginnend von v4 werden alle Knoten besucht.\Halfpoint
+\end{itemize}
+\end{enumerate}
+\end{Lsg}
diff --git a/Info/11/NTG/1/Aufgaben/tiefensuche.tex b/Info/11/NTG/1/Aufgaben/tiefensuche.tex
new file mode 100644
index 00000000..e9bc4a6c
--- /dev/null
+++ b/Info/11/NTG/1/Aufgaben/tiefensuche.tex
@@ -0,0 +1,36 @@
+\begin{Aufg}[Tiefensuche]
+\noindent{}\begin{tabular}{p{0.68\textwidth} p{0.32\textwidth}}
+Gibt die Besuchsreihenfolge des folgenden Graphens ausgehend von Knoten A an.
+Zur Traversierung wird eine abgewandelte Breitensuche verwendet, bei der die Warteschlange wie ein Bücherstapel funktioniert.
+Der zuletzt eingefügte Knoten wird als erstes wieder behandelt.
+\textit{(Nachbarknoten werden aufsteigend nach alphabetischer Reihenfolge in die Warteschlange eingefügt.)}
+&
+\vspace{0cm}
+\begin{tikzpicture}[node/.style={circle, thick, draw, inner sep=1pt}]
+    \node[node] (f) at (0, 2) {F};
+    \node[node, thick] (a) at (1,1) {A};
+    \node[node] (b) at (3,1) {B};
+    \node[node] (c) at (1,-1) {C};
+    \node[node] (d) at (3,-1) {D};
+    \node[node] (e) at (4, 0) {E};
+    \node[node] (g) at (0, -2) {G};
+
+    \draw[-Triangle] (f) -- (a);
+    \draw[-Triangle] (a) -- (b);
+    \draw[-Triangle] (b) -- (d);
+    \draw[-Triangle] (a) -- (c);
+    \draw[-Triangle] (c) -- (g);
+    \draw[-Triangle] (d) -- (c);
+    \draw[-Triangle] (d) -- (e);
+    \draw[-Triangle] (e) -- (b);
+
+    % \node[draw, label={[anchor=west]west:Warteschlange}, minimum width=8cm, minimum height=1cm] at (5, -2) {};
+\end{tikzpicture}
+\\
+\end{tabular}
+\iflehrer{}{\liniert{1}}
+\end{Aufg}
+
+\begin{Lsg}
+$A / B / D / E / C / G$ \BE{3}
+\end{Lsg}
diff --git a/Info/11/NTG/1/Aufgaben/traversierung.tex b/Info/11/NTG/1/Aufgaben/traversierung.tex
index e06ec87b..3d58b061 100644
--- a/Info/11/NTG/1/Aufgaben/traversierung.tex
+++ b/Info/11/NTG/1/Aufgaben/traversierung.tex
@@ -2,8 +2,9 @@
 \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]
+\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. \textit{(Auf die Notation des Vorgängers kannst du verzichten.)}
 \iflehrer{}{
+\\[0.3cm]
 \begin{tabular}{p{0.6\textwidth} p{0.4\textwidth}}
 \vspace{-5cm}
 \begin{tabular}{c | c | c | c | c | c | c | c}
@@ -46,7 +47,7 @@ akt. & A & B & C & D & E & F & WS \\
 \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}}
+\iflehrer{}{\\[0.2cm] \kariert{20}}
 % \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) {