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

\newcommand{\ZETTELNUMMER}{8}
\newcommand{\ABGABEDATUM}{am 15. Dezember 2015 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{H\"aufigkeiten mit Funktionen h\"oherer Ordnung}{10 Punkte}

Auf der Veranstaltungswebsite finden Sie das Haskell-Skript
zur 14.\@ und zur 15.\@ Vorlesung. In der 15.\@ Vorlesung
wurde die  H\"aufigkeitsanalyse
unter Verwendung von Funktionen h\"oherer Ordnung
neu implementiert. Vergleichen Sie die beiden Implementierungen.
Beantworten Sie dann folgende Fragen:
\begin{enumerate}
  \item Erkl\"aren Sie die neue Definition von \texttt{haeufigkeit}.
    Warum ist der Parameter \texttt{cs} nicht aufgef\"uhrt?
  \item
    Was macht die Funktion \texttt{scanr}? Geben Sie ein
    einfaches Beispiel f\"ur eine Anwendung von \texttt{scanr},
    das nicht im Vorlesungsskript vorkommt.
  \item  Wie unterscheidet sich die Funktion \texttt{erhoehe}
    aus der 15.~Vorlesung von der Funktion \texttt{erhoehe} aus der
    14.~Vorlesung?
  \item  Liefert die Funktion \texttt{haeufigkeit} aus der 15.\@
    Vorlesung das gleiche Ergebnis wie in der 14.\@ Vorlesung?
    Begr\"unden Sie Ihre Antwort im Detail.
  \item Was macht die Funktion \texttt{foldl1} in der
    neuen Implementierung von \texttt{sortiere}?
  \item Was bedeutet der Ausdruck \texttt{(/= erster)}
    in der neuen Implementierung von \texttt{sortiere}?
\end{enumerate}


\AUFGABE{Sortieren, Ausw\"ahlen, Suchen}{10 Punkte}

\begin{enumerate}
\item Schreiben Sie die Funktion \texttt{sortiere} aus
der Vorlesung so um, dass man sie auf beliebige Typen aus der Typklasse
 \texttt{Ord} anwenden kann.
\item
Sei \texttt{xs::[t]} eine Liste, wobei \texttt{t} ein
Typ aus der Typklasse \texttt{Ord} ist.
Sei $n$ die L\"ange von \texttt{xs}.
Der \emph{Median}  von \texttt{xs}  ist der Eintrag, der an 
Position $\lfloor n/2\rfloor$
steht, nachdem \texttt{xs} sortiert wurde. 

Schreiben Sie eine Funktion
\texttt{median}, die diesen bestimmt.
\item 
Implementieren Sie eine Funktion
\texttt{isSubstr:: (String, String) -> Bool}.
Diese sollen testen, ob in dem Eingabestringpaar der erste String 
\emph{Teilstring} des zweiten ist. 

Dabei ist ein String Teilstring eines anderen, 
wenn er als Teilwort von aufeinander
folgenden Zeichen auftritt. 
Zum Beispiel ist ``orma'' ein Teilstring von ``informatika'', 
``ioa'' aber nicht.
Gro\ss-- und Kleinschreibung soll ignoriert werden.
\end{enumerate}

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

\AUFGABE{Listen}{10 Punkte}

\begin{enumerate}
\item
Sei \texttt{xs::[t]} eine Liste, wobei \texttt{t} ein
Typ aus der Typklasse \texttt{Show} ist.
Schreiben Sie eine Funktion \texttt{druckeListe},
welche die Eintr\"age aus \texttt{xs} einzeln Zeile f\"ur Zeile 
ausgibt.

\emph{Hinweis}: Benutzen Sie \texttt{putStr}.
  Was ist der R\"uckgabetyp?

\item 
Eine \emph{Listenzahl} ist eine Folge von Ziffern, welche
als Liste dargestellt wird und eine nat\"urliche
Zahl repr\"asentiert. Beispielsweise repr\"asentiert die
Listenzahl \texttt{[1,4,3,5]} die Zahl 1435.

Benutzen Sie \texttt{foldl}, um eine Funktion
\texttt{dec2int} zu implementieren, welche eine
Listenzahl in den zugeh\"origen \texttt{Int} umwandelt.
Zum Beispiel soll
\texttt{dec2int [1,4,3,5]} das Ergebnis \texttt{1435} haben.

\item 
Schreiben Sie eine Funktion 
\texttt{addiere::[Int]->[Int]->[Int]},
welche zwei gegebene Listenzahlen addiert.
Ihre Funktion soll direkt auf Listenzahlen
arbeiten. Ein Umweg \"uber \texttt{Int} oder
\texttt{Integer} ist nicht erlaubt.

\emph{Achtung}: Bei einer g\"ultigen Listenzahl sind nur
 die Ziffern $0$ bis $9$ erlaubt. F\"uhrende Nullen sind auch
 nicht zul\"assig.
\end{enumerate}

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


\end{description}
\end{document}
