--- a/notes/tex/preamble.tex	Tue Jun 25 00:11:35 2013 +0200
+++ b/notes/tex/preamble.tex	Tue Jun 25 00:11:39 2013 +0200
@@ -13,6 +13,7 @@
 \usepackage{xcolor}
 \usepackage{tikz}
 \usepackage{pgfplots}
+\usepackage{mathdots}
 \usetikzlibrary{automata}
 \usetikzlibrary{calc}
 \usetikzlibrary{shapes}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue09_notes.tex	Tue Jun 25 00:11:39 2013 +0200
@@ -0,0 +1,281 @@
+\input{preamble.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] {Alle Algorithmen};
+            \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 \mapsto \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{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{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 \mapsto \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 \mapsto \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 + 1) = \max \left\{ 0, x \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 = 0 \\ b & n \neq 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{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}
+
+\end{document}

Binary file notes/ue09_notes.pdf has changed