\documentclass[11pt, a4paper]{article}

\usepackage{ngerman}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage[pdftex,             
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
            pdftitle={},
            pdfauthor={Jan Hendrik Dithmar},
            pdfsubject={},
            pdfkeywords={},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden 
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}


\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\pagestyle{myheadings}
\markright{Jan Hendrik Dithmar; Matrikelnummer 2031259; Andreas Augustin }
%\markright{Dirk Heine; Matrikelnummer 2030941; Andreas Augustin}

%\title{Programmierung II - Übungsblatt 11 \\
%	Übungsgruppe Do 14-16 \\	
%	Andreas Augustin}
%\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
%	Dirk Heine (Matrikelnummer 2030941) \\
%	Andreas Glitsch (Matrikelnummer 2026130)}
%\date{}

%\maketitle

\newpage
\section*{Aufgabe 1}
{\bfseries Bearbeitungszeit: } 20 Minuten \\

\subsubsection*{(a)}
Eine Template-Klasse kann in C++ dazu benutzt werden, Algorithmen und Datenstrukturen so unabhängig wie möglich von einem Typ zu implementieren. Ein Beispiel dafür ist die Klasse
\verb!vector<T>!, die Daten des Typs \verb!T! speichert, so z.B. \verb!int!-Variablen in einem \verb!vector<int>! oder Variablen vom Typ \verb!string! in einem \verb!vector<string>!.

\subsubsection*{(b)}
Sei $F:=\{f|f:\SetN \to \SetR_0^+\}$. Dann ist für $g \in F$:
$$\Theta(g) := \{f \in F| \exists c_1,c_2 >0 \; \AND \; \exists n_0 \in \SetN: \forall n \ge n_0: c_1 g(n) \le f(n) \le c_2 g(n)\}$$

\subsubsection*{(c)}
{\bfseries Doppelt verkettete Liste:}
\begin{itemize}
	\item {\itshape Vorne anfügen} geht bei Beibehaltung der Sortierung in $\OnotO(n)$, da zuerst der richtige Einfügeort gesucht werden muss ($\OnotO(n)$, wobei $n=$Länge der Liste).
		Das Einfügen geht in $\OnotO(1)$. \\
		Muss man die Sortierung nicht beibehalten, so geht das Einfügen offensichtlich in $\OnotO(1)$.
	\item {\itshape Suche} geht bei doppelt verketteten Listen nur in $\OnotO(n)$, da man von vorne bis nach hinten durch die Liste gehen muss, bis das Element gefunden wurde.
		Die Ordnungseigenschaft kann dabei nicht ausgenutzt werden.
\end{itemize}
{\bfseries unsortiertes Array:}
\begin{itemize}
	\item {\itshape Vorne anfügen} braucht Zeit $\OnotO(n)$, da das gesammte Array nach hinten verschoben werden muss, um vorne für das neue Element Platz zu schaffen.
	\item Wir haben keine Informationen über die gespeicherten Einträge, sodass man bei der {\itshape Suche} ggf. alle Elemente überprüfen muss, bis das gesuchte gefunden wurde.
		Somit haben wir $\OnotO(n)$.
\end{itemize}

\subsubsection*{(d)}
\begin{enumerate}[(i)]
	\item {\itshape linear probing:} wenn eine Kollision auftritt wird solange ein neuer Hashwert mit einer Linearkombination des alten Hashwertes und einem Laufindex $i$ bestimmt, 
		bis man auf ein freies Feld  stößt:
		$$h(k,i) = (h_{alt}(k,i) + i) \mod m$$
	\item {\itshape quadratic probing:} funktioniert wie {\itshape linear probing}, jedoch wird ein Polynom zweiten Grades verwendet:
		$$h(k,i) = (h_{alt}(k) + c_1i + c_2i^2) \mod m$$
	\item {\itshape double hashing:} hier wird mit Hilfe einer zweiten Hashfunktion solange ein neuer Hashwert berechnet, bis man auf ein freies Feld stößt:
		$$h(k,i) = (h_{alt}(k) + ih_2(k)) \mod m$$
\end{enumerate}

