henrydatei/Musterklausur Lösung.tex

## Musterklausur Lösung.tex
\documentclass{article}

\usepackage{amsmath,amssymb}
\usepackage{tikz}
\usepackage{xcolor}
\usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage{marvosym}
\usepackage{tabularx}
\usepackage{xcolor}
\usepackage{colortbl}

\usepackage[utf8]{inputenc}

\renewcommand*{\arraystretch}{1.4}

\newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}}
\newcolumntype{R}[1]{>{\raggedleft\arraybackslash}p{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}

\title{\textbf{Einführung in die Informatik, Musterklausur SS2020}}
\author{\textsc{Henry Haustein}}
\date{}

\begin{document}
	\maketitle

	\section*{Aufgabe 1}
	\begin{enumerate}[label=(\alph*)]
		\item nein, da $\sqrt{9}-\sqrt{4}=3-2 \not\ge 2$ ist. Zum Beispiel ist $(1,9)\in R$, da $\sqrt{9}-\sqrt{1}=3-1\ge 2$ gilt.
		\item transitiv: $(a,b),(b,c)\in R\Rightarrow (a,c) \in R$. $R$ ist transitiv, denn
		\begin{align}
			(b,c) \in R \Leftrightarrow \sqrt{c} - \sqrt{b} &\ge 2 \notag \\
			\sqrt{c} - 2 &\ge \sqrt{b} \notag \\
			(a,b) \in R\Leftrightarrow \sqrt{b} - \sqrt{a} &\ge 2 \notag \\
			\sqrt{c} - 2 - \sqrt{a} &\ge 2 \notag \\
			\sqrt{c} - \sqrt{a} &\ge 2 \notag
		\end{align}
		\item ja, da $\mathbb{N}^2$ abzählbar unendlich ist (siehe Vorlesung) und $R\subset\mathbb{N}^2$ muss $R$ abzählbar unendlich sein.
	\end{enumerate}

	\section*{Aufgabe 2}
	\begin{enumerate}[label=(\alph*)]
		\item Der Greedy-Algorithmus versucht bei der Rückgabe von Talern die Münze mit den größten Wert, der noch in den restlichen auszuzahlenden Betrag passt, zurückzugeben. Es werden also zweimal 11 Taler und zweimal 1 Taler zurückgegeben.
		\item dreimal 8 Taler ist die optimale Lösung. Gibt man zuerst eine wertmäßig höhere Münze zurück, wird man im Greedy-Ansatzc landen, bei kleinerem Wert braucht man zu viele Münzen.
		\item $n=30$. Der Greedy-Algorihtmus wird hier zweimal 11 Taler und dann einmal 8 Taler zurückgeben.
	\end{enumerate}

	\section*{Aufgabe 3}
	\begin{enumerate}[label=(\alph*)]
		\item Die Gewichtsmatrix lautet:
		\begin{align}
			W = \begin{pmatrix}
				\infty & 2 & 7 & \infty & \infty & \infty \\
				\infty & \infty & 4 & 1 & \infty & \infty \\
				1 & 3 & \infty & 4 & 3 & \infty \\
				\infty & \infty & 2 & \infty & \infty & \infty \\
				\infty & \infty & 2 & 7 & \infty & 4 \\
				\infty & \infty & \infty & \infty & \infty & \infty
			\end{pmatrix} \notag
		\end{align}
		\item siehe Tabelle
		\begin{center}
			\begin{tabular}{c|ccccccc}
				Iteration & $S$ & $v_1$ & $D(b)$ & $D(c)$ & $D(d)$ & $D(e)$ & $D(f)$ \\
				\hline
				0 & $\{a\}$ & & 2 & 7 & $\infty$ & $\infty$ & $\infty$ \\
				1 & $\{a,b\}$ & $b$ & 2 & 6 & 3 & $\infty$ & $\infty$ \\
				2 & $\{a,b,d\}$ & $d$ & 2 & 5 & 3 & $\infty$ & $\infty$ \\
				3 & $\{a,b,d,c\}$ & $c$ & 2 & 5 & 3 & $\infty$ & 8 \\
				4 & $\{a,b,d,c,f\}$ & $f$ & 2 & 5 & 3 & $\infty$ & 8
			\end{tabular}
		\end{center}
	\end{enumerate}

	\section*{Aufgabe 4}
	\begin{enumerate}[label=(\alph*)]
		\item An der Regel $A\to AB$ sieht man gut, dass die Grammatik $G$ weder linear (mehr als ein nicht-terminales Symbol) noch rechtslinear ist, da bei $S\to aSb$ das nicht-terminale Symbol nicht rechts steht.
		\item $T_1 = \{C\}$ \\
		$T_2 = \{C,B\}$ \\
		$T_3 = \{C,B,S\} = T_4 = ...$
		\item dreimaliges Anwenden der Regel $S\to aS$ liefert: $aaaS$ \\
		Anwendung von $S\to cB$ liefert: $aaacB$ \\
		Anwendung von $B\to Bb$ liefert: $aaacBb$ \\
		Anwendung von $B\to Cb$ liefert: $aaacCbb$ \\
		Anwendung von $C\to c$ liefert: $aaaccbb$ $\Rightarrow$ $aaaccbb\in L(G)$
		\item $L(G)=a^\ast\cdot c^+\cdot b^+$
		\item Da $L(G)$ regulär ist, ist es auch kontextfrei.
	\end{enumerate}

	\section*{Aufgabe 5}
	\begin{enumerate}[label=(\alph*)]
		\item Der Automat $\mathcal{A}_2$ akzeptiert $aaabab$: $p_0\xrightarrow{a} p_2 \xrightarrow{a} p_2 \xrightarrow{a} p_2 \xrightarrow{b} p_3 \xrightarrow{a} p_3 \xrightarrow{b} p_3$
		\item siehe Abbildung
		\begin{center}
			\begin{tikzpicture}
			\node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$};
			\node[circle,draw=black, fill=white] (q1) at (2,0) {$q_1$};
			\node[circle,draw=black, fill=white] (q2) at (4,0) {$q_2$};

			\node[circle,draw=black, fill=white] (p0) at (4,-2) {$p_0$};
			\node[circle,draw=black, fill=white] (p1) at (6,-2) {$p_1$};
			\node[circle,draw=black, fill=white] (p2) at (4,-4) {$p_2$};
			\node[circle,draw=black, fill=white,double] (p3) at (6,-4) {$p_3$};

			\draw[->] (-1,0) -- (q0);
			\draw[->] (q0) to node[midway,above] {$a$} (q1);
			\draw[->] (q1) to node[midway,above] {$a$} (q2);
			\draw[->,looseness=4] (q1) to[out=60,in=120] node[midway,above] {$b$} (q1);

			\draw[->] (p0) to node[midway,above] {$a$} (p1);
			\draw[->] (p0) to node[midway,left] {$a$} (p2);
			\draw[->] (p1) to node[midway,right] {$a,b$} (p3);
			\draw[->] (p2) to node[midway,above] {$b$} (p3);
			\draw[->,looseness=4] (p2) to[out=150,in=210] node[midway,left] {$a$} (p2);
			\draw[->,looseness=4] (p3) to[out=-30,in=30] node[midway,right] {$a,b$} (p3);

			\draw[->,lightgray] (q1) to node[midway,above right] {$\varepsilon$} (p0);
			\draw[->,lightgray] (q2) to node[midway,right] {$\varepsilon$} (p0);

			\draw[->,blue] (q0) to node[midway,above] {$a$} (p0);
			\draw[->,blue] (q1) to[bend left=10] node[midway,above right] {$a,b$} (p0);
			\draw[->,blue] (q1) to[bend left=90] node[midway,above] {$a$} (p1);
			\draw[->,blue] (q1) to node[midway,below left] {$a$} (p2);
			\draw[->,blue] (q2) to node[midway,above] {$a$} (p1);
			\draw[->,blue] (q2) to[bend left=20] node[midway,right] {$a$} (p2);
			\end{tikzpicture}
		\end{center}
	\end{enumerate}

	\section*{Aufgabe 6}
	\begin{enumerate}[label=(\alph*)]
		\item siehe Abbildung
		\begin{center}
			\begin{tikzpicture}
				\node at (0,0) (1) {$\phi$};
				\node at (0,-1) (2) {$(\neg p\lor r)\land (p\lor q)$};
				\node at (0,-2) (3) {$p\land (\neg p\lor\neg q)$};
				\node at (0,-3) (4) {$\neg p\lor r$};
				\node at (0,-4) (5) {$p\lor q$};
				\node at (-2,-5) (6) {$\neg p$};
				\node at (-3,-6) (7) {$p$};
				\node at (-1,-6) (8) {$q$};
				\node at (-1,-7) (9) {$p$};
				\node at (-1,-8) (10) {$\neg p\lor\neg q$};
				\node at (2,-5) (11) {$r$};
				\node at (1,-6) (12) {$p$};
				\node at (3,-6) (13) {$q$};
				\node at (3,-7) (14) {$p$};
				\node at (3,-8) (15) {$\neg p\lor\neg q$};
				\node at (2,-9) (16) {$\neg p$};
				\node at (4,-9) (17) {$\neg p$};

				\node[red] at (7.south) {$\times$};
				\node[red] at (10.south) {$\times$};
				\node[red] at (16.south) {$\times$};
				\node[red] at (17.south) {$\times$};

				\draw (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7);
				\draw (6) -- (8) -- (9) -- (10);
				\draw (5) -- (11) -- (12);
				\draw (11) -- (13) -- (14) -- (15) -- (16);
				\draw (15) -- (17);
 			\end{tikzpicture}
		\end{center}
		\item ja, $\phi$ ist erfüllbar. $w(p)=1$, $w(q)=0$ und $w(r)=1$ erfüllt $\phi$.
		\item nein, $\phi$ ist nicht allgemeingültig, da nicht alle Zweige im Tableau offen sind. So sorgt z.B. $w(p)=0$ dafür, dass $\phi$ nicht erfüllbar sein kann.
	\end{enumerate}

	\section*{Aufgabe 7}
	\begin{enumerate}[label=(\alph*)]
		\item wahr, z.B. hat dieser Graph die Gradsequenz (4,3,3,2,2)
		\begin{center}
			\begin{tikzpicture}
				\node[circle,draw=black, fill=white] (a) at (0,0) {4};
				\node[circle,draw=black, fill=white] (b) at (-2,1) {3};
				\node[circle,draw=black, fill=white] (c) at (-2,-1) {3};
				\node[circle,draw=black, fill=white] (d) at (-4,1) {2};
				\node[circle,draw=black, fill=white] (e) at (-4,-1) {2};

				\draw[double] (a) -- (b);
				\draw[double] (a) -- (c);
				\draw (b) -- (d) -- (e) -- (c);
			\end{tikzpicture}
		\end{center}
		\item falsch, der $K_5$ ist ungerichtet, aber nicht planar.
		\item wahr, $\mathcal{A}=(\{q_0\},\{\varepsilon\},q_0,\Delta,\{q_0\})$.
		\item falsch, denn DEAs sind NEAs äquivalent, das heißt sie akzeptieren die selbe Sprache.
		\item falsch, eine Grammatik mit der Produktion $S\to aaS$ ist rechtslinear, aber nicht in Chomsky-Normalform, da auf der rechten Seite mehr als ein Terminalsymbol vorkommt.
		\item wahr, Kommutativität der ersten aussagenlogischen Formel und Umbenennung von $p$ nach $q$ liefert $q\lor\neg q$.
		\item wahr, offensichtlich ist $\{f(i)\mid i\ge 0\}\subseteq\mathbb{N}$, also gilt auch $\vert \{f(i)\mid i\ge 0\}\vert\le \vert\mathbb{N}\vert$.
		\item wahr, denn $R$ ist entscheidbar genau dann wenn $R$ und $\overline{R}$ partiell entscheidbar sind. $\overline{R}$ ist nicht entscheidbar und somit ist $\overline{R}$ auch nicht partiell entscheidbar und somit auch nicht $R$.
	\end{enumerate}

