Mercurial > 13ws.ds

comparison notes/tex/growth.tex @ 37:3de775b67d8c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
eigth sheet and notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 10 Dec 2013 01:58:46 +0100
parents
children e65f4b1a6e32
comparison
equal deleted inserted replaced
36:f386dfdaeade 37:3de775b67d8c
1 \defineUnit{landausymbole}{%
2 {
3 \pgfplotsset{
4 standard/.style={
5 axis lines=middle,
6 enlarge x limits=0.1,
7 enlarge y limits=0.1,
8 mark size=.4pt,
9 only marks,
10 xtick=\empty,
11 ytick=\empty,
12 xlabel={$\N$},
13 ylabel={$\R$},
14 every axis x label/.style={at={(current axis.right of origin)},anchor=west},
15 every axis y label/.style={at={(current axis.above origin)},anchor=south},
16 every x tick/.style={semithick, black},
17 domain=0:2,
18 samples=50,
19 clip=false,
20 height=.5\textheight,
21 }
22 }
23
24 \begin{frame}
25 \frametitle{Asymptotisches Verhalten}
26 \setbeamercovered{dynamic}
27
28 \begin{definition}[Asymptotisches Verhalten]
29 Eine Funktion $g$ ist \structure{asymptotisch größer} (\structure{wächst asymptotisch schneller}) als eine andere Funktion $f$, wenn gilt
30 \begin{align}
31 \exists n_0 > 0 \forall n \geq n_0.\; \left| f(n) \right| < \left| g(n) \right|
32 \end{align}
33 \end{definition}
34 \begin{itemize}
35 \item Der Einfachheit halber betrachten wir \alert{strikt positive} Funktionen
36 \item Dann sind die Beträge egal
37 \vspace{2em}
38 \item Oftmals sind \structure{Vorfaktoren} nicht interessant
39 \end{itemize}
40
41 \begin{center}
42 \begin{tikzpicture}
43 \begin{axis}[
44 standard,
45 extra x ticks={1},
46 extra x tick style={
47 thick,
48 xticklabel={$n_0$}
49 },
50 ]
51 \addplot[tumblue]{sqrt(x)} node[right]{$\hphantom{c_{<1} \cdot {}}f$};
52 \only<2->{
53 \addplot[tumblue]{.6 * sqrt(x)} node[right]{$c_{<1} \cdot f$};
54 \addplot[tumblue]{1.4 * sqrt(x)} node[right]{$c_{>1} \cdot f$};
55 }
56 \addplot[tumred]{2^x - 1} node[pos=0.95, above left]{$g$};
57 \only<1>{
58 \addplot[ycomb, mark=square*, mark size=1pt, semithick] plot coordinates {(1,1)};
59 }
60 \end{axis}
61 \end{tikzpicture}
62 \end{center}
63 \end{frame}
64
65 \begin{frame}
66 \frametitle{Landausymbole}
67 \setbeamercovered{dynamic}
68
69 \begin{definition}[Asymptotische obere Schranke]
70 Seien $f,g$ \alert{strikt positiv}.
71 Eine Funktion $f$ wächst \structure{asymptotisch maximal so schnell} wie eine Funktion $g$, wenn gilt
72 \begin{align}
73 \exists c > 0\exists n_0 > 0 \forall n \geq n_0.\; f(n) \leq c \cdot g(n)
74 \end{align}
75 wir schreiben dann
76 \begin{align}
77 f &\in \Oh(g)
78 \end{align}
79 \end{definition}
80
81 \vfill
82
83 \begin{center}
84 \begin{tikzpicture}
85 \begin{axis}[
86 standard,
87 extra x ticks={1},
88 extra x tick style={
89 thick,
90 xticklabel={$n_0$}
91 },
92 ]
93 \addplot[tumblue]{sqrt(x)} node[pos=0.9, below]{$f$};
94 \addplot[tumred]{2^x - 1} node[pos=0.95, above left]{$g$};
95 \addplot[ycomb, mark=square*, mark size=1pt, semithick] plot coordinates {(1,1)};
96 \end{axis}
97 \end{tikzpicture}
98 \end{center}
99 \end{frame}
100
101 \begin{frame}
102 \frametitle{Landausymbole}
103 \setbeamercovered{dynamic}
104
105 \begin{itemize}
106 \item $\Oh(g)$ ist eine Menge von Funktionen \ldots
107 \item \ldots die maximal so schnell wachsen wie $g$
108 \end{itemize}
109
110 \vspace{-1em}
111 \begin{columns}
112 \begin{column}{1.03\textwidth}
113 \begin{definition}[Landausymbole]
114 Seien $f,g$ \alert{strikt positiv}.
115 Analog zu $\Oh(g)$ definiert man weitere Mengen von Funktionen.
116 \begin{align}
117 \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}}\\
118 \noalign{\smallskip}
119 \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}}\\
120 \noalign{\smallskip}
121 %\structure{\Theta(g)} &\defeq \left\{ f \mid f \in \Oh(g) \wedge f \in \Omega(g) \right\} \tag{\structure{gleich schnell}}\\
122 \structure{\Theta(g)} &\defeq \Oh(g) \cap \Omega(g) \tag{\structure{gleich schnell}}\\
123 \noalign{\smallskip}
124 \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}}\\
125 \noalign{\smallskip}
126 \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}}
127 \end{align}
128 \vspace{-1em}
129 \end{definition}
130 \end{column}
131 \end{columns}
132
133 \vspace{2em}
134 Es ist
135 \begin{align}
136 o(g) &\subseteq \Oh(g) & o(g) \cap \Omega(g) &= \emptyset\\
137 \omega(g) &\subseteq \Omega(g) & \omega(g) \cap \Oh(g) &= \emptyset
138 \end{align}
139 \end{frame}
140
141 \begin{frame}[c]
142 \frametitle{Darstellung mit Grenzwerten}
143 \setbeamercovered{dynamic}
144
145 \begin{theorem}[Landausymbole mit Grenzwerten]
146 \smallskip
147 Existiert der Grenzwert $\lim_{n \to \infty} \left| \frac{f(n)}{g(n)} \right|$, dann gilt
148
149 \begin{align}
150 f &\in \structure{o(g)} &\text{gdw.}&& \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| = 0\\
151 f &\in \structure{\Oh(g)} &\text{gdw.}&& 0 \leq \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| < \infty\\
152 f &\in \structure{\Theta(g)} &\text{gdw.}&& 0 < \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| < \infty\\
153 f &\in \structure{\Omega(g)} &\text{gdw.}&& 0 < \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| \leq \infty\\
154 f &\in \structure{\omega(g)} &\text{gdw.}&& \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| = \infty
155 \end{align}
156 \end{theorem}
157 \end{frame}
158 }
159 }