Mercurial > 13ss.theoinf

changeset 55:b815b94ae158

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ue13 notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Mon, 22 Jul 2013 23:56:37 +0200
parents 25f8a7e1c9bf
children 912d08706f16
files notes/tex/complete_notes.tex notes/tex/computation.tex notes/tex/frames.tex notes/tex/preamble.tex notes/tex/ue13_notes.tex
diffstat 5 files changed, 169 insertions(+), 5 deletions(-) [+]
line wrap: on
line diff
--- a/notes/tex/complete_notes.tex	Mon Jul 15 23:54:45 2013 +0200
+++ b/notes/tex/complete_notes.tex	Mon Jul 22 23:56:37 2013 +0200
@@ -76,6 +76,9 @@
 \showUnit{tmif}
 \showUnit{while}
 \showUnit{goto}
+\showUnit{typ0sprachen}
+\showUnit{spracheigenschaften}
+\showUnit{formalesprachen}
 \showUnit{berechenbarkeit}
 \showUnit{entscheidbarkeit}
 \showUnit{breduktion}
@@ -97,4 +100,7 @@
 \showUnit{npvollstaendigkeit}
 \showUnit{sat}
 \showUnit{3col}
+
+% ue13
+\showUnit{klausur}
 \end{document}
--- 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}
+}
--- a/notes/tex/frames.tex	Mon Jul 15 23:54:45 2013 +0200
+++ b/notes/tex/frames.tex	Mon Jul 22 23:56:37 2013 +0200
@@ -68,6 +68,31 @@
 \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}
+}
+
 \input{automatons.tex}
 \input{grammars.tex}
 \input{computation.tex}
--- a/notes/tex/preamble.tex	Mon Jul 15 23:54:45 2013 +0200
+++ b/notes/tex/preamble.tex	Mon Jul 22 23:56:37 2013 +0200
@@ -42,3 +42,5 @@
 \tikzstyle{machine} = [rectangle, draw, minimum width=2cm, minimum height=1cm, inner sep=3mm, fill=tumgreen!10]
 
 \newcommand{\pcp}[2]{ \begin{tabu}{c} #1 \\ \tabucline{-} #2 \\ \end{tabu} }
+\newcommand{\chomsky}[4]{\draw[rect, #1, fill=#1!10, #2] ({5.5 - #3 * 1}, {0 + #3 * 0.3}) rectangle ({-5.5 + #3 * 1}, {7 - #3 * 1.2}) node[caption] {#4};}
+\newcommand{\langclass}[4]{\draw[rect, #1, fill=#1!20, #2] ({5.2 - #3 * 0.5}, {0 + #3 * 0.12}) rectangle ({-5.2 + #3 * 0.5}, {7.5 - #3 * 0.75}) node[caption] {#4};}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue13_notes.tex	Mon Jul 22 23:56:37 2013 +0200
@@ -0,0 +1,14 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 13: Wiederholung}
+\subtitle{Theoretische Informatik Sommersemester 2013}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{typ0sprachen}
+\showUnit{spracheigenschaften}
+\showUnit{formalesprachen}
+\showUnit{klausur}
+\end{document}