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

\newcommand{\ZETTELNUMMER}{11}
\newcommand{\ABGABEDATUM}{am 19. 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{Traversieren von bin\"aren Suchb\"aumen}{10 Punkte}

Eine \emph{Traversierung} eines bin\"aren Suchbaums
$T$ ist eine Funktion, welche alle Knoten von $T$
systematisch besucht und die gesehenen Eintr\"age in einer
Liste zur\"uckgibt.
Es gibt vier Arten der Traversierung:
\begin{itemize}
\item \textbf{Preorder}: Besuche erst die Wurzel,
  dann rekursiv das linke Kind, gefolgt von dem rechten Kind.
\item \textbf{Inorder}: Besuche erst rekursiv das linke Kind,
  danach die Wurzel, dann das rechte Kind.
\item \textbf{Postorder}: Besuche erst rekursiv das linke Kind,
  dann das rechte Kind  und schlie\ss{}lich die Wurzel.
\item \textbf{Levelorder}: Besuche die Knoten nach
  aufsteigender Tiefe und alle Knoten mit der gleichen
  Tiefe von links nach rechts.
\end{itemize}

Bearbeiten Sie die folgenden Aufgaben:
\begin{enumerate}
\item Schreiben Sie Funktionen
  \texttt{preorder}, \texttt{inorder}, \texttt{postorder},
  \texttt{levelorder:: Ord k => SBaum k v -> [(k,v)]},
  welche die vier Traversierungsarten implementieren.
\item Beweisen Sie durch Induktion: Wenn wir die Eintr\"age
eines bin\"aren Suchbaums in Inorder ausgeben, dann sind
die Schl\"ussel in den Eintr\"agen aufsteigend sortiert.
\item
Die Preorder-Traversierung eines bin\"aren Suchbaums mit
10 Eintr\"agen ergibt die folgende Schl\"usselfolge:
M B A F D P N O Z R. Die Postorder-Traversierung liefert
A D F B O N R Z P M. Wie sieht der Baum aus?
\end{enumerate}

\AUFGABE{Algorithmische Probleme}{10 Punkte}

Betrachten Sie das algorithmische Problem
\textsc{AlleVerschieden}:
\begin{itemize}
  \item \textbf{Eingabe}: Eine Liste \texttt{xs::[t]},
  wobei \texttt{t} in der Typklasse \texttt{Ord} enthalten ist.
  \item \textbf{Ausgabe}: \texttt{True}, falls alle
    Elemente in \texttt{xs} paarweise verschieden sind, 
    und \texttt{False}, sonst.
\end{itemize}
Im folgenden sehen Sie drei Algorithmen, die
\textsc{AlleVerschieden} l\"osen sollen.
Welche Algorithmen sind korrekt?
Wenn ein Algorithmus nicht korrekt ist, geben Sie ein
Gegenbeispiel. Wenn ein Algorithmus korrekt ist,
bewerten Sie seine Effizienz, indem Sie die Anzahl
von Vergleichen absch\"atzen, die er ben\"otigt (in 
Abh\"angigkeit von der Listenl\"ange $n$).

\begin{verbatim}
-- Erster Algorithmus
av1::Ord t => [t] -> Bool
av1 []  = True
av1 [x] = True
av1 (x1:(x2:xs)) 
  | x1 /= x2   = av1 (x2:xs)
  | otherwise = False

-- Zweiter Algorithmus
av2::Ord t => [t] -> Bool
av2 []     = True
av2 (x:xs) = xunique && av2 xs
  where 
    xunique = (filter (==x) xs) == []

-- Dritter Algorithmus
av3::Ord t => [t] -> Bool
av3 = av1 . msort

-- Merge Sort
msort::Ord t => [t] -> [t]
msort []  = []
msort [x] = [x]
msort xs  = merge ys zs
  where 
    ys = msort (take half xs)
    zs = msort (drop half xs)
    half = (length xs) `div` 2
merge::Ord t => [t] -> [t] -> [t]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y    = x:merge xs (y:ys)
  | otherwise = y:merge (x:xs) ys
\end{verbatim}

\AUFGABE{Sortieren}{10 Punkte}

\begin{enumerate}
\item 
Geben Sie eine Permutation der Ziffern 1 bis 8 an, bei deren 
Eingabe Merge Sort die
maximale Anzahl von Vergleichen t\"atigt. Wieviele sind das?
\item
Analysieren Sie die Anzahl der Vergleiche beim Standardquicksort 
(Pivot ist der Kopf
der Liste), wenn die Eingabefolge der L\"ange $n$ absteigend sortiert ist.
\item
Wie viele Vergleiche ben\"otigt der Insertion Sort Algorithmus
aus der Vorlesung, wenn
die Eingabefolge der L\"ange $n$ aufsteigend sortiert ist?
\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}
