Mercurial > 14ss.theoinf
view notes/tex/computation.tex @ 3:624c6e0e4383
first slides
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Sun, 13 Apr 2014 20:22:34 +0200 |
parents | a9275b863a0d |
children | efd13093bd47 |
line wrap: on
line source
\defineUnit{tmdefinition}{% \begin{frame} \frametitle{Turingmaschinen} \setbeamercovered{dynamic} \begin{definition}[Turingmaschine] Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem \begin{itemize} \item endlichen Menge von \alert{Zuständen} $Q$ \item endlichen \alert{Eingabealphabet} $\Sigma$ \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$ \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ \item \alert{Startzustand} $q_0 \in Q$ \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$ \item Menge von \alert{Endzuständen} $F \subseteq Q$ \end{itemize} \end{definition} \end{frame} } \defineUnit{tmvisualisierung}{% \begin{frame} \frametitle{Turingmaschinen} \setbeamercovered{dynamic} \begin{definition}[Turingmaschine] Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem \begin{itemize} \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ \end{itemize} \end{definition} \vfill \begin{center} \begin{tikzpicture} % Tape \begin{scope}[start chain, node distance=0] \node[on chain] {\ldots}; \node[tape] {$\square$}; \node[tape] (l) {$\square$}; \node[tape] {$0$}; \node[tape] {$1$}; \node<1>[tape, active] (a){$0$}; \node<2>[tape] (a){$1$}; \node<1>[tape] (b){$0$}; \node<2>[tape, active] (b){$0$}; \node[tape] {$\square$}; \node[on chain] {\ldots}; \end{scope} % Head \node<1> [head,yshift=-4mm] at (a.south) (head) {$q_0$}; \node<2> [head,yshift=-4mm] at (b.south) (head) {$q_1$}; % Machine \node[machine, below=1.5cm of l] (machine) {Programm}; \draw[every edge] (machine) .. controls (3.5, -2) .. (head.south); % Example-Transition \node[yshift=5mm] at (current bounding box.north) {$\delta(q_0, 0) = (q_1, 1, R)$}; \end{tikzpicture} \end{center} \end{frame} } \defineUnit{tmkonfiguration}{% \begin{frame} \frametitle{Turingmaschinen} \setbeamercovered{dynamic} \begin{definition}[Konfiguration] Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\ Dies modelliert eine TM mit: \begin{itemize} \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$ \item \alert{Zustand} $q$ \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$ \end{itemize} Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$. \end{definition} \vfill \only<1> { \begin{center} \begin{tikzpicture} % Tape \begin{scope}[start chain, node distance=0] \node[on chain] {\ldots}; \node[tape] {$\square$}; \node[tape] (l) {$\square$}; \node[tape] {$0$}; \node[tape] {$1$}; \node[tape] (a){$1$}; \node[tape, active] (b){$0$}; \node[tape] {$\square$}; \node[on chain] {\ldots}; \end{scope} % Head \node [head,yshift=-4mm] at (b.south) (head) {$q_1$}; % Machine \node[below=1.5cm of l] (machine) {}; \draw[every edge, dashed] (machine) .. controls (3.5, -2) .. (head.south); % Example-Transition \node[yshift=5mm] at (current bounding box.north) {$(011,q_1,0)$}; \end{tikzpicture} \end{center} } \only<2> { \begin{definition}[Akzeptanz] Eine TM $M$ \alert{akzeptiert} die Sprache \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \] \end{definition} } \end{frame} } \defineUnit{ndtm}{% \begin{frame} \frametitle{Nichtdeterministische TM} \setbeamercovered{dynamic} \begin{definition}[Nichtdeterministische Turingmaschine] Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem \begin{itemize} \item \ldots \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$ \item \ldots \end{itemize} \end{definition} \vfill \begin{theorem} Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}. \end{theorem} \end{frame} } \defineUnit{chomsky}{% \begin{frame}[c] \frametitle{Chomsky-Hierarchie} \setbeamercovered{dynamic} \begin{center} \begin{tikzpicture}[auto] \tikzstyle{rect} = [thick]; \tikzstyle{caption} = [align=left, anchor=north west]; \chomsky{tumlightblue}{}{0}{Alle formalen Sprachen}; \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik}; \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik}; \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal}; \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik}; \end{tikzpicture} \end{center} \end{frame} } \defineUnit{berechenbarkeit}{% \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} } \defineUnit{berechenbarkeitbeispiel}{% \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} } \defineUnit{pr}{% \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} } \defineUnit{prrekursion}{% \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} } \defineUnit{prprogramme}{% \begin{frame} \frametitle{PR-Programme} \setbeamercovered{dynamic} U.a. diese Programme sind laut Vorlesung oder Übung PR: \begin{itemize} \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 Die restliche einfache Arithmetik\ldots \vspace{1.5em} \item $tower(n) = 2^{2^{2^{\iddots}}}$ mit $tower(4) = 2^{16}$ \item $sqr(x) = x^2$, $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} } \defineUnit{prerweitert}{% \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} } \defineUnit{tmif}{% \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} } \defineUnit{while}{% \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} } \defineUnit{goto}{% \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} } \defineUnit{loop}{% \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} } \defineUnit{prmax}{% \begin{frame} \frametitle{Beschränkte Operationen} \setbeamercovered{dynamic} \begin{definition} Ein Prädikat $P$ ist \alert{PR}, wenn es eine PR Funktion $\hat{P}$ gibt mit \[\hat{P}(x) = 1 \Longleftrightarrow P(x)\] \end{definition} \begin{definition}[Beschränkte Operationen] Ist $P$ PR, dann auch \begin{itemize} \item der \alert{beschränkte max-Operator} \[\max \left\{ x \alert{\leq n} \mid P(x) \right\}, \quad \max \left\{ \emptyset \right\} = 0\] \item der \alert{beschränkte Existenzquantor} \[\exists x \alert{\leq n}. P(x)\] \end{itemize} \end{definition} \end{frame} } \defineUnit{murekursion}{% \begin{frame} \frametitle{$\mu$-Rekursion} \setbeamercovered{dynamic} \begin{definition}[$\mu$-Operator] Sei $f: \N^{k+1} \to \N$ eine Funktion.\\Der \alert{$\mu$-Operator} definiert eine neue Funktion $\mu f : \N^k \to \N$: \[(\mu f)(\bar{x}) := \begin{cases} \min \left\{ n \in \N \mid \alert{f (n, \bar{x}) = 0}\right\} & \text{falls } n \text{ existent\alert{$^*$}} \\ \perp & \text{sonst}\end{cases}\] \end{definition} \vfill \begin{itemize} \item \alert{$^*$}Für alle \alert{$m \leq n$} muss $f$ definiert sein: $f(m, \bar{x}) \neq \perp$ \item PR + $\mu$ = $\mu$-Rekursion \item In Pseudocode: \begin{align*} \mu f(\bar{x}) &= find(0, \bar{x}) \\ find(n, \bar{x}) &= \mathbf{if}\ f(n, \bar{x}) = 0 \ \mathbf{then}\ n \ \mathbf{else}\ find(n+1, \bar{x}) \end{align*} \end{itemize} \end{frame} } \defineUnit{modelluebersetzungen}{% \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}; \node (MR) [left of = WH] {$\mu$R}; \draw [every edge, ->] (LO) -- (WH); \draw [every edge, ->] (PR) -- (MR); \draw [every edge, tumgreen, <->] (LO) -- (PR); \draw [every edge, tumgreen, <->] (WH) -- (MR); \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} } \defineUnit{entscheidbarkeit}{% \begin{frame} \frametitle{Entscheidbarkeit} \setbeamercovered{dynamic} \begin{definition}[Entscheidbarkeit] Eine Menge $A$ heißt \alert{entscheidbar} gdw ihre \alert{charakteristische Funktion} \[ \chi_A(x) := \begin{cases}1 & \text{falls } x \in A \\ 0 & \text{falls } x \not \in A \end{cases} \] berechenbar ist. \end{definition} \begin{definition}[Semi-Entscheidbarkeit] Eine Menge $A$ heißt \alert{semi-entscheidbar} gdw \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \] berechenbar ist. \end{definition} \end{frame} } \defineUnit{breduktion}{% \begin{frame} \frametitle{Reduzierbarkeit} \setbeamercovered{dynamic} \begin{definition}[Reduzierbarkeit] Eine Menge $A \subseteq \Sigma^*$ ist \alert{reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] Wir schreiben dann \alert{$A \leq B$}. \end{definition} \vfill \structure{Intuition}: \begin{itemize} \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$ \item Ist $A$ unlösbar, dann auch $B$. \item Ist $B$ lösbar, dann erst recht $A$. \end{itemize} \end{frame} } \defineUnit{spezielleshalteproblem}{% \begin{frame} \frametitle{Spezielles Halteproblem} \setbeamercovered{dynamic} \begin{definition}[Spezielles Halteproblem] Gegeben ein \structure{Wort} $w \in \left\{ 0, 1 \right\}^*$.\\ Hält \alert{$M_w$} bei Eingabe \alert{$w$}? \[\alert{K} := \left\{ w \mid M_w[w]\downarrow \right\}\] \end{definition} \begin{theorem}[] Das spezielle Halteproblem ist \alert{nicht entscheidbar}. \end{theorem} \vfill \begin{itemize} \item Hält eine Turingmaschine mit sich selbst als Eingabe? \item $w$ ist die \structure{Gödelisierung} von $M_w$. \item $K$ ist semi-entscheidbar, $\overline{K}$ \alert{nicht}. \end{itemize} \end{frame} } \defineUnit{halteproblem}{% \begin{frame} \frametitle{Allgemeines Halteproblem} \setbeamercovered{dynamic} \begin{definition}[Allgemeines Halteproblem] Gegeben \structure{Wörter} $w, x \in \left\{ 0, 1 \right\}^*$.\\ Hält \alert{$M_w$} bei Eingabe \alert{$x$}? \[\alert{H} := \left\{ w\#x \mid M_w[x]\downarrow \right\}\] \end{definition} \begin{theorem}[] Das allgemeine Halteproblem ist \alert{nicht entscheidbar}. \end{theorem} \vfill \begin{itemize} \item Es ist $K \leq H$. Warum? \end{itemize} \end{frame} } \defineUnit{aufzaehlbarkeit}{% \begin{frame} \frametitle{Rekursive Aufzählbarkeit} \setbeamercovered{dynamic} \begin{definition}[Rekursiv aufzählbar] Eine Menge $A$ heißt \alert{rekursiv aufzählbar} wenn $A = \emptyset$ oder es eine \alert{berechenbare} totale Funktion $f : \N \to A$ gibt, so dass \[A = \left\{ f(0), f(1), \ldots \right\} = \bigcup_{n \in \N} \left\{ f(n) \right\}\] \end{definition} \vfill \structure{Äquivalent:} \begin{itemize} \item $A$ rekursiv aufzählbar \item $A$ semi-entscheidbar, also $\chi'_A$ berechenbar \item $A=L(M)$ für eine TM $M$ \item $A$ ist Bild oder Urbild einer berechenbaren Funktion \end{itemize} \end{frame} } \defineUnit{rice}{% \begin{frame} \frametitle{Satz von Rice} \setbeamercovered{dynamic} \begin{theorem}[Rice] Sei $F$ eine Menge berechenbarer Funktionen.\\ Sei weder $F = \emptyset$ noch $F = \text{alle ber. Funktionen}$ (\alert{$F$ nicht trivial}).\\ Dann ist \alert{unentscheidbar}, ob die von einer gegebenen TM $M_w$ berechnete Funktion in $F$ ist, also ob \alert{$\varphi_w \in F$}. \end{theorem} \begin{itemize} \item Nicht-triviale \alert{semantische} Eigenschaften von Programmen sind unentscheidbar. \item \alert{Termination} ist unentscheidbar. \end{itemize} \vfill \structure{Rice-Shapiro:} \begin{itemize} \item Termination ist nicht semi-entscheidbar. \item Nicht-Termination ist nicht semi-entscheidbar. \end{itemize} \end{frame} } \defineUnit{pcp}{% \begin{frame} \frametitle{PCP} \setbeamercovered{dynamic} \begin{definition}[Postsches Korrespondenzproblem] Gegeben \structure{endliche Folge} $(x_1, y_1), \ldots, (x_k, y_k)$ mit $x_i, y_i \in \Sigma^+$.\\ Gibt es eine \alert{Folge von Indizes} $i_1, \ldots, i_n \in \left\{ 1, \ldots, k \right\}$ mit \alert{\[x_{i_1}, \ldots, x_{i_n} = y_{i_1}, \ldots, y_{i_n}\]} \end{definition} \vfill \begin{center} \begin{tikzpicture} \begin{scope}[start chain, node distance=2em] \node[tape, active] {\pcp{$x_i$}{$y_i$}}; \node[tape] (a) {\pcp{$001$}{$00$}}; \node[tape] (b) {\pcp{$10$}{$11$}}; \node[tape] (c) {\pcp{$1$}{$01$}}; \end{scope} \node[below of=a] {$1$}; \node[below of=b] {$2$}; \node[below of=c] {$3$}; \end{tikzpicture} \end{center} \vfill \begin{theorem}[] Das PCP ist \alert{unentscheidbar}, aber semi-entscheidbar. \end{theorem} \end{frame} } \defineUnit{pcpbeispiel}{% \begin{frame} \frametitle{PCP lösen} \setbeamercovered{dynamic} \begin{block}{Idee} \alert{Mögliche Lösungen} aufzählen, richtige Lösungen identifizieren \end{block} \begin{center} \begin{tikzpicture} \begin{scope}[start chain, node distance=2em] \node[tape, active] {\pcp{$x_i$}{$y_i$}}; \node[tape] (a) {\pcp{$001$}{$00$}}; \node[tape] (b) {\pcp{$01$}{$10$}}; \node[tape] (c) {\pcp{$1$}{$11$}}; \end{scope} \node[below of=a] {$1$}; \node[below of=b] {$2$}; \node[below of=c] {$3$}; \end{tikzpicture} \vspace{2em} \begin{tikzpicture}[grow=right, level distance = 2cm] \tikzstyle{every node} = [] \tikzstyle{residual} = [rectangular, thin, fill=tumgreen!10, font=\scriptsize] \tikzstyle{edge from parent} = [every edge] \tikzstyle{level 1} = [sibling distance = 1.7cm] \tikzstyle{level 2} = [sibling distance = 1.1cm] \node[residual] {} child { node[residual] {\pcp{$1$}{}} child { node[residual] {\pcp{$1$}{}} child { node[residual] {\pcp{$1$}{}} child { node[residual]{$\ldots$} edge from parent } edge from parent node[below] {$2$} } child { node[residual, active] {\pcp{}{}} edge from parent node[above] {$3$} } edge from parent node[below] {$2$} } child { node[residual, active] {\pcp{}{}} edge from parent node[above] {$3$} } edge from parent node[below] {$1$} } child { node[residual]{\pcp{}{$1$}} child { node[residual]{\pcp{}{$11$}} child { node[residual]{$\ldots$} edge from parent node[above] {$3$} } edge from parent node[above] {$3$} } edge from parent node[above] {$3$} }; \uncover<2>{\node at (10cm, 0) {$L = \left\{ (12^*3)^+ \right\}$};} \end{tikzpicture} \end{center} \end{frame} } \defineUnit{time}{% \begin{frame}[t] \frametitle{$TIME$} \setbeamercovered{dynamic} \begin{definition}[$TIME$] Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{DTM} $M$ mit Eingabe $w$ hält als $\alert{time_M(w)} \in \N \cup \left\{ \infty \right\}$.\\ \vspace{1em} Sei $f : \N \to \N$ total. Dann ist \begin{align*} \alert{TIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{DTM}\ M. A = L(M) \wedge \\ &\forall w \in \Sigma^*. \structure{time_M(w) \leq f(|w|)} \} \end{align*} die Klasse der \structure{in Zeit $f(n)$} von einer \structure{DTM} entscheidbaren Sprachen. \end{definition} \vfill \begin{itemize} \item $TIME(\Oh(n))$ enthält alle "\structure{linearen Probleme}". \item Also alle Probleme, für die ein Linearzeitalgorithmus existiert. \end{itemize} \end{frame} } \defineUnit{ntime}{% \begin{frame}[t] \frametitle{$NTIME$} \setbeamercovered{dynamic} \begin{definition}[$NTIME$] Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{NTM} $M$ mit Eingabe $w$ hält als $\alert{ntime_M(w)} \in \N$. \[ \alert{ntime_M(w)} := \begin{cases} \text{minimale Schrittanzahl} & \text{falls } w \in L(M) \\ 0 & \text{falls } w \not \in L(M)\end{cases} \] Dann ist \begin{align*} \alert{NTIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{NTM}\ M. A = L(M) \wedge \\ &\forall w \in \Sigma^*. \structure{ntime_M(w) \leq f(|w|)} \} \end{align*} die Klasse der \structure{in Zeit $f(n)$} von einer \structure{NTM} entscheidbaren Sprachen. \end{definition} \end{frame} } \defineUnit{pundnp}{% \begin{frame} \frametitle{P und NP} \setbeamercovered{dynamic} \begin{definition} \alert{P} ist die Menge aller von einer \structure{DTM} in polynomieller Zeit entscheidbaren Sprachen. \[\alert{P}:= \bigcup_{p\text{ Polynom}} TIME(p(n)) = \bigcup_{k \in \N} TIME(\alert{\Oh(n^k)}) \] \end{definition} \begin{definition} \alert{NP} ist die Menge aller von einer \structure{NTM} in polynomieller Zeit entscheidbaren Sprachen. \[\alert{NP}:= \bigcup_{p\text{ Polynom}} NTIME(p(n)) = \bigcup_{k \in \N} NTIME(\alert{\Oh(n^k)}) \] \end{definition} \end{frame} } \defineUnit{verifikator}{% \begin{frame} \frametitle{Verifikator} \setbeamercovered{dynamic} \begin{definition}[Verifikator] Sei $M$ eine \structure{DTM} mit $L(M) \subseteq \left\{ w\# c \mid w \in \Sigma^*, c \in \Delta^* \right\}$. \begin{itemize} \item Falls $w\#c \in L(M)$, dann heißt $c$ \alert{Zertifikat} für $w$. \item $M$ ist ein \alert{polynomiell beschränkter Verifikator} für \[\left\{ \structure{w \in \Sigma^*} \mid \exists c \in \Delta^* . w\#c \in L(M) \right\}\] falls $time_M(w\#c) \leq p(|w|)$ für ein Polynom $p$. \end{itemize} \end{definition} \begin{itemize} \item \structure{NTM} rät Lösung (Zertifikat), \structure{DTM} probiert sie aus. \item Verifizieren (wahrscheinlich) einfacher als Lösung finden. \end{itemize} \vfill \begin{theorem} \alert{$A \in NP$} gdw es einen pol. beschränkten Verifikator für A gibt. \end{theorem} \end{frame} } \defineUnit{preduktion}{% \begin{frame} \frametitle{Polynomielle Reduzierbarkeit} \setbeamercovered{dynamic} \begin{definition}[Polynomielle Reduzierbarkeit] Eine Menge $A \subseteq \Sigma^*$ ist \alert{polynomiell reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und \structure{von einer DTM in polynomieller Zeit} berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\] Wir schreiben dann \alert{$A \leq_P B$}. \end{definition} \vfill \begin{itemize} \item Die Relation $\leq_P$ ist \structure{transitiv}. \item P und NP sind \structure{nach unten abgeschlossen}: \[A \leq_P B \in P/NP \Longrightarrow A \in P/NP\] \end{itemize} \end{frame} } \defineUnit{npvollstaendigkeit}{% \begin{frame} \frametitle{NP-Vollständigkeit} \setbeamercovered{dynamic} \begin{definition}[NP-Schwere] Eine Sprache $L$ heißt \alert{NP-schwer} (NP-hart) wenn sich \structure{alle Sprachen} in NP auf $L$ reduzieren lassen. \[\forall A \in NP. A \leq_P L\] \end{definition} \begin{definition}[NP-Vollständigkeit] Eine Sprache $L$ heißt \alert{NP-vollständig} wenn $L$ \structure{NP-schwer} ist und \structure{$L \in NP$}. \end{definition} \vfill \structure{Fragen}: \begin{itemize} \item Gibt es überhaupt NP-vollständige Sprachen? \item Gibt es eine NP-vollständige Sprache in $P$? \end{itemize} \end{frame} } \defineUnit{sat}{% \begin{frame} \frametitle{SAT} \setbeamercovered{dynamic} \begin{definition}[Aussagenlogik] Syntax der \alert{Aussagenlogik}.\\ \begin{description} \item[Formeln] $F \rightarrow \neg F \mid (F \wedge F) \mid (F \vee F) \mid X$ \item[Variablen] $X \rightarrow x \mid y \mid z \mid \ldots$ \end{description} \end{definition} \vfill \begin{definition}[SAT] Gegeben eine \structure{aussagenlogische Formel} $F$.\\ Ist $F$ \alert{erfüllbar}, also gibt es eine Belegung der Variablen in $F$, sodass $F$ gilt? \end{definition} \begin{theorem}[Cook 1971] $\mathbf{SAT}$ ist \alert{NP-vollständig}. \end{theorem} \end{frame} } \defineUnit{3col}{% \begin{frame} \frametitle{3COL} \setbeamercovered{dynamic} \begin{definition}[3COL] Gegeben ein \structure{Graph} $G = (V, E)$.\\ Gibt es eine \alert{Färbung der Knoten} $V$ mit $3$ Farben, so dass keine zwei benachbarten Knoten die gleiche Farbe haben? \end{definition} \vfill \begin{center} \begin{tikzpicture} \tikzstyle{red} = [fill=tumred!50] \tikzstyle{green} = [fill=tumgreen!50] \tikzstyle{blue} = [fill=tumblue!50] \tikzstyle{vertex} = [draw, circle, thin, blue] \tikzstyle{edge} = [draw, thick] \foreach \name/\angle/\dist/\col in { ia/18/0.8cm/blue, ib/90/0.8cm/red, ic/162/0.8cm/red, id/234/0.8cm/green, ie/306/0.8cm/green, oa/18/1.6cm/red, ob/90/1.6cm/blue, oc/162/1.6cm/green, od/234/1.6cm/red, oe/306/1.6cm/blue} { \node<1>[vertex] (\name) at (\angle:\dist) {}; \node<2>[vertex, \col] (\name) at (\angle:\dist) {}; } \foreach \a/\b in { ia/oa, ib/ob, ic/oc, id/od, ie/oe, oa/ob, ob/oc, oc/od, od/oe, oe/oa, ia/ic, ic/ie, ie/ib, ib/id, id/ia} { \draw[edge] (\a) -- (\b); } \end{tikzpicture} \end{center} \begin{theorem} Es ist \alert{$\mathbf{3COL} \leq_P \mathbf{SAT}$} und $\alert{\mathbf{SAT}} \leq_P \mathbf{3SAT} \alert{\leq_P \mathbf{3COL}}$. \end{theorem} \end{frame} } \defineUnit{typ0sprachen}{% \begin{frame} \frametitle{Typ 0 Sprachen} \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 (MR) [left of = WH] {$\mu$R}; \draw [every edge, tumgreen, <->] (WH) -- (MR); \draw [every edge, <->] (WH) -- (GO); \draw [every edge, ->] (WH) -- (TM); \draw [every edge, ->] (TM) -- (GO); \end{tikzpicture} \end{center} \vfill \begin{theorem}[] Sei $A$ formale Sprache, dann ist äuqivalent: \vspace{1em} \begin{itemize} \item $A$ ist \alert{Typ 0 Sprache} \item $A$ \alert{rekursiv aufzählbar} \item $A$ \alert{semi-entscheidbar}, also $\chi'_A$ berechenbar \item $A=L(M)$ für eine \alert{TM $M$} \item $A$ ist \alert{Bild oder Urbild} einer berechenbaren Funktion \end{itemize} \end{theorem} \end{frame} } \defineUnit{spracheigenschaften}{% \begin{frame} \frametitle{Spracheigenschaften} \setbeamercovered{dynamic} \begin{itemize} \item \alert{Abschlusseigenschaften} \end{itemize} \begin{table} \begin{tabu}to \textwidth{X[c]|ccccc} & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} REG & ja & ja & ja & ja & ja\\ CFL & nein & ja & nein & ja & ja\\ TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja} \end{tabu} \end{table} \vfill \begin{itemize} \item \alert{Entscheidbarkeit} \end{itemize} \begin{table} \begin{tabu}to \textwidth{X[c]|cccc} & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} DFA & $\Oh(n)$ & ja & ja & ja\\ CFG & $\Oh(n^3)$ & ja & nein & nein\\ TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein} \end{tabu} \end{table} \end{frame} } \defineUnit{formalesprachen}{% \begin{frame}[c] \frametitle{Formale Sprachen} \setbeamercovered{dynamic} \begin{center} \begin{tikzpicture}[auto] \tikzstyle{rect} = [thick]; \tikzstyle{caption} = [align=left, anchor=north west]; \langclass{brown}{}{0}{Formale Sprache - $\Sigma^*$}; \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar}; \langclass{tumgreen}{}{2}{Entscheidbar}; \langclass{violet}{}{3}{LOOP, PR}; \langclass{tumred}{}{4}{NP}; \langclass{tumorange}{dashed}{5}{P}; \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei}; \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär}; \langclass{tumblue!20!black}{}{8}{Endlich}; \end{tikzpicture} \end{center} \end{frame} }