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

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{am 12. Januar 2016 bis 12 Uhr in die
Tutorenf\"acher}

\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{\B}{\mathbb{B}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}



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


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

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

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM


\vskip 0.5cm

\begin{description}

\AUFGABE{Bin\"are Suchb\"aume I}{10 Punkte}

\begin{enumerate}
  \item F\"ugen Sie die Schl\"ussel I, N, F, O, R, M, A, T, K, Z in dieser
       Reihenfolge in einen anfangs leeren bin\"aren Suchbaum ein. 
       L\"oschen Sie sodann die Schl\"ussel
       Z, O, N. Zeichnen Sie
       den Baum nach jedem Einf\"uge- und L\"oschvorgang.
  \item Angenommen, wir haben einen bin\"aren Suchbaum $T$, welcher die 
  Zahlen von 1 bis 1000 als Schl"ussel speichert. Wir suchen in $T$ nach 
  dem Schl\"ussel 363. Bestimmen Sie f\"ur jede der folgenden 
  Schl\"usselfolgen, ob sie
	als Folge der Markierungen auf dem Suchpfad nach 363 auftreten kann.
	Begr\"unden Sie jeweils Ihre Antwort.
	\begin{enumerate}
            \item 2, 252, 401, 398, 330, 344, 397, 363.
	    \item 924, 220, 911, 244, 898, 258, 362, 363.
	    \item 925, 202, 911, 240, 912, 245, 363.
	    \item 2, 399, 387, 219, 266, 382, 381, 278, 363.
	    \item 935, 278, 347, 621, 299, 392, 358, 363.
	\end{enumerate}
\end{enumerate}

\AUFGABE{Bin\"are Suchb\"aume II}{10 Punkte}

In der Vorlesung hatten wir den algebraischen Datentypen \texttt{SBaum} 
definiert. Implementieren Sie folgende Funktionen.

\begin{enumerate}
\item Bestimme die H\"ohe eines gegebenen Bin\"arbaums.
  \begin{center}
    \texttt{hoehe:: Ord k => SBaum k v -> Int}
  \end{center}
\item Teste, ob ein gegebener Bin\"arbaum die Suchbaumeigenschaft besitzt.
  \begin{center}
    \texttt{istSuchbaum:: Ord k => SBaum k v -> Bool}
  \end{center}
\item Definiere den folgenden Datentypen
  \begin{center}
    \begin{tabbing}
      \texttt{data}  \=\texttt{Suchantwort v = Gefunden v | NichtGefunden} \\
      \>\texttt{deriving Show}
    \end{tabbing}
  \end{center}
  Gegeben einen Suchbaum und einen Schl\"ussel \texttt{s}, suche 
  einen Knoten mit Schl\"ussel \texttt{s}. 
  Im Erfolgsfall soll
  \texttt{Gefunden w} zur\"uckgegeben werden, 
  ansonsten \texttt{NichtGefunden}. Hierbei ist
  \texttt{w} der zu \texttt{s} geh\"orige Wert.
  \begin{center}
    \texttt{suche:: Ord k => SBaum k v -> k -> Suchantwort v}
  \end{center}

\iffalse
  \item 
    In der Vorlesung haben wir Haskell die
    Funktion \texttt{show} auf \texttt{SBaum} 
    mittels ``\texttt{deriving Show}'' automatisch generieren lassen.
    Wir wollen die Stringdarstellung unseres Datentyps \texttt{BBaum}  
    anpassen.
    Entfernen Sie dazu zun\"achst die Zeile \texttt{deriving Show} unter
    \texttt{data SBaum = $\dots$} .
    Deklarieren Sie dann \texttt{SBaum} als Instanz der Typklasse 
    \texttt{Show} und
    implementieren Sie eine eigene Funktion \texttt{show}. Sie k\"onnen sich
    eine eigene Stringdarstellung \"uberlegen, die Struktur des Baums sollte
    aber erkennbar sein.
\fi
\end{enumerate}

\AUFGABE{Boolesche Terme in Haskell}{10 Punkte}

\begin{enumerate}
\item
Definieren Sie einen algebraischen Datentypen
\texttt{BTerm} in 
Haskell, welcher Boolesche Terme repr\"asentiert,
so wie Sie sie zu Beginn der Vorlesung gesehen haben.

\emph{Hinweis}: Sie k\"onnen davon ausgehen,
dass es nur zwei Konstanten gibt: \emph{wahr}
und \emph{falsch}. Ihr Boolescher Term soll
aber potentiell beliebig viele Variablen haben k\"onnen.
Wie k\"onnen Sie das im algebraischen Datentyp
darstellen?

\item
Machen Sie \texttt{BTerm} zu einer Instanz der 
Typklasse \texttt{Show} und implementieren Sie eine
ansprechende Ausgabefunktion.

\item
Definieren Sie Funktionen, um den Rang und die
Variablenmenge eines gegebenen Booleschen Terms zu finden.

\emph{Hinweis}: Sie k\"onnen den Datentypen \texttt{Menge}
vom neunten Aufgabenblatt verwenden. Eine Musterl\"osung wird
am 5.\@ Januar 2016 auf der Website  verlinkt.

\item \emph{(freiwillig, 5 Zusatzpunkte)}
Definieren Sie eine Funktion, welche die Wahrheitstafel zu einem gegebenen
Booleschen Term aufstellt. Benutzen Sie Ihre Funktion, um
einen gegebenen Booleschen Term in einen \"aquivalenten Booleschen
Termin in kanonischer DNF umzuwandeln.
\end{enumerate}
\end{description}

\noindent
Geben Sie immer alle Signaturen an und machen Sie geeignete Testl\"aufe.
Versehen Sie Ihr Skript mit geeigneten Kommentaren.

\end{document}
