\documentclass[10pt]{article}

\usepackage{ngerman,a4,amssymb,amsmath}
\usepackage[latin1]{inputenc}

\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}}}

\thispagestyle{empty}

\begin{center}
  {\Large Übungsblatt 4} \\
  Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
  Carsten Saar (Matrikelnummer 2030107) \\
  Thomas Ospelt (Matrikelnummer 2029959) \\
  Timo Adam (Matrikelnummer 2031946) \\
  Übungsgruppe 8 - Di, 15-17 Uhr \\
  Steffen Heil \\
\end{center}

\newpage
\section*{Aufgabe 1}
zu zeigen: $(a^b)^c = a^{b\cdot c}$. Benutzt wird dabei
\begin{eqnarray*}
a^0 & = & 1 \; \; \; \; \; \; \; \; \; \text{ entspricht Vor. 12}\\
a^{i+1} & = & a^i\cdot a \; \; \; \text{ entspricht Vor. 13}
\end{eqnarray*}
sowie die bereits bewiesenen Rechenregeln. \\
Beweis durch vollständige Induktion über $c\in\SetN$:
\begin{enumerate}
\item Induktionsanfang:
\begin{enumerate}
\item $c=0$:
\begin{eqnarray*}
(a^b)^0 & = & a^{b \cdot 0} \\
\text{Setze: }a^b & = & z \\
z^0 & = & a^0 \\
1 & = & 1 \text{ (w)}
\end{eqnarray*}

\item $c=1$:
$$(a^b)^1 = a^b = a^{b\cdot1} = a^{b\cdot c}$$
\end{enumerate}

\item
\begin{enumerate}
\item Induktionsannahme: Es gilt $\forall c\in\SetN$: $(a^b)^c = a^{b\cdot c}$

\item Induktionsbehauptung: Dann gilt $\forall (c+1)\in\SetN$: $(a^b)^{c+1} = a^{b \cdot (c+1)}$

\item Induktionsbegründung: Benutze dabei $(a^b) = z \; \; \; (*)$
\begin{eqnarray*}
(a^b)^{c+1} & \stackrel{(*)}{=} & z^{c+1} \\
& = & z^c \cdot z \\
& \stackrel{(*)}{=} & (a^b)^c \cdot (a^b) \\
& \stackrel{(2a)}{=} & (a^{b\cdot c}) \cdot (a^b) \\
& = & (a^{(b\cdot c)}) \cdot (a^b) \\
& \stackrel{\text{Vor. 18}}{=} & a^{(b\cdot c)+b} \\
& = & a^{b(c+1)}
\end{eqnarray*}
\hfill $\Box$
\end{enumerate}
\end{enumerate}

\section*{Aufgabe 2}
\subsubsection*{(a)}
\begin{eqnarray*}
\left<a, 0^i\right> & = & \sum_{j=i}^{n-1} a_j \cdot 2^j + \sum_{j=0}^{i-1} 0_j \cdot 2^j \\
& = & \sum_{j=i}^{n-1} a_j \cdot 2^j + 0 \\
& = & \sum_{j=i}^{n-1} a_j \cdot 2^j \\
& = & \left<a\right> \cdot 2^i
\end{eqnarray*}

\subsubsection*{(b)}
\begin{eqnarray*}
\left<0^j, a\right> & = & \sum_{i=l}^j 0_i \cdot 2^i + \sum_{i=0}^{l-1} a_i \cdot 2^i \\
& = & 0 + \sum_{i=0}^{l-1} a_i \cdot 2^i \\
& = & \sum_{i=0}^{l-1} a_i \cdot 2^i \\
& = & \left<a\right>
\end{eqnarray*}

\section*{Aufgabe 3}
siehe hinten

