Mercurial > 14ss.theoinf
annotate notes/tex/computation.tex @ 31:777563904120
tenth sheet and notes
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Sun, 29 Jun 2014 16:58:20 +0200 |
| parents | b56fe50e0132 |
| children | 24d446e2f94c |
| 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}{% | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
230 \begin{frame}[t] |
| 1 | 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} | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
252 |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
253 \only<2> { |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
254 \vfill |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
255 |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
256 \begin{center} |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
257 Alle drei Funktionen sind intuitiv berechenbar. |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
258 \end{center} |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
259 } |
| 1 | 260 \end{frame} |
| 261 } | |
| 262 | |
| 263 \defineUnit{pr}{% | |
| 264 \begin{frame} | |
| 265 \frametitle{Primitive Rekursion} | |
| 266 \setbeamercovered{dynamic} | |
| 267 | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
268 \begin{definition}[Basisfunktionen der PR] |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
269 Die Menge der \structure{primitiv rekursiven (PR)} Funktionen ist induktiv definiert. Die Basisfunktionen sind die |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
270 \begin{description}[Projektionsfunktion\quad] |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
271 \item[konstante Funktion] $f(x) = 0$ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
272 \item[Nachfolgerfunktion] $s(n) = n + 1$ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
273 \item[Projektionsfunktion] $\pi_i^k : \N^k \to \N, i \in [k]$ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
274 \end{description} |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
275 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] |
| 1 | 276 \end{definition} |
| 277 | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
278 \vfill |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
279 |
| 1 | 280 \begin{definition}[Komposition] |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
281 Seien $g$ und $h_i$ \structure{PR} und $\bar{x} = (x_1, \ldots, x_n)$.\\ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
282 Dann ist auch die \structure{Komposition $f$} PR. |
| 1 | 283 \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \] |
| 284 \end{definition} | |
| 285 \end{frame} | |
| 286 } | |
| 287 | |
| 288 \defineUnit{prrekursion}{% | |
| 289 \begin{frame} | |
| 290 \frametitle{Primitive Rekursion} | |
| 291 \setbeamercovered{dynamic} | |
| 292 \begin{block}{Basisfunktionen und Komposition} | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
293 Die folgenden Funktionen sind schon als \structure{primitiv rekursiv} bekannt. |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
294 \begin{description}[Projektionsfunktion\quad] |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
295 \item[konstante Funktion] $f(x) = 0$ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
296 \item[Nachfolgerfunktion] $s(n) = n + 1$ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
297 \item[Projektionsfunktion] $\pi_i^k : \N^k \to \N, i \in [k]$ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
298 \item[Komposition] $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
299 \end{description} |
| 1 | 300 \end{block} |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
301 |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
302 \vfill |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
303 |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
304 \begin{definition}[Primitive Rekursion] |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
305 Das Schema der \structure{primitiven Rekursion} erzeugt aus $g$ und $h$ die neue Funktion \structure{$f$}. |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
306 \begin{align*} |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
307 f(0, \bar{x}) &= g(\bar{x}) \\ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
308 f(\alert{m + 1}, \bar{x}) &= h(f(\alert{m}, \bar{x}), \alert{m}, \bar{x}) |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
309 \end{align*} |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
310 $f$ ist ebenfalls \structure{primitiv rekursiv}. |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
311 \end{definition} |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
312 \end{frame} |
| 1 | 313 } |
| 314 | |
| 315 \defineUnit{prprogramme}{% | |
| 316 \begin{frame} | |
| 317 \frametitle{PR-Programme} | |
| 318 \setbeamercovered{dynamic} | |
| 319 | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
320 Unter anderem diese Programme sind laut Vorlesung oder Übung PR: |
| 1 | 321 \begin{itemize} |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
322 \item $succ(x) = x + 1$ |
| 1 | 323 \item $pred(x) = \max \left\{ 0, x - 1 \right\}$ |
| 324 \item \alert{$add(x, y) = x + y$} | |
| 325 \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$} | |
| 326 \item \alert{$mult(x, y) = x \cdot y$} | |
| 327 \item $div(x, y) = x \div y$ (Ganzzahldivision) | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
328 \item $pow(x, y) = x^y$ |
| 1 | 329 \item Die restliche einfache Arithmetik\ldots |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
330 \vfill |
| 1 | 331 \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
332 \item $sqr(x) = x^2$ |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
333 \item $sqrt(x) = \sqrt{x}$ |
| 1 | 334 \item $c(x), p_1(x), p_2(x)$ (Cantorsche Paarungsfunktion) |
| 335 \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$ | |
| 336 \end{itemize} | |
| 337 \end{frame} | |
| 338 } | |
| 339 | |
| 340 \defineUnit{prerweitert}{% | |
| 341 \begin{frame} | |
| 342 \frametitle{Erweitertes PR-Schema} | |
| 343 \setbeamercovered{dynamic} | |
| 344 | |
| 345 \begin{definition}[Erweitertes PR-Schema] | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
346 Das \structure{erweiterte Schema der primitiven Rekursion} erlaubt |
| 1 | 347 \begin{align*} |
| 348 f(0, \bar{x}) &= t_0 \\ | |
| 349 f(m + 1, \bar{x}) &= t | |
| 350 \end{align*} | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
351 wobei $t_0$ und $t$ \structure{Terme} sind für die gilt |
| 1 | 352 \begin{itemize} |
| 353 \item $t_0$ enthält nur PR-Funktionen und die $x_i$ | |
| 354 \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$. | |
| 355 \end{itemize} | |
| 356 \end{definition} | |
| 357 | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
358 \vfill |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
359 |
| 1 | 360 \begin{theorem} |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
361 Das erweiterte Schema der primitiven Rekursion führt nicht aus \structure{PR} heraus. |
| 1 | 362 \end{theorem} |
| 363 \end{frame} | |
| 364 } | |
| 365 | |
| 366 \defineUnit{tmif}{% | |
| 367 \begin{frame} | |
| 368 \frametitle{Programmieren mit TMs} | |
| 369 \setbeamercovered{dynamic} | |
| 370 | |
| 371 Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet | |
| 372 \begin{center} | |
| 373 \begin{tikzpicture} | |
| 374 \node (M) at (0, 0) {$M$}; | |
| 375 \node[above right=0.2cm and 1cm of M] (M1) {$M_1$}; | |
| 376 \node[below right=0.2cm and 1cm of M] (M2) {$M_2$}; | |
| 377 \coordinate[right of=M1] (M1s); | |
| 378 \coordinate[right of=M2] (M2s); | |
| 379 | |
| 380 \draw[every edge] (-1, 0) -- (M); | |
| 381 \draw[every edge] (M) -- node[above left] {$f_1$} (M1); | |
| 382 \draw[every edge] (M) -- node[below left] {$f_2$} (M2); | |
| 383 \draw[every edge] (M1) -- (M1s); | |
| 384 \draw[every edge] (M2) -- (M2s); | |
| 385 \end{tikzpicture} | |
| 386 \end{center} | |
| 387 eine \alert{Fallunterscheidung}.\\ | |
| 388 \begin{example}[Band=0?] | |
| 389 \begin{align*} | |
| 390 \delta(q_0, 0) &= (q_0, 0, R) \\ | |
| 391 \delta(q_0, \square) &= (ja, \square, L) \\ | |
| 392 \delta(q_0, a) &= (nein, a, N) \qquad \text{für } a \neq 0, \square | |
| 393 \end{align*} | |
| 394 \end{example} | |
| 395 \end{frame} | |
| 396 } | |
| 397 | |
| 398 \defineUnit{while}{% | |
| 399 \begin{frame} | |
| 400 \frametitle{WHILE-Programme} | |
| 401 \setbeamercovered{dynamic} | |
| 402 | |
| 403 \begin{definition}[WHILE-Programm] | |
| 404 Syntax von \alert{WHILE-Programmen}.\\ | |
| 405 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. | |
| 406 \begin{align*} | |
| 407 P &\rightarrow X := X + C \\ | |
| 408 &\mid X := X - C \\ | |
| 409 &\mid P; P \\ | |
| 410 &\mid \alert{\mathbf{WHILE}\ X \neq 0 \ \mathbf{DO}\ P \ \mathbf{END}} \\ | |
| 411 &\mid \textcolor{gray}{\mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END}} \\ | |
| 412 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} | |
| 413 \end{align*} | |
| 414 \end{definition} | |
| 415 | |
| 416 \begin{itemize} | |
| 417 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. | |
| 418 \item Semantik wie erwartet. | |
| 419 \end{itemize} | |
| 420 \end{frame} | |
| 421 } | |
| 422 | |
| 423 \defineUnit{goto}{% | |
| 424 \begin{frame} | |
| 425 \frametitle{GOTO-Programme} | |
| 426 \setbeamercovered{dynamic} | |
| 427 | |
| 428 \begin{definition}[GOTO-Programm] | |
| 429 Syntax von \alert{GOTO-Programmen}.\\ | |
| 430 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \\ | |
| 431 Alle Anweisungen haben eine Markierung \alert{$M_1 : A_1; M_2 : A_2$}. | |
| 432 \begin{align*} | |
| 433 P &\rightarrow X := X + C \\ | |
| 434 &\mid X := X - C \\ | |
| 435 &\mid P; P \\ | |
| 436 &\mid \mathbf{GOTO}\ M_i \\ | |
| 437 &\mid \mathbf{IF}\ X = 0 \ \mathbf{GOTO}\ M_i \\ | |
| 438 &\mid \mathbf{HALT} | |
| 439 \end{align*} | |
| 440 \end{definition} | |
| 441 | |
| 442 \begin{itemize} | |
| 443 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. | |
| 444 \end{itemize} | |
| 445 \end{frame} | |
| 446 } | |
| 447 | |
| 448 \defineUnit{loop}{% | |
| 449 \begin{frame} | |
| 450 \frametitle{LOOP-Programme} | |
| 451 \setbeamercovered{dynamic} | |
| 452 | |
| 453 \begin{definition}[LOOP-Programm] | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
454 Syntax von \structure{LOOP-Programmen}.\\ |
| 1 | 455 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. |
| 456 \begin{align*} | |
| 457 P &\rightarrow X := X + C \\ | |
| 458 &\mid X := X - C \\ | |
| 459 &\mid P; P \\ | |
| 460 &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\ | |
| 461 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} | |
| 462 \end{align*} | |
| 463 \end{definition} | |
| 464 | |
|
31
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
465 \vfill |
|
777563904120
tenth sheet and notes
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
30
diff
changeset
|
466 |
| 1 | 467 \begin{itemize} |
| 468 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. | |
| 469 \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.} | |
| 470 \end{itemize} | |
| 471 \end{frame} | |
| 472 } | |
| 473 | |
| 474 \defineUnit{prmax}{% | |
| 475 \begin{frame} | |
| 476 \frametitle{Beschränkte Operationen} | |
| 477 \setbeamercovered{dynamic} | |
| 478 \begin{definition} | |
| 479 Ein Prädikat $P$ ist \alert{PR}, wenn es eine PR Funktion $\hat{P}$ gibt mit | |
| 480 \[\hat{P}(x) = 1 \Longleftrightarrow P(x)\] | |
| 481 \end{definition} | |
| 482 | |
| 483 \begin{definition}[Beschränkte Operationen] | |
| 484 Ist $P$ PR, dann auch | |
| 485 \begin{itemize} | |
| 486 \item der \alert{beschränkte max-Operator} | |
| 487 \[\max \left\{ x \alert{\leq n} \mid P(x) \right\}, \quad \max \left\{ \emptyset \right\} = 0\] | |
| 488 \item der \alert{beschränkte Existenzquantor} | |
| 489 \[\exists x \alert{\leq n}. P(x)\] | |
| 490 \end{itemize} | |
| 491 \end{definition} | |
| 492 \end{frame} | |
| 493 } | |
| 494 | |
| 495 \defineUnit{murekursion}{% | |
| 496 \begin{frame} | |
| 497 \frametitle{$\mu$-Rekursion} | |
| 498 \setbeamercovered{dynamic} | |
| 499 | |
| 500 \begin{definition}[$\mu$-Operator] | |
| 501 Sei $f: \N^{k+1} \to \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \to \N$: | |
| 502 \[(\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}\] | |
| 503 \end{definition} | |
| 504 | |
| 505 \vfill | |
| 506 | |
| 507 \begin{itemize} | |
| 508 \item \alert{$^*$}Für alle \alert{$m \leq n$} muss $f$ definiert sein: $f(m, \bar{x}) \neq \perp$ | |
| 509 \item PR + $\mu$ = $\mu$-Rekursion | |
| 510 \item In Pseudocode: | |
| 511 \begin{align*} | |
| 512 \mu f(\bar{x}) &= find(0, \bar{x}) \\ | |
| 513 find(n, \bar{x}) &= \mathbf{if}\ f(n, \bar{x}) = 0 \ \mathbf{then}\ n \ \mathbf{else}\ find(n+1, \bar{x}) | |
| 514 \end{align*} | |
| 515 \end{itemize} | |
| 516 \end{frame} | |
| 517 } | |
| 518 | |
| 519 \defineUnit{modelluebersetzungen}{% | |
| 520 \begin{frame} | |
| 521 \frametitle{Übersetzungen} | |
| 522 \setbeamercovered{dynamic} | |
| 523 | |
| 524 \begin{center} | |
| 525 \begin{tikzpicture}[node distance=2.5cm] | |
| 526 \node (WH) {WHILE}; | |
| 527 \node (GO) [above left of = WH] {GOTO}; | |
| 528 \node (TM) [above right of = WH] {TM}; | |
| 529 \node (LO) [below of = WH] {LOOP}; | |
| 530 \node (PR) [left of = LO] {PR}; | |
| 531 \node (MR) [left of = WH] {$\mu$R}; | |
| 532 | |
| 533 \draw [every edge, ->] (LO) -- (WH); | |
| 534 \draw [every edge, ->] (PR) -- (MR); | |
| 535 \draw [every edge, tumgreen, <->] (LO) -- (PR); | |
| 536 \draw [every edge, tumgreen, <->] (WH) -- (MR); | |
| 537 \draw [every edge, <->] (WH) -- (GO); | |
| 538 \draw [every edge, ->] (WH) -- (TM); | |
| 539 \draw [every edge, ->] (TM) -- (GO); | |
| 540 \end{tikzpicture} | |
| 541 \end{center} | |
| 542 | |
| 543 \vfill | |
| 544 | |
| 545 LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger). | |
| 546 \end{frame} | |
| 547 } | |
| 548 | |
| 549 \defineUnit{entscheidbarkeit}{% | |
| 550 \begin{frame} | |
| 551 \frametitle{Entscheidbarkeit} | |
| 552 \setbeamercovered{dynamic} | |
| 553 | |
| 554 \begin{definition}[Entscheidbarkeit] | |
|
6
efd13093bd47
use structures instead of alerts
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
555 Eine Menge $A$ heißt \structure{entscheidbar} gdw ihre \alert{charakteristische Funktion} |
| 1 | 556 \[ \chi_A(x) := \begin{cases}1 & \text{falls } x \in A \\ 0 & \text{falls } x \not \in A \end{cases} \] |
| 557 berechenbar ist. | |
| 558 \end{definition} | |
| 559 | |
|
6
efd13093bd47
use structures instead of alerts
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
560 \vfill |
|
efd13093bd47
use structures instead of alerts
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
561 |
| 1 | 562 \begin{definition}[Semi-Entscheidbarkeit] |
|
6
efd13093bd47
use structures instead of alerts
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
563 Eine Menge $A$ heißt \structure{semi-entscheidbar} gdw |
| 1 | 564 \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \] |
| 565 berechenbar ist. | |
| 566 \end{definition} | |
| 567 \end{frame} | |
| 568 } | |
| 569 | |
| 570 \defineUnit{breduktion}{% | |
| 571 \begin{frame} | |
| 572 \frametitle{Reduzierbarkeit} | |
| 573 \setbeamercovered{dynamic} | |
| 574 | |
| 575 \begin{definition}[Reduzierbarkeit] | |
| 576 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 | |
| 577 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] | |
| 578 Wir schreiben dann \alert{$A \leq B$}. | |
| 579 \end{definition} | |
| 580 | |
| 581 \vfill | |
| 582 | |
| 583 \structure{Intuition}: | |
| 584 \begin{itemize} | |
| 585 \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$ | |
| 586 \item Ist $A$ unlösbar, dann auch $B$. | |
| 587 \item Ist $B$ lösbar, dann erst recht $A$. | |
| 588 \end{itemize} | |
| 589 \end{frame} | |
| 590 } | |
| 591 | |
| 592 \defineUnit{spezielleshalteproblem}{% | |
| 593 \begin{frame} | |
| 594 \frametitle{Spezielles Halteproblem} | |
| 595 \setbeamercovered{dynamic} | |
| 596 | |
| 597 \begin{definition}[Spezielles Halteproblem] | |
| 598 Gegeben ein \structure{Wort} $w \in \left\{ 0, 1 \right\}^*$.\\ | |
| 599 Hält \alert{$M_w$} bei Eingabe \alert{$w$}? | |
| 600 \[\alert{K} := \left\{ w \mid M_w[w]\downarrow \right\}\] | |
| 601 \end{definition} | |
| 602 | |
| 603 \begin{theorem}[] | |
| 604 Das spezielle Halteproblem ist \alert{nicht entscheidbar}. | |
| 605 \end{theorem} | |
| 606 | |
| 607 \vfill | |
| 608 | |
| 609 \begin{itemize} | |
| 610 \item Hält eine Turingmaschine mit sich selbst als Eingabe? | |
| 611 \item $w$ ist die \structure{Gödelisierung} von $M_w$. | |
| 612 \item $K$ ist semi-entscheidbar, $\overline{K}$ \alert{nicht}. | |
| 613 \end{itemize} | |
| 614 \end{frame} | |
| 615 } | |
| 616 | |
| 617 \defineUnit{halteproblem}{% | |
| 618 \begin{frame} | |
| 619 \frametitle{Allgemeines Halteproblem} | |
| 620 \setbeamercovered{dynamic} | |
| 621 | |
| 622 \begin{definition}[Allgemeines Halteproblem] | |
| 623 Gegeben \structure{Wörter} $w, x \in \left\{ 0, 1 \right\}^*$.\\ | |
| 624 Hält \alert{$M_w$} bei Eingabe \alert{$x$}? | |
| 625 \[\alert{H} := \left\{ w\#x \mid M_w[x]\downarrow \right\}\] | |
| 626 \end{definition} | |
| 627 | |
| 628 \begin{theorem}[] | |
| 629 Das allgemeine Halteproblem ist \alert{nicht entscheidbar}. | |
| 630 \end{theorem} | |
| 631 | |
| 632 \vfill | |
| 633 | |
| 634 \begin{itemize} | |
| 635 \item Es ist $K \leq H$. Warum? | |
| 636 \end{itemize} | |
| 637 \end{frame} | |
| 638 } | |
| 639 | |
| 640 \defineUnit{aufzaehlbarkeit}{% | |
| 641 \begin{frame} | |
| 642 \frametitle{Rekursive Aufzählbarkeit} | |
| 643 \setbeamercovered{dynamic} | |
| 644 | |
| 645 \begin{definition}[Rekursiv aufzählbar] | |
| 646 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 | |
| 647 \[A = \left\{ f(0), f(1), \ldots \right\} = \bigcup_{n \in \N} \left\{ f(n) \right\}\] | |
| 648 \end{definition} | |
| 649 | |
| 650 \vfill | |
| 651 | |
| 652 \structure{Äquivalent:} | |
| 653 \begin{itemize} | |
| 654 \item $A$ rekursiv aufzählbar | |
| 655 \item $A$ semi-entscheidbar, also $\chi'_A$ berechenbar | |
| 656 \item $A=L(M)$ für eine TM $M$ | |
| 657 \item $A$ ist Bild oder Urbild einer berechenbaren Funktion | |
| 658 \end{itemize} | |
| 659 \end{frame} | |
| 660 } | |
| 661 | |
| 662 \defineUnit{rice}{% | |
| 663 \begin{frame} | |
| 664 \frametitle{Satz von Rice} | |
| 665 \setbeamercovered{dynamic} | |
| 666 | |
| 667 \begin{theorem}[Rice] | |
| 668 Sei $F$ eine Menge berechenbarer Funktionen.\\ | |
| 669 Sei weder $F = \emptyset$ noch $F = \text{alle ber. Funktionen}$ (\alert{$F$ nicht trivial}).\\ | |
| 670 Dann ist \alert{unentscheidbar}, ob die von einer gegebenen TM $M_w$ berechnete Funktion in $F$ ist, also ob \alert{$\varphi_w \in F$}. | |
| 671 \end{theorem} | |
| 672 | |
| 673 \begin{itemize} | |
| 674 \item Nicht-triviale \alert{semantische} Eigenschaften von Programmen sind unentscheidbar. | |
| 675 \item \alert{Termination} ist unentscheidbar. | |
| 676 \end{itemize} | |
| 677 | |
| 678 \vfill | |
| 679 | |
| 680 \structure{Rice-Shapiro:} | |
| 681 \begin{itemize} | |
| 682 \item Termination ist nicht semi-entscheidbar. | |
| 683 \item Nicht-Termination ist nicht semi-entscheidbar. | |
| 684 \end{itemize} | |
| 685 \end{frame} | |
| 686 } | |
| 687 | |
| 688 \defineUnit{pcp}{% | |
| 689 \begin{frame} | |
| 690 \frametitle{PCP} | |
| 691 \setbeamercovered{dynamic} | |
| 692 | |
| 693 \begin{definition}[Postsches Korrespondenzproblem] | |
| 694 Gegeben \structure{endliche Folge} $(x_1, y_1), \ldots, (x_k, y_k)$ mit $x_i, y_i \in \Sigma^+$.\\ | |
| 695 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}\]} | |
| 696 \end{definition} | |
| 697 | |
| 698 \vfill | |
| 699 | |
| 700 \begin{center} | |
| 701 \begin{tikzpicture} | |
| 702 \begin{scope}[start chain, node distance=2em] | |
| 703 \node[tape, active] {\pcp{$x_i$}{$y_i$}}; | |
| 704 \node[tape] (a) {\pcp{$001$}{$00$}}; | |
| 705 \node[tape] (b) {\pcp{$10$}{$11$}}; | |
| 706 \node[tape] (c) {\pcp{$1$}{$01$}}; | |
| 707 \end{scope} | |
| 708 \node[below of=a] {$1$}; | |
| 709 \node[below of=b] {$2$}; | |
| 710 \node[below of=c] {$3$}; | |
| 711 \end{tikzpicture} | |
| 712 \end{center} | |
| 713 | |
| 714 \vfill | |
| 715 | |
| 716 \begin{theorem}[] | |
| 717 Das PCP ist \alert{unentscheidbar}, aber semi-entscheidbar. | |
| 718 \end{theorem} | |
| 719 \end{frame} | |
| 720 } | |
| 721 | |
| 722 \defineUnit{pcpbeispiel}{% | |
| 723 \begin{frame} | |
| 724 \frametitle{PCP lösen} | |
| 725 \setbeamercovered{dynamic} | |
| 726 | |
| 727 \begin{block}{Idee} | |
| 728 \alert{Mögliche Lösungen} aufzählen, richtige Lösungen identifizieren | |
| 729 \end{block} | |
| 730 | |
| 731 \begin{center} | |
| 732 \begin{tikzpicture} | |
| 733 \begin{scope}[start chain, node distance=2em] | |
| 734 \node[tape, active] {\pcp{$x_i$}{$y_i$}}; | |
| 735 \node[tape] (a) {\pcp{$001$}{$00$}}; | |
| 736 \node[tape] (b) {\pcp{$01$}{$10$}}; | |
| 737 \node[tape] (c) {\pcp{$1$}{$11$}}; | |
| 738 \end{scope} | |
| 739 \node[below of=a] {$1$}; | |
| 740 \node[below of=b] {$2$}; | |
| 741 \node[below of=c] {$3$}; | |
| 742 \end{tikzpicture} | |
| 743 | |
| 744 \vspace{2em} | |
| 745 | |
| 746 \begin{tikzpicture}[grow=right, level distance = 2cm] | |
| 747 \tikzstyle{every node} = [] | |
| 748 \tikzstyle{residual} = [rectangular, thin, fill=tumgreen!10, font=\scriptsize] | |
| 749 \tikzstyle{edge from parent} = [every edge] | |
| 750 | |
| 751 \tikzstyle{level 1} = [sibling distance = 1.7cm] | |
| 752 \tikzstyle{level 2} = [sibling distance = 1.1cm] | |
| 753 | |
| 754 \node[residual] {} | |
| 755 child { | |
| 756 node[residual] {\pcp{$1$}{}} | |
| 757 child { | |
| 758 node[residual] {\pcp{$1$}{}} | |
| 759 child { | |
| 760 node[residual] {\pcp{$1$}{}} | |
| 761 child { | |
| 762 node[residual]{$\ldots$} | |
| 763 edge from parent | |
| 764 } | |
| 765 edge from parent | |
| 766 node[below] {$2$} | |
| 767 } | |
| 768 child { | |
| 769 node[residual, active] {\pcp{}{}} | |
| 770 edge from parent | |
| 771 node[above] {$3$} | |
| 772 } | |
| 773 edge from parent | |
| 774 node[below] {$2$} | |
| 775 } | |
| 776 child { | |
| 777 node[residual, active] {\pcp{}{}} | |
| 778 edge from parent | |
| 779 node[above] {$3$} | |
| 780 } | |
| 781 edge from parent | |
| 782 node[below] {$1$} | |
| 783 } | |
| 784 child { | |
| 785 node[residual]{\pcp{}{$1$}} | |
| 786 child { | |
| 787 node[residual]{\pcp{}{$11$}} | |
| 788 child { | |
| 789 node[residual]{$\ldots$} | |
| 790 edge from parent | |
| 791 node[above] {$3$} | |
| 792 } | |
| 793 edge from parent | |
| 794 node[above] {$3$} | |
| 795 } | |
| 796 edge from parent | |
| 797 node[above] {$3$} | |
| 798 }; | |
| 799 | |
| 800 \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};} | |
| 801 \end{tikzpicture} | |
| 802 \end{center} | |
| 803 \end{frame} | |
| 804 } | |
| 805 | |
| 806 \defineUnit{time}{% | |
| 807 \begin{frame}[t] | |
| 808 \frametitle{$TIME$} | |
| 809 \setbeamercovered{dynamic} | |
| 810 | |
| 811 \begin{definition}[$TIME$] | |
| 812 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\}$.\\ | |
| 813 \vspace{1em} | |
| 814 Sei $f : \N \to \N$ total. Dann ist | |
| 815 \begin{align*} | |
| 816 \alert{TIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{DTM}\ M. A = L(M) \wedge \\ | |
| 817 &\forall w \in \Sigma^*. \structure{time_M(w) \leq f(|w|)} \} | |
| 818 \end{align*} | |
| 819 die Klasse der \structure{in Zeit $f(n)$} von einer \structure{DTM} entscheidbaren Sprachen. | |
| 820 \end{definition} | |
| 821 | |
| 822 \vfill | |
| 823 | |
| 824 \begin{itemize} | |
| 825 \item $TIME(\Oh(n))$ enthält alle "\structure{linearen Probleme}". | |
| 826 \item Also alle Probleme, für die ein Linearzeitalgorithmus existiert. | |
| 827 \end{itemize} | |
| 828 \end{frame} | |
| 829 } | |
| 830 | |
| 831 \defineUnit{ntime}{% | |
| 832 \begin{frame}[t] | |
| 833 \frametitle{$NTIME$} | |
| 834 \setbeamercovered{dynamic} | |
| 835 | |
| 836 \begin{definition}[$NTIME$] | |
| 837 Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{NTM} $M$ mit Eingabe $w$ hält als $\alert{ntime_M(w)} \in \N$. | |
| 838 \[ \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} \] | |
| 839 Dann ist | |
| 840 \begin{align*} | |
| 841 \alert{NTIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{NTM}\ M. A = L(M) \wedge \\ | |
| 842 &\forall w \in \Sigma^*. \structure{ntime_M(w) \leq f(|w|)} \} | |
| 843 \end{align*} | |
| 844 die Klasse der \structure{in Zeit $f(n)$} von einer \structure{NTM} entscheidbaren Sprachen. | |
| 845 \end{definition} | |
| 846 \end{frame} | |
| 847 } | |
| 848 | |
| 849 \defineUnit{pundnp}{% | |
| 850 \begin{frame} | |
| 851 \frametitle{P und NP} | |
| 852 \setbeamercovered{dynamic} | |
| 853 | |
| 854 \begin{definition} | |
| 855 \alert{P} ist die Menge aller von einer \structure{DTM} in polynomieller Zeit entscheidbaren Sprachen. | |
| 856 \[\alert{P}:= \bigcup_{p\text{ Polynom}} TIME(p(n)) = \bigcup_{k \in \N} TIME(\alert{\Oh(n^k)}) \] | |
| 857 \end{definition} | |
| 858 | |
| 859 \begin{definition} | |
| 860 \alert{NP} ist die Menge aller von einer \structure{NTM} in polynomieller Zeit entscheidbaren Sprachen. | |
| 861 \[\alert{NP}:= \bigcup_{p\text{ Polynom}} NTIME(p(n)) = \bigcup_{k \in \N} NTIME(\alert{\Oh(n^k)}) \] | |
| 862 \end{definition} | |
| 863 \end{frame} | |
| 864 } | |
| 865 | |
| 866 \defineUnit{verifikator}{% | |
| 867 \begin{frame} | |
| 868 \frametitle{Verifikator} | |
| 869 \setbeamercovered{dynamic} | |
| 870 | |
| 871 \begin{definition}[Verifikator] | |
| 872 Sei $M$ eine \structure{DTM} mit $L(M) \subseteq \left\{ w\# c \mid w \in \Sigma^*, c \in \Delta^* \right\}$. | |
| 873 \begin{itemize} | |
| 874 \item Falls $w\#c \in L(M)$, dann heißt $c$ \alert{Zertifikat} für $w$. | |
| 875 \item $M$ ist ein \alert{polynomiell beschränkter Verifikator} für | |
| 876 \[\left\{ \structure{w \in \Sigma^*} \mid \exists c \in \Delta^* . w\#c \in L(M) \right\}\] | |
| 877 falls $time_M(w\#c) \leq p(|w|)$ für ein Polynom $p$. | |
| 878 \end{itemize} | |
| 879 \end{definition} | |
| 880 | |
| 881 \begin{itemize} | |
| 882 \item \structure{NTM} rät Lösung (Zertifikat), \structure{DTM} probiert sie aus. | |
| 883 \item Verifizieren (wahrscheinlich) einfacher als Lösung finden. | |
| 884 \end{itemize} | |
| 885 | |
| 886 \vfill | |
| 887 | |
| 888 \begin{theorem} | |
| 889 \alert{$A \in NP$} gdw es einen pol. beschränkten Verifikator für A gibt. | |
| 890 \end{theorem} | |
| 891 \end{frame} | |
| 892 } | |
| 893 | |
| 894 \defineUnit{preduktion}{% | |
| 895 \begin{frame} | |
| 896 \frametitle{Polynomielle Reduzierbarkeit} | |
| 897 \setbeamercovered{dynamic} | |
| 898 | |
| 899 \begin{definition}[Polynomielle Reduzierbarkeit] | |
| 900 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 | |
| 901 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] | |
| 902 Wir schreiben dann \alert{$A \leq_P B$}. | |
| 903 \end{definition} | |
| 904 | |
| 905 \vfill | |
| 906 | |
| 907 \begin{itemize} | |
| 908 \item Die Relation $\leq_P$ ist \structure{transitiv}. | |
| 909 \item P und NP sind \structure{nach unten abgeschlossen}: | |
| 910 \[A \leq_P B \in P/NP \Longrightarrow A \in P/NP\] | |
| 911 \end{itemize} | |
| 912 \end{frame} | |
| 913 } | |
| 914 | |
| 915 \defineUnit{npvollstaendigkeit}{% | |
| 916 \begin{frame} | |
| 917 \frametitle{NP-Vollständigkeit} | |
| 918 \setbeamercovered{dynamic} | |
| 919 | |
| 920 \begin{definition}[NP-Schwere] | |
| 921 Eine Sprache $L$ heißt \alert{NP-schwer} (NP-hart) wenn sich \structure{alle Sprachen} in NP auf $L$ reduzieren lassen. | |
| 922 \[\forall A \in NP. A \leq_P L\] | |
| 923 \end{definition} | |
| 924 | |
| 925 \begin{definition}[NP-Vollständigkeit] | |
| 926 Eine Sprache $L$ heißt \alert{NP-vollständig} wenn $L$ \structure{NP-schwer} ist und \structure{$L \in NP$}. | |
| 927 \end{definition} | |
| 928 | |
| 929 \vfill | |
| 930 | |
| 931 \structure{Fragen}: | |
| 932 \begin{itemize} | |
| 933 \item Gibt es überhaupt NP-vollständige Sprachen? | |
| 934 \item Gibt es eine NP-vollständige Sprache in $P$? | |
| 935 \end{itemize} | |
| 936 \end{frame} | |
| 937 } | |
| 938 | |
| 939 \defineUnit{sat}{% | |
| 940 \begin{frame} | |
| 941 \frametitle{SAT} | |
| 942 \setbeamercovered{dynamic} | |
| 943 | |
| 944 \begin{definition}[Aussagenlogik] | |
| 945 Syntax der \alert{Aussagenlogik}.\\ | |
| 946 \begin{description} | |
| 947 \item[Formeln] $F \rightarrow \neg F \mid (F \wedge F) \mid (F \vee F) \mid X$ | |
| 948 \item[Variablen] $X \rightarrow x \mid y \mid z \mid \ldots$ | |
| 949 \end{description} | |
| 950 \end{definition} | |
| 951 | |
| 952 \vfill | |
| 953 | |
| 954 \begin{definition}[SAT] | |
| 955 Gegeben eine \structure{aussagenlogische Formel} $F$.\\ | |
| 956 Ist $F$ \alert{erfüllbar}, also gibt es eine Belegung der Variablen in $F$, sodass $F$ gilt? | |
| 957 \end{definition} | |
| 958 | |
| 959 \begin{theorem}[Cook 1971] | |
| 960 $\mathbf{SAT}$ ist \alert{NP-vollständig}. | |
| 961 \end{theorem} | |
| 962 \end{frame} | |
| 963 } | |
| 964 | |
| 965 \defineUnit{3col}{% | |
| 966 \begin{frame} | |
| 967 \frametitle{3COL} | |
| 968 \setbeamercovered{dynamic} | |
| 969 | |
| 970 \begin{definition}[3COL] | |
| 971 Gegeben ein \structure{Graph} $G = (V, E)$.\\ | |
| 972 Gibt es eine \alert{Färbung der Knoten} $V$ mit $3$ Farben, so dass keine zwei benachbarten Knoten die gleiche Farbe haben? | |
| 973 \end{definition} | |
| 974 | |
| 975 \vfill | |
| 976 | |
| 977 \begin{center} | |
| 978 \begin{tikzpicture} | |
| 979 \tikzstyle{red} = [fill=tumred!50] | |
| 980 \tikzstyle{green} = [fill=tumgreen!50] | |
| 981 \tikzstyle{blue} = [fill=tumblue!50] | |
| 982 \tikzstyle{vertex} = [draw, circle, thin, blue] | |
| 983 \tikzstyle{edge} = [draw, thick] | |
| 984 | |
| 985 \foreach \name/\angle/\dist/\col in { | |
| 986 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, | |
| 987 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} { | |
| 988 \node<1>[vertex] (\name) at (\angle:\dist) {}; | |
| 989 \node<2>[vertex, \col] (\name) at (\angle:\dist) {}; | |
| 990 } | |
| 991 | |
| 992 \foreach \a/\b in { | |
| 993 ia/oa, ib/ob, ic/oc, id/od, ie/oe, | |
| 994 oa/ob, ob/oc, oc/od, od/oe, oe/oa, | |
| 995 ia/ic, ic/ie, ie/ib, ib/id, id/ia} { | |
| 996 \draw[edge] (\a) -- (\b); | |
| 997 } | |
| 998 \end{tikzpicture} | |
| 999 \end{center} | |
| 1000 | |
| 1001 \begin{theorem} | |
| 1002 Es ist \alert{$\mathbf{3COL} \leq_P \mathbf{SAT}$} und $\alert{\mathbf{SAT}} \leq_P \mathbf{3SAT} \alert{\leq_P \mathbf{3COL}}$. | |
| 1003 \end{theorem} | |
| 1004 \end{frame} | |
| 1005 } | |
| 1006 | |
| 1007 \defineUnit{typ0sprachen}{% | |
| 1008 \begin{frame} | |
| 1009 \frametitle{Typ 0 Sprachen} | |
| 1010 \setbeamercovered{dynamic} | |
| 1011 | |
| 1012 \begin{center} | |
| 1013 \begin{tikzpicture}[node distance=2.5cm] | |
| 1014 \node (WH) {WHILE}; | |
| 1015 \node (GO) [above left of = WH] {GOTO}; | |
| 1016 \node (TM) [above right of = WH] {TM}; | |
| 1017 \node (MR) [left of = WH] {$\mu$R}; | |
| 1018 | |
| 1019 \draw [every edge, tumgreen, <->] (WH) -- (MR); | |
| 1020 \draw [every edge, <->] (WH) -- (GO); | |
| 1021 \draw [every edge, ->] (WH) -- (TM); | |
| 1022 \draw [every edge, ->] (TM) -- (GO); | |
| 1023 \end{tikzpicture} | |
| 1024 \end{center} | |
| 1025 | |
| 1026 \vfill | |
| 1027 | |
| 1028 \begin{theorem}[] | |
|
27
f7bcd68a0c12
eigth sheet and notes; add hierarchy slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
1029 Sei $A$ formale Sprache, dann ist äquivalent: |
| 1 | 1030 \vspace{1em} |
| 1031 \begin{itemize} | |
|
27
f7bcd68a0c12
eigth sheet and notes; add hierarchy slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
1032 \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
|
1033 \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
|
1034 \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
|
1035 \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
|
1036 \item $A$ ist \structure{Bild oder Urbild} einer berechenbaren Funktion |
| 1 | 1037 \end{itemize} |
| 1038 \end{theorem} | |
| 1039 \end{frame} | |
| 1040 } | |
| 1041 | |
| 1042 \defineUnit{spracheigenschaften}{% | |
| 1043 \begin{frame} | |
| 1044 \frametitle{Spracheigenschaften} | |
| 1045 \setbeamercovered{dynamic} | |
| 1046 | |
| 1047 \begin{itemize} | |
|
27
f7bcd68a0c12
eigth sheet and notes; add hierarchy slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
1048 \item Abschlusseigenschaften |
| 1 | 1049 \end{itemize} |
| 1050 \begin{table} | |
| 1051 \begin{tabu}to \textwidth{X[c]|ccccc} | |
| 1052 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} | |
| 1053 REG & ja & ja & ja & ja & ja\\ | |
| 1054 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
|
1055 CSL & ja & ja & ja & ja & ja\\ |
| 1 | 1056 TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja} |
| 1057 \end{tabu} | |
| 1058 \end{table} | |
| 1059 | |
| 1060 \vfill | |
| 1061 | |
| 1062 \begin{itemize} | |
|
27
f7bcd68a0c12
eigth sheet and notes; add hierarchy slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
1063 \item Entscheidbarkeit |
| 1 | 1064 \end{itemize} |
| 1065 \begin{table} | |
| 1066 \begin{tabu}to \textwidth{X[c]|cccc} | |
| 1067 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} | |
| 1068 DFA & $\Oh(n)$ & ja & ja & ja\\ | |
| 1069 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
|
1070 CSL & $\Oh(2^n)$ & nein & nein & nein\\ |
| 1 | 1071 TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein} |
| 1072 \end{tabu} | |
| 1073 \end{table} | |
| 1074 \end{frame} | |
| 1075 } | |
| 1076 | |
| 1077 \defineUnit{formalesprachen}{% | |
| 1078 \begin{frame}[c] | |
| 1079 \frametitle{Formale Sprachen} | |
| 1080 \setbeamercovered{dynamic} | |
| 1081 | |
| 1082 \begin{center} | |
| 1083 \begin{tikzpicture}[auto] | |
| 1084 \tikzstyle{rect} = [thick]; | |
| 1085 \tikzstyle{caption} = [align=left, anchor=north west]; | |
| 1086 | |
|
27
f7bcd68a0c12
eigth sheet and notes; add hierarchy slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
1087 \definecolor{hannahyellow}{HTML}{FFB81C} |
|
f7bcd68a0c12
eigth sheet and notes; add hierarchy slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
1088 \langclass{brown}{}{0}{Formale Sprache $\subseteq \Sigma^*$}; |
| 1 | 1089 \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar}; |
| 1090 \langclass{tumgreen}{}{2}{Entscheidbar}; | |
| 1091 \langclass{violet}{}{3}{LOOP, PR}; | |
| 1092 \langclass{tumred}{}{4}{NP}; | |
|
27
f7bcd68a0c12
eigth sheet and notes; add hierarchy slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
1093 \langclass{hannahyellow}{dashed}{5}{P}; |
| 1 | 1094 \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei}; |
| 1095 \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär}; | |
| 1096 \langclass{tumblue!20!black}{}{8}{Endlich}; | |
| 1097 \end{tikzpicture} | |
| 1098 \end{center} | |
| 1099 \end{frame} | |
| 1100 } |