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

\newcommand{\ZETTELNUMMER}{12}
\newcommand{\ABGABEDATUM}{am 26. 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

\noindent
Dies ist das vorletzte Aufgabenblatt.

\vskip 0.5cm

\begin{description}

\AUFGABE{Bottom-Up Merge-Sort}{10 Punkte}

\emph{Bottom-Up Merge Sort} ist eine Variante
von Merge-Sort, welche die Mischoperation ``von unten'' 
durchf\"uhrt.
Es funktioniert folgenderma\ss{}en:
\begin{itemize}
  \item Wandle die Eingabeliste \texttt{xs::[t]}
  um in eine Liste von Listen \texttt{xss::[[t]]},
  welche f\"ur jedes Element \texttt{x} aus 
  \texttt{xs} genau eine Liste der Form \texttt{[x]}
  enth\"alt.
  \item Solange \texttt{xss} mehr als eine Liste
    enth\"alt, gehe \texttt{xss} durch und mische 
    benachbarte Listen mit Hilfe von \texttt{merge}.
  \item Gib die verbleibende Liste in \texttt{xss} zur\"uck.
\end{itemize}
Bearbeiten Sie die folgenden Aufgaben:
\begin{enumerate}
  \item Implementieren Sie Bottom-Up Merge Sort in
    Haskell.
  \item Sch\"atzen Sie ab, wie viele Vergleiche
    Bottom-Up Merge Sort ben\"otigt.
\end{enumerate}

\AUFGABE{Induktion}{10 Punkte}

\begin{enumerate}
\item
Beweisen Sie mittels struktureller Induktion,
dass f\"ur alle endlichen Listen (von Listen) 
\texttt{xss} und alle Funktionen \texttt{f} gilt:
\[
\texttt{concat (map (map f) xss) = map f (concat xss)}.
\]
Zur Erinnerung:
\begin{verbatim}
(++)::[a] -> [a] -> [a]
[] ++ ys    = ys                    -- ++.1
(x:xs) ++ ys = x:(xs ++ ys)         -- ++.2

concat::[[a]] -> [a]
concat []       = []                --concat.1
concat (xs:xss) = xs ++ concat xss  --concat.2

map::(a -> b) -> [a] -> [b]
map g []     = []                   --map.1
map g (y:ys) = g y : map g ys       --map.2
\end{verbatim}

\emph{Hinweis}: Beweisen Sie zun\"achst folgendes
Lemma: F\"ur alle endlichen Listen
\texttt{xs,ys::[a]} gilt:
\[
\texttt{map f (xs ++ ys) = map f xs ++ map f ys}.
\]
\item
Zeigen Sie mit vollst\"andiger Induktion, dass 
f\"ur alle nat\"urlichen Zahlen 
\texttt{n} gilt:
\[
\texttt{iter n id = id}.
\]
Dabei ist die Iterationsfunktion defininiert durch
\begin{verbatim}
iter::Int -> (a -> a) -> (a -> a)
iter n f
| n > 0     = f . iter (n - 1) f --iter.1
| otherwise = id                 --iter.2
\end{verbatim}
und \texttt{id::a -> a} ist die polymorphe 
Identit\"atsfunktion, durch 
\begin{verbatim}
id x = x  --id.1
\end{verbatim} 
gegeben.
Der \texttt{.}-Operator beschreibt die 
Funktionskomposition: f\"ur Funktionen \texttt{g::a -> b} und 
\texttt{f::b -> c} hat die Funktionskomposition 
\texttt{f . g} die Signatur \texttt{f . g::a -> c} und
\begin{verbatim}
(f . g) x = f (g x)  -- .1
\end{verbatim}
\end{enumerate}

\AUFGABE{Codierung}{10 Punkte}

Der \emph{Kreuzsicherungscode}
wandelt ein $0$-$1$-Wort
der L\"ange $n^2$ in ein $0$-$1$-Wort der 
L\"ange $n^2 + 2n$ um, indem er die Eingabe
als $n \times n$-Matrix auffasst und 
f\"ur jede der $n$ Zeilen und $n$ Spalten jeweils ein Parit\"atsbit
anh\"angt.

\begin{enumerate}
\item
Zeigen Sie: Der Kreuzsicherungscode ist $1$-fehlerkorrigierend.
\item
Schreiben Sie eine Kodierungsfunktion 
\texttt{encode::Int -> [Int] -> [Int]}
f\"ur den Kreuzsicherungscode. Dabei
soll der erste Parameter die 
Dimension $n$ der Code-Matrix  angeben.

Definieren Sie dazu zun\"achst geeignete Teilaufgaben.
Achten Sie im Sinne der Wiederverwendbarkeit darauf,
Ihre Funktionen so allgemein wie m\"oglich zu halten. 
\item (freiwillig, 5 Zusatzpunkte)
Geben Sie eine Implementierung einer 
 funktionierenden 1-fehlerkorrigierenden Decodierfunktion
 f\"ur den Kreuzsicherungscode.
\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}
