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

\thispagestyle{empty}

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

\newpage
\section*{Aufgabe 1}
\subsubsection* {(a)}
Die Knoten in eine Knotenliste einlesen und dem 1. Knoten den \glqq Namen\grqq\ 0 geben, dem 2. Knoten den \glqq Namen\grqq\ 1 geben bis der letzte, n. Knoten, den \glqq Namen\grqq\ n-1 bekommt; \\
Dazu die Kanten merken; \\
Liste Sortierteliste = nil;
While (Suche jeweils einen Knoten mit dem ingrad(0) = true) \\
// Suche nach Quellen \\
\{ \\
Sortierteliste = Knoten @ Sortierteliste; \\
Entferne diesen Knoten aus der Knotenliste; \\
Entferne die von diesem Knoten ausgehenden Kanten; \\
\} \\
Ausgabe(Sortierteliste);

\subsubsection* {(b)}
1. \\
Beweis der Bedingung, dass eine Sortierung von $G$ eine injektive Funktion $s:V\rightarrow \SetN$ ist: \\
Gleich beim Einlesen wird jedem Knoten ein Wert $\in\SetN$ (bzw. \glqq Namen\grqq ) zugeordnet. Somit ist die Funktion $s$ injektiv. \hfill $\Box$ \\ \\
2. \\
Beweis, dass $\forall (u,v) \in E$ gilt: $s(u)<s(v)$: \\
Wenn man immer wieder die Quellen mit deren zugehörigen Kanten \glqq auswischt\grqq , kann es beim DAG nie passieren, dass $s(u)<s(v)$ nicht zutrifft. Die Quelle ist immer das jeweilige $s(u)$, da $ingrad(u)=0$. \hfill $\Box$ \\ \\
3. \\
Beweis der Terminierung des Algorithmus: \\
Jeder endliche DAG hat nur endlich viele Knoten n. Wenn man bei jedem Schritt einen Knoten wegnimmt, so gilt immer $n \succ n-1$. Die Gefahr, dass der Algorithmus scheitert, weil man auf einmal noch Knoten hat und keiner dieser mehr eine Quelle ist, ist nicht möglich, da ein DAG immer mindestens eine Quelle hat und jedesmal, wenn eine Quelle und ihre Kanten entfernt werden es mindestens einen anderen Knoten gibt, der eine Quelle ist. \hfill $\Box$

\section*{Aufgabe 2}
Beweis durch Widerspruch\\
Annahme: Jeder DAG hat eine Tiefe \\
Wähle nun einen Graphen, der eine Quelle und sonst nur Knoten mit $ingrad = 1$ und $outgrad = 1$ - somit auch keine Senke - hat (Ein Zyklus kommt laut Def. des DAG nicht vor). Dann hätte der Graph laut Annahme eine (bestimmbare) Tiefe. Da der Pfad von der Quelle durch den Graphen unendlich ist, kann man seine Tiefe nicht bestimmen. $\rightarrow$ Widerspruch \hfill $\Box$

\section*{Aufgabe 3}
        \begin{center}
        \begin{tabular}{cc}
        1. Vor.: & $ a^0 = 1 $\\
        2. Vor.: & $ a^{i+1} = a^i $\\
        \end{tabular}
        \end{center}
    \subsubsection*{(a)}
        $$a^{n+m} = a^n \cdot a^m$$
        \begin{eqnarray*}
        a^{n+m} & = & a^{(n+m-1)+1}\\
        & \stackrel{Vor.2}{=} & a^{(n+m-1)} \cdot a\\ 
        & = & a^{n+m-1-1+1} \cdot a\\
        & = & a^{n+m-2+1} \cdot a\\
        & = & a^{(n+m-2)+1} \cdot a\\
        & \stackrel{Vor.2}{=} & a^{(n+m-2)} \cdot a \cdot a\\
        & = & a^{(n+m-2)+1} \cdot a^1 \cdot a\\
        & = & a^{(n+m-2)} \cdot a^2\\
        & \vdots & \text {solange fortführen bis}\\
        & = & a^{n+m-m} \cdot a^m\\
        & = & a^{n+0} \cdot a^m\\
        & = & a^n \cdot a^m
        \end{eqnarray*}
        \hfill $\Box$
    \subsubsection*{(b)}
        Zu zeigen: $ (a \cdot b)^n = a^n \cdot b^n $
        Beweis durch vollständige Induktion über $n\in\SetN$:
        \begin{enumerate}
        \item Induktionsanfang: $n=0$:
        $$(\underbrace{a\cdot b}_{=z})^0 \stackrel{z^0=1}{=} 1 = 1 \cdot 1 = a^0 \cdot b^0$$
        
        \item
        \begin{enumerate}
        \item Induktionsannahme: Es gilt $\forall n \in \SetN$: $(a\cdot b)^n = a^n \cdot b^n$
        \item Induktionsbehauptung: \\
        Dann gilt auch für $(n+1)\in\SetN$: $(a\cdot b)^{n+1} = a^{n+1} \cdot b^{n+1}$
        \item Induktionsbegründung:
        \begin{eqnarray*}
        (a\cdot b)^{n+1} & \stackrel{Vor.2}{=} & (a\cdot b)^n \cdot (a\cdot b) \\
        & \stackrel{(2a)}{=} & a^n \cdot b^n \cdot a \cdot b = a^n \cdot a \cdot b^n \cdot b \\
        & \stackrel{\text{Teil (a)}}{=} & a^{n+1} \cdot b^{n+1}
        \end{eqnarray*}
        \end{enumerate}
        \end{enumerate}
        \hfill $\Box$

