Mercurial > 13ss.theoinf

comparison notes/tex/ue09_notes.tex @ 44:15351d87ce76

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
transition notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Thu, 11 Jul 2013 22:06:26 +0200
parents 27fedbbdab6d
children
comparison
equal deleted inserted replaced
43:c14b92bfa07f 44:15351d87ce76
1 \input{preamble.tex} 1 \input{preamble.tex}
2 \input{frames.tex}
2 3
3 \title{Übung 9: Berechnungsmodelle} 4 \title{Übung 9: Berechnungsmodelle}
4 \subtitle{Theoretische Informatik Sommersemester 2013} 5 \subtitle{Theoretische Informatik Sommersemester 2013}
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} 6 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
6 7
7 \begin{document} 8 \begin{document}
8 9 \showUnit{titel}
9 \begin{frame} 10 \showUnit{chomsky}
10 \titlepage 11 \showUnit{berechenbarkeit}
11 \end{frame} 12 \showUnit{berechenbarkeitbeispiel}
12 13 \showUnit{loop}
13 \begin{frame}[c] 14 \showUnit{pr}
14 \frametitle{Chomsky-Hierarchie} 15 \showUnit{prrekursion}
15 \setbeamercovered{dynamic} 16 \showUnit{prprogramme}
16 17 \showUnit{prerweitert}
17 \begin{center} 18 \showUnit{tmif}
18 \begin{tikzpicture}[auto] 19 \showUnit{while}
19 \tikzstyle{rect} = [thick]; 20 \showUnit{goto}
20 \tikzstyle{caption} = [align=left, anchor=north west];
21
22 \draw[rect, tumblue, fill=tumblue!10] (5.5, 0) rectangle (-5.5, 7) node[caption] {Berechenbare Funktionen};
23 \draw[rect, dashed, tumred, fill=tumred!10] (4.5, 0.3) rectangle (-4.5, 6) node[caption] {Typ 0 - Rekursiv aufzählbar\\Turingmaschinen, $\lambda$-Kalkül};
24 \draw[rect, tumivory, fill=tumivory!10] (3.5, 0.6) rectangle (-3.5, 4.8) node[caption] {Typ 1 - Kontextsensitiv\\CSG};
25 \draw[rect, tumorange, fill=tumorange!10] (2.5, 0.9) rectangle (-2.5, 3.6) node[caption] {Typ 2 - Kontextfrei\\PDA, CFG};
26 \draw[rect, tumgreen, fill=tumgreen!10] (1.5, 1.2) rectangle (-1.5, 2.4) node[caption] {Typ 3 - Regulär\\DFA, RE};
27 \end{tikzpicture}
28 \end{center}
29 \end{frame}
30
31 \begin{frame}
32 \frametitle{Berechenbarkeit}
33 \setbeamercovered{dynamic}
34
35 \begin{definition}[Intuitive Berechenbarkeit]
36 Eine Funktion $f : \N^k \to \N$ heißt \alert{intuitiv berechenbar}, wenn es einen Algorithmus gibt, der bei Eingabe $(n_1, \ldots, n_k) \in \N^k$
37 \begin{itemize}
38 \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist,
39 \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist.
40 \end{itemize}
41 \end{definition}
42
43 \vfill
44
45 \begin{block}{Churchsche These (nicht beweisbar)}
46 Turing-Maschinen können genau \alert{alle} intuitiv berechenbaren Funktionen berechnen.
47 \end{block}
48 \end{frame}
49
50 \begin{frame}[c]
51 \frametitle{Berechenbarkeit}
52 \setbeamercovered{dynamic}
53
54 \begin{example}[Berechenbarkeit]
55 Sind die folgenden Funktionen intuitiv berechenbar?
56
57 \begin{align*}
58 f_1(n) &= \begin{cases}
59 1 & \text{falls $n$ prim}\\
60 0 & \text{sonst}
61 \end{cases} \\
62 f_2(n) &= \begin{cases}
63 1 & \text{falls $n$ die ersten $n$ Ziffern von $\pi$ darstellt}\\
64 0 & \text{sonst}
65 \end{cases} \\
66 f_3(n) &= \begin{cases}
67 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\
68 0 & \text{sonst}
69 \end{cases}
70 \end{align*}
71 \end{example}
72 \end{frame}
73
74 \begin{frame}
75 \frametitle{LOOP-Programme}
76 \setbeamercovered{dynamic}
77
78 \begin{definition}[LOOP-Programm]
79 Syntax von \alert{LOOP-Programmen}.\\
80 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$.
81 \begin{align*}
82 P &\rightarrow X := X + C \\
83 &\mid X := X - C \\
84 &\mid P; P \\
85 &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\
86 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}}
87 \end{align*}
88 \end{definition}
89
90 \begin{itemize}
91 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
92 \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.}
93 \end{itemize}
94 \end{frame}
95
96 \begin{frame}
97 \frametitle{Primitive Rekursion}
98 \setbeamercovered{dynamic}
99
100 \begin{definition}[Basisfunktionen]
101 \alert{Primitiv Rekursiv} sind:
102 \begin{itemize}
103 \item Die konstante Funktion \alert{0}
104 \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$
105 \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$
106 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \]
107 \end{itemize}
108 \end{definition}
109
110 \begin{definition}[Komposition]
111 Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR:
112 \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \]
113 \end{definition}
114 \end{frame}
115
116 \begin{frame}
117 \frametitle{Primitive Rekursion}
118 \setbeamercovered{dynamic}
119 \begin{block}{Basisfunktionen und Komposition}
120 Schon \alert{PR} sind:
121 \begin{itemize}
122 \item Konstante: $0$
123 \item Nachfolger: $s(n) = n + 1$
124 \item Projektion: $\pi_i^k : \N^k \to \N$
125 \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$
126 \end{itemize}
127 \end{block}
128
129 \begin{definition}[Primitive Rekursion]
130 Das Schema der \alert{primitiven Rekursion} erzeugt aus $g$ und $h$ die Funktion \alert{$f$}:
131 \begin{align*}
132 f(0, \bar{x}) &= g(\bar{x}) \\
133 f(\alert{m + 1}, \bar{x}) &= h(f(\alert{m}, \bar{x}), \alert{m}, \bar{x})
134 \end{align*}
135 \end{definition}
136 \end{frame}
137
138 \begin{frame}
139 \frametitle{PR-Programme}
140 \setbeamercovered{dynamic}
141
142 U.a. diese Programme sind laut Vorlesung oder Übung PR:
143 \begin{itemize}
144 \item \alert{$add(x, y) = x + y$}
145 \item \alert{$mult(x, y) = x \cdot y$}
146 \item $pred(x) = \max \left\{ 0, x - 1 \right\}$
147 \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$}
148 \item $div(x, y) = x \div y$ (Ganzzahldivision)
149 \item $mod(x, y) = x \mod y$
150 \vspace{1.5em}
151 \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$
152 \item $sqr(x) = x^2$
153 \item $twopow(n) = 2^n$
154 \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$
155 \end{itemize}
156 \end{frame}
157
158 \begin{frame}
159 \frametitle{Erweitertes PR-Schema}
160 \setbeamercovered{dynamic}
161
162 \begin{definition}[Erweitertes PR-Schema]
163 Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt
164 \begin{align*}
165 f(0, \bar{x}) &= t_0 \\
166 f(m + 1, \bar{x}) &= t
167 \end{align*}
168 wobei
169 \begin{itemize}
170 \item $t_0$ enthält nur PR-Funktionen und die $x_i$
171 \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$.
172 \end{itemize}
173 \end{definition}
174
175 \begin{theorem}
176 Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus.
177 \end{theorem}
178 \end{frame}
179
180 \begin{frame}
181 \frametitle{Programmieren mit TMs}
182 \setbeamercovered{dynamic}
183
184 Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet
185 \begin{center}
186 \begin{tikzpicture}
187 \node (M) at (0, 0) {$M$};
188 \node[above right=0.2cm and 1cm of M] (M1) {$M_1$};
189 \node[below right=0.2cm and 1cm of M] (M2) {$M_2$};
190 \coordinate[right of=M1] (M1s);
191 \coordinate[right of=M2] (M2s);
192
193 \draw[every edge] (-1, 0) -- (M);
194 \draw[every edge] (M) -- node[above left] {$f_1$} (M1);
195 \draw[every edge] (M) -- node[below left] {$f_2$} (M2);
196 \draw[every edge] (M1) -- (M1s);
197 \draw[every edge] (M2) -- (M2s);
198 \end{tikzpicture}
199 \end{center}
200 eine \alert{Fallunterscheidung}.\\
201 \begin{example}[Band=0?]
202 \begin{align*}
203 \delta(q_0, 0) &= (q_0, 0, R) \\
204 \delta(q_0, \square) &= (ja, \square, L) \\
205 \delta(q_0, a) &= (nein, a, N) \qquad \text{für} a \neq 0, \square
206 \end{align*}
207 \end{example}
208 \end{frame}
209
210 \begin{frame}
211 \frametitle{WHILE-Programme}
212 \setbeamercovered{dynamic}
213
214 \begin{definition}[WHILE-Programm]
215 Syntax von \alert{WHILE-Programmen}.\\
216 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$.
217 \begin{align*}
218 P &\rightarrow X := X + C \\
219 &\mid X := X - C \\
220 &\mid P; P \\
221 &\mid \alert{\mathbf{WHILE}\ X \neq 0 \ \mathbf{DO}\ P \ \mathbf{END}} \\
222 &\mid \textcolor{gray}{\mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END}} \\
223 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}}
224 \end{align*}
225 \end{definition}
226
227 \begin{itemize}
228 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
229 \item Semantik wie erwartet.
230 \end{itemize}
231 \end{frame}
232
233 \begin{frame}
234 \frametitle{GOTO-Programme}
235 \setbeamercovered{dynamic}
236
237 \begin{definition}[GOTO-Programm]
238 Syntax von \alert{GOTO-Programmen}.\\
239 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \\
240 Alle Anweisungen haben eine Markierung \alert{$M_1 : A_1; M_2 : A_2$}.
241 \begin{align*}
242 P &\rightarrow X := X + C \\
243 &\mid X := X - C \\
244 &\mid P; P \\
245 &\mid \mathbf{GOTO}\ M_i \\
246 &\mid \mathbf{IF}\ X = 0 \ \mathbf{GOTO}\ M_i \\
247 &\mid \mathbf{HALT}
248 \end{align*}
249 \end{definition}
250
251 \begin{itemize}
252 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0.
253 \end{itemize}
254 \end{frame}
255
256 \begin{frame}
257 \frametitle{Übersetzungen}
258 \setbeamercovered{dynamic}
259
260 \begin{center}
261 \begin{tikzpicture}[node distance=2.5cm]
262 \node (WH) {WHILE};
263 \node (GO) [above left of = WH] {GOTO};
264 \node (TM) [above right of = WH] {TM};
265 \node (LO) [below of = WH] {LOOP};
266 \node (PR) [left of = LO] {PR};
267
268 \draw [every edge, ->] (LO) -- (WH);
269 \draw [every edge, tumgreen, <->] (LO) -- (PR);
270 \draw [every edge, <->] (WH) -- (GO);
271 \draw [every edge, ->] (WH) -- (TM);
272 \draw [every edge, ->] (TM) -- (GO);
273 \end{tikzpicture}
274 \end{center}
275
276 \vfill
277
278 LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger).
279 \end{frame}
280
281 \end{document} 21 \end{document}