%  Zwischenklausur ALP3 WS 2003/2004
\documentclass [11pt] {article}
\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=15,5cm
\textheight=24cm
\hoffset = -17mm
\voffset = -25mm

\begin{document}



\def\blatt#1#2#3#4
{
\count0=5
\begin{centering}
{
\openup 1ex
\large \bf Algorithmen und Programmieren 3
\hfill Matrikelnummer: \vrule width 3cm height -2.5pt depth 3pt


 Nachklausur zur Endklausur
\hfill FAMILIENNAME: \vrule width 4cm height -2.5pt depth 3pt

WS 2003/2004.
Dienstag, 6. April 2004.
\hfill Vorname: \vrule width 4cm height -2.5pt depth 3pt
\par}
\bigskip
\par \bigskip
\end{centering}
\hrule
\medskip

\noindent \emph{Anleitung}:
Streichen Sie \emph{eine} Aufgabe deutlich auf dem Angabeblatt.
Diese Aufgabe wird nicht in die Bewertung einbezogen.
Wenn Sie selbst keine Aufgabe streichen, wird die erste
Aufgabe nicht in die Bewertung einbezogen.
Bearbeiten Sie die "ubrigen drei Aufgaben.

\medskip

%\emph{Alle Antworten sind zu begründen!}
%
%\medskip

\emph{Bearbeiten Sie jede Aufgabe auf einem getrennten Blatt.}
Jede Aufgabe hat 10 Punkte. Bearbeitungszeit: 90 Minuten

$$
\begin{tabular}[c]{|l|c|c|c|c|c|}
\hline
Aufgabe&1&2&3&4&Summe\\
\hline
Punkte&10&10&10&10&30\\
\hline
Punkte&&&&&\\
\hline
\end{tabular}
$$
\bigskip
\hrule
\medskip
\begin{enumerate}
%\parskip=0,5\parskip
%\itemsep=0pt
\item \aufgabe #1
\item \aufgabe #2
\eject
\item \aufgabe #3
\item \aufgabe #4
\end{enumerate}
%%%\eject
}

\newbox\prog
\setbox\prog= \vbox{
\begin{verbatim}
class Menge100
{
}
\end{verbatim}}

