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

\newcommand{\ZETTELNUMMER}{1}
\newcommand{\ABGABEDATUM}{am 3. 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{Breitensuche}{10 Punkte}

\begin{enumerate}
\item F\"uhren Sie im folgenden Graphen eine Breitensuche
  ausgehend vom Knoten $a$ durch. Zeigen Sie die einzelnen Schritte.
  \begin{center}
  \includegraphics{bfs}
   \end{center}
\item Ein \emph{Kreis} in einem ungerichteten 
   Graphen $G$ ist eine Folge von mindestens drei paarweise verschiedenen Knoten
  in $G$, so dass je zwei aufeinander folgende Knoten sowie der letzte und
  der erste Knoten durch eine Kante  verbunden sind.
  
  Beschreiben Sie, wie man Breitensuche verwenden kann, um festzustellen,
  ob ein gegebener Knoten $a$ in einem Kreis enthalten ist.

 Geben Sie ein Beispiel von einem Graphen, in dem $a$ in einem
 Kreis enthalten ist, und ein Beispiel von einem Graphen,
 in dem $a$ nicht in einem Kreis enthalten ist. Zeigen Sie die
 Schritte Ihres Algorithmus auf den beiden Graphen. 
\end{enumerate}

\AUFGABE{Das Kleine-Welt-Ph\"anomen}{10 Punkte}

Das \emph{Kleine-Welt-Ph\"anomen} besagt,
dass zwei beliebige Menschen auf der Welt 
durch eine Kette von h\"ochstens sechs
Bekanntschaftsbeziehungen verbunden sind.

\begin{enumerate}
  \item Modellieren Sie das Kleine-Welt-Ph\"anomen mit einem
    Graphen, und geben Sie eine m\"oglichst pr\"azise
    Definition daf\"ur, dass ein Graph die Kleine-Welt-Eigenschaft 
    besitzt.
  \item Beschreiben Sie einen Algorithmus, welcher \"uberpr\"uft,
    ob ein gegebener Graph die Kleine-Welt-Eigenschaft besitzt.
    Begr\"unden Sie kurz, warum Ihr Algorithmus funktioniert.
  \item Demonstrieren Sie Ihren Algorithmus an zwei kleinen Beispielen,
    von denen eines die Kleine-Welt-Eigenschaft erf\"ullen soll und
    das andere nicht.
\end{enumerate}

\newpage
\AUFGABE{Erste Schritte in Python}{10 Punkte}

\begin{enumerate}
\item Laden Sie die Python-Programmiersprache (Version 3) herunter
  und installieren Sie sie auf Ihrem Rechner.
\item Starten Sie das Programm \texttt{python} und 
  geben Sie die folgenden Befehle ein. Was passiert?
  Geben Sie jeweils eine kurze Interpretation.
  \begin{enumerate}
    \item \begin{verbatim}a = 8 + 10\end{verbatim}
    \item \begin{verbatim}
help()
quit 
\end{verbatim}
    \item \begin{verbatim}3 + 5 * 7 == a - 2\end{verbatim}
    \item \begin{verbatim}
a = 40
3 + 5 * 7 == a - 2
\end{verbatim}
\item \begin{verbatim}print("InfB", str(a * 50 + 16) + ".\n")\end{verbatim}
    \item \begin{verbatim}True | (False & True)\end{verbatim}
    \item \begin{verbatim}
if a - 4 <= 5:
    print("Ja")
else:
    print("Nein")
          \end{verbatim}
    \item \begin{verbatim}
2 * (4 +

5)
\end{verbatim}
    \item \begin{verbatim}
for i in range(10):
    print(2 * i +  1)
    \end{verbatim}
    \item \begin{verbatim}exit()\end{verbatim}
  \end{enumerate}
\item
  Laden Sie die Datei \texttt{mystery.py} von der Veranstaltungswebsite 
  herunter und importieren Sie sie mit Hilfe des Befehls
  \texttt{from mystery import mystery} nach Python.
  Was passiert, wenn Sie 
  \begin{verbatim}
mystery("anna") 
mystery("banane")
mystery("caesar") 
\end{verbatim}
eingeben?

  F\"uhren Sie weitere Experimente durch und \"au\ss{}ern Sie eine
  Vermutung, was die Funktion \texttt{mystery} tut.
\end{enumerate}
\end{description}
\end{document}
