|
1
|
1 \defineUnit{tmdefinition}{% |
|
|
2 \begin{frame} |
|
|
3 \frametitle{Turingmaschinen} |
|
|
4 \setbeamercovered{dynamic} |
|
|
5 |
|
|
6 \begin{definition}[Turingmaschine] |
|
|
7 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem |
|
|
8 \begin{itemize} |
|
|
9 \item endlichen Menge von \alert{Zuständen} $Q$ |
|
|
10 \item endlichen \alert{Eingabealphabet} $\Sigma$ |
|
|
11 \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$ |
|
|
12 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ |
|
|
13 \item \alert{Startzustand} $q_0 \in Q$ |
|
|
14 \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$ |
|
|
15 \item Menge von \alert{Endzuständen} $F \subseteq Q$ |
|
|
16 \end{itemize} |
|
|
17 \end{definition} |
|
|
18 \end{frame} |
|
|
19 } |
|
|
20 |
|
|
21 \defineUnit{tmvisualisierung}{% |
|
|
22 \begin{frame} |
|
|
23 \frametitle{Turingmaschinen} |
|
|
24 \setbeamercovered{dynamic} |
|
|
25 |
|
|
26 \begin{definition}[Turingmaschine] |
|
|
27 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem |
|
|
28 \begin{itemize} |
|
|
29 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ |
|
|
30 \end{itemize} |
|
|
31 \end{definition} |
|
|
32 |
|
|
33 \vfill |
|
|
34 |
|
|
35 \begin{center} |
|
|
36 \begin{tikzpicture} |
|
|
37 % Tape |
|
|
38 \begin{scope}[start chain, node distance=0] |
|
|
39 \node[on chain] {\ldots}; |
|
|
40 \node[tape] {$\square$}; |
|
|
41 \node[tape] (l) {$\square$}; |
|
|
42 \node[tape] {$0$}; |
|
|
43 \node[tape] {$1$}; |
|
|
44 \node<1>[tape, active] (a){$0$}; |
|
|
45 \node<2>[tape] (a){$1$}; |
|
|
46 \node<1>[tape] (b){$0$}; |
|
|
47 \node<2>[tape, active] (b){$0$}; |
|
|
48 \node[tape] {$\square$}; |
|
|
49 \node[on chain] {\ldots}; |
|
|
50 \end{scope} |
|
|
51 |
|
|
52 % Head |
|
|
53 \node<1> [head,yshift=-4mm] at (a.south) (head) {$q_0$}; |
|
|
54 \node<2> [head,yshift=-4mm] at (b.south) (head) {$q_1$}; |
|
|
55 |
|
|
56 % Machine |
|
|
57 \node[machine, below=1.5cm of l] (machine) {Programm}; |
|
|
58 \draw[every edge] (machine) .. controls (3.5, -2) .. (head.south); |
|
|
59 |
|
|
60 % Example-Transition |
|
|
61 \node[yshift=5mm] at (current bounding box.north) {$\delta(q_0, 0) = (q_1, 1, R)$}; |
|
|
62 \end{tikzpicture} |
|
|
63 \end{center} |
|
|
64 \end{frame} |
|
|
65 } |
|
|
66 |
|
|
67 \defineUnit{tmkonfiguration}{% |
|
|
68 \begin{frame} |
|
|
69 \frametitle{Turingmaschinen} |
|
|
70 \setbeamercovered{dynamic} |
|
|
71 |
|
|
72 \begin{definition}[Konfiguration] |
|
|
73 Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\ |
|
|
74 Dies modelliert eine TM mit: |
|
|
75 \begin{itemize} |
|
|
76 \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$ |
|
|
77 \item \alert{Zustand} $q$ |
|
|
78 \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$ |
|
|
79 \end{itemize} |
|
|
80 Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$. |
|
|
81 \end{definition} |
|
|
82 |
|
|
83 \vfill |
|
|
84 |
|
|
85 \only<1> { |
|
|
86 \begin{center} |
|
|
87 \begin{tikzpicture} |
|
|
88 % Tape |
|
|
89 \begin{scope}[start chain, node distance=0] |
|
|
90 \node[on chain] {\ldots}; |
|
|
91 \node[tape] {$\square$}; |
|
|
92 \node[tape] (l) {$\square$}; |
|
|
93 \node[tape] {$0$}; |
|
|
94 \node[tape] {$1$}; |
|
|
95 \node[tape] (a){$1$}; |
|
|
96 \node[tape, active] (b){$0$}; |
|
|
97 \node[tape] {$\square$}; |
|
|
98 \node[on chain] {\ldots}; |
|
|
99 \end{scope} |
|
|
100 |
|
|
101 % Head |
|
|
102 \node [head,yshift=-4mm] at (b.south) (head) {$q_1$}; |
|
|
103 |
|
|
104 % Machine |
|
|
105 \node[below=1.5cm of l] (machine) {}; |
|
|
106 \draw[every edge, dashed] (machine) .. controls (3.5, -2) .. (head.south); |
|
|
107 |
|
|
108 % Example-Transition |
|
|
109 \node[yshift=5mm] at (current bounding box.north) {$(011,q_1,0)$}; |
|
|
110 \end{tikzpicture} |
|
|
111 \end{center} |
|
|
112 } |
|
|
113 |
|
|
114 \only<2> { |
|
|
115 \begin{definition}[Akzeptanz] |
|
|
116 Eine TM $M$ \alert{akzeptiert} die Sprache |
|
|
117 \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \] |
|
|
118 \end{definition} |
|
|
119 } |
|
|
120 \end{frame} |
|
|
121 } |
|
|
122 |
|
|
123 \defineUnit{ndtm}{% |
|
|
124 \begin{frame} |
|
|
125 \frametitle{Nichtdeterministische TM} |
|
|
126 \setbeamercovered{dynamic} |
|
|
127 |
|
|
128 \begin{definition}[Nichtdeterministische Turingmaschine] |
|
|
129 Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem |
|
|
130 \begin{itemize} |
|
|
131 \item \ldots |
|
|
132 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$ |
|
|
133 \item \ldots |
|
|
134 \end{itemize} |
|
|
135 \end{definition} |
|
|
136 |
|
|
137 \vfill |
|
|
138 |
|
|
139 \begin{theorem} |
|
|
140 Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}. |
|
|
141 \end{theorem} |
|
|
142 \end{frame} |
|
|
143 } |
|
|
144 |
|
|
145 \defineUnit{chomsky}{% |
|
|
146 \begin{frame}[c] |
|
|
147 \frametitle{Chomsky-Hierarchie} |
|
|
148 \setbeamercovered{dynamic} |
|
|
149 |
|
|
150 \begin{center} |
|
|
151 \begin{tikzpicture}[auto] |
|
|
152 \tikzstyle{rect} = [thick]; |
|
|
153 \tikzstyle{caption} = [align=left, anchor=north west]; |
|
|
154 |
|
3
|
155 \chomsky{tumlightblue}{}{0}{Alle formalen Sprachen}; |
|
|
156 \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik}; |
|
|
157 \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik}; |
|
|
158 \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal}; |
|
|
159 \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik}; |
|
1
|
160 \end{tikzpicture} |
|
|
161 \end{center} |
|
|
162 \end{frame} |
|
|
163 } |
|
|
164 |
|
|
165 \defineUnit{berechenbarkeit}{% |
|
|
166 \begin{frame} |
|
|
167 \frametitle{Berechenbarkeit} |
|
|
168 \setbeamercovered{dynamic} |
|
|
169 |
|
|
170 \begin{definition}[Intuitive Berechenbarkeit] |
|
|
171 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$ |
|
|
172 \begin{itemize} |
|
|
173 \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist, |
|
|
174 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist. |
|
|
175 \end{itemize} |
|
|
176 \end{definition} |
|
|
177 |
|
|
178 \vfill |
|
|
179 |
|
|
180 \begin{block}{Churchsche These (nicht beweisbar)} |
|
|
181 Turing-Maschinen können genau \alert{alle} intuitiv berechenbaren Funktionen berechnen. |
|
|
182 \end{block} |
|
|
183 \end{frame} |
|
|
184 } |
|
|
185 |
|
|
186 \defineUnit{berechenbarkeitbeispiel}{% |
|
|
187 \begin{frame}[c] |
|
|
188 \frametitle{Berechenbarkeit} |
|
|
189 \setbeamercovered{dynamic} |
|
|
190 |
|
|
191 \begin{example}[Berechenbarkeit] |
|
|
192 Sind die folgenden Funktionen intuitiv berechenbar? |
|
|
193 |
|
|
194 \begin{align*} |
|
|
195 f_1(n) &= \begin{cases} |
|
|
196 1 & \text{falls $n$ prim}\\ |
|
|
197 0 & \text{sonst} |
|
|
198 \end{cases} \\ |
|
|
199 f_2(n) &= \begin{cases} |
|
|
200 1 & \text{falls $n$ die ersten $n$ Ziffern von $\pi$ darstellt}\\ |
|
|
201 0 & \text{sonst} |
|
|
202 \end{cases} \\ |
|
|
203 f_3(n) &= \begin{cases} |
|
|
204 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\ |
|
|
205 0 & \text{sonst} |
|
|
206 \end{cases} |
|
|
207 \end{align*} |
|
|
208 \end{example} |
|
|
209 \end{frame} |
|
|
210 } |
|
|
211 |
|
|
212 \defineUnit{pr}{% |
|
|
213 \begin{frame} |
|
|
214 \frametitle{Primitive Rekursion} |
|
|
215 \setbeamercovered{dynamic} |
|
|
216 |
|
|
217 \begin{definition}[Basisfunktionen] |
|
|
218 \alert{Primitiv Rekursiv} sind: |
|
|
219 \begin{itemize} |
|
|
220 \item Die konstante Funktion \alert{0} |
|
|
221 \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$ |
|
|
222 \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$ |
|
|
223 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] |
|
|
224 \end{itemize} |
|
|
225 \end{definition} |
|
|
226 |
|
|
227 \begin{definition}[Komposition] |
|
|
228 Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR: |
|
|
229 \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \] |
|
|
230 \end{definition} |
|
|
231 \end{frame} |
|
|
232 } |
|
|
233 |
|
|
234 \defineUnit{prrekursion}{% |
|
|
235 \begin{frame} |
|
|
236 \frametitle{Primitive Rekursion} |
|
|
237 \setbeamercovered{dynamic} |
|
|
238 \begin{block}{Basisfunktionen und Komposition} |
|
|
239 Schon \alert{PR} sind: |
|
|
240 \begin{itemize} |
|
|
241 \item Konstante: $0$ |
|
|
242 \item Nachfolger: $s(n) = n + 1$ |
|
|
243 \item Projektion: $\pi_i^k : \N^k \to \N$ |
|
|
244 \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ |
|
|
245 \end{itemize} |
|
|
246 \end{block} |
|
|
247 \begin{definition}[Primitive Rekursion] Das Schema der \alert{primitiven Rekursion} erzeugt aus $g$ und $h$ die Funktion \alert{$f$}: \begin{align*} f(0, \bar{x}) &= g(\bar{x}) \\ f(\alert{m + 1}, \bar{x}) &= h(f(\alert{m}, \bar{x}), \alert{m}, \bar{x}) \end{align*} \end{definition} \end{frame} |
|
|
248 } |
|
|
249 |
|
|
250 \defineUnit{prprogramme}{% |
|
|
251 \begin{frame} |
|
|
252 \frametitle{PR-Programme} |
|
|
253 \setbeamercovered{dynamic} |
|
|
254 |
|
|
255 U.a. diese Programme sind laut Vorlesung oder Übung PR: |
|
|
256 \begin{itemize} |
|
|
257 \item $pred(x) = \max \left\{ 0, x - 1 \right\}$ |
|
|
258 \item \alert{$add(x, y) = x + y$} |
|
|
259 \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$} |
|
|
260 \item \alert{$mult(x, y) = x \cdot y$} |
|
|
261 \item $div(x, y) = x \div y$ (Ganzzahldivision) |
|
|
262 \item Die restliche einfache Arithmetik\ldots |
|
|
263 \vspace{1.5em} |
|
|
264 \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ |
|
|
265 \item $sqr(x) = x^2$, $sqrt(x) = \sqrt{x}$ |
|
|
266 \item $c(x), p_1(x), p_2(x)$ (Cantorsche Paarungsfunktion) |
|
|
267 \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$ |
|
|
268 \end{itemize} |
|
|
269 \end{frame} |
|
|
270 } |
|
|
271 |
|
|
272 \defineUnit{prerweitert}{% |
|
|
273 \begin{frame} |
|
|
274 \frametitle{Erweitertes PR-Schema} |
|
|
275 \setbeamercovered{dynamic} |
|
|
276 |
|
|
277 \begin{definition}[Erweitertes PR-Schema] |
|
|
278 Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt |
|
|
279 \begin{align*} |
|
|
280 f(0, \bar{x}) &= t_0 \\ |
|
|
281 f(m + 1, \bar{x}) &= t |
|
|
282 \end{align*} |
|
|
283 wobei |
|
|
284 \begin{itemize} |
|
|
285 \item $t_0$ enthält nur PR-Funktionen und die $x_i$ |
|
|
286 \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$. |
|
|
287 \end{itemize} |
|
|
288 \end{definition} |
|
|
289 |
|
|
290 \begin{theorem} |
|
|
291 Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus. |
|
|
292 \end{theorem} |
|
|
293 \end{frame} |
|
|
294 } |
|
|
295 |
|
|
296 \defineUnit{tmif}{% |
|
|
297 \begin{frame} |
|
|
298 \frametitle{Programmieren mit TMs} |
|
|
299 \setbeamercovered{dynamic} |
|
|
300 |
|
|
301 Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet |
|
|
302 \begin{center} |
|
|
303 \begin{tikzpicture} |
|
|
304 \node (M) at (0, 0) {$M$}; |
|
|
305 \node[above right=0.2cm and 1cm of M] (M1) {$M_1$}; |
|
|
306 \node[below right=0.2cm and 1cm of M] (M2) {$M_2$}; |
|
|
307 \coordinate[right of=M1] (M1s); |
|
|
308 \coordinate[right of=M2] (M2s); |
|
|
309 |
|
|
310 \draw[every edge] (-1, 0) -- (M); |
|
|
311 \draw[every edge] (M) -- node[above left] {$f_1$} (M1); |
|
|
312 \draw[every edge] (M) -- node[below left] {$f_2$} (M2); |
|
|
313 \draw[every edge] (M1) -- (M1s); |
|
|
314 \draw[every edge] (M2) -- (M2s); |
|
|
315 \end{tikzpicture} |
|
|
316 \end{center} |
|
|
317 eine \alert{Fallunterscheidung}.\\ |
|
|
318 \begin{example}[Band=0?] |
|
|
319 \begin{align*} |
|
|
320 \delta(q_0, 0) &= (q_0, 0, R) \\ |
|
|
321 \delta(q_0, \square) &= (ja, \square, L) \\ |
|
|
322 \delta(q_0, a) &= (nein, a, N) \qquad \text{für } a \neq 0, \square |
|
|
323 \end{align*} |
|
|
324 \end{example} |
|
|
325 \end{frame} |
|
|
326 } |
|
|
327 |
|
|
328 \defineUnit{while}{% |
|
|
329 \begin{frame} |
|
|
330 \frametitle{WHILE-Programme} |
|
|
331 \setbeamercovered{dynamic} |
|
|
332 |
|
|
333 \begin{definition}[WHILE-Programm] |
|
|
334 Syntax von \alert{WHILE-Programmen}.\\ |
|
|
335 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. |
|
|
336 \begin{align*} |
|
|
337 P &\rightarrow X := X + C \\ |
|
|
338 &\mid X := X - C \\ |
|
|
339 &\mid P; P \\ |
|
|
340 &\mid \alert{\mathbf{WHILE}\ X \neq 0 \ \mathbf{DO}\ P \ \mathbf{END}} \\ |
|
|
341 &\mid \textcolor{gray}{\mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END}} \\ |
|
|
342 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} |
|
|
343 \end{align*} |
|
|
344 \end{definition} |
|
|
345 |
|
|
346 \begin{itemize} |
|
|
347 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. |
|
|
348 \item Semantik wie erwartet. |
|
|
349 \end{itemize} |
|
|
350 \end{frame} |
|
|
351 } |
|
|
352 |
|
|
353 \defineUnit{goto}{% |
|
|
354 \begin{frame} |
|
|
355 \frametitle{GOTO-Programme} |
|
|
356 \setbeamercovered{dynamic} |
|
|
357 |
|
|
358 \begin{definition}[GOTO-Programm] |
|
|
359 Syntax von \alert{GOTO-Programmen}.\\ |
|
|
360 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \\ |
|
|
361 Alle Anweisungen haben eine Markierung \alert{$M_1 : A_1; M_2 : A_2$}. |
|
|
362 \begin{align*} |
|
|
363 P &\rightarrow X := X + C \\ |
|
|
364 &\mid X := X - C \\ |
|
|
365 &\mid P; P \\ |
|
|
366 &\mid \mathbf{GOTO}\ M_i \\ |
|
|
367 &\mid \mathbf{IF}\ X = 0 \ \mathbf{GOTO}\ M_i \\ |
|
|
368 &\mid \mathbf{HALT} |
|
|
369 \end{align*} |
|
|
370 \end{definition} |
|
|
371 |
|
|
372 \begin{itemize} |
|
|
373 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. |
|
|
374 \end{itemize} |
|
|
375 \end{frame} |
|
|
376 } |
|
|
377 |
|
|
378 \defineUnit{loop}{% |
|
|
379 \begin{frame} |
|
|
380 \frametitle{LOOP-Programme} |
|
|
381 \setbeamercovered{dynamic} |
|
|
382 |
|
|
383 \begin{definition}[LOOP-Programm] |
|
|
384 Syntax von \alert{LOOP-Programmen}.\\ |
|
|
385 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. |
|
|
386 \begin{align*} |
|
|
387 P &\rightarrow X := X + C \\ |
|
|
388 &\mid X := X - C \\ |
|
|
389 &\mid P; P \\ |
|
|
390 &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\ |
|
|
391 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} |
|
|
392 \end{align*} |
|
|
393 \end{definition} |
|
|
394 |
|
|
395 \begin{itemize} |
|
|
396 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. |
|
|
397 \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.} |
|
|
398 \end{itemize} |
|
|
399 \end{frame} |
|
|
400 } |
|
|
401 |
|
|
402 \defineUnit{prmax}{% |
|
|
403 \begin{frame} |
|
|
404 \frametitle{Beschränkte Operationen} |
|
|
405 \setbeamercovered{dynamic} |
|
|
406 \begin{definition} |
|
|
407 Ein Prädikat $P$ ist \alert{PR}, wenn es eine PR Funktion $\hat{P}$ gibt mit |
|
|
408 \[\hat{P}(x) = 1 \Longleftrightarrow P(x)\] |
|
|
409 \end{definition} |
|
|
410 |
|
|
411 \begin{definition}[Beschränkte Operationen] |
|
|
412 Ist $P$ PR, dann auch |
|
|
413 \begin{itemize} |
|
|
414 \item der \alert{beschränkte max-Operator} |
|
|
415 \[\max \left\{ x \alert{\leq n} \mid P(x) \right\}, \quad \max \left\{ \emptyset \right\} = 0\] |
|
|
416 \item der \alert{beschränkte Existenzquantor} |
|
|
417 \[\exists x \alert{\leq n}. P(x)\] |
|
|
418 \end{itemize} |
|
|
419 \end{definition} |
|
|
420 \end{frame} |
|
|
421 } |
|
|
422 |
|
|
423 \defineUnit{murekursion}{% |
|
|
424 \begin{frame} |
|
|
425 \frametitle{$\mu$-Rekursion} |
|
|
426 \setbeamercovered{dynamic} |
|
|
427 |
|
|
428 \begin{definition}[$\mu$-Operator] |
|
|
429 Sei $f: \N^{k+1} \to \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \to \N$: |
|
|
430 \[(\mu f)(\bar{x}) := \begin{cases} \min \left\{ n \in \N \mid \alert{f (n, \bar{x}) = 0}\right\} & \text{falls } n \text{ existent\alert{$^*$}} \\ \perp & \text{sonst}\end{cases}\] |
|
|
431 \end{definition} |
|
|
432 |
|
|
433 \vfill |
|
|
434 |
|
|
435 \begin{itemize} |
|
|
436 \item \alert{$^*$}Für alle \alert{$m \leq n$} muss $f$ definiert sein: $f(m, \bar{x}) \neq \perp$ |
|
|
437 \item PR + $\mu$ = $\mu$-Rekursion |
|
|
438 \item In Pseudocode: |
|
|
439 \begin{align*} |
|
|
440 \mu f(\bar{x}) &= find(0, \bar{x}) \\ |
|
|
441 find(n, \bar{x}) &= \mathbf{if}\ f(n, \bar{x}) = 0 \ \mathbf{then}\ n \ \mathbf{else}\ find(n+1, \bar{x}) |
|
|
442 \end{align*} |
|
|
443 \end{itemize} |
|
|
444 \end{frame} |
|
|
445 } |
|
|
446 |
|
|
447 \defineUnit{modelluebersetzungen}{% |
|
|
448 \begin{frame} |
|
|
449 \frametitle{Übersetzungen} |
|
|
450 \setbeamercovered{dynamic} |
|
|
451 |
|
|
452 \begin{center} |
|
|
453 \begin{tikzpicture}[node distance=2.5cm] |
|
|
454 \node (WH) {WHILE}; |
|
|
455 \node (GO) [above left of = WH] {GOTO}; |
|
|
456 \node (TM) [above right of = WH] {TM}; |
|
|
457 \node (LO) [below of = WH] {LOOP}; |
|
|
458 \node (PR) [left of = LO] {PR}; |
|
|
459 \node (MR) [left of = WH] {$\mu$R}; |
|
|
460 |
|
|
461 \draw [every edge, ->] (LO) -- (WH); |
|
|
462 \draw [every edge, ->] (PR) -- (MR); |
|
|
463 \draw [every edge, tumgreen, <->] (LO) -- (PR); |
|
|
464 \draw [every edge, tumgreen, <->] (WH) -- (MR); |
|
|
465 \draw [every edge, <->] (WH) -- (GO); |
|
|
466 \draw [every edge, ->] (WH) -- (TM); |
|
|
467 \draw [every edge, ->] (TM) -- (GO); |
|
|
468 \end{tikzpicture} |
|
|
469 \end{center} |
|
|
470 |
|
|
471 \vfill |
|
|
472 |
|
|
473 LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger). |
|
|
474 \end{frame} |
|
|
475 } |
|
|
476 |
|
|
477 \defineUnit{entscheidbarkeit}{% |
|
|
478 \begin{frame} |
|
|
479 \frametitle{Entscheidbarkeit} |
|
|
480 \setbeamercovered{dynamic} |
|
|
481 |
|
|
482 \begin{definition}[Entscheidbarkeit] |
|
|
483 Eine Menge $A$ heißt \alert{entscheidbar} gdw ihre \alert{charakteristische Funktion} |
|
|
484 \[ \chi_A(x) := \begin{cases}1 & \text{falls } x \in A \\ 0 & \text{falls } x \not \in A \end{cases} \] |
|
|
485 berechenbar ist. |
|
|
486 \end{definition} |
|
|
487 |
|
|
488 \begin{definition}[Semi-Entscheidbarkeit] |
|
|
489 Eine Menge $A$ heißt \alert{semi-entscheidbar} gdw |
|
|
490 \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \] |
|
|
491 berechenbar ist. |
|
|
492 \end{definition} |
|
|
493 \end{frame} |
|
|
494 } |
|
|
495 |
|
|
496 \defineUnit{breduktion}{% |
|
|
497 \begin{frame} |
|
|
498 \frametitle{Reduzierbarkeit} |
|
|
499 \setbeamercovered{dynamic} |
|
|
500 |
|
|
501 \begin{definition}[Reduzierbarkeit] |
|
|
502 Eine Menge $A \subseteq \Sigma^*$ ist \alert{reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit |
|
|
503 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] |
|
|
504 Wir schreiben dann \alert{$A \leq B$}. |
|
|
505 \end{definition} |
|
|
506 |
|
|
507 \vfill |
|
|
508 |
|
|
509 \structure{Intuition}: |
|
|
510 \begin{itemize} |
|
|
511 \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$ |
|
|
512 \item Ist $A$ unlösbar, dann auch $B$. |
|
|
513 \item Ist $B$ lösbar, dann erst recht $A$. |
|
|
514 \end{itemize} |
|
|
515 \end{frame} |
|
|
516 } |
|
|
517 |
|
|
518 \defineUnit{spezielleshalteproblem}{% |
|
|
519 \begin{frame} |
|
|
520 \frametitle{Spezielles Halteproblem} |
|
|
521 \setbeamercovered{dynamic} |
|
|
522 |
|
|
523 \begin{definition}[Spezielles Halteproblem] |
|
|
524 Gegeben ein \structure{Wort} $w \in \left\{ 0, 1 \right\}^*$.\\ |
|
|
525 Hält \alert{$M_w$} bei Eingabe \alert{$w$}? |
|
|
526 \[\alert{K} := \left\{ w \mid M_w[w]\downarrow \right\}\] |
|
|
527 \end{definition} |
|
|
528 |
|
|
529 \begin{theorem}[] |
|
|
530 Das spezielle Halteproblem ist \alert{nicht entscheidbar}. |
|
|
531 \end{theorem} |
|
|
532 |
|
|
533 \vfill |
|
|
534 |
|
|
535 \begin{itemize} |
|
|
536 \item Hält eine Turingmaschine mit sich selbst als Eingabe? |
|
|
537 \item $w$ ist die \structure{Gödelisierung} von $M_w$. |
|
|
538 \item $K$ ist semi-entscheidbar, $\overline{K}$ \alert{nicht}. |
|
|
539 \end{itemize} |
|
|
540 \end{frame} |
|
|
541 } |
|
|
542 |
|
|
543 \defineUnit{halteproblem}{% |
|
|
544 \begin{frame} |
|
|
545 \frametitle{Allgemeines Halteproblem} |
|
|
546 \setbeamercovered{dynamic} |
|
|
547 |
|
|
548 \begin{definition}[Allgemeines Halteproblem] |
|
|
549 Gegeben \structure{Wörter} $w, x \in \left\{ 0, 1 \right\}^*$.\\ |
|
|
550 Hält \alert{$M_w$} bei Eingabe \alert{$x$}? |
|
|
551 \[\alert{H} := \left\{ w\#x \mid M_w[x]\downarrow \right\}\] |
|
|
552 \end{definition} |
|
|
553 |
|
|
554 \begin{theorem}[] |
|
|
555 Das allgemeine Halteproblem ist \alert{nicht entscheidbar}. |
|
|
556 \end{theorem} |
|
|
557 |
|
|
558 \vfill |
|
|
559 |
|
|
560 \begin{itemize} |
|
|
561 \item Es ist $K \leq H$. Warum? |
|
|
562 \end{itemize} |
|
|
563 \end{frame} |
|
|
564 } |
|
|
565 |
|
|
566 \defineUnit{aufzaehlbarkeit}{% |
|
|
567 \begin{frame} |
|
|
568 \frametitle{Rekursive Aufzählbarkeit} |
|
|
569 \setbeamercovered{dynamic} |
|
|
570 |
|
|
571 \begin{definition}[Rekursiv aufzählbar] |
|
|
572 Eine Menge $A$ heißt \alert{rekursiv aufzählbar} wenn $A = \emptyset$ oder es eine \alert{berechenbare} totale Funktion $f : \N \to A$ gibt, so dass |
|
|
573 \[A = \left\{ f(0), f(1), \ldots \right\} = \bigcup_{n \in \N} \left\{ f(n) \right\}\] |
|
|
574 \end{definition} |
|
|
575 |
|
|
576 \vfill |
|
|
577 |
|
|
578 \structure{Äquivalent:} |
|
|
579 \begin{itemize} |
|
|
580 \item $A$ rekursiv aufzählbar |
|
|
581 \item $A$ semi-entscheidbar, also $\chi'_A$ berechenbar |
|
|
582 \item $A=L(M)$ für eine TM $M$ |
|
|
583 \item $A$ ist Bild oder Urbild einer berechenbaren Funktion |
|
|
584 \end{itemize} |
|
|
585 \end{frame} |
|
|
586 } |
|
|
587 |
|
|
588 \defineUnit{rice}{% |
|
|
589 \begin{frame} |
|
|
590 \frametitle{Satz von Rice} |
|
|
591 \setbeamercovered{dynamic} |
|
|
592 |
|
|
593 \begin{theorem}[Rice] |
|
|
594 Sei $F$ eine Menge berechenbarer Funktionen.\\ |
|
|
595 Sei weder $F = \emptyset$ noch $F = \text{alle ber. Funktionen}$ (\alert{$F$ nicht trivial}).\\ |
|
|
596 Dann ist \alert{unentscheidbar}, ob die von einer gegebenen TM $M_w$ berechnete Funktion in $F$ ist, also ob \alert{$\varphi_w \in F$}. |
|
|
597 \end{theorem} |
|
|
598 |
|
|
599 \begin{itemize} |
|
|
600 \item Nicht-triviale \alert{semantische} Eigenschaften von Programmen sind unentscheidbar. |
|
|
601 \item \alert{Termination} ist unentscheidbar. |
|
|
602 \end{itemize} |
|
|
603 |
|
|
604 \vfill |
|
|
605 |
|
|
606 \structure{Rice-Shapiro:} |
|
|
607 \begin{itemize} |
|
|
608 \item Termination ist nicht semi-entscheidbar. |
|
|
609 \item Nicht-Termination ist nicht semi-entscheidbar. |
|
|
610 \end{itemize} |
|
|
611 \end{frame} |
|
|
612 } |
|
|
613 |
|
|
614 \defineUnit{pcp}{% |
|
|
615 \begin{frame} |
|
|
616 \frametitle{PCP} |
|
|
617 \setbeamercovered{dynamic} |
|
|
618 |
|
|
619 \begin{definition}[Postsches Korrespondenzproblem] |
|
|
620 Gegeben \structure{endliche Folge} $(x_1, y_1), \ldots, (x_k, y_k)$ mit $x_i, y_i \in \Sigma^+$.\\ |
|
|
621 Gibt es eine \alert{Folge von Indizes} $i_1, \ldots, i_n \in \left\{ 1, \ldots, k \right\}$ mit \alert{\[x_{i_1}, \ldots, x_{i_n} = y_{i_1}, \ldots, y_{i_n}\]} |
|
|
622 \end{definition} |
|
|
623 |
|
|
624 \vfill |
|
|
625 |
|
|
626 \begin{center} |
|
|
627 \begin{tikzpicture} |
|
|
628 \begin{scope}[start chain, node distance=2em] |
|
|
629 \node[tape, active] {\pcp{$x_i$}{$y_i$}}; |
|
|
630 \node[tape] (a) {\pcp{$001$}{$00$}}; |
|
|
631 \node[tape] (b) {\pcp{$10$}{$11$}}; |
|
|
632 \node[tape] (c) {\pcp{$1$}{$01$}}; |
|
|
633 \end{scope} |
|
|
634 \node[below of=a] {$1$}; |
|
|
635 \node[below of=b] {$2$}; |
|
|
636 \node[below of=c] {$3$}; |
|
|
637 \end{tikzpicture} |
|
|
638 \end{center} |
|
|
639 |
|
|
640 \vfill |
|
|
641 |
|
|
642 \begin{theorem}[] |
|
|
643 Das PCP ist \alert{unentscheidbar}, aber semi-entscheidbar. |
|
|
644 \end{theorem} |
|
|
645 \end{frame} |
|
|
646 } |
|
|
647 |
|
|
648 \defineUnit{pcpbeispiel}{% |
|
|
649 \begin{frame} |
|
|
650 \frametitle{PCP lösen} |
|
|
651 \setbeamercovered{dynamic} |
|
|
652 |
|
|
653 \begin{block}{Idee} |
|
|
654 \alert{Mögliche Lösungen} aufzählen, richtige Lösungen identifizieren |
|
|
655 \end{block} |
|
|
656 |
|
|
657 \begin{center} |
|
|
658 \begin{tikzpicture} |
|
|
659 \begin{scope}[start chain, node distance=2em] |
|
|
660 \node[tape, active] {\pcp{$x_i$}{$y_i$}}; |
|
|
661 \node[tape] (a) {\pcp{$001$}{$00$}}; |
|
|
662 \node[tape] (b) {\pcp{$01$}{$10$}}; |
|
|
663 \node[tape] (c) {\pcp{$1$}{$11$}}; |
|
|
664 \end{scope} |
|
|
665 \node[below of=a] {$1$}; |
|
|
666 \node[below of=b] {$2$}; |
|
|
667 \node[below of=c] {$3$}; |
|
|
668 \end{tikzpicture} |
|
|
669 |
|
|
670 \vspace{2em} |
|
|
671 |
|
|
672 \begin{tikzpicture}[grow=right, level distance = 2cm] |
|
|
673 \tikzstyle{every node} = [] |
|
|
674 \tikzstyle{residual} = [rectangular, thin, fill=tumgreen!10, font=\scriptsize] |
|
|
675 \tikzstyle{edge from parent} = [every edge] |
|
|
676 |
|
|
677 \tikzstyle{level 1} = [sibling distance = 1.7cm] |
|
|
678 \tikzstyle{level 2} = [sibling distance = 1.1cm] |
|
|
679 |
|
|
680 \node[residual] {} |
|
|
681 child { |
|
|
682 node[residual] {\pcp{$1$}{}} |
|
|
683 child { |
|
|
684 node[residual] {\pcp{$1$}{}} |
|
|
685 child { |
|
|
686 node[residual] {\pcp{$1$}{}} |
|
|
687 child { |
|
|
688 node[residual]{$\ldots$} |
|
|
689 edge from parent |
|
|
690 } |
|
|
691 edge from parent |
|
|
692 node[below] {$2$} |
|
|
693 } |
|
|
694 child { |
|
|
695 node[residual, active] {\pcp{}{}} |
|
|
696 edge from parent |
|
|
697 node[above] {$3$} |
|
|
698 } |
|
|
699 edge from parent |
|
|
700 node[below] {$2$} |
|
|
701 } |
|
|
702 child { |
|
|
703 node[residual, active] {\pcp{}{}} |
|
|
704 edge from parent |
|
|
705 node[above] {$3$} |
|
|
706 } |
|
|
707 edge from parent |
|
|
708 node[below] {$1$} |
|
|
709 } |
|
|
710 child { |
|
|
711 node[residual]{\pcp{}{$1$}} |
|
|
712 child { |
|
|
713 node[residual]{\pcp{}{$11$}} |
|
|
714 child { |
|
|
715 node[residual]{$\ldots$} |
|
|
716 edge from parent |
|
|
717 node[above] {$3$} |
|
|
718 } |
|
|
719 edge from parent |
|
|
720 node[above] {$3$} |
|
|
721 } |
|
|
722 edge from parent |
|
|
723 node[above] {$3$} |
|
|
724 }; |
|
|
725 |
|
|
726 \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};} |
|
|
727 \end{tikzpicture} |
|
|
728 \end{center} |
|
|
729 \end{frame} |
|
|
730 } |
|
|
731 |
|
|
732 \defineUnit{time}{% |
|
|
733 \begin{frame}[t] |
|
|
734 \frametitle{$TIME$} |
|
|
735 \setbeamercovered{dynamic} |
|
|
736 |
|
|
737 \begin{definition}[$TIME$] |
|
|
738 Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{DTM} $M$ mit Eingabe $w$ hält als $\alert{time_M(w)} \in \N \cup \left\{ \infty \right\}$.\\ |
|
|
739 \vspace{1em} |
|
|
740 Sei $f : \N \to \N$ total. Dann ist |
|
|
741 \begin{align*} |
|
|
742 \alert{TIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{DTM}\ M. A = L(M) \wedge \\ |
|
|
743 &\forall w \in \Sigma^*. \structure{time_M(w) \leq f(|w|)} \} |
|
|
744 \end{align*} |
|
|
745 die Klasse der \structure{in Zeit $f(n)$} von einer \structure{DTM} entscheidbaren Sprachen. |
|
|
746 \end{definition} |
|
|
747 |
|
|
748 \vfill |
|
|
749 |
|
|
750 \begin{itemize} |
|
|
751 \item $TIME(\Oh(n))$ enthält alle "\structure{linearen Probleme}". |
|
|
752 \item Also alle Probleme, für die ein Linearzeitalgorithmus existiert. |
|
|
753 \end{itemize} |
|
|
754 \end{frame} |
|
|
755 } |
|
|
756 |
|
|
757 \defineUnit{ntime}{% |
|
|
758 \begin{frame}[t] |
|
|
759 \frametitle{$NTIME$} |
|
|
760 \setbeamercovered{dynamic} |
|
|
761 |
|
|
762 \begin{definition}[$NTIME$] |
|
|
763 Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{NTM} $M$ mit Eingabe $w$ hält als $\alert{ntime_M(w)} \in \N$. |
|
|
764 \[ \alert{ntime_M(w)} := \begin{cases} \text{minimale Schrittanzahl} & \text{falls } w \in L(M) \\ 0 & \text{falls } w \not \in L(M)\end{cases} \] |
|
|
765 Dann ist |
|
|
766 \begin{align*} |
|
|
767 \alert{NTIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{NTM}\ M. A = L(M) \wedge \\ |
|
|
768 &\forall w \in \Sigma^*. \structure{ntime_M(w) \leq f(|w|)} \} |
|
|
769 \end{align*} |
|
|
770 die Klasse der \structure{in Zeit $f(n)$} von einer \structure{NTM} entscheidbaren Sprachen. |
|
|
771 \end{definition} |
|
|
772 \end{frame} |
|
|
773 } |
|
|
774 |
|
|
775 \defineUnit{pundnp}{% |
|
|
776 \begin{frame} |
|
|
777 \frametitle{P und NP} |
|
|
778 \setbeamercovered{dynamic} |
|
|
779 |
|
|
780 \begin{definition} |
|
|
781 \alert{P} ist die Menge aller von einer \structure{DTM} in polynomieller Zeit entscheidbaren Sprachen. |
|
|
782 \[\alert{P}:= \bigcup_{p\text{ Polynom}} TIME(p(n)) = \bigcup_{k \in \N} TIME(\alert{\Oh(n^k)}) \] |
|
|
783 \end{definition} |
|
|
784 |
|
|
785 \begin{definition} |
|
|
786 \alert{NP} ist die Menge aller von einer \structure{NTM} in polynomieller Zeit entscheidbaren Sprachen. |
|
|
787 \[\alert{NP}:= \bigcup_{p\text{ Polynom}} NTIME(p(n)) = \bigcup_{k \in \N} NTIME(\alert{\Oh(n^k)}) \] |
|
|
788 \end{definition} |
|
|
789 \end{frame} |
|
|
790 } |
|
|
791 |
|
|
792 \defineUnit{verifikator}{% |
|
|
793 \begin{frame} |
|
|
794 \frametitle{Verifikator} |
|
|
795 \setbeamercovered{dynamic} |
|
|
796 |
|
|
797 \begin{definition}[Verifikator] |
|
|
798 Sei $M$ eine \structure{DTM} mit $L(M) \subseteq \left\{ w\# c \mid w \in \Sigma^*, c \in \Delta^* \right\}$. |
|
|
799 \begin{itemize} |
|
|
800 \item Falls $w\#c \in L(M)$, dann heißt $c$ \alert{Zertifikat} für $w$. |
|
|
801 \item $M$ ist ein \alert{polynomiell beschränkter Verifikator} für |
|
|
802 \[\left\{ \structure{w \in \Sigma^*} \mid \exists c \in \Delta^* . w\#c \in L(M) \right\}\] |
|
|
803 falls $time_M(w\#c) \leq p(|w|)$ für ein Polynom $p$. |
|
|
804 \end{itemize} |
|
|
805 \end{definition} |
|
|
806 |
|
|
807 \begin{itemize} |
|
|
808 \item \structure{NTM} rät Lösung (Zertifikat), \structure{DTM} probiert sie aus. |
|
|
809 \item Verifizieren (wahrscheinlich) einfacher als Lösung finden. |
|
|
810 \end{itemize} |
|
|
811 |
|
|
812 \vfill |
|
|
813 |
|
|
814 \begin{theorem} |
|
|
815 \alert{$A \in NP$} gdw es einen pol. beschränkten Verifikator für A gibt. |
|
|
816 \end{theorem} |
|
|
817 \end{frame} |
|
|
818 } |
|
|
819 |
|
|
820 \defineUnit{preduktion}{% |
|
|
821 \begin{frame} |
|
|
822 \frametitle{Polynomielle Reduzierbarkeit} |
|
|
823 \setbeamercovered{dynamic} |
|
|
824 |
|
|
825 \begin{definition}[Polynomielle Reduzierbarkeit] |
|
|
826 Eine Menge $A \subseteq \Sigma^*$ ist \alert{polynomiell reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und \structure{von einer DTM in polynomieller Zeit} berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit |
|
|
827 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] |
|
|
828 Wir schreiben dann \alert{$A \leq_P B$}. |
|
|
829 \end{definition} |
|
|
830 |
|
|
831 \vfill |
|
|
832 |
|
|
833 \begin{itemize} |
|
|
834 \item Die Relation $\leq_P$ ist \structure{transitiv}. |
|
|
835 \item P und NP sind \structure{nach unten abgeschlossen}: |
|
|
836 \[A \leq_P B \in P/NP \Longrightarrow A \in P/NP\] |
|
|
837 \end{itemize} |
|
|
838 \end{frame} |
|
|
839 } |
|
|
840 |
|
|
841 \defineUnit{npvollstaendigkeit}{% |
|
|
842 \begin{frame} |
|
|
843 \frametitle{NP-Vollständigkeit} |
|
|
844 \setbeamercovered{dynamic} |
|
|
845 |
|
|
846 \begin{definition}[NP-Schwere] |
|
|
847 Eine Sprache $L$ heißt \alert{NP-schwer} (NP-hart) wenn sich \structure{alle Sprachen} in NP auf $L$ reduzieren lassen. |
|
|
848 \[\forall A \in NP. A \leq_P L\] |
|
|
849 \end{definition} |
|
|
850 |
|
|
851 \begin{definition}[NP-Vollständigkeit] |
|
|
852 Eine Sprache $L$ heißt \alert{NP-vollständig} wenn $L$ \structure{NP-schwer} ist und \structure{$L \in NP$}. |
|
|
853 \end{definition} |
|
|
854 |
|
|
855 \vfill |
|
|
856 |
|
|
857 \structure{Fragen}: |
|
|
858 \begin{itemize} |
|
|
859 \item Gibt es überhaupt NP-vollständige Sprachen? |
|
|
860 \item Gibt es eine NP-vollständige Sprache in $P$? |
|
|
861 \end{itemize} |
|
|
862 \end{frame} |
|
|
863 } |
|
|
864 |
|
|
865 \defineUnit{sat}{% |
|
|
866 \begin{frame} |
|
|
867 \frametitle{SAT} |
|
|
868 \setbeamercovered{dynamic} |
|
|
869 |
|
|
870 \begin{definition}[Aussagenlogik] |
|
|
871 Syntax der \alert{Aussagenlogik}.\\ |
|
|
872 \begin{description} |
|
|
873 \item[Formeln] $F \rightarrow \neg F \mid (F \wedge F) \mid (F \vee F) \mid X$ |
|
|
874 \item[Variablen] $X \rightarrow x \mid y \mid z \mid \ldots$ |
|
|
875 \end{description} |
|
|
876 \end{definition} |
|
|
877 |
|
|
878 \vfill |
|
|
879 |
|
|
880 \begin{definition}[SAT] |
|
|
881 Gegeben eine \structure{aussagenlogische Formel} $F$.\\ |
|
|
882 Ist $F$ \alert{erfüllbar}, also gibt es eine Belegung der Variablen in $F$, sodass $F$ gilt? |
|
|
883 \end{definition} |
|
|
884 |
|
|
885 \begin{theorem}[Cook 1971] |
|
|
886 $\mathbf{SAT}$ ist \alert{NP-vollständig}. |
|
|
887 \end{theorem} |
|
|
888 \end{frame} |
|
|
889 } |
|
|
890 |
|
|
891 \defineUnit{3col}{% |
|
|
892 \begin{frame} |
|
|
893 \frametitle{3COL} |
|
|
894 \setbeamercovered{dynamic} |
|
|
895 |
|
|
896 \begin{definition}[3COL] |
|
|
897 Gegeben ein \structure{Graph} $G = (V, E)$.\\ |
|
|
898 Gibt es eine \alert{Färbung der Knoten} $V$ mit $3$ Farben, so dass keine zwei benachbarten Knoten die gleiche Farbe haben? |
|
|
899 \end{definition} |
|
|
900 |
|
|
901 \vfill |
|
|
902 |
|
|
903 \begin{center} |
|
|
904 \begin{tikzpicture} |
|
|
905 \tikzstyle{red} = [fill=tumred!50] |
|
|
906 \tikzstyle{green} = [fill=tumgreen!50] |
|
|
907 \tikzstyle{blue} = [fill=tumblue!50] |
|
|
908 \tikzstyle{vertex} = [draw, circle, thin, blue] |
|
|
909 \tikzstyle{edge} = [draw, thick] |
|
|
910 |
|
|
911 \foreach \name/\angle/\dist/\col in { |
|
|
912 ia/18/0.8cm/blue, ib/90/0.8cm/red, ic/162/0.8cm/red, id/234/0.8cm/green, ie/306/0.8cm/green, |
|
|
913 oa/18/1.6cm/red, ob/90/1.6cm/blue, oc/162/1.6cm/green, od/234/1.6cm/red, oe/306/1.6cm/blue} { |
|
|
914 \node<1>[vertex] (\name) at (\angle:\dist) {}; |
|
|
915 \node<2>[vertex, \col] (\name) at (\angle:\dist) {}; |
|
|
916 } |
|
|
917 |
|
|
918 \foreach \a/\b in { |
|
|
919 ia/oa, ib/ob, ic/oc, id/od, ie/oe, |
|
|
920 oa/ob, ob/oc, oc/od, od/oe, oe/oa, |
|
|
921 ia/ic, ic/ie, ie/ib, ib/id, id/ia} { |
|
|
922 \draw[edge] (\a) -- (\b); |
|
|
923 } |
|
|
924 \end{tikzpicture} |
|
|
925 \end{center} |
|
|
926 |
|
|
927 \begin{theorem} |
|
|
928 Es ist \alert{$\mathbf{3COL} \leq_P \mathbf{SAT}$} und $\alert{\mathbf{SAT}} \leq_P \mathbf{3SAT} \alert{\leq_P \mathbf{3COL}}$. |
|
|
929 \end{theorem} |
|
|
930 \end{frame} |
|
|
931 } |
|
|
932 |
|
|
933 \defineUnit{typ0sprachen}{% |
|
|
934 \begin{frame} |
|
|
935 \frametitle{Typ 0 Sprachen} |
|
|
936 \setbeamercovered{dynamic} |
|
|
937 |
|
|
938 \begin{center} |
|
|
939 \begin{tikzpicture}[node distance=2.5cm] |
|
|
940 \node (WH) {WHILE}; |
|
|
941 \node (GO) [above left of = WH] {GOTO}; |
|
|
942 \node (TM) [above right of = WH] {TM}; |
|
|
943 \node (MR) [left of = WH] {$\mu$R}; |
|
|
944 |
|
|
945 \draw [every edge, tumgreen, <->] (WH) -- (MR); |
|
|
946 \draw [every edge, <->] (WH) -- (GO); |
|
|
947 \draw [every edge, ->] (WH) -- (TM); |
|
|
948 \draw [every edge, ->] (TM) -- (GO); |
|
|
949 \end{tikzpicture} |
|
|
950 \end{center} |
|
|
951 |
|
|
952 \vfill |
|
|
953 |
|
|
954 \begin{theorem}[] |
|
|
955 Sei $A$ formale Sprache, dann ist äuqivalent: |
|
|
956 \vspace{1em} |
|
|
957 \begin{itemize} |
|
|
958 \item $A$ ist \alert{Typ 0 Sprache} |
|
|
959 \item $A$ \alert{rekursiv aufzählbar} |
|
|
960 \item $A$ \alert{semi-entscheidbar}, also $\chi'_A$ berechenbar |
|
|
961 \item $A=L(M)$ für eine \alert{TM $M$} |
|
|
962 \item $A$ ist \alert{Bild oder Urbild} einer berechenbaren Funktion |
|
|
963 \end{itemize} |
|
|
964 \end{theorem} |
|
|
965 \end{frame} |
|
|
966 } |
|
|
967 |
|
|
968 \defineUnit{spracheigenschaften}{% |
|
|
969 \begin{frame} |
|
|
970 \frametitle{Spracheigenschaften} |
|
|
971 \setbeamercovered{dynamic} |
|
|
972 |
|
|
973 \begin{itemize} |
|
|
974 \item \alert{Abschlusseigenschaften} |
|
|
975 \end{itemize} |
|
|
976 \begin{table} |
|
|
977 \begin{tabu}to \textwidth{X[c]|ccccc} |
|
|
978 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} |
|
|
979 REG & ja & ja & ja & ja & ja\\ |
|
|
980 CFL & nein & ja & nein & ja & ja\\ |
|
|
981 TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja} |
|
|
982 \end{tabu} |
|
|
983 \end{table} |
|
|
984 |
|
|
985 \vfill |
|
|
986 |
|
|
987 \begin{itemize} |
|
|
988 \item \alert{Entscheidbarkeit} |
|
|
989 \end{itemize} |
|
|
990 \begin{table} |
|
|
991 \begin{tabu}to \textwidth{X[c]|cccc} |
|
|
992 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} |
|
|
993 DFA & $\Oh(n)$ & ja & ja & ja\\ |
|
|
994 CFG & $\Oh(n^3)$ & ja & nein & nein\\ |
|
|
995 TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein} |
|
|
996 \end{tabu} |
|
|
997 \end{table} |
|
|
998 \end{frame} |
|
|
999 } |
|
|
1000 |
|
|
1001 \defineUnit{formalesprachen}{% |
|
|
1002 \begin{frame}[c] |
|
|
1003 \frametitle{Formale Sprachen} |
|
|
1004 \setbeamercovered{dynamic} |
|
|
1005 |
|
|
1006 \begin{center} |
|
|
1007 \begin{tikzpicture}[auto] |
|
|
1008 \tikzstyle{rect} = [thick]; |
|
|
1009 \tikzstyle{caption} = [align=left, anchor=north west]; |
|
|
1010 |
|
|
1011 \langclass{brown}{}{0}{Formale Sprache - $\Sigma^*$}; |
|
|
1012 \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar}; |
|
|
1013 \langclass{tumgreen}{}{2}{Entscheidbar}; |
|
|
1014 \langclass{violet}{}{3}{LOOP, PR}; |
|
|
1015 \langclass{tumred}{}{4}{NP}; |
|
|
1016 \langclass{tumorange}{dashed}{5}{P}; |
|
|
1017 \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei}; |
|
|
1018 \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär}; |
|
|
1019 \langclass{tumblue!20!black}{}{8}{Endlich}; |
|
|
1020 \end{tikzpicture} |
|
|
1021 \end{center} |
|
|
1022 \end{frame} |
|
|
1023 } |
