datalog.tex

gistfile1.txt

\documentclass[12pt, a4paper]{scrartcl}
\usepackage{fancyhdr}
\usepackage[ngerman]{babel}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{setspace}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\newcommand{\abs}[1]{\ensuremath{\left\vert#1\right\vert}}
\newcommand{\qed}{\hfill \ensuremath{\Box}}
\geometry{a4paper, portrait, left=1.5cm, right=1.5cm, top=1.8cm, bottom=1.5cm, foot=0.5cm}
\raggedbottom
\onehalfspacing

\pagestyle{fancy} %eigener Seitenstil
\fancyhf{} %alle Kopf- und Fußzeilenfelder bereinigen
\fancyhead[L]{Datenstrukturen und Algorithmen\\Lösungen zu Übungsblatt 1} %Kopfzeile links
\fancyhead[C]{} %zentrierte Kopfzeile
\fancyhead[R]{307760 - Tim Buchwaldt\\Übungsgruppe 5} %Kopfzeile rechts
\renewcommand{\headrulewidth}{0.4pt} %obere Trennlinie
\fancyfoot[C]{\thepage} %Seitennummer
\begin{document}
\section*{Aufgabe H1}
\begin{eqnarray*}
\frac{1}{O(n)}=\Omega (\frac{1}{n}) \Leftrightarrow \frac{1}{O(n)} \subseteq \Omega (\frac{1}{n})
\end{eqnarray*}
Sei $f(n) = \frac{1}{n}$ und $g(n) = \frac{1}{O(n)}$, dann ist zu zeigen, dass
\begin{eqnarray*}
\liminf_{n \to \infty} \frac{\abs{g(n)}}{\abs{f(n)}} = \liminf_{n \to \infty} \frac{\abs{n}}{\abs{O(n)}} \neq 0.
\end{eqnarray*}
Sei $\hat f(n) = O(n)$ und damit $\hat f(n) \leq c\abs{n} \quad \exists c \neq 0 \quad \forall n > n_0$. Nun muss man zwischen zwei Fällen unterscheiden:

1. $\hat f(n) = c\abs{n}$: Der Faktor $n$ ist sowohl im Zähler als auch Nenner vorhanden, wodurch man ihn kürzen kann. Für den Grenzwert des Ausdrucks ergibt sich dann genau $\frac{1}{c} \neq 0 \quad \forall c \neq 0$.

2. $\hat f(n) < c\abs{n}$: In diesem Fall überwiegt für große $n$ der Zähler den Nenner, woraus sich ein Grenzwert $g > 1 \neq 0$ ergibt.

Die Bedingung ist somit in allen möglichen Fällen für $\hat f(n)$ erfüllt und die obige Aussage damit wahr.$\qed$
\section*{Aufgabe H2.1}
Zu zeigen: ${\lim \sup}_{n \to \infty}\left| \frac{n^{\log n}}{(\log n)^n} \right|$ existiert. Für den Logarithmus gilt, dass er zur Basis 2 ist (jede andere Basis würde aber genau so funktionieren). Zunächst formen wir den Term um:
\begin{equation*} \begin{split}
&\limsup_{n \to \infty}\left| \frac{n^{\log n}}{(\log n)^n} \right| \\[6pt]
=&\limsup_{n \to \infty}\left| \frac{2^{log (n^{\log n})}}{2^{log((\log n)^n)}} \right| \\[6pt]
=&\limsup_{n \to \infty}\left| 2^{\log (n^{\log n})-\log ((\log n)^n)} \right| \\[6pt]
=&\limsup_{n \to \infty}\left| 2^{\log n \cdot \log n - n \cdot \log (\log n)} \right| \\[6pt]
\end{split} \end{equation*}
Betrachten wir den Exponenten des Ausdrucks. Es gilt $\log n \ll n$ für große $n$. Folglich gilt auch:
\begin{equation*} \begin{split}
\log n \cdot \log n < n \log (\log n) \quad \vert -(n \log (\log n)) \\
\log n \cdot \log n - n \log (\log n) < 0 \quad \vert \text{ für große n}
\end{split} \end{equation*}
Der Exponent des Ausdrucks ist für große $n$ negativ. Weiterhin gilt $a^{-b} = \frac{1}{a^b}$. Somit können wir für $n \to \infty$ sagen
\begin{equation*}
\limsup_{n \to \infty}\left| 2^{\log n \cdot \log n - n \cdot \log (\log n)} \right| = 0.
\end{equation*}
Es existiert also ein Grenzwert und die Bedingung für $O((\log n)^n)$ ist erfüllt. Wäre der Grenzwert $\neq 0$, so wäre auch die Bedingung für $\Omega ((\log n)^n)$ erfüllt, dies ist in diesem Fall aber nicht gegeben.

\section*{Aufgabe H2.2}
Annahme: 
\begin{equation*}
(\sqrt{n})^{n^2} = \Omega ((n^2)^n)
\end{equation*}
Zu zeigen:
\begin{equation*} \begin{split}
&(\sqrt{n})^{n^2} \geq (n^2)^n \quad \forall n \in \mathbb{N}, n \geq n_0 \\
&\Leftrightarrow (n^{\frac{1}{2}})^{n^2} \geq n^{2n} \\
&\Leftrightarrow n^{\frac{1}{2}n^2} \geq n^{2n} \quad \vert \log_{n} \cdot \\
&\Leftrightarrow \frac{1}{2}n^2 \geq 2n \quad \vert : n \\
&\Leftrightarrow \frac{1}{2}n \geq 2 \quad \vert \cdot 2 \\
&\Leftrightarrow n \geq 4
\end{split} \end{equation*}
Somit gilt:
\begin{equation*} \begin{split}
(\sqrt{n})^{n^2} \geq (n^2)^n \quad \forall n \in \mathbb{N}, n \geq 4
\end{split} \end{equation*}
und damit
\begin{equation*} \begin{split}
(\sqrt{n})^{n^2} = \Omega ((n^2)^n) \quad \forall n \geq 4
\end{split} \end{equation*}
Da $(\sqrt{n})^{n^2}$ ab $n=4$ sogar echt größer als $(n^2)^n$, gilt auch $(\sqrt{n})^{n^2} \neq O((n^2)^n)$.
\section*{Aufgabe H2.3}
$H_{n}$ ist die Harmonische Reihe. Laut Definition\footnote{S. Skiema: "`The Algorithm Design Manual"', Telos, 1997. Seite 48f.} gilt: $H_{n} \sim \ln n$. Daraus folgt: $H_{n} = \Theta (\ln n)$ und damit $H_{n} = O(\ln n) \wedge H_{n} = \Omega (\ln n)$.
\section*{Aufgabe H3}
Folgendes gilt und wird gleich benötigt:
\begin{equation}\sum_{i=a}^{b}c=(b-a+1) \cdot c \quad \vert \text{ c ist unabhängig von i}\end{equation}
Die Gaußsche Summenformel:\begin{equation}\sum_{i=1}^{n}i=\frac{n \cdot (n+1)}{2}\end{equation}
Die Quadratische Pyramidalzahl:\begin{equation}\sum_{i=1}^{n}i^{2}=\frac{1}{6}n \cdot (n+1) \cdot (2n+1)\end{equation}
Der Quellcode lässt sich als eine Folge von Summen beschreiben. Jede for-Schleife entspricht einer Summe. Für den print-Befehl in der innersten Schleife wird ein konstanter Wert 1 berechnet. Es ergibt sich somit folgende Gleichung für $f(n)$:
\begin{equation*} \begin{split}
&f(n)=\sum_{i=1}^{n}\sum_{j=i}^{n}\sum_{k=i}^{j}1\\
&=\sum_{i=1}^{n}\sum_{j=i}^{n}(j-i+1)\quad \vert \text{ nach (1)}\\
&=\sum_{i=1}^{n}((i-i+1)+((i+1)-i+1)+\cdots+(n-i+1))\\
&=\sum_{i=1}^{n}(1+2+\cdots+(n-i+1))\\
&=\sum_{i=1}^{n}\sum_{j=1}^{n-i+1}j\\
&=\sum_{i=1}^{n}\frac{(n-i+1) \cdot ((n-i+1)+1)}{2}\quad\vert\text{ nach (2)}\\
&=\sum_{i=1}^{n}\frac{(n-i+1) \cdot (n-i+2)}{2}\\
&=\sum_{i=1}^{n}\frac{n^{2}+n-in-in-i+i^{2}+2n+2-2i}{2}\\
&=\sum_{i=1}^{n}\frac{n^{2}+3n-2in-3i+i^{2}+2}{2}\\
&=\sum_{i=1}^{n}(\frac{n^{2}}{2}+\frac{3n}{2}-\frac{2in}{2}-\frac{3i}{2}+\frac{i^{2}}{2}+\frac{2}{2})\\
&=\sum_{i=1}^{n}\frac{n^{2}}{2}+\sum_{i=1}^{n}\frac{3n}{2}-\sum_{i=1}^{n}in-\sum_{i=1}^{n}\frac{3i}{2}+\sum_{i=1}^{n}\frac{i^{2}}{2}+\sum_{i=1}^{n}1\quad \vert \text{ n ist unabh. von i, deswegen}\\
&=\frac{1}{2}n^{2}\sum_{i=1}^{n}1+\frac{3}{2}n\sum_{i=1}^{n}1-n\sum_{i=1}^{n}i-\frac{3}{2}\sum_{i=1}^{n}i+\frac{1}{2}\sum_{i=1}^{n}i^{2}+\sum_{i=1}^{n}1\quad \vert \text{ kann man es aus der Summe ziehen}\\
&=\frac{1}{2}n^{2} \cdot n+\frac{3}{2}n \cdot n-n \cdot \frac{n \cdot (n+1)}{2}-\frac{3}{2} \cdot \frac{n \cdot (n+1)}{2}+\frac{1}{2} \cdot \frac{1}{6} \cdot n \cdot (n+1) \cdot (2n+1)+n\quad \vert \text{ nach (1)-(3)}\\
&=\frac{1}{2}n^{3}+\frac{3}{2}n^{2}-\frac{n^{3}+n^{2}}{2}-\frac{3n^{2}+3n}{4}+\frac{2n^{3}+3n^{2}+n}{12}+n\\
&=\frac{1}{6} \cdot n^{3}+\frac{1}{2} \cdot n^{2}+\frac{1}{3} \cdot n \\
&=\frac{1}{6} (n^{3}+3n^{2}+2n)\\
\qed
\end{split} \end{equation*}
\end{document}