Mercurial > 13ss.theoinf
comparison notes/tex/ue09_notes.tex @ 34:d89b21ed9eb4
ue09 notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Tue, 25 Jun 2013 00:11:39 +0200 |
parents | |
children | 844698060e1c |
comparison
equal
deleted
inserted
replaced
33:cb59a72b2ea1 | 34:d89b21ed9eb4 |
---|---|
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} |