Mercurial > 13ss.theoinf
comparison notes/tex/ue09_notes.tex @ 35:844698060e1c
move frame down; minor erros
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Tue, 25 Jun 2013 14:27:47 +0200 |
parents | d89b21ed9eb4 |
children | 27fedbbdab6d |
comparison
equal
deleted
inserted
replaced
34:d89b21ed9eb4 | 35:844698060e1c |
---|---|
17 \begin{center} | 17 \begin{center} |
18 \begin{tikzpicture}[auto] | 18 \begin{tikzpicture}[auto] |
19 \tikzstyle{rect} = [thick]; | 19 \tikzstyle{rect} = [thick]; |
20 \tikzstyle{caption} = [align=left, anchor=north west]; | 20 \tikzstyle{caption} = [align=left, anchor=north west]; |
21 | 21 |
22 \draw[rect, tumblue, fill=tumblue!10] (5.5, 0) rectangle (-5.5, 7) node[caption] {Alle Algorithmen}; | 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}; | 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}; | 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}; | 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}; | 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} | 27 \end{tikzpicture} |
67 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\ | 67 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\ |
68 0 & \text{sonst} | 68 0 & \text{sonst} |
69 \end{cases} | 69 \end{cases} |
70 \end{align*} | 70 \end{align*} |
71 \end{example} | 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 \mapsto \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 \mapsto \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} | |
72 \end{frame} | 178 \end{frame} |
73 | 179 |
74 \begin{frame} | 180 \begin{frame} |
75 \frametitle{Programmieren mit TMs} | 181 \frametitle{Programmieren mit TMs} |
76 \setbeamercovered{dynamic} | 182 \setbeamercovered{dynamic} |
100 \end{align*} | 206 \end{align*} |
101 \end{example} | 207 \end{example} |
102 \end{frame} | 208 \end{frame} |
103 | 209 |
104 \begin{frame} | 210 \begin{frame} |
105 \frametitle{LOOP-Programme} | |
106 \setbeamercovered{dynamic} | |
107 | |
108 \begin{definition}[LOOP-Programm] | |
109 Syntax von \alert{LOOP-Programmen}.\\ | |
110 Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. | |
111 \begin{align*} | |
112 P &\rightarrow X := X + C \\ | |
113 &\mid X := X - C \\ | |
114 &\mid P; P \\ | |
115 &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\ | |
116 &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} | |
117 \end{align*} | |
118 \end{definition} | |
119 | |
120 \begin{itemize} | |
121 \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. | |
122 \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.} | |
123 \end{itemize} | |
124 \end{frame} | |
125 | |
126 \begin{frame} | |
127 \frametitle{Primitive Rekursion} | |
128 \setbeamercovered{dynamic} | |
129 | |
130 \begin{definition}[Basisfunktionen] | |
131 \alert{Primitiv Rekursiv} sind: | |
132 \begin{itemize} | |
133 \item Die konstante Funktion \alert{0} | |
134 \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$ | |
135 \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \mapsto \N, i \in [k]$ | |
136 \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] | |
137 \end{itemize} | |
138 \end{definition} | |
139 | |
140 \begin{definition}[Komposition] | |
141 Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR: | |
142 \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \] | |
143 \end{definition} | |
144 \end{frame} | |
145 | |
146 \begin{frame} | |
147 \frametitle{Primitive Rekursion} | |
148 \setbeamercovered{dynamic} | |
149 \begin{block}{Basisfunktionen und Komposition} | |
150 Schon \alert{PR} sind: | |
151 \begin{itemize} | |
152 \item Konstante: $0$ | |
153 \item Nachfolger: $s(n) = n + 1$ | |
154 \item Projektion: $\pi_i^k : \N^k \mapsto \N$ | |
155 \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ | |
156 \end{itemize} | |
157 \end{block} | |
158 | |
159 \begin{definition}[Primitive Rekursion] | |
160 Das Schema der \alert{primitiven Rekursion} erzeugt aus $g$ und $h$ die Funktion \alert{$f$}: | |
161 \begin{align*} | |
162 f(0, \bar{x}) &= g(\bar{x}) \\ | |
163 f(\alert{m + 1}, \bar{x}) &= h(f(\alert{m}, \bar{x}), \alert{m}, \bar{x}) | |
164 \end{align*} | |
165 \end{definition} | |
166 \end{frame} | |
167 | |
168 \begin{frame} | |
169 \frametitle{PR-Programme} | |
170 \setbeamercovered{dynamic} | |
171 | |
172 U.a. diese Programme sind laut Vorlesung oder Übung PR: | |
173 \begin{itemize} | |
174 \item \alert{$add(x, y) = x + y$} | |
175 \item \alert{$mult(x, y) = x \cdot y$} | |
176 \item $pred(x + 1) = \max \left\{ 0, x \right\}$ | |
177 \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$} | |
178 \item $div(x, y) = x \div y$ (Ganzzahldivision) | |
179 \item $mod(x, y) = x \mod y$ | |
180 \vspace{1.5em} | |
181 \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ | |
182 \item $sqr(x) = x^2$ | |
183 \item $twopow(n) = 2^n$ | |
184 \item $ifthen(n, a, b) = \begin{cases} a & n = 0 \\ b & n \neq 0 \end{cases}$ | |
185 \end{itemize} | |
186 \end{frame} | |
187 | |
188 \begin{frame} | |
189 \frametitle{Erweitertes PR-Schema} | |
190 \setbeamercovered{dynamic} | |
191 | |
192 \begin{definition}[Erweitertes PR-Schema] | |
193 Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt | |
194 \begin{align*} | |
195 f(0, \bar{x}) &= t_0 \\ | |
196 f(m + 1, \bar{x}) &= t | |
197 \end{align*} | |
198 wobei | |
199 \begin{itemize} | |
200 \item $t_0$ enthält nur PR-Funktionen und die $x_i$ | |
201 \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$. | |
202 \end{itemize} | |
203 \end{definition} | |
204 | |
205 \begin{theorem} | |
206 Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus. | |
207 \end{theorem} | |
208 \end{frame} | |
209 | |
210 \begin{frame} | |
211 \frametitle{WHILE-Programme} | 211 \frametitle{WHILE-Programme} |
212 \setbeamercovered{dynamic} | 212 \setbeamercovered{dynamic} |
213 | 213 |
214 \begin{definition}[WHILE-Programm] | 214 \begin{definition}[WHILE-Programm] |
215 Syntax von \alert{WHILE-Programmen}.\\ | 215 Syntax von \alert{WHILE-Programmen}.\\ |