\newpage

\section*{Aufgabe 4}
Zu Zeigen: $ \displaystyle \sum_{i=0}^{n-1} (B-1) \cdot B^i = B^n-1$. \\
Beweis durch vollständige Induktion über $n\in\SetN$:
    \begin{enumerate}
    \item Induktionsanfang: $n=0$ \\
    $$\displaystyle \sum_{i=0}^{n-1} (B-1) \cdot B^i=\sum_{i=0}^{-1} (B-1) \cdot B^i=0\cdot B^i=0=1-1=B^0-1$$
    \item
    \begin{enumerate}
    \item Induktionsannahme: Es gilt $\displaystyle \forall n\in\SetN : \sum_{i=0}^{n-1} (B-1) \cdot B^i = B^n-1$
    \item Induktionsbehauptung: Dann gilt $\forall (n+1) \in\SetN$:\\
    $$\sum_{i=0}^n (B-1) \cdot B^i = B^{n+1}-1$$
    \item Induktionsbegründung:\\
    \begin{eqnarray*}
    \sum_{i=0}^n (B-1) \cdot B^i & = & \sum_{i=0}^{(n-1)+1} (B-1) \cdot B^i\\
    & = & \sum_{i=0}^{n-1} (B-1) \cdot B^i + (B-1) \cdot B^n\\
    & \stackrel{(2a)}{=} & B^n-1+(B-1) \cdot B^n\\
    & = & B^n-1+B\cdot B^n - B^n\\
    & = & -1+B^n\\
    & = & B^n-1
    \end{eqnarray*}
    \hfill $\Box$
    \end{enumerate}
    \end{enumerate}

\section*{Aufgabe 5}
Zu zeigen: $\left<a[n-1:0]\right>_B = B^h \cdot \left<a[n-1:h]\right>_B + \left<a[h-1:0]\right>_B$\\
\begin{eqnarray*}
B^h \cdot \left<a[n-1:h]\right>_B + \left<a[h-1:0]\right>_B & = & B^h \cdot \sum_{i=h}^{n-1} a_i \cdot B^{i-h} + \sum_{i=0}^{h-1} a_i \cdot B^i \\
& = & B^h \cdot \sum_{i=h}^{n-1} a_i \cdot \frac{B^i}{B^h} + \sum_{i=0}^{h-1} a_i \cdot B^i \\
& = & \sum_{i=h}^{n-1} a_i \cdot B^i + \sum_{i=0}^{h-1} a_i \cdot B^i \\
& = & \sum_{i=0}^{n-1} a_i \cdot B^i \\
& = & \left<a[n-1:0]\right>_B
\end{eqnarray*}
\hfill $\Box$