\def\punkt#1 #2 #3 {\put(#1,#2){\circle*{3}}
\put(#1,#2){\put(-4,4){\mbox{$P_#3$}}}}

\newbox\progg
\setbox\progg=\vbox{
\begin{verbatim}
int anz(int[ ] a, int[ ] b, int n) { return anz2(a,b,n,0); }
\end{verbatim}}

\long\def\aufgabe #1{\ifcase #1\or
%\item %(10 Punkte)

Eine st"uckweise lineare Funktionen  $f\colon (u,v]\to \mathbb{R}$ ist
durch eine zusammenh"angende
Folge von Intervallen mit entsprechenden linearen Funktionen
$f(x)=ax+b$ für jedes Intervall gegeben, z. B.
$$f(x)=
\begin{cases}
-x,&\text{ f"ur $-1<x\le 0$}\\
2x,&\text{ f"ur $0<x\le2$}\\
-3x+9,&\text{ f"ur $2< x \le 4$}
\end{cases}
$$
% Geben Sie wahlweise eine \emph{algebraische} oder eine
% \emph{modellierende} Spezifikation für einen abstrakten Datentyp
% zur Darstellung solcher Funktionen.
Die Datenstruktur soll % zumindest
folgende Operationen erlauben:
\begin{enumerate}
\item Erzeugen einer Funktion $f(x)=ax+b$ mit einem einzigen Intervall
$(u,v]$.
\item
Berechnung des Wertes einer solche Funktion $f(x)$ an einer
gegebenen Stelle~$x$.
% Falls $x$ nicht im Definitionsbereich liegt, soll der Wert 0 zur"uckgegeben werden.
\item Addition zweier st"uckweise linearer Funktionen.
\end{enumerate}
Nehmen Sie der Einfachheit halber
 an, dass alle Intervalle
halboffen sind, und zwar links offen und rechts abgeschlossen,
wie im obigen Beispiel.

Der Datentyp ist durch die folgenden Axiome (mit geeigneten
Signaturen) algebraisch spezifiziert:
\begin{eqnarray*}
  \textit{berechne}(\textit{stLinFun}(u,v,a,b),x) &=& 
  \begin{cases}
    ax+b, & \text{für $u\le x<v$}\\
    0,&\text{sonst}
  \end{cases}\\
  \textit{berechne}( \textit{add}(f,g),x) &=&
  \textit{berechne}(f,x)+
  \textit{berechne}(g,x)
\end{eqnarray*}


Implementieren Sie diesen Datentyp % mit den ersten beiden Operationen 
in Java oder Haskell
und beweisen Sie die Korrektheit.
%  (Geben Sie im Fall einer
% modellierenden Spezifikation die Abstraktionsfunktion, die
% Darstellungsinvariante, sowie die Vorbedingungen an.)

\or % \item %(10 Punkte)
\def\ez{Erd\H os-Zahl}
Die sogenannte \emph{Erd\H
  os-Zahl}\footnote{\texttt{http://personalwebs.oakland.edu/\char`\~grossman/erdoshp.html}} ist nach dem berühmten ungarischen Mathematiker Paul
{Erd\H os}
(1913--1996) benannt.
Er selbst hat \ez~0. Alle seine Koautoren, mit denen er
wissenschaftliche Arbeiten publiziert hat, haben \ez~1.
Wer eine gemeinsame Arbeit mit jemandem mit \ez\ 1 geschrieben hat,
aber nicht mit Erd\H os selbst, hat \ez~2, und so weiter.
Personen, die nicht auf diese Weise mit Erd\H os verbunden sind, haben \ez~$\infty$.

Der \emph{Kollaborationsgraph} enthält alle lebenden oder toten
Personen als Knoten. Zwei Knoten sind durch eine Kante verbunden,
wenn die beiden Personen gemeinsame Autoren einer wissenschaftlichen
Publikation sind.

\begin{enumerate}
\item Geben Sie einen \emph{Algorithmus} an, der für eine gegebene
  Person im Kollaborationsgraphen die \ez\ berechnet.

\item Geben Sie einen Algorithmus an, der 
% in der   Zusammenhangskomponente von Erd\H os 
die größte endliche \ez\ bestimmt.

\end{enumerate}
Algorithmen aus der Vorlesung können Sie direkt verwenden; die müssen
Sie nicht ``ausprogrammieren''.

\or % \item
\begin{enumerate}
\item (5 Punkte)
Zeichne sie den
\begin{enumerate}
\item digitalen Suchbaum
\item den komprimierten digitalen Suchbaum
\end{enumerate}
für die Bitketten
\texttt{0011000101},
\texttt{001111001},
\texttt{01011},
\texttt{00111111},
\texttt{01010},
\texttt{001101}.
Zeigen Sie, wie die Bäume nach dem Einfügen des Wertes
\texttt{0011000} aussehen.
Entfernen Sie
\texttt{001111001} und zeichnen Sie die Bäume danach.
\item (5 Punkte) 
Wie kann man aus der Verschiebefunktion des Wortes $x\#w\$$ berechnen,
ob $x$ ein Teilwort von $w$ ist? (Hier sind \# und \$ neue Buchstaben,
die nicht in $x$ und $w$ vorkommen.) \emph{Begründen Sie Ihre Antwort!}
\end{enumerate}

\or % \item %(10 Punkte)

Bestimmen Sie die untere konvexe Hülle der folgenden sortierten
 Punktmenge
$P_1,\ldots,P_9$ mit
dem inkrementellen Algorithmus aus der Vorlesung.
Geben Sie die Folge der Orientierungstests an, die der Algorithmus
 ausführt.
 \begin{center}
   \fbox{
 \begin{picture}(300,120)
\punkt 10 40 1
\punkt 30 105 2
\punkt 65 95 3
\punkt 95 60 4
\punkt 140 90 5
\punkt 180 40 6
\punkt 200 10 7
\punkt 250 80 8
\punkt 280 90 9
 \end{picture}
}

 \end{center}

\fi
}

\def\alleperm
{
\blatt 1234
\blatt 2341
\blatt 3412
\blatt 4123

\blatt 1243
\blatt 2431
\blatt 4312
\blatt 3124

\blatt 1432
\blatt 4321
\blatt 3214
\blatt 2143

\blatt 1423
\blatt 4231
\blatt 2314
\blatt 3142

\blatt 1342
\blatt 3421
\blatt 4213
\blatt 2134

\blatt 1324
\blatt 3241
\blatt 2413
\blatt 4132
}

\blatt 2314
%\end{document}

\end{document}

\alleperm

%\blatt 1234
\end{document}

