% -*- coding: utf-8; -*-

\begin{lecture exercises}

  \begin{exercise}[title=Informelle Beweise führen,
                   level=schwer,
                   how=Einzelarbeit,
                   credits=4 Punkte]
    Seien $\Sigma$ und $\Gamma$ Alphabete. Beweisen oder widerlegen
    Sie:
    \begin{enumerate}
    \item $(\Sigma\cap\Gamma)^* = \Sigma^* \cap \Gamma^*$,
    \item  $(\Sigma \setminus \Gamma)^* = \Sigma^* \setminus \Gamma^*$.
    \end{enumerate}
    Beweisen sollen Sie diejenigen Behauptungen, die korrekt sind (welche
    dies sind, müssen Sie selbst herausfinden). »Beweisen« bedeutet, dass
    Sie die Aussage einem skeptischen Leser gegenüber begründen. Stellen
    Sie sich jemanden vor, der die Aussage erstmal nicht glaubt und den
    Sie überzeugen müssen.

    »Widerlegen« bedeutet, dass Sie erkennen, dass die Aussage in einer
    bestimmten Situation nicht stimmt und dass Sie eine solche Situation
    explizit beschreiben. Man spricht dann von einem Gegenbeispiel.
  \end{exercise}

  \begin{exercise}[title=Informelle Beweise führen,
 		 level=schwer,
        	 how=Einzelarbeit,
        	 credits=4 Punkte]
    Seien $L_1$ und $L_2$ unendliche Sprachen über dem Alphabet
    $\Sigma=\{a,b,\ldots,z\}$. Das heißt,  $L_1$ und $L_2$ enthalten
    unendlich viele verschiedene Worte.  Beweisen oder widerlegen Sie:
    \begin{enumerate}
     \item $L_1 \cup L_2$ ist unendlich.
     \item  $L_1 \cap L_2$ ist unendlich.
    \end{enumerate}
    %   Beweisen sollen Sie diejenigen Behauptungen, die korrekt sind (welche
    %   dies sind, müssen Sie selbst herausfinden). »Beweisen« bedeutet, dass
    %   Sie die Aussage einem skeptischen Leser gegenüber begründen. Stellen
    %   Sie sich jemanden vor, der die Aussage erstmal nicht glaubt und den
    %   Sie überzeugen müssen.
    %
    %   »Widerlegen« bedeutet, dass Sie erkennen, dass die Aussage in einer
    %   bestimmten Situation nicht stimmt und dass Sie eine solche Situation
    %   explizit beschreiben. Man spricht dann von einem Gegenbeispiel.
  \end{exercise}

  \begin{exercise}[title=Den Wortbegriff vertiefen,
		level=mittel,
		how=Einzelarbeit,
		credits=4 Punkte]
    Sei $w$ ein Wort über einem beliebigen Alphabet $\Sigma$. Ein
    \emph{Teilwort} von $w$ ist ein Wort, das durch Löschen beliebig
    vieler Buchstaben am Anfang und/oder am Ende von $w$ entsteht.
    Die Reihenfolge der übrigen Buchstaben darf dabei aber nicht geändert werden.


    Zum Beispiel sind \texttt{IKFUE}, \texttt{LOGIK} und
    \texttt{INFORMATIK} alle Teilwörter von
    \texttt{LOGIKFUERINFORMATIKER}, aber \texttt{GIEK} ist keines.


    Wie viele Teilwörter hat ein Wort der Länge $n$
    mindestens? Wie viele höchstens? Geben Sie für $n=30$ jeweils ein Wort an, bei dem die
    Mindest- bzw. Höchstzahl an Teilwörtern vorkommt.
  \end{exercise}


  \begin{exercise}[title=Kombinatorische Überlegungen üben,
		level=mittel,
		how=Einzelarbeit,
		credits=2 Punkte,]
    Wie viele Teilwörter hat das Wort \texttt{INFORMATIKERIN}?
  \end{exercise}

  \begin{exercise}[title=Den Wortbegriff vertiefen,
                   level=mittel,
                   how=Einzelarbeit,
                   credits=4 Punkte]
    Sei $w$ ein Wort über einem beliebigen Alphabet $\Sigma$. Ein
    \emph{verstreutes Teilwort} von $w$ ist ein Wort, das durch Löschen beliebig
    vieler Buchstaben aus $w$ entsteht. Die Reihenfolge der übrigen Buchstaben darf
    dabei aber nicht geändert werden. Zum Beispiel sind \texttt{FUENF},
    \texttt{GIEK} und \texttt{OIUEIOAIE} alles verstreute Teilwörter von
    \texttt{LOGIKFUERINFORMATIKER}, aber \texttt{GEEK} ist keines.

    Wie viele verstreute Teilwörter hat ein Wort der Länge $n$
    mindestens? Wie viele höchstens? Geben Sie jeweils ein Wort an, bei dem die
    Mindest- bzw. Höchstzahl an verstreuten Teilwörtern vorkommt.
  \end{exercise}


  \begin{exercise}[title=Kombinatorische Überlegungen üben,
                   level=schwer,
                   how=Einzelarbeit,
                   credits=2 Punkte,]
    Wie viele verstreute Teilwörter hat das Wort
    \begin{quote}
     \texttt{MENSCHISTDOCHWAHRLICHALLESGANZLOGISCH}?
    \end{quote}

  \end{exercise}


  \begin{exercise}[title=Kodieren üben,
                   level=mittel,
                   how=Einzelarbeit,
                   credits=4 Punkte]
    Ein \emph{Schaltkreis} besteht aus Gattern und Verbindungen.
    Es gibt fünf Arten von Gattern: \texttt{0}, \texttt{1}, \texttt{AND},
    \texttt{OR}, \texttt{NOT}. Alle Gatter haben einen Ausgang. Die Gatter \texttt{0} und
    \texttt{1} haben keinen Eingang, das Gatter \texttt{NOT} hat einen Eingang, die Gatter
    \texttt{AND} und \texttt{OR} haben zwei Eingänge. Bei jedem Gatter muss jeder Eingange mit
    dem Ausgang eines anderen Gatters verbunden sein.

    Überlegen Sie sich eine Methode, um Schaltkreise als Zeichenketten über einem
    Alphabet Ihrer Wahl zu kodieren. Beschreiben Sie Ihre Methode und kodieren Sie
    den unten abgebildeten Schaltkreis damit.

    \begin{center}
      \begin{tikzpicture}[graph,scale=.5]
        \node[gate] at (0, 4) (n3) {\texttt{1}};
        \node[gate] at (0, 2) (n2) {\texttt{0}};
        \node[gate] at (0,-1) (n4) {\texttt{0}};

        \node[gate] at (2, 3) (n5) {\texttt{AND}};
        \node[gate] at (2,-1) (n6) {\texttt{NOT}};

        \node[gate] at (4, 0) (n7) {\texttt{OR}};
        \node[gate] at (6, 1) (n8) {\texttt{OR}};
        \coordinate (out) at (8,1);

        \draw[->] (n2) -- (n5);
        \draw[->] (n3) -- (n5);
        \draw[->] (n2) -- (n7);
        \draw[->] (n4) -- (n6);
        \draw[->] (n6) -- (n7);
        \draw[->] (n7) -- (n8);
        \draw[->] (n5) -- (n8);
        \draw[->] (n8) -- (out);

      \end{tikzpicture}
    \end{center}
  \end{exercise}


  \begin{exercise}[title=Kodieren üben,
                   level=mittel,
                   how=Einzelarbeit,
                   credits=4 Punkte]
    Wer kennt das nicht: Man fährt mit seinem nagelneuen Off-Roader
    in die Pampa und das Navigationssystem meldet\nopagebreak
    \begin{quote}
      »Bitte wenden!«
    \end{quote}
    Der Navi kennt wieder einmal das lokale Straßennetz nicht, weshalb
    wir spontan beschließen, unser eigenes System zu programmieren.
    Gesagt, getan. Die erste Aufgabe ist, die Straßenkarte
    unserem System zur Verfügung zu stellen. Dabei betrachten wir
    das Straßennetz als ungerichteten Graphen mit den Städten als Knoten
    und den Straßen als Kanten.

    Überlegen Sie sich eine Methode, um ungerichtete Graphen als
    Zeichenketten über einem Alphabet Ihrer Wahl zu
    kodieren. Beschreiben Sie Ihre Methode und kodieren Sie
    das unten stehende Straßennetz damit.

    \begin{center}
    \begin{tikzpicture}[graph,scale=0.5]
 	\tikzstyle{city}=[node,long label]
 	\tikzstyle{weight}=[midway,above,sloped,font=\small]
	\node[city] (A) at (1,0) {Ahstedt};
	\node[city] (B) at (-2,-3) {Beeholz};
	\node[city] (C) at (4,-3) {Cätendorf};
	\node[city] (D) at (2,3) {Detensen};
	\node[city] (E) at (2,-6) {Ehrenfels};
	\node[city] (F) at (6,-6) {Freihaus};
	\draw (A) -- (B) node[weight] {15 km};
	\draw (A) -- (D) node[weight] {8 km};
	\draw (B) to[bend left] node[weight] {21 km} (D);
	\draw (A) -- (C) node[weight] {9 km};
	\draw (B) -- (E) node[weight] {11 km};
	\draw (C) -- (E) node[weight] {7 km};
	\draw (C) -- (F) node[weight] {14 km};
    \end{tikzpicture}
    \end{center}
  \end{exercise}

  \begin{exercise}[title=Kodieren üben,
                  level=mittel,
                  how=Einzelarbeit]
  Bevor Bilbo Beutlin mit Thorin, Bifur, Bofur, Fili, Kili, Dori,
  Nori, Ori, Oin, Gloin, Balin, Dwalin und Bombur zum Einsamen Berg in
  Rhovanion aufbricht, um gegen den Drachen Smaug anzutreten, erhält
  er von Gandalf eine Karte von Mittelerde. Da Gandalf ein mächtiger
  Zauberer ist, hat er die Karte  mit Ti\textit{k}Z kodiert. Helfen
  Sie Bilbo diese Karte zu dekodieren und fertigen Sie eine Skizze von
  Mittelerde an. 

