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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{am 4. Mai 2018 bis 10 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}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}



\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{Nichtsequentielle und Verteilte Programmierung}\hfill SoSe 
2018 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katinka Wolter

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}
\AUFGABE{Nebenl\"aufiges Z\"ahlen}{10 Punkte}

Sei $K \in \N$. Betrachten Sie den folgenden Pseudocode:
\begin{verbatim}
                 global int n <- 0 
a1: for i := 1 to K do         | b1: for j := 1 to K do
a2:     a <- n                 | b2:     b <- n 
a3:     n <- a + 1             | b3:     n <- b - 1
\end{verbatim}

\begin{enumerate}
\item In Abh\"angigkeit von $K$, was sind die m\"oglichen
  Werte, die \texttt{n} am Ende des Programms annehmen kann?
  Begr\"unden Sie Ihre Antwort.
\item Implementieren Sie den Pseudocode in Java und versuchen
  Sie mit Hilfe geeigneter \texttt{Thread.sleep()} und
  \texttt{Thread.yield()} Anweisungen m\"oglichst viele verschiedene
  Ergebnisse zu produzieren.
\end{enumerate}

\AUFGABE{Parallele Suche}{10 Punkte}

Gegeben sei eine Funktion $f: \Z \rightarrow \Z$ und
das Versprechen, dass $f$ eine Nullstelle besitzt (d.h.,
es existiert ein $i \in \Z$ mit $f(i) = 0$). 
Gesucht ist ein Programm, das eine
Nullstelle von $f$ findet.

Ein solches Programm ist \emph{korrekt}, wenn \emph{alle} Prozesse
in allen m\"oglichen Szenarien terminieren und eine Nullstelle 
von $f$ gefunden wird. Beweisen Sie f\"ur jedes der folgenden 
drei Programme, dass es korrekt ist (unter der Annahme der schwachen
Fairness), oder geben Sie ein Szenario an, das zu inkorrektem
Verhalten f\"uhrt.

\begin{enumerate}
\item
\begin{verbatim}
=======================================================
                   global bool found
a1: i <- 0                     |b1:  j <- 1
a2: found <- false             |b2:  found <- false
a3: while not found            |b3:  while not found
a4:     i <- i + 1             |b4:      j <- j - 1
a5:     found <- (f(i) == 0)   |b5:      found <- (f(j) == 0) 
\end{verbatim}
\item
\begin{verbatim}
=======================================================
                global bool found <- false
a1: i <- 0                     |b1:  j <- 1
a2: while not found            |b2:  while not found
a3:     i <- i + 1             |b3:      j <- j - 1
a4:     found <- (f(i) == 0)   |b4:      found <- (f(j) == 0) 
\end{verbatim}
\item
\begin{verbatim}
=======================================================
                global bool found <- false
a1: i <- 0                     |b1:  j <- 1
a2: while not found            |b2:  while not found
a3:     i <- i + 1             |b3:      j <- j - 1
a4:     if f(i) == 0 then      |b4:      if f(j) == 0 then
a5:         found <- true      |b5:          found <- true 
\end{verbatim}
\end{enumerate}

\AUFGABE{Das Froschpuzzle}{10 Punkte}

Sei $n \in N$ und seien $2n+1$ Steine in einem Sumpf
gegeben, die entlang einer Reihe angeordnet sind.
Auf jedem der linken $n$ Steine sitzt jeweils ein m\"annlicher
Frosch, der nach rechts schaut; auf jedem der rechten $n$ Steine
sitzt jeweils eine weibliche Fr\"oschin, die nach links schaut;
der mittlere Stein ist unbesetzt.

Die Fr\"osche k\"onnen nur in ihre Blickrichtung springen.
Wenn der entsprechende benachbarte Stein frei ist, so kann der
Frosch oder die Fr\"oschin direkt zu diesem Stein springen.
Au\ss{}erdem ist es m\"oglich, einen benachbarten Frosch oder
eine benachbarte Fr\"oschin zu \"uberspringen, um zu einem entsprechenden
freien Stein zu gelangen.

Gesucht ist eine Folge von Spr\"ungen, so dass alle $n$ m\"annlichen
Fr\"osche auf den rechten $n$ Steinen und alle $n$ weiblichen
Fr\"oschinnen auf den linken $n$ Steinen landen.

Modellieren Sie das Froschpuzzle f\"ur $n = 2$ durch ein Zustandsdiagramm
und geben Sie eine L\"osung an.

\end{description}
\end{document}
