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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{am 24. 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{Aufrufkonventionen}{10 Punkte}

In der Vorlesung wurde erw\"ahnt, dass es beim
Aufruf von Funktionen unterschiedliche M\"oglichkeiten
geben kann, wie sich formale und tats\"achliche
Parameter zueinander verhalten.

\begin{enumerate}
  \item Recherchieren Sie die Aufrufkonventionen 
    \emph{call by reference}, \emph{call by value} und
    \emph{call by name}, und erkl\"aren Sie jede Aufrufkonvention
    kurz in zwei S\"atzen.
  \item
    Betrachten Sie das folgende Codefragment:
\begin{verbatim}
  def f(x, y)
      print("f: x = " + str(x) + ", y = " + str(y) + ".")
      x = x + y
      y = 2 * x
      print("f: x = " + str(x) + ", y = " + str(y) + ".")

  a = 2
  b = 4
  print("main: a = " + str(a) + ", b = " + str(b) + ".")
  f(a, b)
  print("main: a = " + str(a) + ", b = " + str(b) + ".")
\end{verbatim}
  Was gibt das Programm aus, wenn \texttt{f} \emph{call by value} verwendet?
  Was passiert bei \emph{call by reference}?
  \item
    Betrachten Sie das folgende Codefragment:
\begin{verbatim}
  def f():
    print("Hier ist f.")
    return 5

  def g(a):
    x = a
    y = 2 * a
    return x + y

  z = g(f())
  print("main: z = " + str(z) + ".")
\end{verbatim}
  Was gibt das Programm aus, wenn \texttt{g} \emph{call by value} verwendet?
  Was passiert bei \emph{call by name}?

\end{enumerate}


\AUFGABE{Mehrheitselement}{10 Punkte}

Sei \texttt{l} eine Liste von $n$ Zahlen. Eine Zahl $x$
hei\ss{}t \emph{Mehrheitselement} von \texttt{l}, wenn 
$x$ an mindestens $\lfloor n/2\rfloor + 1$ Positionen von \texttt{l}
vorkommt.

\begin{enumerate}
\item
  Sei \texttt{l1} die Liste, die aus den ersten $\lceil n/2\rceil$
  Zahlen aus \texttt{l} besteht, und
   \texttt{l2} die Liste, die aus den verbleibenden $\lfloor n/2\rfloor$
  Zahlen aus \texttt{l} besteht. Zeigen Sie:
  Wenn $x$ Mehrheitselement von \texttt{l} ist, so ist
  $x$ Mehrheitselement von \texttt{l1} oder von \texttt{l2}.
\item 
    Entwerfen Sie mit Hilfe von (a) einen rekursiven Algorithmus,
    um das Mehrheitselement von \texttt{l} zu bestimmen, falls es existiert.
\item 
  Implementieren Sie Ihren Algorithmus als eine rekursive Funktion in Python. 
  Falls kein Mehrheitselement existiert, soll Ihre Funktion \texttt{None} zur\"uckliefern.
  Machen Sie geeignete Testl\"aufe,
  und achten Sie auf eine angemessene Fehlerbehandlung und Dokumentation
  Ihres Programms.
\end{enumerate}

\emph{Bemerkung}. Der Algorithmus aus dieser Aufgabe ist nicht optimal.
  


\AUFGABE{Rekursion}{10 Punkte}

\begin{enumerate}
  \item
     Implementieren Sie den erweiterten euklidischen Algorithmus
     in Python.
  \item
     Erweitern Sie den rekursiven Algorithmus f\"ur das 
     Speisekartenproblem aus der Vorlesung so, dass er das folgende
     Problem l\"ost:

     Gegeben sei eine Speisekarte mit $n$ Speisen und
     ein Budget von $B$ Euro.
     Jede Speise $i$, $1 \leq i \leq n$,  hat einen Preis $p_i > 0$
     und einen \emph{Lustgewinn} $l_i > 0$. Wir suchen den
     maximalen Lustgewinn, den wir erzielen k\"onnen,
     ohne unser Budget zu \"uberschreiten, d.h, gesucht ist
     \[
       \max_{I \subseteq \{1, \dots, n\}, \sum_{i \in I} p_i \leq B}
         \sum_{i \in I} l_i.
     \]
  \item
     Der rekursive Algorithmus aus der Vorlesung f\"ur das 
     Speisekartenproblem wird schnell sehr langsam.
     Schneller geht es mit der \emph{Ged\"achtnistechnik} (engl.
     \emph{memoization}):
     Da sich viele rekursive Aufrufe wiederholen, benutzen wir
     ein globales W\"orterbuch, um die schon berechneten 
     Funktionswerte zu speichern.  Wird die Funktion ein weiteres
     mal mit den gleichen Parametern aufgerufen, k\"onnen wir 
     die Antwort direkt im W\"orterbuch nachschlagen.

     Passen Sie den Algorithmus aus der Vorlesung so an,
     dass er die Ged\"achntistechnik verwendet, und vergleichen
     Sie Ihre neue Implementierung mit der urspr\"unglichen Version.

     \emph{Hinweis}: Bei den Funktionsaufrufen kommt es nur
       darauf an, wie viele Speisen noch zur Auswahl stehen.

\end{enumerate}
Machen Sie geeignete Testl\"aufe,
und achten Sie auf eine angemessene Fehlerbehandlung und Dokumentation
Ihres Programms.

\end{description}
\end{document}