\section*{Aufgabe 4}
\begin{eqnarray*}
D(Tree_b) & = & D(Tree_{\frac{b}{2}}) + 6 \\
D(Tree_{\frac{b}{2}}) & = & D(Tree_{\frac{b}{4}}) + 6 + 6 \\
D(Tree_{\frac{b}{4}}) & = & D(Tree_{\frac{b}{8}}) + 6 + 6 + 6 \\
\vdots & & \\
\Rightarrow D(Tree_b) & = & D(Tree_{\frac{b}{2^K}}) + K \cdot 6
\end{eqnarray*}
Aus $D(Tree_4)=6$ ergibt sich:
\begin{eqnarray*}
\left(\frac{b}{2^K}\right) & = & 4 \\
b & = & 2^{(K+2)} \\
log(b) & = & K+2 \\
K & = & log(b)-2
\end{eqnarray*}
\begin{eqnarray*}
D(Tree_b) & = & D(Tree_4) + (log(b)-2) \cdot 6 \\
D(Tree_b) & = & -6 + 6 \cdot log(b)
\end{eqnarray*}
Fallunterscheidung:
\begin{enumerate}
\item Fall: $b=4$
$$D(Tree_4) = -6 + 6 \cdot log(4) = -6 + 6 \cdot 2 = 6 \; \; \; (ok)$$
\item Fall: $b>4$
\begin{eqnarray*}
D(Tree_b) & = & D(Tree_{\frac{b}{2}}) + 6 \\
& = & -6 + 6 \cdot (log(b)-1) + 6 \\
& = & -6 + 6 \cdot log(b) -6 +6 \\
& = & -6 + 6 \cdot log(b)
\end{eqnarray*}
\end{enumerate}

\section*{Aufgabe 5}
Zu zeigen: Es existiert genau ein $x' \in \{a,...,a+k-1\}$ mit $x \equiv x' \mod k$ \\
Beweis: Seien$a,x \in \SetZ$ beliebig, $k \in \SetN^*$ beliebig. \\
Betrachte $x-a$:
\begin{enumerate}
\item Fall: $x-a \ge 0$ \\
$x-a$ lässt bei Division durch $k\in\SetN^*$ einen eindeutig bestimmten Rest $r\in\{0,...,k-1\}$. Somit besitzt $x-a$ eine eindeutig bestimmte Darstellung der Form:
\begin{eqnarray*}
x-a & = & n \cdot k + r \; \; \; \; \text{ mit } n\in\SetN \AND 0 \le r \le k-1 \; \; \; (I) \\
\Rightarrow x & = & (a+r)+n\cdot k \\
\Leftrightarrow x & \equiv & (a+r) \mod k
\end{eqnarray*}
Setzt man $x':=a+r$, so ist $x\equiv x' \mod k$. \\
Weiterhin gilt: \\
(1) \\
Aus $(I)$ folgt: $a \le a+r \le a+k-1$ und somit $a \le x' \le a+k-1$, d.h. $x'\in\{a,...,a+k-1\}$ \\
(2) \\
Da $r\in\{0,...,k-1\}$ eindeutig bestimmt ist $\Rightarrow a+r=x'$ ist eindeutig bestimmt.

\item Fall: $x-a<0 \Leftrightarrow -(x-a)>0$ \\
$-(x-a)$ lässt bei Division durch $k\in\SetN^*$ einen eindeutig bestimmten Rest $r'\in\{0,...,k-1\}$. Somit besitzt $-(x-a)$ eine eindeutig bestimmte Darstellung der Form:
\begin{eqnarray*}
-(x-a) & = & m \cdot k + r' \; \; \; \; \text{ mit } m\in\SetN \AND 0 \le r' \le k-1 \\
\Leftrightarrow x-a & = & (-m) \cdot k + (-r') \Leftrightarrow x=(a-r')+(-m)\cdot k \; \; \; (*)
\end{eqnarray*}
\begin{enumerate}
\item $r'=0$
\begin{eqnarray*}
\Rightarrow x & = & a+(-m)\cdot k \\
\Leftrightarrow x & \equiv & a \mod k
\end{eqnarray*}
Setze $x'=a \Rightarrow x \equiv x' \mod k$. Dann ist $x'=a\in\{a,...,a+k-1\}$ und $x'=a$ ist eindeutig bestimmt.
\item Sei nun $0<r'\le k-1 \Leftrightarrow 1 \le r' \le k-1 \; \; \; (**)$ \\
Aus $(*)$ folgt: $x\equiv(a-r')\mod k \Leftrightarrow x \equiv (a-r'+k) \mod k$ \\
Setze $x':=a-r'+k \Rightarrow x \equiv x' \mod k$
\begin{eqnarray*}
(**) & \Leftrightarrow & -1 \ge -r' \ge 1-k \\
& \Leftrightarrow & a+k-1 \ge a+k-r' \ge 1+a \\
& \Leftrightarrow & a+1 \le a-r'+k \le a+k-1 \\
& \Leftrightarrow & a+1 \le x' \le a+k-1
\end{eqnarray*}
$\Leftrightarrow x' \in \{a+1,...,a+k-1\} \subset \{a,...,a+k-1\}$, d.h. $x'\in\{a,...,a+k-1\}$. \\
Außerdem ist $r'\in\{1,...,k-1\}$ (vgl. $(**)$) eindeutig bestimmt \\
$\Rightarrow a-r'+k = x'$ eindeutig bestimmt.
\end{enumerate}
\end{enumerate}

