%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% /vol/tex/inputs/latex/local/anwendungsbericht_muster.tex
% Beispiel fuer das Layout eines Anwendungsberichts des ZPR
% 22.12.94 Michael Wottawa (wottawa@zpr.uni-koeln.de)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[din_a4, german, anwendungsbericht]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Verwendete Standard-Style-Files:
%      din_a4.sty       zur Anpassung der Blattgroesse
%      german.sty       fuer die deutschen Sonderzeichen
%      epsf.sty         wird von anwendungsbericht.sty geladen
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% anwendungsbericht.sty findet man auf den ZPR-Rechnern (z.B. Fileserv1) unter
%
% /vol/tex/inputs/latex/local/anwendungsbericht.sty
% Zusaetzlich benoetigt man die Logos
% /vol/tex/inputs/latex/local/uni-logo.eps
% /vol/tex/inputs/latex/local/zprlogo.eps
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frenchspacing
\parindent 0pt
\parskip 4pt

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Befehle aus anwendungsbericht.sty:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\kooperationspartner{(in Kooperation mit XXXX Ltd.)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% optionaler Parameter zur Erweiterung der "Uberschrift
% ''Zentrum f"ur Paralleles Rechnen''
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\leftpicture{uni-logo.eps}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% optionaler Parameter f"ur das Logo des Kooperationspartners in der linken
% oberen Ecke (Default: Uni-Logo)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\arbeitsgruppe{Prof. Dr. Zacharias P. Rastlos}
%\telefon{123456}
%\telefax{654321}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% optionale Parameter zur Angabe der Arbeitsgruppe in der Fusszeile
% (Default: 'Prof. Dr. A. Bachem', '470--6030', '470--5160')
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\kopf{25}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Aufruf des Anwendungsbericht-Layouts mit der laufenden Nummer ('x')
% des Anwendungsberichts. Die laufende Nummer wird zentral
% (zpr@zpr oder wottawa@zpr) eindeutig festgelegt.
%
% WICHTIG: \kopf muss hinter den Definitionen von \kooperationspartner,
%              \leftpicture, \arbeitsgruppe, \telefon und \telefax stehen.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ende der Befehle aus anwendungsbericht.sty:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Layout-Vorschlag fuer den Text:
%
% Vorderseite:        Rueckseite:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%     Kopfzeile     %                  %
% ----------------- %     abbildung    %
% LOGO      abbild  %     abbildung    %
%           ung ab  %     abbildung    %
% texttext  bildun  %                  %
% texttex   g abbi  % texttexttexttext %
% texttext          % texttexttexttext %
% texttexttexttext  % texttexttexttext %
% texttexttexttext  % texttexttexttext %
% texttexttexttext  % texttexttexttext %
% texttexttexttext  % texttexttexttext %
% texttexttexttext  % texttexttexttext %
% texttexttexttext  % ---------------- %
% texttexttexttext  % Ansprechpartner: %
% texttexttexttext  % .......          %
% ----------------- % ......           %
%     Fusszeile     % Stand: ...       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mbox{
  \begin{minipage}[b]{7.5cm}
    \begin{center}
      \
      \epsfxsize=5.5cm
      \rule[-5mm]{0cm}{1cm} \huge CATBox++
%      \epsfbox{logo.ps}
    \end{center}
    CATBox++ ist ein inter\-ak\-ti\-ves, in\-te\-grier\-tes
    Text-Vi\-sua\-li\-sie\-rungs-Lern\-system f"ur eine Auswahl
    kombinatorischer Algorithmen. Ziel ist es, dem Nutzer eine
    Einf"uhrung in die Theorie und Anwendung kombinatorischer und
    graphentheoretischer Algorithmen zu geben. Dies soll in der
    CATBOX++ durch Kom\-bi\-na\-tion von Buch und Begleitsoftware
    erreicht werden. Im Buch werden kombinatorische Probleme anhand
    von praktischen Anwendungsproblemen motiviert und auf Modellierung
    und L"osungsans"atze eingegangen. Die Software visualisiert die
    algorithmischen L"osungen und soll so das Verst"andnis der
    Verfahren erleichtern und vertiefen.
  \end{minipage}
  \hspace{5.1mm}
%  \fbox{\rule{0cm}{7.5cm}\makebox[6cm]{Photo}}
      \epsfxsize=7.5cm
      \epsfbox{cat-bild.ps}
}

\section*{Konzeption}

Das Ziel der CATBox++ ist die Veranschaulichung geschickter
kombinatorischer Ideen und moderner Datenstrukturtechniken anhand
einiger ausgew"ahlter kombinatorischer Algorithmen, um das
Verst"andnis der Verfahren zu erleichtern. Die CATBox++ ist eine
objektorientierte Neukonzeption einer Idee unserer Arbeitsgruppe aus
dem Jahre 1987, die mit der in Pascal unter DOS implementierten CATBox
({\bf C}ombinatorial {\bf A}lgorithm {\bf T}ool{\bf Box}) verwirklicht
wurde und die die Arbeitsweise kombinatorischer Algorithmen durch
Animation ihres Ablaufs visuell darstellen sollte.

Die Erfahrungen mit dem bestehenden System haben gezeigt, da"s das
Vorhandensein eines Begleitbuches f"ur den didaktischen Einsatz z.B.\ 
in einer Vorlesung unabdingbar ist. Der Nutzen eines solchen Systems
wird im Sinne des visuell unterst"utzten Lernens durch M"oglichkeiten
der Interaktion mit dem Programm deutlich erh"oht.

Die CATBox++ ist daher als Buch mit interaktiver Begleitsoftware
konzipiert. Die objektorientierte Programmierung in C++ soll nicht
zuletzt erm"oglichen, ein erstelltes Programm ohne zu gro"sen Aufwand
um zus\"atzliche Algorithmen zu erweitern. Das Produkt richtet sich an
Kursteilnehmer der Mathematik und Informatik in der gymnasialen
Oberstufe, jeden algorithmisch oder mathematisch Interessierten und an
H"orer von Hochschulvorlesungen zum Thema. Partner f"ur den
Vertrieb ist der Springer--Verlag.

\section*{Aufbau des Buches}

Das Buch wird in sechs Kapitel gegliedert, deren Themen sich
hinsichtlich des Schwierigkeitsgrads steigern. Im ersten Kapitel wird
das Minimal--Spannender--Baum--Problem und seine erfolgreiche L"osung
mit der denkbar einfachsten Idee vorgestellt. Kapitel 2, 3 und 4
widmen sich dem K"urzeste--Wege--Problem, dem
Maximaler--Flu"s--Problem und dem Kardinalit"atsmatching. Im f"unften
Kapitel wird das Konzept der Dualit"at durch Wiederbetrachtung des
Minimal--Spannender--Baum--Problems eingef"uhrt und an den anderen
schon betrachteten Problemen erl"autert. Das letzte Kapitel behandelt
die primal--dualen Algorithmen zur L"osung der gewichteten
Matching--Probleme.

In jedem Kapitel wird die Besch"aftigung mit der Problemklasse durch
eine Reihe von praktischen Problemen motiviert. Im Anschlu"s werden
"Uberlegungen vorgestellt, die zur L"osung des Problems geeignet
scheinen und deren Erfolg bzw.\ Mi"serfolg anhand der vorgestellten
praktischen Probleme erl"autert und begr"undet. Erfolgreiche Ideen
werden zu Algorithmen konkretisiert, deren Funktionsweise im
Begleitprogramm verfolgt werden kann. Der Hauptteil des Textes wird
allgemeinverst"andlich, in enger Anlehnung an die praktischen
Beispiele geschrieben. In besonders gekennzeichneten Abschnitten
werden die mathematischen Grundlagen dargestellt; diese Abschnitte des
Textes kann der Leser "ubergehen, ohne Schwierigkeiten im Verst"andnis
des nachfolgenden Haupttextes bef"urchten zu m"ussen.

\section*{Beschreibung des Programms}

Die heute "ubliche Fenstertechnik in Windows oder unter X erlaubt es,
gleichzeitig verschiedene Blickwinkel auf das gleiche Objekt
vorzustellen. Die behandelten Algorithmen werden in zwei, ggf.\ drei
Fenstern dargestellt. Das {\em Graphikfenster} enth"alt eine
graphische Darstellung des Beispielgraphen, auf den der Algorithmus
angewendet wird. Durch F"arbungen oder andere optische Hilfsmittel
wird der Ablauf des Algorithmus visualisiert.  Im {\em
  Algorithmusfenster} wird der Algorithmus in einer
Pseudoprogrammiersprache angezeigt. In der Grundeinstellung
wird der Algorithmus im "Uberblick geboten, die Umsetzung einer
Anweisung kann sich der Benutzer in detaillierterer Form anzeigen
lassen, indem er die entsprechende Zeile ausw"ahlt. Im {\em
  Datenfenster} werden ggf.\ die Datenstrukturen dargestellt,
