Mercurial > 13ss.theoinf

comparison notes/tex/computation.tex @ 43:c14b92bfa07f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add missing slides; correct some errors
author Markus Kaiser <markus.kaiser@in.tum.de>
date Thu, 11 Jul 2013 21:57:50 +0200
parents 5d10471f5585
children 8e79d33bdece
comparison
equal deleted inserted replaced
42:35e8bb96da7b 43:c14b92bfa07f
118 \end{definition} 118 \end{definition}
119 } 119 }
120 \end{frame} 120 \end{frame}
121 } 121 }
122 122
123 \defineUnit{ndtm}{%
124 \begin{frame}
125 \frametitle{Nichtdeterministische TM}
126 \setbeamercovered{dynamic}
127
128 \begin{definition}[Nichtdeterministische Turingmaschine]
129 Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
130 \begin{itemize}
131 \item \ldots
132 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$
133 \item \ldots
134 \end{itemize}
135 \end{definition}
136
137 \vfill
138
139 \begin{theorem}
140 Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}.
141 \end{theorem}
142 \end{frame}
143 }
144
123 \defineUnit{chomsky}{% 145 \defineUnit{chomsky}{%
124 \begin{frame}[c] 146 \begin{frame}[c]
125 \frametitle{Chomsky-Hierarchie} 147 \frametitle{Chomsky-Hierarchie}
126 \setbeamercovered{dynamic} 148 \setbeamercovered{dynamic}
127 149
466 \begin{definition}[Semi-Entscheidbarkeit] 488 \begin{definition}[Semi-Entscheidbarkeit]
467 Eine Menge $A$ heißt \alert{semi-entscheidbar} gdw 489 Eine Menge $A$ heißt \alert{semi-entscheidbar} gdw
468 \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \] 490 \[ \chi'_A(x) := \begin{cases}1 & \text{falls } x \in A \\ \perp & \text{falls } x \not \in A \end{cases} \]
469 berechenbar ist. 491 berechenbar ist.
470 \end{definition} 492 \end{definition}
493 \end{frame}
494 }
495
496 \defineUnit{breduktion}{%
497 \begin{frame}
498 \frametitle{Reduzierbarkeit}
499 \setbeamercovered{dynamic}
500
501 \begin{definition}[Reduzierbarkeit]
502 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
503 \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\]
504 Wir schreiben dann \alert{$A \leq B$}.
505 \end{definition}
506
507 \vfill
508
509 \structure{Intuition}:
510 \begin{itemize}
511 \item $B$ ist \alert{mindestens so schwer} zu lösen wie $A$
512 \item Ist $A$ unlösbar, dann auch $B$.
513 \item Ist $B$ unlösbar, dann erst recht $A$.
514 \end{itemize}
471 \end{frame} 515 \end{frame}
472 } 516 }
473 517
474 \defineUnit{spezielleshalteproblem}{% 518 \defineUnit{spezielleshalteproblem}{%
475 \begin{frame} 519 \begin{frame}