Mercurial > 13ss.theoinf
annotate notes/tex/computation.tex @ 55:b815b94ae158
ue13 notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Mon, 22 Jul 2013 23:56:37 +0200 |
parents | a2d28c18251a |
children | 3ac958d9b7c4 |
rev | line source |
---|---|
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
1 \defineUnit{tmdefinition}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
2 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
3 \frametitle{Turingmaschinen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
4 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
5 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
6 \begin{definition}[Turingmaschine] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
7 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
8 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
9 \item endlichen Menge von \alert{Zuständen} $Q$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
10 \item endlichen \alert{Eingabealphabet} $\Sigma$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
11 \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
12 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
13 \item \alert{Startzustand} $q_0 \in Q$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
14 \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
15 \item Menge von \alert{Endzuständen} $F \subseteq Q$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
16 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
17 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
18 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
19 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
20 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
21 \defineUnit{tmvisualisierung}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
22 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
23 \frametitle{Turingmaschinen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
24 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
25 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
26 \begin{definition}[Turingmaschine] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
27 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
28 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
29 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
30 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
31 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
32 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
33 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
34 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
35 \begin{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
36 \begin{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
37 % Tape |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
38 \begin{scope}[start chain, node distance=0] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
39 \node[on chain] {\ldots}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
40 \node[tape] {$\square$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
41 \node[tape] (l) {$\square$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
42 \node[tape] {$0$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
43 \node[tape] {$1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
44 \node<1>[tape, active] (a){$0$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
45 \node<2>[tape] (a){$1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
46 \node<1>[tape] (b){$0$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
47 \node<2>[tape, active] (b){$0$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
48 \node[tape] {$\square$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
49 \node[on chain] {\ldots}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
50 \end{scope} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
51 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
52 % Head |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
53 \node<1> [head,yshift=-4mm] at (a.south) (head) {$q_0$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
54 \node<2> [head,yshift=-4mm] at (b.south) (head) {$q_1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
55 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
56 % Machine |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
57 \node[machine, below=1.5cm of l] (machine) {Programm}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
58 \draw[every edge] (machine) .. controls (3.5, -2) .. (head.south); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
59 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
60 % Example-Transition |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
61 \node[yshift=5mm] at (current bounding box.north) {$\delta(q_0, 0) = (q_1, 1, R)$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
62 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
63 \end{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
64 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
65 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
66 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
67 \defineUnit{tmkonfiguration}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
68 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
69 \frametitle{Turingmaschinen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
70 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
71 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
72 \begin{definition}[Konfiguration] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
73 Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
74 Dies modelliert eine TM mit: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
75 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
76 \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
77 \item \alert{Zustand} $q$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
78 \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
79 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
80 Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
81 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
82 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
83 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
84 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
85 \only<1> { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
86 \begin{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
87 \begin{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
88 % Tape |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
89 \begin{scope}[start chain, node distance=0] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
90 \node[on chain] {\ldots}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
91 \node[tape] {$\square$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
92 \node[tape] (l) {$\square$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
93 \node[tape] {$0$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
94 \node[tape] {$1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
95 \node[tape] (a){$1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
96 \node[tape, active] (b){$0$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
97 \node[tape] {$\square$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
98 \node[on chain] {\ldots}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
99 \end{scope} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
100 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
101 % Head |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
102 \node [head,yshift=-4mm] at (b.south) (head) {$q_1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
103 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
104 % Machine |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
105 \node[below=1.5cm of l] (machine) {}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
106 \draw[every edge, dashed] (machine) .. controls (3.5, -2) .. (head.south); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
107 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
108 % Example-Transition |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
109 \node[yshift=5mm] at (current bounding box.north) {$(011,q_1,0)$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
110 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
111 \end{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
112 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
113 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
114 \only<2> { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
115 \begin{definition}[Akzeptanz] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
116 Eine TM $M$ \alert{akzeptiert} die Sprache |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
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\} \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
118 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
119 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
120 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
121 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
122 |
43
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
123 \defineUnit{ndtm}{% |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
124 \begin{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
125 \frametitle{Nichtdeterministische TM} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
126 \setbeamercovered{dynamic} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
127 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
128 \begin{definition}[Nichtdeterministische Turingmaschine] |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
129 Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
130 \begin{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
131 \item \ldots |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
132 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
133 \item \ldots |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
134 \end{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
135 \end{definition} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
136 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
137 \vfill |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
138 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
139 \begin{theorem} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
140 Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}. |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
141 \end{theorem} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
142 \end{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
143 } |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
144 |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
145 \defineUnit{chomsky}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
146 \begin{frame}[c] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
147 \frametitle{Chomsky-Hierarchie} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
148 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
149 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
150 \begin{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
151 \begin{tikzpicture}[auto] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
152 \tikzstyle{rect} = [thick]; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
153 \tikzstyle{caption} = [align=left, anchor=north west]; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
154 |
55 | 155 \chomsky{tumblue}{}{0}{Berechenbare Funktionen}; |
156 \chomsky{tumred}{dashed}{1}{Typ 0 - Rekursiv aufzählbar\\Turingmaschinen, $\lambda$-Kalkül}; | |
157 \chomsky{tumivory}{}{2}{Typ 1 - Kontextsensitiv\\CSG}; | |
158 \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\PDA, CFG}; | |
159 \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\DFA, RE}; | |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
160 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
161 \end{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
162 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
163 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
164 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
165 \defineUnit{berechenbarkeit}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
166 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
167 \frametitle{Berechenbarkeit} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
168 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
169 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
170 \begin{definition}[Intuitive Berechenbarkeit] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
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$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
172 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
173 \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist, |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
174 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
175 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
176 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
177 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
178 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
179 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
180 \begin{block}{Churchsche These (nicht beweisbar)} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
181 Turing-Maschinen können genau \alert{alle} intuitiv berechenbaren Funktionen berechnen. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
182 \end{block} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
183 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
184 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
185 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
186 \defineUnit{berechenbarkeitbeispiel}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
187 \begin{frame}[c] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
188 \frametitle{Berechenbarkeit} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
189 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
190 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
191 \begin{example}[Berechenbarkeit] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
192 Sind die folgenden Funktionen intuitiv berechenbar? |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
193 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
194 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
195 f_1(n) &= \begin{cases} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
196 1 & \text{falls $n$ prim}\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
197 0 & \text{sonst} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
198 \end{cases} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
199 f_2(n) &= \begin{cases} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
200 1 & \text{falls $n$ die ersten $n$ Ziffern von $\pi$ darstellt}\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
201 0 & \text{sonst} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
202 \end{cases} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
203 f_3(n) &= \begin{cases} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
204 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
205 0 & \text{sonst} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
206 \end{cases} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
207 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
208 \end{example} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
209 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
210 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
211 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
212 \defineUnit{pr}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
213 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
214 \frametitle{Primitive Rekursion} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
215 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
216 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
217 \begin{definition}[Basisfunktionen] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
218 \alert{Primitiv Rekursiv} sind: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
219 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
220 \item Die konstante Funktion \alert{0} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
221 \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
222 \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
223 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
224 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
225 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
226 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
227 \begin{definition}[Komposition] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
228 Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
229 \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
230 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
231 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
232 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
233 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
234 \defineUnit{prrekursion}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
235 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
236 \frametitle{Primitive Rekursion} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
237 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
238 \begin{block}{Basisfunktionen und Komposition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
239 Schon \alert{PR} sind: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
240 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
241 \item Konstante: $0$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
242 \item Nachfolger: $s(n) = n + 1$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
243 \item Projektion: $\pi_i^k : \N^k \to \N$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
244 \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
245 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
246 \end{block} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
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} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
248 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
249 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
250 \defineUnit{prprogramme}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
251 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
252 \frametitle{PR-Programme} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
253 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
254 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
255 U.a. diese Programme sind laut Vorlesung oder Übung PR: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
256 \begin{itemize} |
49
72ac27051d7e
fix some more errors; reorganize complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
45
diff
changeset
|
257 \item $pred(x) = \max \left\{ 0, x - 1 \right\}$ |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
258 \item \alert{$add(x, y) = x + y$} |
49
72ac27051d7e
fix some more errors; reorganize complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
45
diff
changeset
|
259 \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$} |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
260 \item \alert{$mult(x, y) = x \cdot y$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
261 \item $div(x, y) = x \div y$ (Ganzzahldivision) |
49
72ac27051d7e
fix some more errors; reorganize complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
45
diff
changeset
|
262 \item Die restliche einfache Arithmetik\ldots |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
263 \vspace{1.5em} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
264 \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ |
49
72ac27051d7e
fix some more errors; reorganize complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
45
diff
changeset
|
265 \item $sqr(x) = x^2$, $sqrt(x) = \sqrt{x}$ |
72ac27051d7e
fix some more errors; reorganize complete notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
45
diff
changeset
|
266 \item $c(x), p_1(x), p_2(x)$ (Cantorsche Paarungsfunktion) |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
267 \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
268 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
269 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
270 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
271 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
272 \defineUnit{prerweitert}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
273 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
274 \frametitle{Erweitertes PR-Schema} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
275 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
276 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
277 \begin{definition}[Erweitertes PR-Schema] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
278 Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
279 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
280 f(0, \bar{x}) &= t_0 \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
281 f(m + 1, \bar{x}) &= t |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
282 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
283 wobei |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
284 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
285 \item $t_0$ enthält nur PR-Funktionen und die $x_i$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
286 \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
287 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
288 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
289 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
290 \begin{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
291 Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
292 \end{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
293 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
294 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
295 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
296 \defineUnit{tmif}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
297 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
298 \frametitle{Programmieren mit TMs} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
299 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
300 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
301 Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
302 \begin{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
303 \begin{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
304 \node (M) at (0, 0) {$M$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
305 \node[above right=0.2cm and 1cm of M] (M1) {$M_1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
306 \node[below right=0.2cm and 1cm of M] (M2) {$M_2$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
307 \coordinate[right of=M1] (M1s); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
308 \coordinate[right of=M2] (M2s); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
309 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
310 \draw[every edge] (-1, 0) -- (M); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
311 \draw[every edge] (M) -- node[above left] {$f_1$} (M1); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
312 \draw[every edge] (M) -- node[below left] {$f_2$} (M2); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
313 \draw[every edge] (M1) -- (M1s); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
314 \draw[every edge] (M2) -- (M2s); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
315 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
316 \end{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
317 eine \alert{Fallunterscheidung}.\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
318 \begin{example}[Band=0?] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
319 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
320 \delta(q_0, 0) &= (q_0, 0, R) \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
321 \delta(q_0, \square) &= (ja, \square, L) \\ |
45 | 322 \delta(q_0, a) &= (nein, a, N) \qquad \text{für } a \neq 0, \square |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
323 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
324 \end{example} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
325 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
326 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
327 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
328 \defineUnit{while}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
329 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
330 \frametitle{WHILE-Programme} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
331 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
332 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
333 \begin{definition}[WHILE-Programm] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
334 Syntax von \alert{WHILE-Programmen}.\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
335 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
336 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
337 P &\rightarrow X := X + C \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
338 &\mid X := X - C \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
339 &\mid P; P \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
340 &\mid \alert{\mathbf{WHILE}\ X \neq 0 \ \mathbf{DO}\ P \ \mathbf{END}} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
341 &\mid \textcolor{gray}{\mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END}} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
342 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
343 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
344 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
345 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
346 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
347 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
348 \item Semantik wie erwartet. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
349 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
350 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
351 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
352 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
353 \defineUnit{goto}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
354 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
355 \frametitle{GOTO-Programme} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
356 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
357 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
358 \begin{definition}[GOTO-Programm] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
359 Syntax von \alert{GOTO-Programmen}.\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
360 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
361 Alle Anweisungen haben eine Markierung \alert{$M_1 : A_1; M_2 : A_2$}. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
362 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
363 P &\rightarrow X := X + C \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
364 &\mid X := X - C \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
365 &\mid P; P \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
366 &\mid \mathbf{GOTO}\ M_i \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
367 &\mid \mathbf{IF}\ X = 0 \ \mathbf{GOTO}\ M_i \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
368 &\mid \mathbf{HALT} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
369 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
370 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
371 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
372 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
373 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
374 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
375 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
376 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
377 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
378 \defineUnit{loop}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
379 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
380 \frametitle{LOOP-Programme} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
381 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
382 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
383 \begin{definition}[LOOP-Programm] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
384 Syntax von \alert{LOOP-Programmen}.\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
385 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
386 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
387 P &\rightarrow X := X + C \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
388 &\mid X := X - C \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
389 &\mid P; P \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
390 &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
391 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
392 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
393 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
394 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
395 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
396 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
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.} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
398 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
399 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
400 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
401 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
402 \defineUnit{prmax}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
403 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
404 \frametitle{Beschränkte Operationen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
405 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
406 \begin{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
407 Ein Prädikat $P$ ist \alert{PR}, wenn es eine PR Funktion $\hat{P}$ gibt mit |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
408 \[\hat{P}(x) = 1 \Longleftrightarrow P(x)\] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
409 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
410 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
411 \begin{definition}[Beschränkte Operationen] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
412 Ist $P$ PR, dann auch |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
413 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
414 \item der \alert{beschränkte max-Operator} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
415 \[\max \left\{ x \alert{\leq n} \mid P(x) \right\}, \quad \max \left\{ \emptyset \right\} = 0\] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
416 \item der \alert{beschränkte Existenzquantor} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
417 \[\exists x \alert{\leq n}. P(x)\] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
418 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
419 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
420 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
421 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
422 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
423 \defineUnit{murekursion}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
424 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
425 \frametitle{$\mu$-Rekursion} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
426 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
427 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
428 \begin{definition}[$\mu$-Operator] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
429 Sei $f: \N^{k+1} \to \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \to \N$: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
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}\] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
431 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
432 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
433 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
434 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
435 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
436 \item \alert{$^*$}Für alle \alert{$m \leq n$} muss $f$ definiert sein: $f(m, \bar{x}) \neq \perp$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
437 \item PR + $\mu$ = $\mu$-Rekursion |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
438 \item In Pseudocode: |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
439 \begin{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
440 \mu f(\bar{x}) &= find(0, \bar{x}) \\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
441 find(n, \bar{x}) &= \mathbf{if}\ f(n, \bar{x}) = 0 \ \mathbf{then}\ n \ \mathbf{else}\ find(n+1, \bar{x}) |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
442 \end{align*} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
443 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
444 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
445 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
446 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
447 \defineUnit{modelluebersetzungen}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
448 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
449 \frametitle{Übersetzungen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
450 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
451 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
452 \begin{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
453 \begin{tikzpicture}[node distance=2.5cm] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
454 \node (WH) {WHILE}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
455 \node (GO) [above left of = WH] {GOTO}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
456 \node (TM) [above right of = WH] {TM}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
457 \node (LO) [below of = WH] {LOOP}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
458 \node (PR) [left of = LO] {PR}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
459 \node (MR) [left of = WH] {$\mu$R}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
460 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
461 \draw [every edge, ->] (LO) -- (WH); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
462 \draw [every edge, ->] (PR) -- (MR); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
463 \draw [every edge, tumgreen, <->] (LO) -- (PR); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
464 \draw [every edge, tumgreen, <->] (WH) -- (MR); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
465 \draw [every edge, <->] (WH) -- (GO); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
466 \draw [every edge, ->] (WH) -- (TM); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
467 \draw [every edge, ->] (TM) -- (GO); |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
468 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
469 \end{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
470 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
471 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
472 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
473 LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger). |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
474 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
475 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
476 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
477 \defineUnit{entscheidbarkeit}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
478 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
479 \frametitle{Entscheidbarkeit} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
480 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
481 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
482 \begin{definition}[Entscheidbarkeit] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
483 Eine Menge $A$ heißt \alert{entscheidbar} gdw ihre \alert{charakteristische Funktion} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
484 \[ \chi_A(x) := \begin{cases}1 & \text{falls } x \in A \\ 0 & \text{falls } x \not \in A \end{cases} \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
485 berechenbar ist. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
486 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
487 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
488 \begin{definition}[Semi-Entscheidbarkeit] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
489 Eine Menge $A$ heißt \alert{semi-entscheidbar} gdw |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
490 \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
491 berechenbar ist. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
492 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
493 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
494 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
495 |
43
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
496 \defineUnit{breduktion}{% |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
497 \begin{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
498 \frametitle{Reduzierbarkeit} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
499 \setbeamercovered{dynamic} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
500 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
501 \begin{definition}[Reduzierbarkeit] |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
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 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
503 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
504 Wir schreiben dann \alert{$A \leq B$}. |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
505 \end{definition} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
506 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
507 \vfill |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
508 |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
509 \structure{Intuition}: |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
510 \begin{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
511 \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$ |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
512 \item Ist $A$ unlösbar, dann auch $B$. |
51
adcb0ab03ade
fix wrong intuition, thanks max!
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
49
diff
changeset
|
513 \item Ist $B$ lösbar, dann erst recht $A$. |
43
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
514 \end{itemize} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
515 \end{frame} |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
516 } |
c14b92bfa07f
add missing slides; correct some errors
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
41
diff
changeset
|
517 |
41
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
518 \defineUnit{spezielleshalteproblem}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
519 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
520 \frametitle{Spezielles Halteproblem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
521 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
522 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
523 \begin{definition}[Spezielles Halteproblem] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
524 Gegeben ein \structure{Wort} $w \in \left\{ 0, 1 \right\}^*$.\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
525 Hält \alert{$M_w$} bei Eingabe \alert{$w$}? |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
526 \[\alert{K} := \left\{ w \mid M_w[w]\downarrow \right\}\] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
527 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
528 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
529 \begin{theorem}[] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
530 Das spezielle Halteproblem ist \alert{nicht entscheidbar}. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
531 \end{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
532 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
533 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
534 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
535 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
536 \item Hält eine Turingmaschine mit sich selbst als Eingabe? |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
537 \item $w$ ist die \structure{Gödelisierung} von $M_w$. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
538 \item $K$ ist semi-entscheidbar, $\overline{K}$ \alert{nicht}. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
539 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
540 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
541 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
542 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
543 \defineUnit{halteproblem}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
544 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
545 \frametitle{Allgemeines Halteproblem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
546 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
547 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
548 \begin{definition}[Allgemeines Halteproblem] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
549 Gegeben \structure{Wörter} $w, x \in \left\{ 0, 1 \right\}^*$.\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
550 Hält \alert{$M_w$} bei Eingabe \alert{$x$}? |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
551 \[\alert{H} := \left\{ w\#x \mid M_w[x]\downarrow \right\}\] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
552 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
553 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
554 \begin{theorem}[] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
555 Das allgemeine Halteproblem ist \alert{nicht entscheidbar}. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
556 \end{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
557 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
558 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
559 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
560 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
561 \item Es ist $K \leq H$. Warum? |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
562 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
563 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
564 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
565 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
566 \defineUnit{aufzaehlbarkeit}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
567 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
568 \frametitle{Rekursive Aufzählbarkeit} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
569 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
570 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
571 \begin{definition}[Rekursiv aufzählbar] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
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 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
573 \[A = \left\{ f(0), f(1), \ldots \right\} = \bigcup_{n \in \N} \left\{ f(n) \right\}\] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
574 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
575 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
576 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
577 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
578 \structure{Äquivalent:} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
579 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
580 \item $A$ rekursiv aufzählbar |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
581 \item $A$ semi-entscheidbar, also $\chi'_A$ berechenbar |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
582 \item $A=L(M)$ für eine TM $M$ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
583 \item $A$ ist Bild oder Urbild einer berechenbaren Funktion |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
584 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
585 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
586 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
587 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
588 \defineUnit{rice}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
589 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
590 \frametitle{Satz von Rice} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
591 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
592 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
593 \begin{theorem}[Rice] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
594 Sei $F$ eine Menge berechenbarer Funktionen.\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
595 Sei weder $F = \emptyset$ noch $F = \text{alle ber. Funktionen}$ (\alert{$F$ nicht trivial}).\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
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$}. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
597 \end{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
598 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
599 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
600 \item Nicht-triviale \alert{semantische} Eigenschaften von Programmen sind unentscheidbar. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
601 \item \alert{Termination} ist unentscheidbar. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
602 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
603 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
604 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
605 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
606 \structure{Rice-Shapiro:} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
607 \begin{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
608 \item Termination ist nicht semi-entscheidbar. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
609 \item Nicht-Termination ist nicht semi-entscheidbar. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
610 \end{itemize} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
611 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
612 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
613 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
614 \defineUnit{pcp}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
615 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
616 \frametitle{PCP} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
617 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
618 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
619 \begin{definition}[Postsches Korrespondenzproblem] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
620 Gegeben \structure{endliche Folge} $(x_1, y_1), \ldots, (x_k, y_k)$ mit $x_i, y_i \in \Sigma^+$.\\ |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
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}\]} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
622 \end{definition} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
623 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
624 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
625 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
626 \begin{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
627 \begin{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
628 \begin{scope}[start chain, node distance=2em] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
629 \node[tape, active] {\pcp{$x_i$}{$y_i$}}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
630 \node[tape] (a) {\pcp{$001$}{$00$}}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
631 \node[tape] (b) {\pcp{$10$}{$11$}}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
632 \node[tape] (c) {\pcp{$1$}{$01$}}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
633 \end{scope} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
634 \node[below of=a] {$1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
635 \node[below of=b] {$2$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
636 \node[below of=c] {$3$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
637 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
638 \end{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
639 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
640 \vfill |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
641 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
642 \begin{theorem}[] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
643 Das PCP ist \alert{unentscheidbar}, aber semi-entscheidbar. |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
644 \end{theorem} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
645 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
646 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
647 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
648 \defineUnit{pcpbeispiel}{% |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
649 \begin{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
650 \frametitle{PCP lösen} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
651 \setbeamercovered{dynamic} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
652 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
653 \begin{block}{Idee} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
654 \alert{Mögliche Lösungen} aufzählen, richtige Lösungen identifizieren |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
655 \end{block} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
656 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
657 \begin{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
658 \begin{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
659 \begin{scope}[start chain, node distance=2em] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
660 \node[tape, active] {\pcp{$x_i$}{$y_i$}}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
661 \node[tape] (a) {\pcp{$001$}{$00$}}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
662 \node[tape] (b) {\pcp{$01$}{$10$}}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
663 \node[tape] (c) {\pcp{$1$}{$11$}}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
664 \end{scope} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
665 \node[below of=a] {$1$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
666 \node[below of=b] {$2$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
667 \node[below of=c] {$3$}; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
668 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
669 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
670 \vspace{2em} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
671 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
672 \begin{tikzpicture}[grow=right, level distance = 2cm] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
673 \tikzstyle{every node} = [] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
674 \tikzstyle{residual} = [rectangular, thin, fill=tumgreen!10, font=\scriptsize] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
675 \tikzstyle{edge from parent} = [every edge] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
676 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
677 \tikzstyle{level 1} = [sibling distance = 1.7cm] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
678 \tikzstyle{level 2} = [sibling distance = 1.1cm] |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
679 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
680 \node[residual] {} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
681 child { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
682 node[residual] {\pcp{$1$}{}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
683 child { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
684 node[residual] {\pcp{$1$}{}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
685 child { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
686 node[residual] {\pcp{$1$}{}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
687 child { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
688 node[residual]{$\ldots$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
689 edge from parent |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
690 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
691 edge from parent |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
692 node[below] {$2$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
693 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
694 child { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
695 node[residual, active] {\pcp{}{}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
696 edge from parent |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
697 node[above] {$3$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
698 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
699 edge from parent |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
700 node[below] {$2$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
701 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
702 child { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
703 node[residual, active] {\pcp{}{}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
704 edge from parent |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
705 node[above] {$3$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
706 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
707 edge from parent |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
708 node[below] {$1$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
709 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
710 child { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
711 node[residual]{\pcp{}{$1$}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
712 child { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
713 node[residual]{\pcp{}{$11$}} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
714 child { |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
715 node[residual]{$\ldots$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
716 edge from parent |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
717 node[above] {$3$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
718 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
719 edge from parent |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
720 node[above] {$3$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
721 } |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
722 edge from parent |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
723 node[above] {$3$} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
724 }; |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
725 |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
726 \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
727 \end{tikzpicture} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
728 \end{center} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
729 \end{frame} |
5d10471f5585
move frame-definitions out of presentations
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
730 } |
53 | 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 } | |
55 | 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 } | |
1024 | |
1025 \defineUnit{klausur}{% | |
1026 \begin{frame} | |
1027 \frametitle{Obacht, Klausur!} | |
1028 \setbeamercovered{dynamic} | |
1029 | |
1030 \begin{itemize} | |
1031 \item \structure{RE $\to$ $\epsilon$-NFA $\to$ NFA $\to$ DFA} | |
1032 \item \structure{(Produktautomat)} | |
1033 \item \structure{Quotientenautomat, Minimale DFAs} | |
1034 \item Reguläres Pumpinglemma | |
1035 \item \structure{CNF-Synthese} | |
1036 \item \structure{Nützliche Symbole, CYK} | |
1037 \item (Kellerautomaten) | |
1038 \item Kontextfreies Pumpinglemma | |
1039 \item Turingmaschinen | |
1040 \item LOOP und PR | |
1041 \item WHILE und $\mu$-Rekursion | |
1042 \item Berechenbarkeit, Entscheidbarkeit, Satz von Rice | |
1043 \item \structure{PCP} | |
1044 \item (P und NP, Verifikatoren) | |
1045 \item Reduktionen von und auf NP-Probleme | |
1046 \end{itemize} | |
1047 \end{frame} | |
1048 } |