\subsubsection*{(e)}
Eine endliche Menge $\mathcal{H}$ von Hashfunktionen $h: \mathcal{U} \to \{0,1,...,m-1\}$ heißt universelle Klasse von Hashfunktionen wenn für jedes Paar $k_i, k_j$ von
verschiedenen Schlüsseln gilt: \\
die Zahl  der Funktionen $h \in \mathcal{H}$ mit $h(k_i) = h(k_j)$ ist höchstens $\displaystyle \frac{|\mathcal{H}|}{m}$.

\subsubsection*{(f)}
Ein Circuit (= Rundgang) in einem Graphen ist ein Pfad, bei dem der erste und der letzte Knoten gleich sind. Ein Euler-Circuit ist ein Rundgang, bei dem jede Kante des Graphen genau
einmal enthalten ist.

\newpage
\section*{Aufgabe 2}
{\bfseries Bearbeitungszeit: } 30 Minuten \\
\subsubsection*{(a)}
\begin{verbatim}
template<class T>
class liste {
  public:
    liste();
    liste(const liste&);
    ~liste();
    liste& operator=(const liste&);

    int elementanzahl() const {return anzahl;}
    
    void links_einfuegen(const T&);
    
    void suche(const T& i);
    
    void loesche(const T& i);
    
  private:
    class listenelement {
      friend class liste<T>;
      T knoten;
      listenelement *nachfolger, *vorgaenger;
      listenelement(const T& dat) 
        : knoten(dat), nachfolger(NULL), vorgaenger(NULL) {}
    };

    listenelement *ende, *anfang;
    int anzahl;
}
\end{verbatim}

\newpage
\subsubsection*{(b)}
\begin{verbatim}
template<class T>
void liste<T>::loesche(const T& i) {
  listenelement *current = anfang;
  while(current) {
    if (i == current->knoten) {
      if (current->vorgaenger != NULL) {
        current->vorgaenger->nachfolger = current->nachfolger;
      }
      else {
        anfang = current->nachfolger;
      }
      if (current->nachfolger != NULL) {
        current->nachfolger->vorgaenger = current->vorgaenger;
      }
      else {
        ende = current->vorgaenger;
      }
      delete current;
      anzahl--;
      }
    current = current->nachfolger;
  }
}
\end{verbatim}

\newpage
\section*{Aufgabe 4}
{\bfseries Bearbeitungszeit: } 15 Minuten \\
Anordnung: d,c,b,a \\
Begründung: \\
$(*)$: L'Hôpital
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{|n \cdot \ln(n)|}{|4^{\log_2(n+1)}|} & = & \lim_{n \to \infty} \frac{|n \cdot \ln(n)|}{|(n+1)^2|} \\
	& \stackrel{(*)}{=} & \lim_{n \to \infty} \frac{|\ln(n)+1|}{|2n+2|} \\
	& \stackrel{(*)}{=} & \lim_{n \to \infty} \frac{|\frac{1}{n}|}{|2|} \\
	& = & \lim_{n \to \infty} \frac{1}{|2n|} = 0
\end{eqnarray*}
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{|(n+1)^2|}{|e^n|} & \stackrel{(*)}{=} & \lim_{n \to \infty} \frac{|2n+2|}{|e^n|} \\
	& \stackrel{(*)}{=} & \lim_{n \to \infty} \frac{2}{|e^n|} = 0
\end{eqnarray*}
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{|e^n|}{|n!|} & = & \lim_{n \to \infty} \frac{|\prod_{i=0}^{n-1} e|}{|\prod_{i=0}^{n-1} (n-i)|} \\
	& = & \lim_{n \to \infty} \prod_{i=0}^{n-1} \frac{e}{n-i} = 0
\end{eqnarray*}

