Mercurial > 13ss.theoinf
annotate notes/tex/ue09_notes.tex @ 37:27fedbbdab6d
change mapsto to to arrows
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Tue, 02 Jul 2013 14:16:16 +0200 |
parents | 844698060e1c |
children | 15351d87ce76 |
rev | line source |
---|---|
34 | 1 \input{preamble.tex} |
2 | |
3 \title{Übung 9: Berechnungsmodelle} | |
4 \subtitle{Theoretische Informatik Sommersemester 2013} | |
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} | |
6 | |
7 \begin{document} | |
8 | |
9 \begin{frame} | |
10 \titlepage | |
11 \end{frame} | |
12 | |
13 \begin{frame}[c] | |
14 \frametitle{Chomsky-Hierarchie} | |
15 \setbeamercovered{dynamic} | |
16 | |
17 \begin{center} | |
18 \begin{tikzpicture}[auto] | |
19 \tikzstyle{rect} = [thick]; | |
20 \tikzstyle{caption} = [align=left, anchor=north west]; | |
21 | |
35
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
22 \draw[rect, tumblue, fill=tumblue!10] (5.5, 0) rectangle (-5.5, 7) node[caption] {Berechenbare Funktionen}; |
34 | 23 \draw[rect, dashed, tumred, fill=tumred!10] (4.5, 0.3) rectangle (-4.5, 6) node[caption] {Typ 0 - Rekursiv aufzählbar\\Turingmaschinen, $\lambda$-Kalkül}; |
24 \draw[rect, tumivory, fill=tumivory!10] (3.5, 0.6) rectangle (-3.5, 4.8) node[caption] {Typ 1 - Kontextsensitiv\\CSG}; | |
25 \draw[rect, tumorange, fill=tumorange!10] (2.5, 0.9) rectangle (-2.5, 3.6) node[caption] {Typ 2 - Kontextfrei\\PDA, CFG}; | |
26 \draw[rect, tumgreen, fill=tumgreen!10] (1.5, 1.2) rectangle (-1.5, 2.4) node[caption] {Typ 3 - Regulär\\DFA, RE}; | |
27 \end{tikzpicture} | |
28 \end{center} | |
29 \end{frame} | |
30 | |
31 \begin{frame} | |
32 \frametitle{Berechenbarkeit} | |
33 \setbeamercovered{dynamic} | |
34 | |
35 \begin{definition}[Intuitive Berechenbarkeit] | |
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
35
diff
changeset
|
36 Eine Funktion $f : \N^k \to \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$ |
34 | 37 \begin{itemize} |
38 \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist, | |
39 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist. | |
40 \end{itemize} | |
41 \end{definition} | |
42 | |
43 \vfill | |
44 | |
45 \begin{block}{Churchsche These (nicht beweisbar)} | |
46 Turing-Maschinen können genau \alert{alle} intuitiv berechenbaren Funktionen berechnen. | |
47 \end{block} | |
48 \end{frame} | |
49 | |
50 \begin{frame}[c] | |
51 \frametitle{Berechenbarkeit} | |
52 \setbeamercovered{dynamic} | |
53 | |
54 \begin{example}[Berechenbarkeit] | |
55 Sind die folgenden Funktionen intuitiv berechenbar? | |
56 | |
57 \begin{align*} | |
58 f_1(n) &= \begin{cases} | |
59 1 & \text{falls $n$ prim}\\ | |
60 0 & \text{sonst} | |
61 \end{cases} \\ | |
62 f_2(n) &= \begin{cases} | |
63 1 & \text{falls $n$ die ersten $n$ Ziffern von $\pi$ darstellt}\\ | |
64 0 & \text{sonst} | |
65 \end{cases} \\ | |
66 f_3(n) &= \begin{cases} | |
67 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\ | |
68 0 & \text{sonst} | |
69 \end{cases} | |
70 \end{align*} | |
71 \end{example} | |
72 \end{frame} | |
73 | |
74 \begin{frame} | |
75 \frametitle{LOOP-Programme} | |
76 \setbeamercovered{dynamic} | |
77 | |
78 \begin{definition}[LOOP-Programm] | |
79 Syntax von \alert{LOOP-Programmen}.\\ | |
80 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. | |
81 \begin{align*} | |
82 P &\rightarrow X := X + C \\ | |
83 &\mid X := X - C \\ | |
84 &\mid P; P \\ | |
85 &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\ | |
86 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} | |
87 \end{align*} | |
88 \end{definition} | |
89 | |
90 \begin{itemize} | |
91 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. | |
92 \item $\mathbf{LOOP}\ x_i \ \mathbf{DO}\ P \ \mathbf{END}$ führt $P$ genau $n$ mal aus, wobei $n$ der Anfangswert von $x_i$ ist. \alert{Zuweisungen an $x_i$ in $P$ ändern die Anzahl der Durchläufe nicht.} | |
93 \end{itemize} | |
94 \end{frame} | |
95 | |
96 \begin{frame} | |
97 \frametitle{Primitive Rekursion} | |
98 \setbeamercovered{dynamic} | |
99 | |
100 \begin{definition}[Basisfunktionen] | |
101 \alert{Primitiv Rekursiv} sind: | |
102 \begin{itemize} | |
103 \item Die konstante Funktion \alert{0} | |
104 \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$ | |
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
35
diff
changeset
|
105 \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$ |
34 | 106 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] |
107 \end{itemize} | |
108 \end{definition} | |
109 | |
110 \begin{definition}[Komposition] | |
111 Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR: | |
112 \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \] | |
113 \end{definition} | |
114 \end{frame} | |
115 | |
116 \begin{frame} | |
117 \frametitle{Primitive Rekursion} | |
118 \setbeamercovered{dynamic} | |
119 \begin{block}{Basisfunktionen und Komposition} | |
120 Schon \alert{PR} sind: | |
121 \begin{itemize} | |
122 \item Konstante: $0$ | |
123 \item Nachfolger: $s(n) = n + 1$ | |
37
27fedbbdab6d
change mapsto to to arrows
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
35
diff
changeset
|
124 \item Projektion: $\pi_i^k : \N^k \to \N$ |
34 | 125 \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ |
126 \end{itemize} | |
127 \end{block} | |
128 | |
129 \begin{definition}[Primitive Rekursion] | |
130 Das Schema der \alert{primitiven Rekursion} erzeugt aus $g$ und $h$ die Funktion \alert{$f$}: | |
131 \begin{align*} | |
132 f(0, \bar{x}) &= g(\bar{x}) \\ | |
133 f(\alert{m + 1}, \bar{x}) &= h(f(\alert{m}, \bar{x}), \alert{m}, \bar{x}) | |
134 \end{align*} | |
135 \end{definition} | |
136 \end{frame} | |
137 | |
138 \begin{frame} | |
139 \frametitle{PR-Programme} | |
140 \setbeamercovered{dynamic} | |
141 | |
142 U.a. diese Programme sind laut Vorlesung oder Übung PR: | |
143 \begin{itemize} | |
144 \item \alert{$add(x, y) = x + y$} | |
145 \item \alert{$mult(x, y) = x \cdot y$} | |
35
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
146 \item $pred(x) = \max \left\{ 0, x - 1 \right\}$ |
34 | 147 \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$} |
148 \item $div(x, y) = x \div y$ (Ganzzahldivision) | |
149 \item $mod(x, y) = x \mod y$ | |
150 \vspace{1.5em} | |
151 \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ | |
152 \item $sqr(x) = x^2$ | |
153 \item $twopow(n) = 2^n$ | |
35
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
154 \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$ |
34 | 155 \end{itemize} |
156 \end{frame} | |
157 | |
158 \begin{frame} | |
159 \frametitle{Erweitertes PR-Schema} | |
160 \setbeamercovered{dynamic} | |
161 | |
162 \begin{definition}[Erweitertes PR-Schema] | |
163 Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt | |
164 \begin{align*} | |
165 f(0, \bar{x}) &= t_0 \\ | |
166 f(m + 1, \bar{x}) &= t | |
167 \end{align*} | |
168 wobei | |
169 \begin{itemize} | |
170 \item $t_0$ enthält nur PR-Funktionen und die $x_i$ | |
171 \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$. | |
172 \end{itemize} | |
173 \end{definition} | |
174 | |
175 \begin{theorem} | |
176 Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus. | |
177 \end{theorem} | |
178 \end{frame} | |
179 | |
180 \begin{frame} | |
35
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
181 \frametitle{Programmieren mit TMs} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
182 \setbeamercovered{dynamic} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
183 |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
184 Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
185 \begin{center} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
186 \begin{tikzpicture} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
187 \node (M) at (0, 0) {$M$}; |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
188 \node[above right=0.2cm and 1cm of M] (M1) {$M_1$}; |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
189 \node[below right=0.2cm and 1cm of M] (M2) {$M_2$}; |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
190 \coordinate[right of=M1] (M1s); |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
191 \coordinate[right of=M2] (M2s); |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
192 |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
193 \draw[every edge] (-1, 0) -- (M); |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
194 \draw[every edge] (M) -- node[above left] {$f_1$} (M1); |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
195 \draw[every edge] (M) -- node[below left] {$f_2$} (M2); |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
196 \draw[every edge] (M1) -- (M1s); |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
197 \draw[every edge] (M2) -- (M2s); |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
198 \end{tikzpicture} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
199 \end{center} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
200 eine \alert{Fallunterscheidung}.\\ |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
201 \begin{example}[Band=0?] |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
202 \begin{align*} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
203 \delta(q_0, 0) &= (q_0, 0, R) \\ |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
204 \delta(q_0, \square) &= (ja, \square, L) \\ |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
205 \delta(q_0, a) &= (nein, a, N) \qquad \text{für} a \neq 0, \square |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
206 \end{align*} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
207 \end{example} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
208 \end{frame} |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
209 |
844698060e1c
move frame down; minor erros
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
34
diff
changeset
|
210 \begin{frame} |
34 | 211 \frametitle{WHILE-Programme} |
212 \setbeamercovered{dynamic} | |
213 | |
214 \begin{definition}[WHILE-Programm] | |
215 Syntax von \alert{WHILE-Programmen}.\\ | |
216 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. | |
217 \begin{align*} | |
218 P &\rightarrow X := X + C \\ | |
219 &\mid X := X - C \\ | |
220 &\mid P; P \\ | |
221 &\mid \alert{\mathbf{WHILE}\ X \neq 0 \ \mathbf{DO}\ P \ \mathbf{END}} \\ | |
222 &\mid \textcolor{gray}{\mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END}} \\ | |
223 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} | |
224 \end{align*} | |
225 \end{definition} | |
226 | |
227 \begin{itemize} | |
228 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. | |
229 \item Semantik wie erwartet. | |
230 \end{itemize} | |
231 \end{frame} | |
232 | |
233 \begin{frame} | |
234 \frametitle{GOTO-Programme} | |
235 \setbeamercovered{dynamic} | |
236 | |
237 \begin{definition}[GOTO-Programm] | |
238 Syntax von \alert{GOTO-Programmen}.\\ | |
239 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \\ | |
240 Alle Anweisungen haben eine Markierung \alert{$M_1 : A_1; M_2 : A_2$}. | |
241 \begin{align*} | |
242 P &\rightarrow X := X + C \\ | |
243 &\mid X := X - C \\ | |
244 &\mid P; P \\ | |
245 &\mid \mathbf{GOTO}\ M_i \\ | |
246 &\mid \mathbf{IF}\ X = 0 \ \mathbf{GOTO}\ M_i \\ | |
247 &\mid \mathbf{HALT} | |
248 \end{align*} | |
249 \end{definition} | |
250 | |
251 \begin{itemize} | |
252 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. | |
253 \end{itemize} | |
254 \end{frame} | |
255 | |
256 \begin{frame} | |
257 \frametitle{Übersetzungen} | |
258 \setbeamercovered{dynamic} | |
259 | |
260 \begin{center} | |
261 \begin{tikzpicture}[node distance=2.5cm] | |
262 \node (WH) {WHILE}; | |
263 \node (GO) [above left of = WH] {GOTO}; | |
264 \node (TM) [above right of = WH] {TM}; | |
265 \node (LO) [below of = WH] {LOOP}; | |
266 \node (PR) [left of = LO] {PR}; | |
267 | |
268 \draw [every edge, ->] (LO) -- (WH); | |
269 \draw [every edge, tumgreen, <->] (LO) -- (PR); | |
270 \draw [every edge, <->] (WH) -- (GO); | |
271 \draw [every edge, ->] (WH) -- (TM); | |
272 \draw [every edge, ->] (TM) -- (GO); | |
273 \end{tikzpicture} | |
274 \end{center} | |
275 | |
276 \vfill | |
277 | |
278 LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger). | |
279 \end{frame} | |
280 | |
281 \end{document} |