--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/growth.tex	Tue Dec 10 01:58:46 2013 +0100
@@ -0,0 +1,159 @@
+\defineUnit{landausymbole}{%
+{
+    \pgfplotsset{
+        standard/.style={
+            axis lines=middle,
+            enlarge x limits=0.1,
+            enlarge y limits=0.1,
+            mark size=.4pt,
+            only marks,
+            xtick=\empty,
+            ytick=\empty,
+            xlabel={$\N$},
+            ylabel={$\R$},
+            every axis x label/.style={at={(current axis.right of origin)},anchor=west},
+            every axis y label/.style={at={(current axis.above origin)},anchor=south},
+            every x tick/.style={semithick, black},
+            domain=0:2,
+            samples=50,
+            clip=false,
+            height=.5\textheight,
+        }
+    }
+
+    \begin{frame}
+        \frametitle{Asymptotisches Verhalten}
+        \setbeamercovered{dynamic}
+
+        \begin{definition}[Asymptotisches Verhalten]
+            Eine Funktion $g$ ist \structure{asymptotisch größer} (\structure{wächst asymptotisch schneller}) als eine andere Funktion $f$, wenn gilt
+            \begin{align}
+                \exists n_0 > 0 \forall n \geq n_0.\; \left| f(n) \right| < \left| g(n) \right|
+            \end{align}
+        \end{definition}
+        \begin{itemize}
+            \item Der Einfachheit halber betrachten wir \alert{strikt positive} Funktionen
+            \item Dann sind die Beträge egal
+            \vspace{2em}
+            \item Oftmals sind \structure{Vorfaktoren} nicht interessant
+        \end{itemize}
+
+        \begin{center}
+            \begin{tikzpicture}
+                \begin{axis}[
+                        standard,
+                        extra x ticks={1},
+                        extra x tick style={
+                            thick,
+                            xticklabel={$n_0$}
+                        },
+                    ]
+                    \addplot[tumblue]{sqrt(x)} node[right]{$\hphantom{c_{<1} \cdot {}}f$};
+                    \only<2->{
+                        \addplot[tumblue]{.6 * sqrt(x)} node[right]{$c_{<1} \cdot f$};
+                        \addplot[tumblue]{1.4 * sqrt(x)} node[right]{$c_{>1} \cdot f$};
+                    }
+                    \addplot[tumred]{2^x - 1} node[pos=0.95, above left]{$g$};
+                    \only<1>{
+                        \addplot[ycomb, mark=square*, mark size=1pt, semithick] plot coordinates {(1,1)};
+                    }
+                \end{axis}
+            \end{tikzpicture}
+        \end{center}
+    \end{frame}
+
+    \begin{frame}
+        \frametitle{Landausymbole}
+        \setbeamercovered{dynamic}
+
+        \begin{definition}[Asymptotische obere Schranke]
+            Seien $f,g$ \alert{strikt positiv}.
+            Eine Funktion $f$ wächst \structure{asymptotisch maximal so schnell} wie eine Funktion $g$, wenn gilt
+            \begin{align}
+                \exists c > 0\exists n_0 > 0 \forall n \geq n_0.\; f(n) \leq c \cdot g(n)
+            \end{align}
+            wir schreiben dann
+            \begin{align}
+                f &\in \Oh(g)
+            \end{align}
+        \end{definition}
+
+        \vfill
+
+        \begin{center}
+            \begin{tikzpicture}
+                \begin{axis}[
+                        standard,
+                        extra x ticks={1},
+                        extra x tick style={
+                            thick,
+                            xticklabel={$n_0$}
+                        },
+                    ]
+                    \addplot[tumblue]{sqrt(x)} node[pos=0.9, below]{$f$};
+                    \addplot[tumred]{2^x - 1} node[pos=0.95, above left]{$g$};
+                    \addplot[ycomb, mark=square*, mark size=1pt, semithick] plot coordinates {(1,1)};
+                \end{axis}
+            \end{tikzpicture}
+        \end{center}
+    \end{frame}
+
+    \begin{frame}
+        \frametitle{Landausymbole}
+        \setbeamercovered{dynamic}
+
+        \begin{itemize}
+            \item $\Oh(g)$ ist eine Menge von Funktionen \ldots
+            \item \ldots die maximal so schnell wachsen wie $g$
+        \end{itemize}
+
+        \vspace{-1em}
+        \begin{columns}
+            \begin{column}{1.03\textwidth}
+                \begin{definition}[Landausymbole]
+                    Seien $f,g$ \alert{strikt positiv}.
+                    Analog zu $\Oh(g)$ definiert man weitere Mengen von Funktionen.
+                    \begin{align}
+                        \structure{o(g)} &\defeq \left\{ f \mid \alert{\forall c} > 0\exists n_0 > 0 \forall n \geq n_0.\; f(n) \alert{<} c \cdot g(n) \right\} \tag{\structure{langsamer}}\\
+                        \noalign{\smallskip}
+                        \structure{\Oh(g)} &\defeq \left\{ f \mid \alert{\exists c} > 0\exists n_0 > 0 \forall n \geq n_0.\; f(n) \alert{\leq} c \cdot g(n) \right\} \tag{\structure{nicht schneller}}\\
+                        \noalign{\smallskip}
+                        %\structure{\Theta(g)} &\defeq \left\{ f \mid  f \in \Oh(g) \wedge f \in \Omega(g) \right\} \tag{\structure{gleich schnell}}\\
+                        \structure{\Theta(g)} &\defeq \Oh(g) \cap \Omega(g) \tag{\structure{gleich schnell}}\\
+                        \noalign{\smallskip}
+                        \structure{\Omega(g)} &\defeq \left\{ f \mid \alert{\exists c} > 0\exists n_0 > 0 \forall n \geq n_0.\; f(n) \alert{\geq} c \cdot g(n) \right\} \tag{\structure{nicht langsamer}}\\
+                        \noalign{\smallskip}
+                        \structure{\omega(g)} &\defeq \left\{ f \mid \alert{\forall c} > 0\exists n_0 > 0 \forall n \geq n_0.\; f(n) \alert{>} c \cdot g(n) \right\} \tag{\structure{schneller}}
+                    \end{align}
+                    \vspace{-1em}
+                \end{definition}
+            \end{column}
+        \end{columns}
+
+        \vspace{2em}
+        Es ist
+        \begin{align}
+            o(g) &\subseteq \Oh(g) & o(g) \cap \Omega(g) &= \emptyset\\
+            \omega(g) &\subseteq \Omega(g) & \omega(g) \cap \Oh(g) &= \emptyset
+        \end{align}
+    \end{frame}
+
+    \begin{frame}[c]
+        \frametitle{Darstellung mit Grenzwerten}
+        \setbeamercovered{dynamic}
+
+        \begin{theorem}[Landausymbole mit Grenzwerten]
+            \smallskip
+            Existiert der Grenzwert $\lim_{n \to \infty} \left| \frac{f(n)}{g(n)} \right|$, dann gilt
+
+            \begin{align}
+                f &\in \structure{o(g)} &\text{gdw.}&& \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| = 0\\
+                f &\in \structure{\Oh(g)} &\text{gdw.}&& 0 \leq \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| < \infty\\
+                f &\in \structure{\Theta(g)} &\text{gdw.}&& 0 < \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| < \infty\\
+                f &\in \structure{\Omega(g)} &\text{gdw.}&& 0 < \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| \leq \infty\\
+                f &\in \structure{\omega(g)} &\text{gdw.}&& \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| = \infty
+            \end{align}
+        \end{theorem}
+    \end{frame}
+}
+}