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

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{am 17. Mai 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}}



\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 B}\hfill SoSe 2016 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Zusammengesetzte Datentypen in Python}{10 Punkte}

\begin{enumerate}
\item
  Schreiben Sie eine Python-Funktion \texttt{sprod(l, k)}, die 
  das \emph{Skalarprodukt} zweier Listen \texttt{l} und \texttt{k} 
  von Gleitkommazahlen berechnet. Das Skalarprodukt von zwei leeren 
  Listen ist definiert als \texttt{0.0}.
  
  Beispiel: \texttt{sprod([1,2], [2,1])} soll \texttt{4} liefern.
\item
  Schreiben Sie eine Python-Funktion \texttt{histogram(s)}, die das 
  \emph{Histogramm} einer Zeichenkette \texttt{s} berechnet. Ein 
  Histogramm ist eine Datenstruktur, die f\"ur jedes in \texttt{s} 
  vorkommende Zeichen die Anzahl der Vorkommen angibt.
  
  Beispiel: \texttt{histogram('Hallo')} soll \texttt{H: 1, a: 1, l: 2, o: 1} liefern.
\item
  Schreiben Sie eine Python-Funktion \texttt{concatenate(l)}, welche eine 
  Liste von Listen erh\"alt und diese Listen zu einer einzelnen Liste
  zusammenf\"ugt.

  Beispiel: \texttt{concatenate([[1,2], [2,1], [True]])} soll \texttt{[1, 2, 2, 1, True]} liefern.
\end{enumerate}

Kommentieren Sie Ihren Quelltext sinnvoll und machen Sie geeignete Testl\"aufe.
Achten Sie auch auf eine angemessene Fehlerbehandlung.

\AUFGABE{Funktionen in Python}{10 Punkte}


\begin{enumerate}
  \item \emph{Sortieren durch Ausw\"ahlen} (selection sort) funktioniert
    folgenderma\ss{}en: Gegeben eine Liste \texttt{l} von paarweise verschiedenen Elementen
    aus einem total geordneten Universum, w\"ahle das kleinste Element \texttt{m} aus \texttt{l} und
    entferne es. Sortiere dann die restliche Liste und schreibe \texttt{m} an den Anfang der sortierten
    Liste. 

    Definieren Sie eine rekursive Python-Funktion \texttt{selectionSort}, welche
    diesen Algorithmus implementiert. Sie d\"urfen Annehmen, dass die Eingabeliste
    aus ganzen Zahlen besteht.
  \item Schreiben Sie eine rekursive Python-Funktion \texttt{toBitstring},
    welche eine gegebene ganze Zahl in ihre Bin\"ardarstellung (als Zeichenkette)
    umwandelt.
  \item L\"osen sie (b) mit einer \emph{iterativen} Funktion.
\end{enumerate}

Kommentieren Sie Ihren Quelltext sinnvoll und machen Sie geeignete Testl\"aufe.
Achten Sie auch auf eine angemessene Fehlerbehandlung.


\AUFGABE{Geld wechseln}{10 Punkte}

In dieser Aufgabe sollen Sie ein Python-Programm 
f\"ur das \emph{Geldwechsel-Problem} schreiben.
Dabei geht es darum, zu einem gegebenen Geldbetrag
und einer gegebenen Folge von M\"unztypen eine
``m\"oglichst gute'' Darstellung des Geldbetrags mit
den vorhandenen M\"unztypen zu finden.
Dabei ist eine Darstellung ``m\"oglichst gut'',
wenn sie die kleinstm\"ogliche Anzahl von M\"unzen verwendet.

Zum Beispiel gibt es Euro-M\"unzen im Wert von 
1 Cent, 2  Cent, 5 Cent, 10 Cent, 20 Cent, 50 Cent,
1 Euro, 2 Euro und (jetzt neu) 5 Euro. Den 
Betrag 2,45 Euro kann man optimal darstellen mit einer 
2-Euro M\"unze, zwei 20-Cent M\"unzen und einer 5-Cent M\"unze.

\begin{enumerate}
  \item Geben Sie Pseudocode f\"ur einen einfachen Algorithmus f\"ur
    das M\"unzwechsel-Problem, das nach dem \emph{gierigen}
    Prinzip funktioniert. Das bedeutet, dass der Algorithmus immer
    die gr\"o\ss{}tm\"ogliche M\"unze verwenden soll, die zur Auswahl steht.
  \item Implementieren Sie eine Python-Funktion \texttt{change(coin\_types, amount)}, 
    die eine Liste von M\"unztypen und einen Betrag erh\"alt und ein
    Darstellung des Betrags mit den gegebenen M\"unztypen liefert. Arbeiten Sie mit
    ganzen Zahlen.
  \item Liefert Ihr gieriger Algorithmus immer eine optimale Darstellung 
  des Betrags f\"ur die gegebenen M\"unztypen? Geben Sie einen Beweis oder
  ein Gegenbeispiel.
\end{enumerate}

Kommentieren Sie Ihren Quelltext sinnvoll und machen Sie geeignete Testl\"aufe.
Achten Sie auch auf eine angemessene Fehlerbehandlung.


\end{description}
\end{document}
