\documentclass{bschlangaul-aufgabe}
\bLadePakete{java}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {Zahl der Inversionen von A},
  Referenz = 66115-2016-H.T1-A4,
  RelativerPfad = Examen/66115/2016/09/Thema-1/Aufgabe-4.tex,
  ZitatSchluessel = examen:66115:2016:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Teile-und-Herrsche (Divide-and-Conquer)},
  EinzelpruefungsNr = 66115,
  Jahr = 2016,
  Monat = 09,
  ThemaNr = 1,
  AufgabeNr = 4,
}

Es sei $A[0 \dots n - 1]$ ein Array von paarweise verschiedenen ganzen
Zahlen.\index{Teile-und-Herrsche (Divide-and-Conquer)}
\footcite{examen:66115:2016:09}

Wir interessieren uns für die Zahl der Inversionen von $A$; das sind
Paare von Indices $(i, j)$, sodass $i < j$ aber $A[i] > A[j]$. Die
Inversionen im Array $[2, 3, 8, 6, 1]$ sind $(0, 4)$, da $A[0] > A[4]$
und weiter $(1, 4)$, $(2, 3)$, $(2, 4)$, $(3, 4)$. Es gibt also $5$
Inversionen.
\begin{enumerate}

%%
% 1.
%%

\item Wie viel Inversionen hat das Array $[3, 7, 1, 4, 5, 9, 2]$?

\begin{bAntwort}
\begin{itemize}
\item $(0, 1)$: $3 > 1$
\item $(0, 6)$: $3 > 2$
\item $(1, 2)$: $7 > 1$
\item $(1, 3)$: $7 > 4$
\item $(1, 4)$: $7 > 5$
\item $(1, 6)$: $7 > 2$
\item $(3, 6)$: $4 > 2$
\item $(4, 6)$: $5 > 2$
\end{itemize}
\end{bAntwort}

%%
% 2.
%%

\item Welches Array mit den Einträgen $\{ 1, \dots, n\}$ hat die meisten
Inversionen, welches hat die wenigsten?

\begin{bAntwort}
Folgt nach der $1$ eine absteigend sortiere Folge, so hat sie am meisten
Inversionen, \zB $\{ 1, 7, 6, 5, 4, 3, 2 \}$.
%
Eine aufsteigend sortierte Zahlenfolge hat keine Inversionen, \zB
$\{ 1, 2, 3, 4, 5, 6, 7 \}$.
\end{bAntwort}

%%
% 3.
%%

\item Entwerfen Sie eine Prozedur
\bJavaCode{int merge(int[] a, int i, int h, int j);}

welche das Teilarray a[i.,j] sortiert und die Zahl der in ihm
enthaltenen Inversionen zurückliefert, wobei die folgenden
Vorbedingungen angenommen werden:

\begin{itemize}
\item $0 \leq i \leq h \leq j < n$, wobei $n$ die Länge von $a$ ist
(\bJavaCode{n = a.length}).

\item $a[i \dots h]$ und $a[h + 1 \dots j]$ sind aufsteigend sortiert.

\item Die Einträge von $a[i \dots j]$ sind paarweise verschieden.
\end{itemize}

Ihre Prozedur soll in linearer Zeit, also $\mathcal{O}(j - i)$ laufen.
Orientieren Sie sich bei Ihrer Lösung an der Mischoperation des
bekannten Mergesort-Verfahrens.

%%
% 4.
%%

\item Entwerfen Sie nun ein Divide-and-Conquer-Verfahren zur Bestimmung
der Zahl der Inversionen, indem Sie angelehnt an das Mergesort-Verfahren
einen Algorithmus \bJavaCode{ZI} beschreiben, der ein gegebenes Array
in sortierter Form liefert und gleichzeitig dessen Inversionsanzahl
berechnet. Im Beispiel wäre also

\begin{displaymath}
ZI([2, 3, 8, 6, 1]) = ([1, 2, 3, 6, 8], 5)
\end{displaymath}

Die Laufzeit Ihres Algorithmus auf einem Array der Größe $n$ soll
$\mathcal{O}(n \log(n))$ sein.

Sie dürfen die Hilfsprozedur merge aus dem vorherigen Aufgabenteil
verwenden, auch, wenn Sie diese nicht gelöst haben.

%%
% 5.
%%

\item Begründen Sie, dass Ihr Algorithmus die Laufzeit $\mathcal{O}(n
\log(n))$ hat.

%%
% 6.
%%

\item Geben Sie die Lösungen folgender asymptotischer Rekurrenzen (in
O-Notation) an:

\begin{enumerate}
%%
% (a)
%%

\item $T(n) = 2 \cdot T(\frac{n}{2}) + \mathcal{O}(\log n)$
%%
% (b)
%%

\item $T(n) = 2 \cdot T(\frac{n}{2}) + \mathcal{O}(n^2)$
%%
% (c)
%%

\item $T(n) = 3 \cdot T(\frac{n}{2}) + \mathcal{O}(n)$
\end{enumerate}
\end{enumerate}

\end{document}