# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1386637126 -3600
# Node ID 3de775b67d8c2dd0c0fc7faacd02ccf95faf94b4
# Parent  f386dfdaeade5fcc8bc02916ad0662e44d698bd6
eigth sheet and notes

diff -r f386dfdaeade -r 3de775b67d8c ds13-08.pdf
Binary file ds13-08.pdf has changed
diff -r f386dfdaeade -r 3de775b67d8c notes/tex/frames.tex
--- a/notes/tex/frames.tex	Mon Dec 02 23:41:32 2013 +0100
+++ b/notes/tex/frames.tex	Tue Dec 10 01:58:46 2013 +0100
@@ -10,3 +10,4 @@
 \input{intro.tex}
 \input{basics.tex}
 \input{logic.tex}
+\input{growth.tex}
diff -r f386dfdaeade -r 3de775b67d8c notes/tex/growth.tex
--- /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}
+}
+}
diff -r f386dfdaeade -r 3de775b67d8c notes/tex/logic.tex
--- a/notes/tex/logic.tex	Mon Dec 02 23:41:32 2013 +0100
+++ b/notes/tex/logic.tex	Tue Dec 10 01:58:46 2013 +0100
@@ -957,3 +957,56 @@
     \end{itemize}
 \end{frame}
 }
+
+\defineUnit{wohlfundierteinduktion}{%
+\begin{frame}
+    \frametitle{Wohlfundierte Relation}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Wohlfundierte Relation]
+        Eine Relation $\prec \subseteq A \times A$ heißt \structure{wohlfundiert}, wenn keine \alert{unendlichen Folgen} von Elementen $a_1, a_2, a_3, \dots \in A$ existieren, sodass
+        \[a_1 \succ a_2 \succ a_3 \succ \dots\]
+        Jede Kette hat ein \structure{unteres Ende}.
+    \end{definition}
+
+    \vfill
+
+    \begin{example}[]
+        \begin{itemize}
+            \item $\prec_1 \defeq \left\{ (a, b) \in \N^2 \mid a < b \right\}$ ist wohlfundiert.
+            \item $\prec_2 \defeq \left\{ (a, b) \in \N^2 \mid a > b \right\}$ ist \alert{nicht} wohlfundiert.
+            \item $\prec_3 \defeq \left\{ (a, b) \in \Z^2 \mid a < b \right\}$ ist \alert{nicht} wohlfundiert.
+            \item $\prec_4 \defeq \left\{ (a, b) \in \N^2 \mid \exists x . x \text{ teilt } a \wedge x \text{ teilt } b \right\}$ ist \alert{nicht} wohlfundiert.
+                \smallskip
+            \item $\prec_5 \defeq \emptyset$ ist wohlfundiert.
+        \end{itemize}
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Wohlfundierte Induktion}
+    \setbeamercovered{dynamic}
+
+    \begin{block}{Wohlfundierte Induktion}
+        Die \structure{wohlfundierte Induktion} verallgemeinert die vollständige Induktion.\\
+        Um für eine Menge $A$ mit wohlfundierter Relation $\prec$ ein Prädikat
+        \[ \alert{\forall a \in A.\; P(a)} \]
+        zu zeigen, beweist man
+        \begin{description}[Induktionsanfang\quad]
+            \item[Induktionsanfang] Man zeigt, dass für alle bezüglich $\prec$ \structure{minimalen} Elemente $m_i$ das Prädikat gilt.
+            \item[Induktionsschritt] Man zeigt, dass wenn \structure{alle kleineren} Elemente als $n$ das Prädikat erfüllen, so auch $n$.
+        \end{description}
+        \vspace{1em}
+        In Prädikatenlogik formuliert gilt
+        \begin{align}
+            \structure{\forall a \in A. \left( \forall b \prec a.\; P(b) \rightarrow P(a) \right)} \quad\text{gdw.}\quad \alert{\forall a \in A.\; P(a)}
+        \end{align}
+    \end{block}
+
+    \vfill
+
+    \begin{itemize}
+        \item Wo ist der Induktionsanfang?
+    \end{itemize}
+\end{frame}
+}
diff -r f386dfdaeade -r 3de775b67d8c notes/tex/ue08_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue08_notes.tex	Tue Dec 10 01:58:46 2013 +0100
@@ -0,0 +1,12 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 8: Induktion II \& Landausymbole}
+\subtitle{Diskrete Strukturen im Wintersemester 2013/2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{wohlfundierteinduktion}
+\showUnit{landausymbole}
+\end{document}
diff -r f386dfdaeade -r 3de775b67d8c notes/ue08_notes.pdf
Binary file notes/ue08_notes.pdf has changed