die f"ur den Ablauf des Algorithmus entscheidend sind.

Der Benutzer hat die M"oglichkeit interaktiv den Ablauf des
Algorithmus zu beeinflussen. Das Algorithmusfenster hat
Debugging--Eigenschaften: der Benutzer kann den Ablauf durch Setzen
von Breakpunkten unterbrechen und in Unterprozeduren hineinzoomen, um
so den Ablauf der Unterprozedur am Graphen im Graphikfenster zu
verfolgen. Die Algorithmen lassen sich ggf.\ halbmanuell ausf"uhren.
So kann etwa in einem Flu"sproblem der Benutzer einen erweiternden Weg
durch Auswahl von Kanten im Graphikfenster angeben. Der Algorithmus
pr"uft die Auswahl und verwendet das Ergebnis ggf.\ im weiteren
Ablauf.

Dem Programm wird ein einfacher Grapheditor zur interaktiven
Erstellung von Beispielgraphen und eine Bibliothek von -- insbesondere
``pathologischen'' -- Beispielgraphen beigegeben.

Das System wird mit Hilfe der Tools zur plattformunabh"angigen
Programmierung der Firma XVT in C++ realisiert.

\section*{Planung und Stand des Projektes}

Der Projektstart war Anfang Oktober 1994. Das Produkt soll bis
sp"atestens Herbst 1996 auf dem Markt sein. Mittlerweile sind der
Grapheneditor realisiert, das Fenster- und Interaktionskonzept zur
Darstellung der Algorithmen prinzipiell programmtechnisch verwirklicht
und zahlreiche MST--Algorithmen implementiert.

