|
37
|
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 |
|
|
27 \begin{definition}[Asymptotisches Verhalten] |
|
|
28 Eine Funktion $g$ ist \structure{asymptotisch größer} (\structure{wächst asymptotisch schneller}) als eine andere Funktion $f$, wenn gilt |
|
|
29 \begin{align} |
|
|
30 \exists n_0 > 0 \forall n \geq n_0.\; \left| f(n) \right| < \left| g(n) \right| |
|
|
31 \end{align} |
|
|
32 \end{definition} |
|
|
33 \begin{itemize} |
|
|
34 \item Der Einfachheit halber betrachten wir \alert{strikt positive} Funktionen |
|
|
35 \item Dann sind die Beträge egal |
|
|
36 \vspace{2em} |
|
|
37 \item Oftmals sind \structure{Vorfaktoren} nicht interessant |
|
|
38 \end{itemize} |
|
|
39 |
|
|
40 \begin{center} |
|
|
41 \begin{tikzpicture} |
|
|
42 \begin{axis}[ |
|
|
43 standard, |
|
|
44 extra x ticks={1}, |
|
|
45 extra x tick style={ |
|
|
46 thick, |
|
|
47 xticklabel={$n_0$} |
|
|
48 }, |
|
|
49 ] |
|
|
50 \addplot[tumblue]{sqrt(x)} node[right]{$\hphantom{c_{<1} \cdot {}}f$}; |
|
|
51 \only<2->{ |
|
|
52 \addplot[tumblue]{.6 * sqrt(x)} node[right]{$c_{<1} \cdot f$}; |
|
|
53 \addplot[tumblue]{1.4 * sqrt(x)} node[right]{$c_{>1} \cdot f$}; |
|
|
54 } |
|
|
55 \addplot[tumred]{2^x - 1} node[pos=0.95, above left]{$g$}; |
|
|
56 \only<1>{ |
|
|
57 \addplot[ycomb, mark=square*, mark size=1pt, semithick] plot coordinates {(1,1)}; |
|
|
58 } |
|
|
59 \end{axis} |
|
|
60 \end{tikzpicture} |
|
|
61 \end{center} |
|
|
62 \end{frame} |
|
|
63 |
|
|
64 \begin{frame} |
|
|
65 \frametitle{Landausymbole} |
|
|
66 |
|
|
67 \begin{definition}[Asymptotische obere Schranke] |
|
|
68 Seien $f,g$ \alert{strikt positiv}. |
|
|
69 Eine Funktion $f$ wächst \structure{asymptotisch maximal so schnell} wie eine Funktion $g$, wenn gilt |
|
|
70 \begin{align} |
|
|
71 \exists c > 0\exists n_0 > 0 \forall n \geq n_0.\; f(n) \leq c \cdot g(n) |
|
|
72 \end{align} |
|
|
73 wir schreiben dann |
|
|
74 \begin{align} |
|
|
75 f &\in \Oh(g) |
|
|
76 \end{align} |
|
|
77 \end{definition} |
|
|
78 |
|
|
79 \vfill |
|
|
80 |
|
|
81 \begin{center} |
|
|
82 \begin{tikzpicture} |
|
|
83 \begin{axis}[ |
|
|
84 standard, |
|
|
85 extra x ticks={1}, |
|
|
86 extra x tick style={ |
|
|
87 thick, |
|
|
88 xticklabel={$n_0$} |
|
|
89 }, |
|
|
90 ] |
|
|
91 \addplot[tumblue]{sqrt(x)} node[pos=0.9, below]{$f$}; |
|
|
92 \addplot[tumred]{2^x - 1} node[pos=0.95, above left]{$g$}; |
|
|
93 \addplot[ycomb, mark=square*, mark size=1pt, semithick] plot coordinates {(1,1)}; |
|
|
94 \end{axis} |
|
|
95 \end{tikzpicture} |
|
|
96 \end{center} |
|
|
97 \end{frame} |
|
|
98 |
|
|
99 \begin{frame} |
|
|
100 \frametitle{Landausymbole} |
|
|
101 |
|
|
102 \begin{itemize} |
|
|
103 \item $\Oh(g)$ ist eine Menge von Funktionen \ldots |
|
|
104 \item \ldots die maximal so schnell wachsen wie $g$ |
|
|
105 \end{itemize} |
|
|
106 |
|
|
107 \vspace{-1em} |
|
|
108 \begin{columns} |
|
|
109 \begin{column}{1.03\textwidth} |
|
|
110 \begin{definition}[Landausymbole] |
|
|
111 Seien $f,g$ \alert{strikt positiv}. |
|
|
112 Analog zu $\Oh(g)$ definiert man weitere Mengen von Funktionen. |
|
|
113 \begin{align} |
|
|
114 \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}}\\ |
|
|
115 \noalign{\smallskip} |
|
|
116 \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}}\\ |
|
|
117 \noalign{\smallskip} |
|
|
118 %\structure{\Theta(g)} &\defeq \left\{ f \mid f \in \Oh(g) \wedge f \in \Omega(g) \right\} \tag{\structure{gleich schnell}}\\ |
|
|
119 \structure{\Theta(g)} &\defeq \Oh(g) \cap \Omega(g) \tag{\structure{gleich schnell}}\\ |
|
|
120 \noalign{\smallskip} |
|
|
121 \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}}\\ |
|
|
122 \noalign{\smallskip} |
|
|
123 \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}} |
|
|
124 \end{align} |
|
|
125 \vspace{-1em} |
|
|
126 \end{definition} |
|
|
127 \end{column} |
|
|
128 \end{columns} |
|
|
129 |
|
|
130 \vspace{2em} |
|
|
131 Es ist |
|
|
132 \begin{align} |
|
|
133 o(g) &\subseteq \Oh(g) & o(g) \cap \Omega(g) &= \emptyset\\ |
|
|
134 \omega(g) &\subseteq \Omega(g) & \omega(g) \cap \Oh(g) &= \emptyset |
|
|
135 \end{align} |
|
|
136 \end{frame} |
|
|
137 |
|
|
138 \begin{frame}[c] |
|
|
139 \frametitle{Darstellung mit Grenzwerten} |
|
|
140 |
|
|
141 \begin{theorem}[Landausymbole mit Grenzwerten] |
|
|
142 \smallskip |
|
|
143 Existiert der Grenzwert $\lim_{n \to \infty} \left| \frac{f(n)}{g(n)} \right|$, dann gilt |
|
|
144 |
|
|
145 \begin{align} |
|
|
146 f &\in \structure{o(g)} &\text{gdw.}&& \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| = 0\\ |
|
|
147 f &\in \structure{\Oh(g)} &\text{gdw.}&& 0 \leq \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| < \infty\\ |
|
|
148 f &\in \structure{\Theta(g)} &\text{gdw.}&& 0 < \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| < \infty\\ |
|
|
149 f &\in \structure{\Omega(g)} &\text{gdw.}&& 0 < \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| \leq \infty\\ |
|
|
150 f &\in \structure{\omega(g)} &\text{gdw.}&& \lim_{n \to \infty} &\left| \frac{f(n)}{g(n)} \right| = \infty |
|
|
151 \end{align} |
|
|
152 \end{theorem} |
|
|
153 \end{frame} |
|
|
154 } |
|
|
155 } |
