\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage{ngerman}
\usepackage{graphicx}
\usepackage{fullpage}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe \arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\N}{\mathbb{N}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
Probeklausur zur Vorlesung

\smallskip
\noindent
\large
\textbf{Informatik A} \hfill WiSe 2015/16\\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule
\smallskip
\noindent
Bearbeitungszeit: mindestens 90 Minuten 

\vskip 0.5cm

\begin{description}

%\newpage
\AUFGABE{Aussagenlogik}{3+3+2+2 Punkte}

Betrachten Sie den folgenden Booleschen Term $t$:
\[
  x \wedge y \vee \neg z \vee (\neg y \vee x \wedge z)
\]

\begin{enumerate}
\item Geben Sie eine vollst\"andige Klammerung f\"ur $t$ an 
 und zeichnen Sie die Baumdarstellung f\"ur $t$.
 Bestimmen Sie den Rang von $t$.
\item
Stellen Sie die Wertetabelle f\"ur die 
dreistellige Boolesche Funktion $f(x,y,z)$ auf,
die durch $t$ definiert ist.
\item Geben Sie die kanonische DNF f\"ur $f(x,y,z)$ an.
\item Wie viele $n$-stellige Boolesche Funktionen gibt es?
Begr\"unden Sie Ihre Antwort.
\end{enumerate}

\AUFGABE{Haskell}{6+4 Punkte}

\begin{enumerate}
  \item Bei welchen der folgenden Zeilen handelt es sich um
    g\"ultige Haskell-Ausdr\"ucke? Geben Sie im positiven
    Fall den Wert und den Typ des Ausdrucks an, begr\"unden
    Sie im negativen Fall, warum der Ausdruck nicht g\"ultig ist.
  \begin{enumerate}
    \item \texttt{if 3 >= 4 then True else 10}
    \item \texttt{10:20:if False then [] else [16,17]}
    \item \texttt{('c', 2+3, even 11)}
  \end{enumerate}

  \emph{Hinweis:} Die Funktion \texttt{even}
  liefert genau dann \texttt{True}, wenn das Argument eine
  gerade Zahl ist.
 \item Definieren Sie eine rekursive Funktion 
   \texttt{int2str}, welche eine 
   \emph{positive} ganze Zahl in einen String umwandelt.
   Zum Beispiel soll \texttt{int2str 10} den String 
   \texttt{``10''} liefern. Geben Sie auch die Signatur an
   und erkl\"aren Sie Ihre Funktion kurz.

   \emph{Hinweise}:
     Um eine Ziffer \texttt{d}, $0 \leq \texttt{d} \leq 9$ 
     in das entsprechende Zeichen umzuwandeln, benutze man den Ausdruck
     \texttt{chr (ord '0' + d)}. 

     Die Funktion \texttt{div::Int -> Int -> Int} f\"uhrt eine
     ganzzahlige Division aus, \texttt{mod::Int -> Int -> Int} liefert
     den Rest. Zum Beispiel ergeben
     \texttt{div 10 3} den Wert \texttt{3} und 
     \texttt{mod 10 3} den Wert \texttt{1}.
\end{enumerate}


\newpage
\AUFGABE{Vermischtes}{3+2+2+3 Punkte}

\begin{enumerate}
  \item
 Testen Sie mit dem Resolutionskalk\"ul  die folgende Formel auf 
 Erf\"ullbarkeit: 
 \[ t = (x \vee y \vee \neg z) \wedge 
   (x \vee \neg y) \wedge (x \vee y \vee z) \wedge \neg x.
 \]

 \item Geben Sie die Definition einer \emph{funktional vollst\"andigen
   logischen Signatur}.
   Beweisen Sie, dass $\{\neg, \vee\}$ funktional vollst\"andig ist.
   Dabei d\"urfen Sie verwenden, dass 
   $\{\neg, \vee, \wedge\}$ funktional vollst\"andig ist.

\item Geben Sie die Definition einer \emph{Typklasse} in Haskell.
  Nennen Sie zwei Operationen der Typklasse \texttt{Ord}.

\item
 Schreiben Sie eine pr\"adikatenlogische Formel, die aussagt, dass 
 f\"ur nat\"urliche
Zahlen gr\"o\ss{}er $1$ gilt, dass zwischen der Zahl und ihrem 
Doppelten mindestens eine Primzahl
liegt. Sie d\"urfen ein Pr\"adikat $\text{isprim}(n)$ benutzen. 

Negieren Sie dann die Formel,
und formen Sie um, bis kein Negationszeichen vor einem Quantor steht.
\end{enumerate}

\AUFGABE{Listen in Haskell}{3+2+5 Punkte}


\begin{enumerate}
  \item Schreiben Sie eine polymorphe und rekursive Funktion
    \texttt{concat}, welche eine Liste von Listen erh\"alt und
    die gegebenen Listen zu einer Liste zusammenf\"uhrt.
    Zum Beispiel soll
    \texttt{concat [[1,2],[2,3]]} das Ergebnis \texttt{[1,2,2,3]} liefern
   und \texttt{concat [[True, False], [], [True]]} soll
     \texttt{[True, False, True]} ergeben.

   Geben Sie auch die Signatur an und erkl\"aren Sie Ihre Funktion.

   \emph{Hinweis}: Der Operator \texttt{++} verbindet zwei Listen
     zu einer neuen Liste.

  \item Implementieren Sie \texttt{concat} aus (a) mit \texttt{foldr}.

    Erkl\"aren Sie, wie Ihre Funktion den Ausdruck
    \texttt{concat [[True, False],[], [True]]} auswertet,
    indem Sie die \texttt{foldr}-Operation explizit ausschreiben.

  \item Sei \texttt{t} ein Typ aus der Typklasse \texttt{Ord}.
    Schreiben Sie eine Funktion \texttt{minmax}, die zu einer
    gegebenen nichtleeren Liste \texttt{xs} vom Typ \texttt{t}
    das Minimum \emph{und} das Maximum bestimmt.
    Ihre Funktion soll durch eine direkte Rekursion implementiert
    sein und die \emph{Akkumulatortechnik} verwenden.

   Geben Sie alle Signaturen an und erkl\"aren Sie Ihre Funktion.
    Zeigen Sie eine schrittweise Auswertung des
    Ausdrucks \texttt{minmax [1,5,0,2]}.
\end{enumerate}
\end{description}
\end{document}
