14ss.theoinf: notes/tex/computation.tex comparison

comparison 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

comparison

equal deleted inserted replaced

-:b56fe50e0132
+:777563904120
 \end{block}
 \end{frame}
 }
 \defineUnit{berechenbarkeitbeispiel}{%
-\begin{frame}[c]
+\begin{frame}[t]
 \frametitle{Berechenbarkeit}
 \setbeamercovered{dynamic}
 \begin{example}[Berechenbarkeit]
 Sind die folgenden Funktionen intuitiv berechenbar?
 1 & \text{falls in $\pi$ $n$ Nullen am Stück vorkommen}\\
 0 & \text{sonst}
 \end{cases}
 \end{align*}
 \end{example}
+\only<2> {
+\vfill
+\begin{center}
+Alle drei Funktionen sind intuitiv berechenbar.
+\end{center}
+}
 \end{frame}
 }
 \defineUnit{pr}{%
 \begin{frame}
 \frametitle{Primitive Rekursion}
 \setbeamercovered{dynamic}
-\begin{definition}[Basisfunktionen]
+\begin{definition}[Basisfunktionen der PR]
-\alert{Primitiv Rekursiv} sind:
+Die Menge der \structure{primitiv rekursiven (PR)} Funktionen ist induktiv definiert. Die Basisfunktionen sind die
-\begin{itemize}
+\begin{description}[Projektionsfunktion\quad]
-\item Die konstante Funktion \alert{0}
+\item[konstante Funktion] $f(x) = 0$
-\item Die \alert{Nachfolgerfunktion} $s(n) = n + 1$
+\item[Nachfolgerfunktion] $s(n) = n + 1$
-\item Die \alert{Projektionsfunktion} $\pi_i^k : \N^k \to \N, i \in [k]$
+\item[Projektionsfunktion] $\pi_i^k : \N^k \to \N, i \in [k]$
-\[ \pi_i^k(x_1, \ldots, x_k) = x_i \]
+\end{description}
-\end{itemize}
+\[ \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}
 }
 \defineUnit{prrekursion}{%
 \begin{frame}
 \frametitle{Primitive Rekursion}
 \setbeamercovered{dynamic}
 \begin{block}{Basisfunktionen und Komposition}
-Schon \alert{PR} sind:
+Die folgenden Funktionen sind schon als \structure{primitiv rekursiv} bekannt.
-\begin{itemize}
+\begin{description}[Projektionsfunktion\quad]
-\item Konstante: $0$
+\item[konstante Funktion] $f(x) = 0$
-\item Nachfolger: $s(n) = n + 1$
+\item[Nachfolgerfunktion] $s(n) = n + 1$
-\item Projektion: $\pi_i^k : \N^k \to \N$
+\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}))$
+\item[Komposition] $f(\bar{x}) = g(h_1(\bar{x}), \ldots, h_k(\bar{x}))$
-\end{itemize}
+\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}{%
 \begin{frame}
 \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}
 \end{frame}
 }
 \begin{frame}
 \frametitle{Erweitertes PR-Schema}
 \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}
 }
 \defineUnit{tmif}{%
 \begin{frame}
 \frametitle{LOOP-Programme}
 \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 \\
 &\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}
+\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.}
 \end{itemize}

Mercurial > 14ss.theoinf

comparison notes/tex/computation.tex @ 31:777563904120