\documentclass[12pt]{article}
\usepackage{a4wide}
\usepackage{german,umlaut,url}
\pagestyle{empty}

\frenchspacing

\input ueb-macros

\begin{document}

%% Arg1: Nr. der Uebung
%% Arg2: Datum der Uebung
\header{6}{31. 5. 2004}


\begin{paufgabe}{Maschinelle Übersetzung}{3+1}
Schreibe ein Programm, das englische Zahlwörter im Zahlenraum von 1
bis 100 in deutsche Zahlwörter übersetzt und umgekehrt. Die
Zielsprache (\verb?de? oder \verb?en?) und das zu übersetzende
Zahlwort werden auf der Kommandozeile übergeben.\\

{\bf Beispiel} (Eingaben sind \textit{kursiv} gedruckt):\\
\texttt{  koller@cicero:\~\$} \textit{java Uebersetzung en fuenfundzwanzig}\\
\texttt{  twenty-five}\\
\texttt{  koller@cicero:\~\$} \textit{java Uebersetzung de thirteen}\\
\texttt{  dreizehn}\\

{\bf Hinweis:} Man könnte ein Array (mit Initialisierern) oder eine
Map verwenden, um zwischen den Zahlwörtern und den
\verb?int?-Werten hin- und herzukonvertieren.\\

{\bf Bonuspunkt:} Ändere das Programm so ab, dass es automatisch die
Quellsprache erkennt und das Zahlwort dann in die andere Sprache
übersetzt. 
\end{paufgabe}

\begin{paufgabe}{Effizienz von Listen-Implementierungen}{3}
Im Java Collections Framework gibt es verschiedene Implementierungen
für das Interface \verb?List?. Diese Implementierungen haben
verschiedene Vor- und Nachteile. Insbesondere unterstützen sie
bestimmte Operationen mehr oder weniger effizient; beim Programmieren
denkt man deshalb darüber nach, welche Operationen das Programm häufig
verwenden wird, und wählt die beste Implementierung aus.

Schreibe ein Programm, das die Effizienz der Methoden \verb?insert?,
\verb?remove(Integer)? und \verb?get?  in den beiden Klassen
\verb?ArrayList<Integer>? und \verb?LinkedList<Integer>?
vergleicht. Für Listen mit 20.000 Elementen sollte man einen
Laufzeitunterschied bemerken, der für größere Listen noch dramatischer
wird. 

Unter welchen Umständen würdest Du eine der beiden Implementierungen
der anderen vorziehen?
\end{paufgabe}


\begin{paufgabe}{Prioritäts-Warteschlangen}{3+1}
Eine Prioritäts-Warteschlange (engl. \emph{priority queue}) ist eine
überaus nützliche Da\-ten\-struk\-tur, deren Einträge mit einer numerischen
\emph{Priorität} versehen sind. Eine Prioritäts-War\-te\-schlan\-ge
unterstützt die folgenden Operationen:
\begin{itemize}
\item \verb?add(entry, priority)?: Fügt der Warteschlange einen neuen
  Eintrag mit der angegebenen Priorät hinzu.
\item \verb?removeMin()?: Gibt den Eintrag mit der kleinsten Priorität
  zurück und löscht ihn aus der Warteschlange.
\item \verb?isEmpty()?: Prüft, ob die Warteschlange leer ist.
\item \verb?size()?: Gibt die Anzahl der Einträge zurück.
\end{itemize}

Definiere ein Interface \verb?IntPriorityQueue?, das
Prioritäts-Warteschlangen mit Ein\-trä\-gen vom Typ \verb?String? und
Prioritäten vom Typ \verb?int? unterstützt. Schreibe eine Klasse, die
das Interface \verb?IntPriorityQueue? implementiert, sowie ein
Hauptprogramm, das die Klasse testet.\\

{\bf Hinweis:} Im Java Collections Framework gibt es eine Variante des
\verb?Map?-Interfaces, die hier nützlich sein könnte.\\

{\bf Bonuspunkt:} Zur Datenstruktur ``Prioritäts-Warteschlange''
gehört normalerweise auch eine Methode
\verb?decreasePriority(entry, newPriority)?, die die Priorität eines
bestehenden Eintrags reduziert. Füge dem Interface und der
implementierenden Klasse eine solche Methode hinzu.
\end{paufgabe}














\footerNoSA{7. 6. 2004}

\end{document}