\section*{Aufgabe 6}
Sei $B\in\SetN; \; B \ge 2; \; a_i,b_i,c_i,s_i \in \{0,...,B-1\} \; \; \forall 0 \le i \le n-1; \; c_{-1} \in {0,1}; \\
\left<c_i \; s_i\right>_B = a_i + b_i + c_{i-1}$ (Vor.) \\
Zu zeigen: $\left<c_{n-1} \; s[n-1:0]\right>_B = \left<a[n-1:0]\right>_B + \left<b[n-1:0]\right>_B + c_{-1}$ \\
Beweis durch vollständige Induktion über $n\in\SetN$:
\begin{enumerate}
\item Induktionsanfang: $n=0$
\begin{eqnarray*}
\left<a[n-1:0]\right>_B + \left<b[n-1:0]\right>_B + c_{-1} & = & \sum_{i=0}^{n-1}a_i \cdot B^i + \sum_{i=0}^{n-1}b_i \cdot B^i + c_{-1} \\
& = & \sum_{i=0}^{-1}a_i \cdot B^i + \sum_{i=0}^{-1}b_i \cdot B^i + c_{-1} \\
& = & 0 + 0 + c_{-1} \\
& = & \left<a\right>_B + \left<b\right>_B + c_{-1} \\
& \stackrel{\text{lt. Vorl.}}{=} & \left<c_{n-1} \; s[n-1]:0\right>_B
\end{eqnarray*}
Die Voraussetzung ist auch erfüllt:
$$\left<c_0 \; s_0\right> = a_0 + b_0 + c_{-1}$$

\item
\begin{enumerate}
\item Induktionsannahme: Es gelte $\forall n\in\SetN$: $$\left<c_{n-1} \; s[n-1:0]\right>_B = \left<a[n-1:0]\right>_B + \left<b[n-1:0]\right>_B + c_{-1}$$

\item Induktionsbehauptung: Dann gilt auch $\forall (n+1)\in\SetN$:
$$ \left<c_n \; s[n:0]\right>_B = \left<a[n:0]\right>_B + \left<b[n:0]\right>_B + c_{-1}$$

\item Induktionsbegründung:
\begin{eqnarray*}
\left<c_n \; s[n:0]\right>_B & = & c_n \cdot B^{n+1} + s_n \cdot B^n + \left<s[n-1:0]\right>_B \\
& = & B \cdot c_n \cdot B^n + s_n \cdot B^n + \left<s[n-1:0]\right>_B \\
& = & \left<c_n \; s_n\right>_B \cdot B^n + \left<s[n-1:0]\right>_B \\
& = & (a_n + b_n + c_{n-1}) \cdot B^n + \left<s[n-1:0]\right>_B \\
& = & (a_n + b_n) \cdot B^n + c_{n-1} \cdot B^n + \left<s[n-1:0]\right>_B \\
& = & c_{n-1} \cdot B^n + \left<s[n-1:0]\right>_B + (a_n + b_n) \cdot B^n \\
& = & \left<c_{n-1} \; s[n-1:0]\right>_B + a_n \cdot B^n + b_n \cdot B^n \\
& \stackrel{(2a)}{=} & \left<a[n-1:0]\right>_B + \left<b[n-1:0]\right>_B + c_{-1} + a_n \cdot B^n + b_n \cdot B^n \\
& = & \left<a[n-1:0]\right>_B + a_n \cdot B^n + \left<b[n-1:0]\right>_B + b_n \cdot B^n + c_{-1} \\
& \stackrel{(*)}{=} & \left<a[n:0]\right>_B + \left<b[n:0]\right>_B + c_{-1} \\ \\
(*) \; \; \left<a[n:0]\right>_B & = & \sum_{i=0}^n a_i \cdot B^i = a_n \cdot B^n + \sum_{i=0}^{n-1} a_i \cdot B^i \\
& = & a_n \cdot B^n + \left<a[n-1:0]\right>_B
\end{eqnarray*}
\end{enumerate}

\end{enumerate}
\hfill $\Box$

\newpage

\section*{Aufgabe 7}
\begin{verbatim}
#include <iostream>
using namespace std;

int main (int argc, char** argv) 
{
int z;
cout << "Dezimalzahl eingeben" << endl;
cin >> z;

do 
  {
    z=z/2;
    cout << z/2 << " "; // die  " " sind nur für die Übersicht
  }
while (z>0);  
}
\end{verbatim}
Formel:\\
$x=$ Dezimalzahl\\
Zuerst bestimmt man $n = min\{t\;|\;x<2^t-1\}$ \\
$$
\left< \; \right>^{-1}: \{0, ...,2^n-1\} \rightarrow \{0,1\}^n, x \mapsto <a_{n-1}, a_{n-2}, ..., a_0> \; \; \text{ mit } \; \; a_i = ( \lfloor (\frac{x}{2^i}) \rfloor ) \bmod 2
$$

\end{document}