Grundlagen und diskrete Strukturen - Prüfungsvorbereitung.tex

\documentclass[10pt, a4paper]{exam}
\printanswers			    % Comment this line to hide the answers 
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[ngerman]{babel}
\usepackage{listings}
\usepackage{float}
\usepackage{graphicx}
\usepackage{color}
\usepackage{listings}
\usepackage[dvipsnames]{xcolor}
\usepackage{tabularx}
\usepackage{geometry}
\usepackage{color,graphicx,overpic}
\usepackage{amsmath,amsthm,amsfonts,amssymb}
\usepackage{tabularx}
\usepackage{listings}
\usepackage[many]{tcolorbox}
\usepackage{multicol}
\usepackage{hyperref}
\usepackage{pgfplots}
\usepackage{bussproofs}
\usepackage{tikz}
\usetikzlibrary{automata, arrows.meta, positioning}
\renewcommand{\solutiontitle}{\noindent\textbf{Antwort}: }
\SolutionEmphasis{\small}
\geometry{top=1cm,left=1cm,right=1cm,bottom=1cm} 

\pdfinfo{
    /Title (Grundlagen und diskrete Strukturen - Prüfungsvorbereitung)
    /Creator (TeX)
    /Producer (pdfTeX 1.40.0)
    /Author (Robert Jeutter)
    /Subject ()
}
\title{Grundlagen und diskrete Strukturen - Prüfungsvorbereitung}
\author{}
\date{}

% Don't print section numbers
\setcounter{secnumdepth}{0}

\newtcolorbox{myboxii}[1][]{
  breakable,
  freelance,
  title=#1,
  colback=white,
  colbacktitle=white,
  coltitle=black,
  fonttitle=\bfseries,
  bottomrule=0pt,
  boxrule=0pt,
  colframe=white,
  overlay unbroken and first={
  \draw[red!75!black,line width=3pt]
    ([xshift=5pt]frame.north west) -- 
    (frame.north west) -- 
    (frame.south west);
  \draw[red!75!black,line width=3pt]
    ([xshift=-5pt]frame.north east) -- 
    (frame.north east) -- 
    (frame.south east);
  },
  overlay unbroken app={
  \draw[red!75!black,line width=3pt,line cap=rect]
    (frame.south west) -- 
    ([xshift=5pt]frame.south west);
  \draw[red!75!black,line width=3pt,line cap=rect]
    (frame.south east) -- 
    ([xshift=-5pt]frame.south east);
  },
  overlay middle and last={
  \draw[red!75!black,line width=3pt]
    (frame.north west) -- 
    (frame.south west);
  \draw[red!75!black,line width=3pt]
    (frame.north east) -- 
    (frame.south east);
  },
  overlay last app={
  \draw[red!75!black,line width=3pt,line cap=rect]
    (frame.south west) --
    ([xshift=5pt]frame.south west);
  \draw[red!75!black,line width=3pt,line cap=rect]
    (frame.south east) --
    ([xshift=-5pt]frame.south east);
  },
}

\begin{document}
\begin{myboxii}[Disclaimer]
  Aufgaben aus dieser Vorlage stammen aus der Vorlesung \textit{Grundlagen und diskrete Strukturen} und wurden zu Übungszwecken verändert oder anders formuliert! Für die Korrektheit der Lösungen wird keine Gewähr gegeben.
\end{myboxii}

Erlaubte Hilfsmittel: eine math. Formelsammlung/Nachschlagwerk, ein handbeschriebenes A4-Blatt mit Formeln und Ergebnissen aus der Vorlesung.

