|
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 |
|
|
22 \draw[rect, tumblue, fill=tumblue!10] (5.5, 0) rectangle (-5.5, 7) node[caption] {Alle Algorithmen}; |
|
|
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] |
|
|
36 Eine Funktion $f : \N^k \mapsto \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$ |
|
|
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{Programmieren mit TMs} |
|
|
76 \setbeamercovered{dynamic} |
|
|
77 |
|
|
78 Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet |
|
|
79 \begin{center} |
|
|
80 \begin{tikzpicture} |
|
|
81 \node (M) at (0, 0) {$M$}; |
|
|
82 \node[above right=0.2cm and 1cm of M] (M1) {$M_1$}; |
|
|
83 \node[below right=0.2cm and 1cm of M] (M2) {$M_2$}; |
|
|
84 \coordinate[right of=M1] (M1s); |
|
|
85 \coordinate[right of=M2] (M2s); |
|
|
86 |
|
|
87 \draw[every edge] (-1, 0) -- (M); |
|
|
88 \draw[every edge] (M) -- node[above left] {$f_1$} (M1); |
|
|
89 \draw[every edge] (M) -- node[below left] {$f_2$} (M2); |
|
|
90 \draw[every edge] (M1) -- (M1s); |
|
|
91 \draw[every edge] (M2) -- (M2s); |
|
|
92 \end{tikzpicture} |
|
|
93 \end{center} |
|
|
94 eine \alert{Fallunterscheidung}.\\ |
|
|
95 \begin{example}[Band=0?] |
|
|
96 \begin{align*} |
|
|
97 \delta(q_0, 0) &= (q_0, 0, R) \\ |
|
|
98 \delta(q_0, \square) &= (ja, \square, L) \\ |
|
|
99 \delta(q_0, a) &= (nein, a, N) \qquad \text{für} a \neq 0, \square |
|
|
100 \end{align*} |
|
|
101 \end{example} |
|
|
102 \end{frame} |
|
|
103 |
|
|
104 \begin{frame} |
|
|
105 \frametitle{LOOP-Programme} |
|
|
106 \setbeamercovered{dynamic} |
|
|
107 |
|
|
108 \begin{definition}[LOOP-Programm] |
|
|
109 Syntax von \alert{LOOP-Programmen}.\\ |
|
|
110 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. |
|
|
111 \begin{align*} |
|
|
112 P &\rightarrow X := X + C \\ |
|
|
113 &\mid X := X - C \\ |
|
|
114 &\mid P; P \\ |
|
|
115 &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\ |
|
|
116 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} |
|
|
117 \end{align*} |
|
|
118 \end{definition} |
|
|
119 |
|
|
120 \begin{itemize} |
|
|
121 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. |
|
|
122 \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.} |
|
|
123 \end{itemize} |
|
|
124 \end{frame} |
|
|
125 |
|
|
126 \begin{frame} |
|
|
127 \frametitle{Primitive Rekursion} |
|
|
128 \setbeamercovered{dynamic} |
|
|
129 |
|
|
130 \begin{definition}[Basisfunktionen] |
|
|
131 \alert{Primitiv Rekursiv} sind: |
|
|
132 \begin{itemize} |
|
|
133 \item Die konstante Funktion \alert{0} |
|
|
134 \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$ |
|
|
135 \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \mapsto \N, i \in [k]$ |
|
|
136 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] |
|
|
137 \end{itemize} |
|
|
138 \end{definition} |
|
|
139 |
|
|
140 \begin{definition}[Komposition] |
|
|
141 Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR: |
|
|
142 \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \] |
|
|
143 \end{definition} |
|
|
144 \end{frame} |
|
|
145 |
|
|
146 \begin{frame} |
|
|
147 \frametitle{Primitive Rekursion} |
|
|
148 \setbeamercovered{dynamic} |
|
|
149 \begin{block}{Basisfunktionen und Komposition} |
|
|
150 Schon \alert{PR} sind: |
|
|
151 \begin{itemize} |
|
|
152 \item Konstante: $0$ |
|
|
153 \item Nachfolger: $s(n) = n + 1$ |
|
|
154 \item Projektion: $\pi_i^k : \N^k \mapsto \N$ |
|
|
155 \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ |
|
|
156 \end{itemize} |
|
|
157 \end{block} |
|
|
158 |
|
|
159 \begin{definition}[Primitive Rekursion] |
|
|
160 Das Schema der \alert{primitiven Rekursion} erzeugt aus $g$ und $h$ die Funktion \alert{$f$}: |
|
|
161 \begin{align*} |
|
|
162 f(0, \bar{x}) &= g(\bar{x}) \\ |
|
|
163 f(\alert{m + 1}, \bar{x}) &= h(f(\alert{m}, \bar{x}), \alert{m}, \bar{x}) |
|
|
164 \end{align*} |
|
|
165 \end{definition} |
|
|
166 \end{frame} |
|
|
167 |
|
|
168 \begin{frame} |
|
|
169 \frametitle{PR-Programme} |
|
|
170 \setbeamercovered{dynamic} |
|
|
171 |
|
|
172 U.a. diese Programme sind laut Vorlesung oder Übung PR: |
|
|
173 \begin{itemize} |
|
|
174 \item \alert{$add(x, y) = x + y$} |
|
|
175 \item \alert{$mult(x, y) = x \cdot y$} |
|
|
176 \item $pred(x + 1) = \max \left\{ 0, x \right\}$ |
|
|
177 \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$} |
|
|
178 \item $div(x, y) = x \div y$ (Ganzzahldivision) |
|
|
179 \item $mod(x, y) = x \mod y$ |
|
|
180 \vspace{1.5em} |
|
|
181 \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ |
|
|
182 \item $sqr(x) = x^2$ |
|
|
183 \item $twopow(n) = 2^n$ |
|
|
184 \item $ifthen(n, a, b) = \begin{cases} a & n = 0 \\ b & n \neq 0 \end{cases}$ |
|
|
185 \end{itemize} |
|
|
186 \end{frame} |
|
|
187 |
|
|
188 \begin{frame} |
|
|
189 \frametitle{Erweitertes PR-Schema} |
|
|
190 \setbeamercovered{dynamic} |
|
|
191 |
|
|
192 \begin{definition}[Erweitertes PR-Schema] |
|
|
193 Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt |
|
|
194 \begin{align*} |
|
|
195 f(0, \bar{x}) &= t_0 \\ |
|
|
196 f(m + 1, \bar{x}) &= t |
|
|
197 \end{align*} |
|
|
198 wobei |
|
|
199 \begin{itemize} |
|
|
200 \item $t_0$ enthält nur PR-Funktionen und die $x_i$ |
|
|
201 \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$. |
|
|
202 \end{itemize} |
|
|
203 \end{definition} |
|
|
204 |
|
|
205 \begin{theorem} |
|
|
206 Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus. |
|
|
207 \end{theorem} |
|
|
208 \end{frame} |
|
|
209 |
|
|
210 \begin{frame} |
|
|
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} |
