# HG changeset patch # User Markus Kaiser # Date 1404053900 -7200 # Node ID 77756390412069223290368883bec0e7bf5f501d # Parent b56fe50e0132b3344533f4f69a4c8cb6f40d8b74 tenth sheet and notes diff -r b56fe50e0132 -r 777563904120 notes/complete_notes.pdf Binary file notes/complete_notes.pdf has changed diff -r b56fe50e0132 -r 777563904120 notes/tex/complete_notes.tex --- a/notes/tex/complete_notes.tex Sat Jun 21 20:11:55 2014 +0200 +++ b/notes/tex/complete_notes.tex Sun Jun 29 16:58:20 2014 +0200 @@ -73,4 +73,13 @@ \showUnit{spracheigenschaften} \showUnit{chomsky} \showUnit{formalesprachen} + +%ue10 +\showUnit{pr} +\showUnit{prrekursion} +\showUnit{prerweitert} +\showUnit{prprogramme} +\showUnit{loop} +\showUnit{berechenbarkeit} +\showUnit{berechenbarkeitbeispiel} \end{document} diff -r b56fe50e0132 -r 777563904120 notes/tex/computation.tex --- a/notes/tex/computation.tex Sat Jun 21 20:11:55 2014 +0200 +++ b/notes/tex/computation.tex Sun Jun 29 16:58:20 2014 +0200 @@ -227,7 +227,7 @@ } \defineUnit{berechenbarkeitbeispiel}{% -\begin{frame}[c] +\begin{frame}[t] \frametitle{Berechenbarkeit} \setbeamercovered{dynamic} @@ -249,6 +249,14 @@ \end{cases} \end{align*} \end{example} + + \only<2> { + \vfill + + \begin{center} + Alle drei Funktionen sind intuitiv berechenbar. + \end{center} + } \end{frame} } @@ -257,18 +265,21 @@ \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} + \begin{definition}[Basisfunktionen der PR] + Die Menge der \structure{primitiv rekursiven (PR)} Funktionen ist induktiv definiert. Die Basisfunktionen sind die + \begin{description}[Projektionsfunktion\quad] + \item[konstante Funktion] $f(x) = 0$ + \item[Nachfolgerfunktion] $s(n) = n + 1$ + \item[Projektionsfunktion] $\pi_i^k : \N^k \to \N, i \in [k]$ + \end{description} + \[ \pi_i^k(x_1, \ldots, x_k) = x_i \] \end{definition} + \vfill + \begin{definition}[Komposition] - Sind $g$ und $h_i$ PR und $\bar{x} = (x_1, \ldots, x_n)$, dann ist auch \alert{$f$} PR: + Seien $g$ und $h_i$ \structure{PR} und $\bar{x} = (x_1, \ldots, x_n)$.\\ + Dann ist auch die \structure{Komposition $f$} PR. \[ f(\bar{x}) = \alert{g(h_1(\bar{x}), \ldots, h_k(\bar{x}))} \] \end{definition} \end{frame} @@ -279,15 +290,26 @@ \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} + Die folgenden Funktionen sind schon als \structure{primitiv rekursiv} bekannt. + \begin{description}[Projektionsfunktion\quad] + \item[konstante Funktion] $f(x) = 0$ + \item[Nachfolgerfunktion] $s(n) = n + 1$ + \item[Projektionsfunktion] $\pi_i^k : \N^k \to \N, i \in [k]$ + \item[Komposition] $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$ + \end{description} \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} + + \vfill + + \begin{definition}[Primitive Rekursion] + Das Schema der \structure{primitiven Rekursion} erzeugt aus $g$ und $h$ die neue Funktion \structure{$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*} + $f$ ist ebenfalls \structure{primitiv rekursiv}. + \end{definition} +\end{frame} } \defineUnit{prprogramme}{% @@ -295,17 +317,20 @@ \frametitle{PR-Programme} \setbeamercovered{dynamic} - U.a. diese Programme sind laut Vorlesung oder Übung PR: + Unter anderem diese Programme sind laut Vorlesung oder Übung PR: \begin{itemize} + \item $succ(x) = x + 1$ \item $pred(x) = \max \left\{ 0, x - 1 \right\}$ \item \alert{$add(x, y) = x + y$} \item \alert{$x \dot{-} y = \max \left\{ 0, x - y \right\}$} \item \alert{$mult(x, y) = x \cdot y$} \item $div(x, y) = x \div y$ (Ganzzahldivision) + \item $pow(x, y) = x^y$ \item Die restliche einfache Arithmetik\ldots - \vspace{1.5em} + \vfill \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ - \item $sqr(x) = x^2$, $sqrt(x) = \sqrt{x}$ + \item $sqr(x) = x^2$ + \item $sqrt(x) = \sqrt{x}$ \item $c(x), p_1(x), p_2(x)$ (Cantorsche Paarungsfunktion) \item $ifthen(n, a, b) = \begin{cases} a & n \neq 0 \\ b & n = 0 \end{cases}$ \end{itemize} @@ -318,20 +343,22 @@ \setbeamercovered{dynamic} \begin{definition}[Erweitertes PR-Schema] - Das \alert{erweiterte Schema der primitiven Rekursion} erlaubt + Das \structure{erweiterte Schema der primitiven Rekursion} erlaubt \begin{align*} f(0, \bar{x}) &= t_0 \\ f(m + 1, \bar{x}) &= t \end{align*} - wobei + wobei $t_0$ und $t$ \structure{Terme} sind für die gilt \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} + \vfill + \begin{theorem} - Das erweiterte Schema der primitiven Rekursion führt nicht aus \alert{PR} heraus. + Das erweiterte Schema der primitiven Rekursion führt nicht aus \structure{PR} heraus. \end{theorem} \end{frame} } @@ -424,7 +451,7 @@ \setbeamercovered{dynamic} \begin{definition}[LOOP-Programm] - Syntax von \alert{LOOP-Programmen}.\\ + Syntax von \structure{LOOP-Programmen}.\\ Es ist $X \in \left\{ x_0, x_1, \ldots \right\}$ und $C \in \N$. \begin{align*} P &\rightarrow X := X + C \\ @@ -435,6 +462,8 @@ \end{align*} \end{definition} + \vfill + \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.} diff -r b56fe50e0132 -r 777563904120 notes/tex/ue10_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue10_notes.tex Sun Jun 29 16:58:20 2014 +0200 @@ -0,0 +1,17 @@ +\input{preamble.tex} +\input{frames.tex} + +\title{Übung 10: PR und LOOP} +\subtitle{Theoretische Informatik Sommersemester 2014} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} +\showUnit{titel} +\showUnit{pr} +\showUnit{prrekursion} +\showUnit{prerweitert} +\showUnit{prprogramme} +\showUnit{loop} +\showUnit{berechenbarkeit} +\showUnit{berechenbarkeitbeispiel} +\end{document} diff -r b56fe50e0132 -r 777563904120 notes/ue10_notes.pdf Binary file notes/ue10_notes.pdf has changed diff -r b56fe50e0132 -r 777563904120 ue10.pdf Binary file ue10.pdf has changed