\begin{verbatim}
\tikz \graph [no placement] {
  Mordor     [x=2, y=0];
  Gondor     [x=0, y=0];
  Rohan      [x=1, y=1];
  Rhovanion  [x=1, y=2];
  Eriador    [x=-1,y=2];
  Forodwaith [x=0, y=3];
  Eriador    -- Rhovanion;
  Eriador    -- Gondor;
  Eriador    -- Rohan;
  Forodwaith -- Rhovanion;
  Gondor     -- Rohan;
  Mordor     -- Rohan;
  Rhovanion  -- Rohan;
};
\end{verbatim}

  \end{exercise}  

\begin{exercise}[title=Kodieren üben,
                  level=mittel,
                  how=Einzelarbeit,
                  credits=6 Punkte]
  Überlegen Sie sich eine Methode, um Bäume möglichst kompakt
  als Zeichenketten über einem Alphabet Ihrer Wahl zu
  kodieren. Beschreiben Sie Ihre Methode und kodieren Sie den
  folgenden Ausschnitt aus Bilbo Beutlins Stammbaum damit. Geben Sie
  das benutzte Alphabet an.
  
  \begin{center}
  \begin{tikzpicture}[graph,
    edge from parent/.style={draw,->},
    level 1/.style={sibling distance=2.5cm},
    level distance=8.5mm]

    \node {Balbo}
        child {
        node {Mungo}
          child{
          node {Bungo}
            child{node{Bilbo}}
          }
        }
        child {
        node {Largo}
          child{
          node {Fosco}
            child{
            node{Drogo}
              child{node{Frodo}}
            }
          }
        }
    ;
  \end{tikzpicture}
  \end{center}
\end{exercise}

\begin{typical exam problems}

  \begin{exam exercise}[
    title=Worte und Alphabete,
    leicht,
    exam=typical,
    exam minutes=10,
    label=ex.alphabete,
    solution=yes
    ]
    Seien $\Sigma=\{a,b\}$ und $\Gamma=\{b,c\}$ Alphabete. Geben Sie
    an, welches Wort in welcher Sprache enthalten ist.

    \begin{colortabular}{l|l|l|l}
      & $\Sigma^* \setminus \Gamma^* $ & $(\Sigma\cap\Gamma)^*$ & $\Gamma^*\setminus \Sigma$\\\hline
      $ababc$  & & &\\
      $b$      & & &\\
      $bbbb$   & & &\\
      $baab$   & & &
    \end{colortabular}
  \end{exam exercise}

\end{typical exam problems}

\end{lecture exercises}