\rule{\textwidth}{1pt}

{\Large \bf Ansprechpartner}

\begin{tabular*}{15cm}{l@{\extracolsep{\fill}}l}
Dr. Martin Peters & 
Dr. Winfried Hochst"attler     \\
& 
Dipl.-Math. Bernd Stevens \\
\\
Springer-Verlag & 
Zentrum f"ur Paralleles Rechnen  \\
Math.\ Editor & 
Universit"at zu K"oln            \\
Tiergartenstra"se 17 & 
Weyertal 80                      \\
69121 Heidelberg & 
50931 K"oln                      \\
Tel: 06221/487-409 & 
Tel: 0221/470-6023              \\
Fax: 06221/487-355& 
Fax: 0221/470-5160               \\
E-mail: Peters@springer.de & 
E-Mail: wh@zpr.uni-koeln.de \\
\\
K"oln, \today
\end{tabular*}



\end{document}

\mbox{
  \begin{minipage}[b]{10cm}
    \begin{center}
      \
      \epsfxsize=5.5cm
  \fbox{\rule{0cm}{3cm}\makebox[5cm]{LOGO}}
%      \epsfbox{logo.ps}
    \end{center}
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
  \end{minipage}
  \hspace{5.1mm}
  \fbox{\rule{0cm}{7.5cm}\makebox[5cm]{Photo}}
%      \epsfxsize=5cm
%      \epsfbox{abb1.ps}
}

\section*{Problembeschreibung}

    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text

    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text

\section*{Modellierung}

    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text

\newpage

\epsfxsize=9cm
\begin{figure}
  \begin{center}
    \
  \fbox{\rule{0cm}{5cm}\makebox[9cm]{Schaubild}}
%    \epsfbox{abb2.ps}
  \end{center}
\caption{Bildchen}
\end{figure}

\section*{Algorithmen}

    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text

\section*{Ergebnisse}

    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text

    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text
    text text text text text text text text text text text text text text


\rule{\textwidth}{1pt}

{\Large \bf Ansprechpartner}

\begin{tabular}{ll}
Dipl.--Math. N.N.     \\
Zentrum f"ur Paralleles Rechnen  \\
Universit"at zu K"oln            \\
Weyertal 80                      \\
50931 K"oln                      \\
Tel: 0221/470-6022               \\
Fax: 0221/470-5160               \\
E-Mail: nn@ZPR.Uni-Koeln.DE \\
\\
K"oln, \today
\end{tabular}


\end{document}