\section*{Aufgabe 6}
Vorbemerkung: \\
Wir bezeichnen für $c\in\{0,2^{n-1}-1\}$ die eindeutige Zeichenreihe $a\in\{0,1\}^n$ mit $\left<a\right>=c$ mit
$$ a = bin_n(c) $$
Beweis: Sei $c\in\{-2^{n-1},...,2^{n-1}-1\}$. \\
Ist $c \ge 0$, so liegt $bin_n(c)$ in $\{0,1\}^{n-1}$. Für $a=(0,bin_n(c))$ gilt dann
$$ [a] = 0 + \left<bin_n(c)\right> = c $$
Ist $c<0$, so liegt $c$ in $\{-2^{n-1},...,-1\}$. Also gilt:
$$ c=-2^{n-1}+c' $$
für ein $c'\in\{0,...,2^{n-1}-1\}$, es folgt $bin_n(c')\in\{0,1\}^{n-1}$. Für $a=(1,bin_n(c'))$ gilt dann
$$ [a] = -2^{n-1}+\left<bin_n(c')\right>=c $$
Also ist die Funktion
$$ [ \; \; ] : \{0,1\}^n \rightarrow \{-2^{n-1},...,2^{n-1}-1\} $$
surjektiv. Da Definitionsbereich und Wertebereich der Funktion beide die Mächtigkeit $2^n$ haben, ist die Funktion auch injektiv. Somit ist gezeigt, dass die Funktion bijektiv ist. \hfill $\Box$

\section*{Aufgabe 7}
\begin{eqnarray*}
C(CSA_n) & = & 3 \cdot C(CSA_{\frac{n}{2}}) + 4 \cdot \frac{n}{2} \\
C(CSA_{\frac{n}{2}}) & = & 3 \cdot 3 \cdot C(CSA_{\frac{n}{4}}) + 4 \cdot \frac{n}{2} + 3 \cdot \left(4\cdot \frac{n}{2^2}\right) \\
\vdots & & \\
C(CSA_{\frac{n}{K}}) & = & 3^K \cdot C(CSA_{\frac{n}{2K}}) + \sum_{i=0}^{K-1} 3^i \left(\frac{2n}{2^i}\right)
\end{eqnarray*}
Für $K=log(n)$ erhält man eine geschlossene Formel:
\begin{eqnarray*}
C(CSA_{\frac{n}{log(n)}}) & = & 3^{log(n)} \cdot 3 + \sum_{i=0}^{log(n)-1} 3^i \left(\frac{2n}{2^i}\right) \\
& = & 3^{log(n)}\cdot 3 + 2n \cdot \sum_{i=0}^{log(n)-1} \left(\frac{3}{2}\right)^i \\
& = & 3^{log(n)}\cdot 3 + 2n \cdot \left(\frac{\left(\frac{3}{2}\right)^{log(n)}-1}{\left(\frac{3}{2}\right)-1}\right) \\
& = & 3^{log(n)}\cdot 3 + 4n \cdot \left(\left(\frac{3}{2}\right)^{log(n)}-1\right)
\end{eqnarray*}

\end{document}