Binary file notes/complete_notes.pdf has changed

--- 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}

--- 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.}

--- /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}

Binary file notes/ue10_notes.pdf has changed

Binary file ue10.pdf has changed