%##########################################
\begin{questions}
  \question
  \begin{parts}
    \part Untersuche, welche der folgenden aussagenlogischen Ausdrücke logisch äquivalent sind. Begründe die Entscheidung.\\\begin{center}
      $\varphi=p\rightarrow (q\wedge\overline{r})$, $\psi=(p\rightarrow q)\wedge(r\rightarrow\overline{p})$, $y=(\overline{p}\vee q)\leftrightarrow r$ \end{center}
    \begin{solution}

      $\varphi=p\rightarrow (q\wedge\overline{r})$
      \begin{tabular}{c|c|c|c|c}
        $p$ & $q$ & $r$ & $q\wedge\overline{r}$ & $p\rightarrow(q\wedge\overline{r})$ \\\hline
        0   & 0   & 0   & 0                     & 1                                   \\
        0   & 0   & 1   & 0                     & 1                                   \\
        0   & 1   & 0   & 1                     & 1                                   \\
        0   & 1   & 1   & 0                     & 1                                   \\
        1   & 0   & 0   & 0                     & 0                                   \\
        1   & 0   & 1   & 1                     & 1                                   \\
        1   & 1   & 0   & 1                     & 1                                   \\
        1   & 1   & 1   & 0                     & 0
      \end{tabular}

      $\psi=(p\rightarrow q)\wedge(r\rightarrow\overline{p})$
      \begin{tabular}{c|c|c|c|c|c}
        $p$ & $q$ & $r$ & $p\rightarrow q$ & $r\rightarrow\overline{p}$ & $(p\rightarrow q)\wedge(r\rightarrow\overline{p})$ \\\hline
        0   & 0   & 0   & 1                & 1                          & 1                                                  \\
        0   & 0   & 1   & 1                & 0                          & 0                                                  \\
        0   & 1   & 0   & 1                & 1                          & 1                                                  \\
        0   & 1   & 1   & 1                & 0                          & 0                                                  \\
        1   & 0   & 0   & 0                & 1                          & 0                                                  \\
        1   & 0   & 1   & 0                & 1                          & 0                                                  \\
        1   & 1   & 0   & 1                & 0                          & 0                                                  \\
        1   & 1   & 1   & 1                & 1                          & 1
      \end{tabular}

      $y=(\overline{p}\vee q)\leftrightarrow r$
      \begin{tabular}{c|c|c|c|c}
        $p$ & $q$ & $r$ & $\overline{p}\vee q$ & $(\overline{p}\vee q)\leftrightarrow r$ \\\hline
        0   & 0   & 0   & 0                    & 1                                       \\
        0   & 0   & 1   & 0                    & 0                                       \\
        0   & 1   & 0   & 1                    & 0                                       \\
        0   & 1   & 1   & 1                    & 1                                       \\
        1   & 0   & 0   & 0                    & 1                                       \\
        1   & 0   & 1   & 0                    & 0                                       \\
        1   & 1   & 0   & 0                    & 1                                       \\
        1   & 1   & 1   & 0                    & 0
      \end{tabular}
    \end{solution}

    \part Negiere die Aussage: $\forall S\in\mathbb{R}\exists m\in\mathbb{N} \forall n\in\mathbb{N}: n>m\Rightarrow a_n>S$
    \begin{solution}
      $\exists S\in\mathbb{R}\exists m\in\mathbb{N} \forall n\in\mathbb{N}: n>m\Rightarrow a_n < S$
    \end{solution}

    \part Negiere die Aussage: ,,In jeder GudS-Klausur gibt es mindestens eine Aufgabe, die von niemandem richtig gelöst wird''
    \begin{solution}
      ,,Es gibt eine GudS-Klausur in der jemand jede Aufgabe richtig löst.''
    \end{solution}
  \end{parts}

  \question Es seien $f,g:\mathbb{N}\rightarrow\mathbb{N}$ zwei Funktionen. Auf der Menge $\mathbb{N}$ der natürlichen Zahlen wird wie folgt eine Relation definiert: $a \sim b \leftrightarrow f(a)-f(b)=g(a)-g(b)$. Weise nach, dass $\sim$ eine Äquivalenzrelation ist. Für den konkreten Fall $f(x)=x^2+1$ und $g(x)=2x$ bestimme man die Äquivalenzklasse $[2]_{\backslash\sim}$
  \begin{solution}
  \end{solution}

  \question
  \begin{parts}
    \part Bestimme mit Hilfe des euklidischen Algorithmus ganze Zahlen $a,b$, für die gilt $1=a*100+b*23$
    \begin{solution}
      $ggT(a,b)= a*x+b*y$

      $\downarrow$: $b_i\rightarrow a_{i+1}$, $r_i\rightarrow b_{i+1}$

      $\uparrow$: $x_i=y_{i+1}$, $y_i=x_{i+1}-q_i*y_{i+1}$

      \begin{tabular}{c|c|c|c|c|c|c|c|c}
        i & a   & b  & q (Teiler) & r(est) & x  & y   & Nebenrechnung $\downarrow$ & Nebenrechnung $\uparrow$          \\\hline
        1 & 100 & 23 & 4          & 8      & 3  & -13 & $100-23*4 = 8$             & $100*3 + 23*(-1-4*3)= 300-299= 1$ \\
        2 & 23  & 8  & 2          & 7      & -1 & 3   & $23-2*8=7$                 & $23*-1 + 8*(1-2*(-1))=1$          \\
        3 & 8   & 7  & 1          & 1      & 1  & -1  & $8-1+7=1$                  & $8*1 + 7*(0-1*1)=1$               \\
        4 & 7   & 1  & 7          & 0      & 0  & 1   & $7-7*1=0$                  & $7*0+1*1 = 1$
      \end{tabular}

      Lösung: $a=3$, $b=-13$
    \end{solution}

    \part Bestimme mit Hilfe des euklidischen Algorithmus ganze Zahlen $a,b$, für die gilt $1=a*23+b*17$
    \begin{solution}
      \begin{tabular}{c|c|c|c|c|c|c}
        i & a  & b  & q & r & x  & y           \\\hline
        1 & 23 & 17 & 1 & 6 & 3  & $-1-1*3=-4$ \\
        2 & 17 & 6  & 2 & 5 & -1 & $1-2*-1=3$  \\
        3 & 6  & 5  & 1 & 1 & 1  & $0-1*1=-1$  \\
        4 & 5  & 1  & 5 & 0 & 0  & 1
      \end{tabular}

      Lösung: $1=-3*23 -4*17 = 69-68 = 1$
    \end{solution}

    \part Untersuche, ob es ein multiplikativ inverses Element zu $\overline{23}$ in $\mathbb{Z}_{100}$ gibt und bestimme dieses gegebenfalls. Gebe außerdem ein nicht invertierbares Element außer $\overline{0}$ in $\mathbb{Z}_{100}$ an.
    \begin{solution}
      multiplikativ inverses: $a^{-1}*a=1$

      die multiplikative Gruppe $\mathbb{Z}_n$ besteht aus den Elementen von $\mathbb{Z}_n$ die teilerfremd zu $n$ sind. Für jedes $a\in\mathbb{Z}_n^*$ gilt $ggt(a,n)=1$ und lässt sich als $1=a*x + n*y$ darstellen $\quad\Rightarrow\quad a^{-1} \equiv y(mod\ n)$

      \begin{tabular}{c|c|c|c|c|c|c}
        i & a   & b  & q & r & x  & y   \\\hline
        1 & 100 & 23 & 4 & 8 & 3  & -13 \\
        2 & 23  & 8  & 2 & 7 & -1 & 3   \\
        3 & 8   & 7  & 1 & 1 & 1  & -1  \\
        4 & 7   & 1  & 7 & 0 & 0  & 1
      \end{tabular}

      $1=100 * 3 - 23 * 13 \Rightarrow \overline{23}= -13 (mod\ 100)$

      Alternativ: $a^{-1}*a=1 \rightarrow a^{-1}=1\backslash a \Rightarrow a^{-1}=\frac{1}{23}$


    \end{solution}
  \end{parts}

  \question Gegeben sei die Menge $G=\{ \begin{pmatrix} 1&a&b\\0&1&c\\0&0&1 \end{pmatrix} \in\mathbb{R}^{(3,3)}\mid a,b,c\in\mathbb{R}\}$. Zeige, dass $G$ eine Gruppe bezüglich der Matrizenmultiplikation ist. Rechengesetze der Matrizenmultiplikation dürfen vorausgesetzt werden. Ist die Gruppe kommutativ? (ohne Beweis)
  \begin{solution}

    Eine nichtleere Menge $G$ von Elementen $a, b, c, ...$ heißt Gruppe, wenn in ihr eine Operation $\circ$ erklärt ist, die folgenden Axiomen genügt:
    \begin{itemize}
      \item Die Operation $\circ$ ist assoziativ, d.h. für alle Elemente $a,b,c\in G$ gilt $a\circ (b\circ c)=(a\circ b)\circ c$
      \item Die Operation $\circ$ ist umkehrbar, d.h. zu beliebigen Elementen $a,b\in G$ sind die Gleichungen $a\circ x=b$ und $y\circ a=b$ (mit $x\in G$ und $y\in G$) lösbar.
    \end{itemize}
    Man nennt $G$ eine kommutative (oder abelsche) Gruppe, wenn zusätzlich noch gilt:
    \begin{itemize}
      \item Die Operation $\circ$ ist kommutativ, d.h. für alle $a,b\in G$ gilt $a\circ b=b\circ a$
    \end{itemize}

    Für die Matrizenmultiplikation von G gilt: 
    $G*G=\begin{pmatrix} 
      1*1+a*0+b*0 & 1*a+a*1+b*0 & 1*b+a*c+b*1 \\ 
      0*1+1*0+c*0 & 0*a+1*1+c*0 & 0*b+1*c+c*1 \\ 
      0*1+0*0+1*0 & 0*a+0*1+1*0 & 0*b+0*c+1*1
    \end{pmatrix} = \begin{pmatrix}
      1 & 2a & 2b+ac\\ 
      0 & 1 & 2c\\
      0 & 0 & 1  
    \end{pmatrix}$

    Zeige dass die Einheitsmatrix Element von $G$ ist.

    Zeige dass die Verknüpfung in $G$ assoziativ ist.

    Begründe dass alle Matrizen in $G$ invertierbar sind. %Erinnere dich dazu daran, was die Matrixmultiplikation mit dem Rang macht.


  \end{solution}

  \question Markus ist politikinteressiert und möchte gerne Bundeskanzler werden. Er überlegt aber noch welcher Partei er beitritt. Er hat zwei Parteien $A$ und $B$, die ihm gefallen, könnte aber auch eine eigene Partei $C$ gründen. Die Chancen bei den nächsten Wahlen als Spitzenkandidat aufgestellt zu werden schätzt er auf $10\%$ bei Partei $A$, auf $20\%$ bei Partei $B$ und $100\%$ bei Partei $C$. Die Chance, dass die jeweilige Partei mit ihm an der Spitze die Wahl gewinnt liegt bei $60\%$, $45\%$ bzw. $2\%$.
  \begin{parts}
    \part Für welche Partei sollte er sich entscheiden, um mit maximaler Wahrscheinlichkeit Bundeskanzler zu werden?
    \begin{solution}
      S: wird Spitzenkandidat, K: wird Bundeskanzler,

      $P(A \cap S) = 0,1$, $P(B\cap S)=0,2$, $P(C\cap S)=1$

      $P(A\cap K)= 0,6$, $P(B\cap K)=0,45$, $P(C\cap K)=0,02$

      $P_A(S\cap K) = P(A \cap S) \cap P(A \cap K) = 0,1 * 0,6 = 0,06$

      $P_B(S \cap K)= P(B \cap S) \cap P(B \cap K) = 0,2 * 0,45 = 0,09$

      $P_C(C \cap K)= P(C \cap S) \cap P(C \cap K)= 1 * 0,02 = 0,02$

      Markus hat bei Partei B die größten Chancen Bundeskanzler zu werden (mit 9\%).
    \end{solution}

    \part Markus lässt die Würfel entscheiden. Bei $1$ tritt er Partei $A$ bei, bei $2$ oder $3$ Partei $B$ und bei $4,5$ oder $6$ gründet er Partei $C$. Markus wird tatsächlich Bundeskanzler. Mit welcher Wahrscheinlichkeit hat er dann Partei $C$ gegründet.
    \begin{solution}
      $P(\text{Tritt A bei}) = \frac{1}{6}$, $P(\text{Tritt B bei})=\frac{2}{6}=\frac{1}{3}$, $P(\text{Tritt C bei})=\frac{3}{6}=\frac{1}{2}$

      $P_{\text{Tritt C bei}}(\text{C gewinnt mit ihm}) = \frac{P_C(C \cap K)}{P(\text{Tritt C bei})} = \frac{0,02}{0,5} = 0,04$

      Wenn Markus Bundeskanzler wird, hat er mit 4\% Wahrscheinlichkeit seine eigene Partei C gegründet.
    \end{solution}
  \end{parts}

  \question Gegeben sei folgender Graph:
  \begin{center}
    \begin{tikzpicture}[node distance = 3cm, on grid, auto]
      \node (A) [state] {A};
      \node (B) [state, left = of A] {B};
      \node (C) [state, above left = of A] {C};
      \node (D) [state, above right = of A] {D};
      \node (E) [state, below left = of A] {E};
      \node (F) [state, above = of A] {F};
      \node (G) [state, below right = of A] {G};
      \node (H) [state, right = of A] {H};
      \node (I) [state, below = of A] {I};

      \path [thick]
      (A) edge (F)
      (A) edge (D)
      (A) edge (H)
      (A) edge (G)
      (A) edge (C)
      (B) edge (C)
      (B) edge (E)
      (C) edge (F)
      (C) edge (E)
      (D) edge (H)
      (E) edge (I)
      (G) edge (I)
      ;
    \end{tikzpicture}
  \end{center}
  \begin{parts}
    \part Gebe einen Tiefensuchbaum mit Startecke $A$ für den Graphen an.
    \begin{solution}
      \begin{center}
        \begin{tikzpicture}[node distance = 1.5cm, on grid, auto]
          \node (A) [state] {A};
          \node (C) [state, below left = of A] {C};
          \node (D) [state, below right = of A] {D};
          \node (H) [state, below = of D] {H};
          \node (B) [state, below left= of C] {B};
          \node (E) [state, below = of B] {E};
          \node (I) [state, below = of E] {I};
          \node (G) [state, below = of I] {G};
          \node (F) [state, below right = of C] {F};

          \path [thick]
          (A) edge (D)
          (A) edge (C)
          (B) edge (C)
          (B) edge (E)
          (C) edge (F)
          (D) edge (H)
          (E) edge (I)
          (G) edge (I)
          ;
        \end{tikzpicture}
      \end{center}
    \end{solution}

    \part Gebe einen Breitensuchbaum mit Startecke $A$ für den Graphen an.
    \begin{solution}
      \begin{center}
        \begin{tikzpicture}[node distance = 1cm, on grid, auto]
          \node (A) [state] {A};
          \node (C) [state, below left = 2cm and 3cm of A] {C};
          \node (D) [state, below right = 2cm and 2cm of A] {D};
          \node (F) [state, below left = 2cm and 2cm of A] {F};
          \node (G) [state, below left= 2cm and 1cm of A] {G};
          \node (H) [state, below right = 2cm and 1cm of A] {H};
          \node (B) [state, below left = 1cm and 1cm of C] {B};
          \node (E) [state, below right= 1cm and 1cm of C] {E};
          \node (I) [state, below = of G] {I};

          \path [thick]
          (A) edge (F)
          (A) edge (D)
          (A) edge (H)
          (A) edge (G)
          (A) edge (C)
          (C) edge (B)
          (C) edge (E)
          (G) edge (I)
          ;
        \end{tikzpicture}
      \end{center}
    \end{solution}

    \part Zeige, dass für jede natürliche Zahl $k\geq 1$ gilt: Jeder Baum, der eine Ecke vom Grad $k$ enthält, hat mindestens $k$ Blätter.
    \begin{solution}

      Induktionsannahme: Es wird angenommen der Baum ist homogen verteilt, d.h. die Teilbäume jedes Baumes sind von gleicher Kantenlänge (Größe). Besitzt ein Teilbaum keinen Unterbaum, so ist er ein Blatt.

      Induktionsstart: Für $k=1$ besitzt ein Baum maximal $2^1$ Kanten mit mindestens 1 Blatt. Daraus folgt $k=1=\sum Blätter$ stimmt

      Induktionsschritt: Für $k=n+1$ besitzt ein Baum maxumal $2^{n+1}$ Kanten mit mindestens 1 Blatt. Daraus folgt $k=n+1...$

    \end{solution}
  \end{parts}
\end{questions}
\end{document}