\newpage
\section*{Aufgabe 5}
{\bfseries Bearbeitungszeit: } 15 Minuten \\
Nach 4 weiteren Runden ist das Spiel auf jeden Fall entschieden.
%Da ein Weiterspielen aber ausgeschlossen ist, werden diese Runden 
%fiktiv ausgespielt.
Da die Wahrscheinlichkeit, dass ein Spieler eine
Runde gewinnt, $\frac{1}{2}$ ist, ergeben sich folgende Möglichkeiten für die
Sieger dieser 4 Runden, wobei jede Kombination gleich wahrscheinlich
ist: \\
\begin{center}
\begin{tabular}{ccc}
A-A \\
A-B-A & B-A-A \\
A-B-B-A & B-A-B-A & B-B-A-A \\
B-B-B \\
B-B-A-B & B-A-B-B & A-B-B-B
%A-A-A-A \\
%A-A-A-B & A-A-B-A & A-B-A-A & B-A-A-A \\
%A-A-B-B & A-B-B-A & A-B-A-B \\
%B-A-A-B & B-A-B-A & B-B-A-A \\
%A-B-B-B & B-A-B-B & B-B-A-B & B-B-B-A \\
%B-B-B-B
\end{tabular}
\end{center}
\begin{eqnarray*}
	P(A \text{ gewinnt zuerst 10 Spiele}) & := & P(A) \\
	P(A) & = & \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 + \left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 + \left(\frac{1}{2}\right)^4 \\
	& = & \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \frac{1}{8} + \frac{1}{16} + \frac{1}{16} \\
	& = & \frac{4+2+1+2+1+1}{16} \\
	& = & \frac{11}{16} \\[0.3cm]
	P(B \text{ gewinnt zuerst 10 Spiele}) & := & P(B) \\
	P(B) & = & 1-P(A) \\
	& = & 1 - \frac{11}{16} \\
	& = & \frac{5}{16}
\end{eqnarray*}
Spieler A gewinnt in 11 von 16 Fällen, Spieler B gewinnt in 5 von 16 Fällen.
Der Gewinn-Betrag geht also zu $\frac{11}{16}$ an Spieler A und zu $\frac{5}{16}$ an Spieler B.

\newpage
\section*{Aufgabe 6}
{\bfseries Bearbeitungszeit: } 10 Minuten \\
$$T(n) = 2 T \left(\frac{n}{3}\right) + n^3$$
Vermutung: $T(n) \in \OnotO(n^3)$ \\
Behauptung: $T(n) \le c \cdot n^3$, wobei $c>1$ beliebig \\
Beweis: \\
$n=1$: $T(1) = 1 \le c$ \\
Induktionsschritt:
\begin{eqnarray*}
	T(n) & = & 2 T \left(\frac{n}{3}\right) + n^3 \\
	& \le & 2 c \left(\frac{n}{3}\right)^3 + n^3 \\
	& = & 2 \cdot \frac{c}{27} n^3 + n^3 \\
	& = & 3 n^3 \quad \text{für } c=27
\end{eqnarray*}

\newpage
\section*{Aufgabe 7}
{\bfseries Bearbeitungszeit: } 15 Minuten \\
\begin{itemize}
	\item $\displaystyle T(n) = 64 T \left(\frac{n}{8}\right) + 1042 n^2 + 1000000n$
		\begin{eqnarray*}
			a & = & 64 \\
			b & = & 8 \\
			f(n) & = & 1042 n^2 + 1000000n \\
			\log_8(64) & = & 2 \\
			f(n) & \in & \Theta(n^{\log_b(a)}) = \Theta(n^2)
		\end{eqnarray*}
		Dann gilt nach dem 2. Fall des Mastertheorems
		$$T(n) = \Theta(n^2 \log(n))$$
	\item $\displaystyle T(n) = 27 T \left(\frac{n}{3}\right) + n^3 \ln(n) + 42$
		\begin{eqnarray*}
			a & = & 27 \\
			b & = & 3 \\
			f(n) & = & n^3 \ln(n) + 42 \\
			\log_3(27) & = & 3 \Rightarrow n^{\log_3(27)} = n^3
		\end{eqnarray*}
		Es gilt:
		$$f(n) \in \Omega(n^3)$$
		Wir können jedoch kein $\varepsilon > 0$ finden, sodass $f(n) \in \Omega(n^{3+\varepsilon})$ ist, da der Logarithmus langsamer wächst als jede Potenz. Somit ist das
		Mastertheorem hier nicht anwendbar.
\end{itemize}


\end{document}
