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

\begin{document}
\setcounter{page}{3}

\newbox\tabel
\setbox\tabel=\vbox{
}


\def\blatt#1#2#3#4
{
\count0=3
\begin{centering}
{
%\openup 1ex
\large \bf Algorithmen und Programmieren 3
\hfill % Matrikelnummer: \vrule width 3cm height -2.5pt depth 3pt
%
 WS 2003/2004, Endklausur
%\hfill FAMILIENNAME: \vrule width 4cm height -2.5pt depth 3pt


Donnerstag, 19. Februar 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}
% $$

% \vspace{2cm}
% \hrule
% \medskip

% {\openup 1ex
% Umfrage zur Teilnahme an der Nachklausur zur \emph{ersten} Klausur: 
% \begin{tabbing}
%   \hskip 1cm \=\+
% $\Box$\quad
% Ich habe die erste Teilklausur schon bestanden.\\
% $\Box$\quad
% \parbox[t]{14cm}{Ich werde am Donnerstag, den 26. 2. 2004, von 14--16 Uhr (heute in
% einer Woche) zur Nachklausur zur ersten Teilklausur antreten.}\\[2ex]
% $\Box$\quad
% Ich werde am  Dienstag, den 6. 4. 2004 zur Nachklausur zur ersten Teilklausur antreten.\\
% $\Box$\quad
%  weiß nicht
% \end{tabbing}
% }

% \hrule
% \medskip
% \eject
\begin{enumerate}
\parskip=0,1\parskip
%\itemsep=0pt
\item \aufgabe #1
\item \aufgabe #2
\item \aufgabe #3
\item \aufgabe #4
\end{enumerate}
%%%\eject
}

\newbox\prog
\setbox\prog= \vbox{
\begin{verbatim}
class Menge100
{  boolean [ ] a = new boolean[100];
   int größe = 0;
   public void enfügen(int x)
   {  if(a[x-1]==false) { a[x-1]=true; größe++; }
   }
   public boolean istleer() { return größe==0; }
   ...
}
\end{verbatim}}

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

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

Die folgende Java-Klasse implementiert (teilweise)
die Mengenoperationen für Mengen, die Teilmengen von
$\{1,2,\ldots,100\}$ sind.
\\
\vbox{\vskip -1ex \moveright 1cm\copy\prog\vskip -2ex}\\
% Die Klass
Geben Sie die Abstraktionsfunktion und die Darstellungsinvariante
an,
und beweisen Sie, dass die Operationen \texttt{einfügen} und
\texttt{istleer} (mit geeigneten Vorbedingungen, falls nötig)
korrekt implementiert sind.


\or % \item %(10 Punkte)
Eine Zeichenkette $p_1p_2\ldots p_m$ hei"st
\emph{periodisch} mit Periode $k$, ($1\le k \le m$) wenn
$p_i=p_{i+k}$ f"ur $1\le i<i+k\le m$ ist,
mit anderen Worten, wenn
$$p_1\ldots p_{m-k} = p_{k+1}\ldots p_m$$
ist. (F"ur $k=m$ ist die Folge unperiodisch.)
\begin{enumerate}
\item (3 Punkte)
Bestimmen Sie die Periode und berechnen sie die Verschiebefunktion $h$ f"ur das Muster
$ababcababcabab$.
Verwenden Sie die % urspr"ungliche 
Definition der Verschiebefunktion
aus der Vorlesung.%
\footnote
{Die urspr"ungliche Definition der Verschiebefunktion aus der Vorlesung lautet
\hrule height 0pt
$$
h_i = 
\max \ \{\,k\mid 1\le k<i,\ p_1\ldots p_{k-1} = p_{i-k+1}\ldots p_{i-1}
\,\}\cup \{0\}
 \textrm{,\qquad f"ur $i\ge 1$}.
$$
Die verbesserte Verschiebefunktion vom 12. "Ubungsblatt 
ist so definiert:
\hrule height 0pt\vskip -0,2ex\hrule height 0pt
$$
h_i = 
% \begin{cases}
\max \ \{\,k\mid 1\le k<i,\ p_1\ldots p_{k-1} = p_{i-k+1}\ldots p_{i-1}
\textrm{ und } p_k \ne p_i \,\}\cup \{0\}
 \textrm{,\qquad f"ur $i\ge 1$}.
% end{cases}
$$
}
Berechnen Sie auch den Wert $h(m+1)$.
\item (0 Punkte) %, ohne Bewertung)
Berechnen sie die Verschiebefunktion f"ur % das Muster
$abcabcabcab$.
\item (7 Punkte)
Wie kann man mit Hilfe der Verschiebefunktion die
(kleinste) Periode~$k$ einer Zeichenkette bestimmen?
\end{enumerate}


\or % \item

Konstruieren Sie mit dem Huffman-Algorithmus einen optimalen
Kode für die Verteilung
$\def\f##1{\frac{##1}{25}}(p_1,\ldots,p_6)=(\f8,\f2,\f1,\f5,\f5,\f4)$.
Zeigen Sie in einzelnen Schritten, wie der Algorithmus abläuft, und
zeichnen Sie den optimalen Kode-Baum.

Ist der optimale Kode eindeutig?


\or % \item %(10 Punkte)
Leiten Sie aus der algebraischen Spezifikation f\"ur Mengen
 \begin{eqnarray}
\textit{istenthalten}(x,\textit{leer}\/) &=& \textit{falsch} \\[-1pt]
\textit{istenthalten}(x,\textit{einf\"uge}(x,M)) &=& \textit{wahr} \\[-3pt]
\textit{istenthalten}(x,\textit{einf\"uge}(y,M)) &=&
\textit{istenthalten}(x,M), \qquad \textrm{f\"ur $x\ne y$}\\[-1pt]
\textit{istenthalten}(x,\textit{l\"osche}(x,M)) &=& \textit{falsch} \\[-3pt]
\textit{istenthalten}(x,\textit{l\"osche}(y,M)) &=&
\textit{istenthalten}(x,M), \qquad \textrm{f\"ur $x\ne y$}
  \end{eqnarray}
%durch Umformungen
 folgende Identit"at her:
$$
\textit{istenthalten}(u,
\textit{einf\"uge}(x,
\textit{l\"osche}(u,
M))) =
\textit{istenthalten}(u,
\textit{einf\"uge}(x,
\textit{leer}))
$$
Geben Sie dabei in jedem Beweisschritt die Nummer der verwendeten Gleichung an.

\fi
}

\blatt 1234
\end{document}
