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