Mercurial > 13ss.theoinf
diff notes/tex/ue09_notes.tex @ 44:15351d87ce76
transition notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Thu, 11 Jul 2013 22:06:26 +0200 |
parents | 27fedbbdab6d |
children |
line wrap: on
line diff
--- a/notes/tex/ue09_notes.tex Thu Jul 11 21:57:50 2013 +0200 +++ b/notes/tex/ue09_notes.tex Thu Jul 11 22:06:26 2013 +0200 @@ -1,281 +1,21 @@ \input{preamble.tex} +\input{frames.tex} \title{Übung 9: Berechnungsmodelle} \subtitle{Theoretische Informatik Sommersemester 2013} \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} \begin{document} - -\begin{frame} - \titlepage -\end{frame} - -\begin{frame}[c] - \frametitle{Chomsky-Hierarchie} - \setbeamercovered{dynamic} - - \begin{center} - \begin{tikzpicture}[auto] - \tikzstyle{rect} = [thick]; - \tikzstyle{caption} = [align=left, anchor=north west]; - - \draw[rect, tumblue, fill=tumblue!10] (5.5, 0) rectangle (-5.5, 7) node[caption] {Berechenbare Funktionen}; - \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}; - \draw[rect, tumivory, fill=tumivory!10] (3.5, 0.6) rectangle (-3.5, 4.8) node[caption] {Typ 1 - Kontextsensitiv\\CSG}; - \draw[rect, tumorange, fill=tumorange!10] (2.5, 0.9) rectangle (-2.5, 3.6) node[caption] {Typ 2 - Kontextfrei\\PDA, CFG}; - \draw[rect, tumgreen, fill=tumgreen!10] (1.5, 1.2) rectangle (-1.5, 2.4) node[caption] {Typ 3 - Regulär\\DFA, RE}; - \end{tikzpicture} - \end{center} -\end{frame} - -\begin{frame} - \frametitle{Berechenbarkeit} - \setbeamercovered{dynamic} - - \begin{definition}[Intuitive Berechenbarkeit] - 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$ - \begin{itemize} - \item nach \alert{endlich vielen Schritten} mit Ergebnis $f(n_1, \ldots, n_k)$ hält, falls $f(\ldots)$ definiert ist, - \item und \alert{nicht terminiert}, falls $f(\ldots)$ nicht definiert ist. - \end{itemize} - \end{definition} - - \vfill - - \begin{block}{Churchsche These (nicht beweisbar)} - Turing-Maschinen können genau \alert{alle} intuitiv berechenbaren Funktionen berechnen. - \end{block} -\end{frame} - -\begin{frame}[c] - \frametitle{Berechenbarkeit} - \setbeamercovered{dynamic} - - \begin{example}[Berechenbarkeit] - Sind die folgenden Funktionen intuitiv berechenbar? - - \begin{align*} - f_1(n) &= \begin{cases} - 1 & \text{falls $n$ prim}\\ - 0 & \text{sonst} - \end{cases} \\ - f_2(n) &= \begin{cases} - 1 & \text{falls $n$ die ersten $n$ Ziffern von $\pi$ darstellt}\\ - 0 & \text{sonst} - \end{cases} \\ - f_3(n) &= \begin{cases} - 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\ - 0 & \text{sonst} - \end{cases} - \end{align*} - \end{example} -\end{frame} - -\begin{frame} - \frametitle{LOOP-Programme} - \setbeamercovered{dynamic} - - \begin{definition}[LOOP-Programm] - Syntax von \alert{LOOP-Programmen}.\\ - Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. - \begin{align*} - P &\rightarrow X := X + C \\ - &\mid X := X - C \\ - &\mid P; P \\ - &\mid \mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END} \\ - &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} - \end{align*} - \end{definition} - - \begin{itemize} - \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. - \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.} - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Primitive Rekursion} - \setbeamercovered{dynamic} - - \begin{definition}[Basisfunktionen] - \alert{Primitiv Rekursiv} sind: - \begin{itemize} - \item Die konstante Funktion \alert{0} - \item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$ - \item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$ - \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] - \end{itemize} - \end{definition} - - \begin{definition}[Komposition] - Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR: - \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \] - \end{definition} -\end{frame} - -\begin{frame} - \frametitle{Primitive Rekursion} - \setbeamercovered{dynamic} - \begin{block}{Basisfunktionen und Komposition} - Schon \alert{PR} sind: - \begin{itemize} - \item Konstante: $0$ - \item Nachfolger: $s(n) = n + 1$ - \item Projektion: $\pi_i^k : \N^k \to \N$ - \item Komposition: $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ - \end{itemize} - \end{block} - - \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} - -\begin{frame} - \frametitle{PR-Programme} - \setbeamercovered{dynamic} - - U.a. diese Programme sind laut Vorlesung oder Übung PR: - \begin{itemize} - \item \alert{$add(x, y) = x + y$} - \item \alert{$mult(x, y) = x \cdot y$} - \item $pred(x) = \max \left\{ 0, x - 1 \right\}$ - \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$} - \item $div(x, y) = x \div y$ (Ganzzahldivision) - \item $mod(x, y) = x \mod y$ - \vspace{1.5em} - \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ - \item $sqr(x) = x^2$ - \item $twopow(n) = 2^n$ - \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$ - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Erweitertes PR-Schema} - \setbeamercovered{dynamic} - - \begin{definition}[Erweitertes PR-Schema] - Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt - \begin{align*} - f(0, \bar{x}) &= t_0 \\ - f(m + 1, \bar{x}) &= t - \end{align*} - wobei - \begin{itemize} - \item $t_0$ enthält nur PR-Funktionen und die $x_i$ - \item $t$ enthält nur \alert{$f(m, \bar{x})$}, PR Funktionen, \alert{$m$} und die $x_i$. - \end{itemize} - \end{definition} - - \begin{theorem} - Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus. - \end{theorem} -\end{frame} - -\begin{frame} - \frametitle{Programmieren mit TMs} - \setbeamercovered{dynamic} - - Sind $f_1$ und $f_2$ Endzustände von $M$, so bezeichnet - \begin{center} - \begin{tikzpicture} - \node (M) at (0, 0) {$M$}; - \node[above right=0.2cm and 1cm of M] (M1) {$M_1$}; - \node[below right=0.2cm and 1cm of M] (M2) {$M_2$}; - \coordinate[right of=M1] (M1s); - \coordinate[right of=M2] (M2s); - - \draw[every edge] (-1, 0) -- (M); - \draw[every edge] (M) -- node[above left] {$f_1$} (M1); - \draw[every edge] (M) -- node[below left] {$f_2$} (M2); - \draw[every edge] (M1) -- (M1s); - \draw[every edge] (M2) -- (M2s); - \end{tikzpicture} - \end{center} - eine \alert{Fallunterscheidung}.\\ - \begin{example}[Band=0?] - \begin{align*} - \delta(q_0, 0) &= (q_0, 0, R) \\ - \delta(q_0, \square) &= (ja, \square, L) \\ - \delta(q_0, a) &= (nein, a, N) \qquad \text{für} a \neq 0, \square - \end{align*} - \end{example} -\end{frame} - -\begin{frame} - \frametitle{WHILE-Programme} - \setbeamercovered{dynamic} - - \begin{definition}[WHILE-Programm] - Syntax von \alert{WHILE-Programmen}.\\ - Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. - \begin{align*} - P &\rightarrow X := X + C \\ - &\mid X := X - C \\ - &\mid P; P \\ - &\mid \alert{\mathbf{WHILE}\ X \neq 0 \ \mathbf{DO}\ P \ \mathbf{END}} \\ - &\mid \textcolor{gray}{\mathbf{LOOP}\ X \ \mathbf{DO}\ P \ \mathbf{END}} \\ - &\mid \textcolor{gray}{\mathbf{IF}\ X = 0 \ \mathbf{DO}\ P \ \mathbf{ELSE}\ Q \ \mathbf{END}} - \end{align*} - \end{definition} - - \begin{itemize} - \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. - \item Semantik wie erwartet. - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{GOTO-Programme} - \setbeamercovered{dynamic} - - \begin{definition}[GOTO-Programm] - Syntax von \alert{GOTO-Programmen}.\\ - Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \\ - Alle Anweisungen haben eine Markierung \alert{$M_1 : A_1; M_2 : A_2$}. - \begin{align*} - P &\rightarrow X := X + C \\ - &\mid X := X - C \\ - &\mid P; P \\ - &\mid \mathbf{GOTO}\ M_i \\ - &\mid \mathbf{IF}\ X = 0 \ \mathbf{GOTO}\ M_i \\ - &\mid \mathbf{HALT} - \end{align*} - \end{definition} - - \begin{itemize} - \item Ausgabe steht in $x_0$, Eingaben in $x_1, \ldots, x_n$, Rest ist 0. - \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Übersetzungen} - \setbeamercovered{dynamic} - - \begin{center} - \begin{tikzpicture}[node distance=2.5cm] - \node (WH) {WHILE}; - \node (GO) [above left of = WH] {GOTO}; - \node (TM) [above right of = WH] {TM}; - \node (LO) [below of = WH] {LOOP}; - \node (PR) [left of = LO] {PR}; - - \draw [every edge, ->] (LO) -- (WH); - \draw [every edge, tumgreen, <->] (LO) -- (PR); - \draw [every edge, <->] (WH) -- (GO); - \draw [every edge, ->] (WH) -- (TM); - \draw [every edge, ->] (TM) -- (GO); - \end{tikzpicture} - \end{center} - - \vfill - - LOOP kann in WHILE \alert{übersetzt} werden, WHILE ist also \alert{mindestens so mächtig} wie LOOP (sogar mächtiger). -\end{frame} - +\showUnit{titel} +\showUnit{chomsky} +\showUnit{berechenbarkeit} +\showUnit{berechenbarkeitbeispiel} +\showUnit{loop} +\showUnit{pr} +\showUnit{prrekursion} +\showUnit{prprogramme} +\showUnit{prerweitert} +\showUnit{tmif} +\showUnit{while} +\showUnit{goto} \end{document}