Mercurial > 13ss.theoinf
diff notes/tex/computation.tex @ 55:b815b94ae158
ue13 notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Mon, 22 Jul 2013 23:56:37 +0200 |
parents | a2d28c18251a |
children | 3ac958d9b7c4 |
line wrap: on
line diff
--- a/notes/tex/computation.tex Mon Jul 15 23:54:45 2013 +0200 +++ b/notes/tex/computation.tex Mon Jul 22 23:56:37 2013 +0200 @@ -152,11 +152,11 @@ \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] {Berechenbare Funktionen}; - \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}; + \chomsky{tumblue}{}{0}{Berechenbare Funktionen}; + \chomsky{tumred}{dashed}{1}{Typ 0 - Rekursiv aufzählbar\\Turingmaschinen, $\lambda$-Kalkül}; + \chomsky{tumivory}{}{2}{Typ 1 - Kontextsensitiv\\CSG}; + \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\PDA, CFG}; + \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\DFA, RE}; \end{tikzpicture} \end{center} \end{frame} @@ -929,3 +929,120 @@ \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} +} + +\defineUnit{klausur}{% +\begin{frame} + \frametitle{Obacht, Klausur!} + \setbeamercovered{dynamic} + + \begin{itemize} + \item \structure{RE $\to$ $\epsilon$-NFA $\to$ NFA $\to$ DFA} + \item \structure{(Produktautomat)} + \item \structure{Quotientenautomat, Minimale DFAs} + \item Reguläres Pumpinglemma + \item \structure{CNF-Synthese} + \item \structure{Nützliche Symbole, CYK} + \item (Kellerautomaten) + \item Kontextfreies Pumpinglemma + \item Turingmaschinen + \item LOOP und PR + \item WHILE und $\mu$-Rekursion + \item Berechenbarkeit, Entscheidbarkeit, Satz von Rice + \item \structure{PCP} + \item (P und NP, Verifikatoren) + \item Reduktionen von und auf NP-Probleme + \end{itemize} +\end{frame} +}