\end{document}
	\documentclass{article}

	\usepackage{amsmath,amssymb}
	\usepackage{tikz}
	\usepackage{xcolor}
	\usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry}
	\usepackage{enumerate}
	\usepackage{enumitem}
	\usepackage{marvosym}
	\usepackage{tabularx}
	\usepackage{xcolor}
	\usepackage{colortbl}

	\usepackage[utf8]{inputenc}

	\renewcommand*{\arraystretch}{1.4}

	\newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}}
	\newcolumntype{R}[1]{>{\raggedleft\arraybackslash}p{#1}}
	\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}

	\title{\textbf{Einführung in die Informatik, Musterklausur SS2020}}
	\author{\textsc{Henry Haustein}}
	\date{}

	\begin{document}
	\maketitle

	\section*{Aufgabe 1}
	\begin{enumerate}[label=(\alph*)]
	\item nein, da $\sqrt{9}-\sqrt{4}=3-2 \not\ge 2$ ist. Zum Beispiel ist $(1,9)\in R$, da $\sqrt{9}-\sqrt{1}=3-1\ge 2$ gilt.
	\item transitiv: $(a,b),(b,c)\in R\Rightarrow (a,c) \in R$. $R$ ist transitiv, denn
	\begin{align}
	(b,c) \in R \Leftrightarrow \sqrt{c} - \sqrt{b} &\ge 2 \notag \\
	\sqrt{c} - 2 &\ge \sqrt{b} \notag \\
	(a,b) \in R\Leftrightarrow \sqrt{b} - \sqrt{a} &\ge 2 \notag \\
	\sqrt{c} - 2 - \sqrt{a} &\ge 2 \notag \\
	\sqrt{c} - \sqrt{a} &\ge 2 \notag
	\end{align}
	\item ja, da $\mathbb{N}^2$ abzählbar unendlich ist (siehe Vorlesung) und $R\subset\mathbb{N}^2$ muss $R$ abzählbar unendlich sein.
	\end{enumerate}

	\section*{Aufgabe 2}
	\begin{enumerate}[label=(\alph*)]
	\item Der Greedy-Algorithmus versucht bei der Rückgabe von Talern die Münze mit den größten Wert, der noch in den restlichen auszuzahlenden Betrag passt, zurückzugeben. Es werden also zweimal 11 Taler und zweimal 1 Taler zurückgegeben.
	\item dreimal 8 Taler ist die optimale Lösung. Gibt man zuerst eine wertmäßig höhere Münze zurück, wird man im Greedy-Ansatzc landen, bei kleinerem Wert braucht man zu viele Münzen.
	\item $n=30$. Der Greedy-Algorihtmus wird hier zweimal 11 Taler und dann einmal 8 Taler zurückgeben.
	\end{enumerate}

	\section*{Aufgabe 3}
	\begin{enumerate}[label=(\alph*)]
	\item Die Gewichtsmatrix lautet:
	\begin{align}
	W = \begin{pmatrix}
	\infty & 2 & 7 & \infty & \infty & \infty \\
	\infty & \infty & 4 & 1 & \infty & \infty \\
	1 & 3 & \infty & 4 & 3 & \infty \\
	\infty & \infty & 2 & \infty & \infty & \infty \\
	\infty & \infty & 2 & 7 & \infty & 4 \\
	\infty & \infty & \infty & \infty & \infty & \infty
	\end{pmatrix} \notag
	\end{align}
	\item siehe Tabelle
	\begin{center}
	\begin{tabular}{c\|ccccccc}
	Iteration & $S$ & $v_1$ & $D(b)$ & $D(c)$ & $D(d)$ & $D(e)$ & $D(f)$ \\
	\hline
	0 & $\{a\}$ & & 2 & 7 & $\infty$ & $\infty$ & $\infty$ \\
	1 & $\{a,b\}$ & $b$ & 2 & 6 & 3 & $\infty$ & $\infty$ \\
	2 & $\{a,b,d\}$ & $d$ & 2 & 5 & 3 & $\infty$ & $\infty$ \\
	3 & $\{a,b,d,c\}$ & $c$ & 2 & 5 & 3 & $\infty$ & 8 \\
	4 & $\{a,b,d,c,f\}$ & $f$ & 2 & 5 & 3 & $\infty$ & 8
	\end{tabular}
	\end{center}
	\end{enumerate}

	\section*{Aufgabe 4}
	\begin{enumerate}[label=(\alph*)]
	\item An der Regel $A\to AB$ sieht man gut, dass die Grammatik $G$ weder linear (mehr als ein nicht-terminales Symbol) noch rechtslinear ist, da bei $S\to aSb$ das nicht-terminale Symbol nicht rechts steht.
	\item $T_1 = \{C\}$ \\
	$T_2 = \{C,B\}$ \\
	$T_3 = \{C,B,S\} = T_4 = ...$
	\item dreimaliges Anwenden der Regel $S\to aS$ liefert: $aaaS$ \\
	Anwendung von $S\to cB$ liefert: $aaacB$ \\
	Anwendung von $B\to Bb$ liefert: $aaacBb$ \\
	Anwendung von $B\to Cb$ liefert: $aaacCbb$ \\
	Anwendung von $C\to c$ liefert: $aaaccbb$ $\Rightarrow$ $aaaccbb\in L(G)$
	\item $L(G)=a^\ast\cdot c^+\cdot b^+$
	\item Da $L(G)$ regulär ist, ist es auch kontextfrei.
	\end{enumerate}

	\section*{Aufgabe 5}
	\begin{enumerate}[label=(\alph*)]
	\item Der Automat $\mathcal{A}_2$ akzeptiert $aaabab$: $p_0\xrightarrow{a} p_2 \xrightarrow{a} p_2 \xrightarrow{a} p_2 \xrightarrow{b} p_3 \xrightarrow{a} p_3 \xrightarrow{b} p_3$
	\item siehe Abbildung
	\begin{center}
	\begin{tikzpicture}
	\node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$};
	\node[circle,draw=black, fill=white] (q1) at (2,0) {$q_1$};
	\node[circle,draw=black, fill=white] (q2) at (4,0) {$q_2$};

	\node[circle,draw=black, fill=white] (p0) at (4,-2) {$p_0$};
	\node[circle,draw=black, fill=white] (p1) at (6,-2) {$p_1$};
	\node[circle,draw=black, fill=white] (p2) at (4,-4) {$p_2$};
	\node[circle,draw=black, fill=white,double] (p3) at (6,-4) {$p_3$};

	\draw[->] (-1,0) -- (q0);
	\draw[->] (q0) to node[midway,above] {$a$} (q1);
	\draw[->] (q1) to node[midway,above] {$a$} (q2);
	\draw[->,looseness=4] (q1) to[out=60,in=120] node[midway,above] {$b$} (q1);

	\draw[->] (p0) to node[midway,above] {$a$} (p1);
	\draw[->] (p0) to node[midway,left] {$a$} (p2);
	\draw[->] (p1) to node[midway,right] {$a,b$} (p3);
	\draw[->] (p2) to node[midway,above] {$b$} (p3);
	\draw[->,looseness=4] (p2) to[out=150,in=210] node[midway,left] {$a$} (p2);
	\draw[->,looseness=4] (p3) to[out=-30,in=30] node[midway,right] {$a,b$} (p3);

	\draw[->,lightgray] (q1) to node[midway,above right] {$\varepsilon$} (p0);
	\draw[->,lightgray] (q2) to node[midway,right] {$\varepsilon$} (p0);

	\draw[->,blue] (q0) to node[midway,above] {$a$} (p0);
	\draw[->,blue] (q1) to[bend left=10] node[midway,above right] {$a,b$} (p0);
	\draw[->,blue] (q1) to[bend left=90] node[midway,above] {$a$} (p1);
	\draw[->,blue] (q1) to node[midway,below left] {$a$} (p2);
	\draw[->,blue] (q2) to node[midway,above] {$a$} (p1);
	\draw[->,blue] (q2) to[bend left=20] node[midway,right] {$a$} (p2);
	\end{tikzpicture}
	\end{center}
	\end{enumerate}

	\section*{Aufgabe 6}
	\begin{enumerate}[label=(\alph*)]
	\item siehe Abbildung
	\begin{center}
	\begin{tikzpicture}
	\node at (0,0) (1) {$\phi$};
	\node at (0,-1) (2) {$(\neg p\lor r)\land (p\lor q)$};
	\node at (0,-2) (3) {$p\land (\neg p\lor\neg q)$};
	\node at (0,-3) (4) {$\neg p\lor r$};
	\node at (0,-4) (5) {$p\lor q$};
	\node at (-2,-5) (6) {$\neg p$};
	\node at (-3,-6) (7) {$p$};
	\node at (-1,-6) (8) {$q$};
	\node at (-1,-7) (9) {$p$};
	\node at (-1,-8) (10) {$\neg p\lor\neg q$};
	\node at (2,-5) (11) {$r$};
	\node at (1,-6) (12) {$p$};
	\node at (3,-6) (13) {$q$};
	\node at (3,-7) (14) {$p$};
	\node at (3,-8) (15) {$\neg p\lor\neg q$};
	\node at (2,-9) (16) {$\neg p$};
	\node at (4,-9) (17) {$\neg p$};

	\node[red] at (7.south) {$\times$};
	\node[red] at (10.south) {$\times$};
	\node[red] at (16.south) {$\times$};
	\node[red] at (17.south) {$\times$};

	\draw (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7);
	\draw (6) -- (8) -- (9) -- (10);
	\draw (5) -- (11) -- (12);
	\draw (11) -- (13) -- (14) -- (15) -- (16);
	\draw (15) -- (17);
	\end{tikzpicture}
	\end{center}
	\item ja, $\phi$ ist erfüllbar. $w(p)=1$, $w(q)=0$ und $w(r)=1$ erfüllt $\phi$.
	\item nein, $\phi$ ist nicht allgemeingültig, da nicht alle Zweige im Tableau offen sind. So sorgt z.B. $w(p)=0$ dafür, dass $\phi$ nicht erfüllbar sein kann.
	\end{enumerate}

	\section*{Aufgabe 7}
	\begin{enumerate}[label=(\alph*)]
	\item wahr, z.B. hat dieser Graph die Gradsequenz (4,3,3,2,2)
	\begin{center}
	\begin{tikzpicture}
	\node[circle,draw=black, fill=white] (a) at (0,0) {4};
	\node[circle,draw=black, fill=white] (b) at (-2,1) {3};
	\node[circle,draw=black, fill=white] (c) at (-2,-1) {3};
	\node[circle,draw=black, fill=white] (d) at (-4,1) {2};
	\node[circle,draw=black, fill=white] (e) at (-4,-1) {2};

	\draw[double] (a) -- (b);
	\draw[double] (a) -- (c);
	\draw (b) -- (d) -- (e) -- (c);
	\end{tikzpicture}
	\end{center}
	\item falsch, der $K_5$ ist ungerichtet, aber nicht planar.
	\item wahr, $\mathcal{A}=(\{q_0\},\{\varepsilon\},q_0,\Delta,\{q_0\})$.
	\item falsch, denn DEAs sind NEAs äquivalent, das heißt sie akzeptieren die selbe Sprache.
	\item falsch, eine Grammatik mit der Produktion $S\to aaS$ ist rechtslinear, aber nicht in Chomsky-Normalform, da auf der rechten Seite mehr als ein Terminalsymbol vorkommt.
	\item wahr, Kommutativität der ersten aussagenlogischen Formel und Umbenennung von $p$ nach $q$ liefert $q\lor\neg q$.
	\item wahr, offensichtlich ist $\{f(i)\mid i\ge 0\}\subseteq\mathbb{N}$, also gilt auch $\vert \{f(i)\mid i\ge 0\}\vert\le \vert\mathbb{N}\vert$.
	\item wahr, denn $R$ ist entscheidbar genau dann wenn $R$ und $\overline{R}$ partiell entscheidbar sind. $\overline{R}$ ist nicht entscheidbar und somit ist $\overline{R}$ auch nicht partiell entscheidbar und somit auch nicht $R$.
	\end{enumerate}

	\end{document}