Mercurial > 13ss.theoinf

comparison notes/tex/computation.tex @ 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 a2d28c18251a
children 3ac958d9b7c4
comparison
equal deleted inserted replaced
54:25f8a7e1c9bf 55:b815b94ae158
150 \begin{center} 150 \begin{center}
151 \begin{tikzpicture}[auto] 151 \begin{tikzpicture}[auto]
152 \tikzstyle{rect} = [thick]; 152 \tikzstyle{rect} = [thick];
153 \tikzstyle{caption} = [align=left, anchor=north west]; 153 \tikzstyle{caption} = [align=left, anchor=north west];
154 154
155 \draw[rect, tumblue, fill=tumblue!10] (5.5, 0) rectangle (-5.5, 7) node[caption] {Berechenbare Funktionen}; 155 \chomsky{tumblue}{}{0}{Berechenbare Funktionen};
156 \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}; 156 \chomsky{tumred}{dashed}{1}{Typ 0 - Rekursiv aufzählbar\\Turingmaschinen, $\lambda$-Kalkül};
157 \draw[rect, tumivory, fill=tumivory!10] (3.5, 0.6) rectangle (-3.5, 4.8) node[caption] {Typ 1 - Kontextsensitiv\\CSG}; 157 \chomsky{tumivory}{}{2}{Typ 1 - Kontextsensitiv\\CSG};
158 \draw[rect, tumorange, fill=tumorange!10] (2.5, 0.9) rectangle (-2.5, 3.6) node[caption] {Typ 2 - Kontextfrei\\PDA, CFG}; 158 \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\PDA, CFG};
159 \draw[rect, tumgreen, fill=tumgreen!10] (1.5, 1.2) rectangle (-1.5, 2.4) node[caption] {Typ 3 - Regulär\\DFA, RE}; 159 \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\DFA, RE};
160 \end{tikzpicture} 160 \end{tikzpicture}
161 \end{center} 161 \end{center}
162 \end{frame} 162 \end{frame}
163 } 163 }
164 164
927 \begin{theorem} 927 \begin{theorem}
928 Es ist \alert{$\mathbf{3COL} \leq_P \mathbf{SAT}$} und $\alert{\mathbf{SAT}} \leq_P \mathbf{3SAT} \alert{\leq_P \mathbf{3COL}}$. 928 Es ist \alert{$\mathbf{3COL} \leq_P \mathbf{SAT}$} und $\alert{\mathbf{SAT}} \leq_P \mathbf{3SAT} \alert{\leq_P \mathbf{3COL}}$.
929 \end{theorem} 929 \end{theorem}
930 \end{frame} 930 \end{frame}
931 } 931 }
932
933 \defineUnit{typ0sprachen}{%
934 \begin{frame}
935 \frametitle{Typ 0 Sprachen}
936 \setbeamercovered{dynamic}
937
938 \begin{center}
939 \begin{tikzpicture}[node distance=2.5cm]
940 \node (WH) {WHILE};
941 \node (GO) [above left of = WH] {GOTO};
942 \node (TM) [above right of = WH] {TM};
943 \node (MR) [left of = WH] {$\mu$R};
944
945 \draw [every edge, tumgreen, <->] (WH) -- (MR);
946 \draw [every edge, <->] (WH) -- (GO);
947 \draw [every edge, ->] (WH) -- (TM);
948 \draw [every edge, ->] (TM) -- (GO);
949 \end{tikzpicture}
950 \end{center}
951
952 \vfill
953
954 \begin{theorem}[]
955 Sei $A$ formale Sprache, dann ist äuqivalent:
956 \vspace{1em}
957 \begin{itemize}
958 \item $A$ ist \alert{Typ 0 Sprache}
959 \item $A$ \alert{rekursiv aufzählbar}
960 \item $A$ \alert{semi-entscheidbar}, also $\chi'_A$ berechenbar
961 \item $A=L(M)$ für eine \alert{TM $M$}
962 \item $A$ ist \alert{Bild oder Urbild} einer berechenbaren Funktion
963 \end{itemize}
964 \end{theorem}
965 \end{frame}
966 }
967
968 \defineUnit{spracheigenschaften}{%
969 \begin{frame}
970 \frametitle{Spracheigenschaften}
971 \setbeamercovered{dynamic}
972
973 \begin{itemize}
974 \item \alert{Abschlusseigenschaften}
975 \end{itemize}
976 \begin{table}
977 \begin{tabu}to \textwidth{X[c]|ccccc}
978 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
979 REG & ja & ja & ja & ja & ja\\
980 CFL & nein & ja & nein & ja & ja\\
981 TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja}
982 \end{tabu}
983 \end{table}
984
985 \vfill
986
987 \begin{itemize}
988 \item \alert{Entscheidbarkeit}
989 \end{itemize}
990 \begin{table}
991 \begin{tabu}to \textwidth{X[c]|cccc}
992 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
993 DFA & $\Oh(n)$ & ja & ja & ja\\
994 CFG & $\Oh(n^3)$ & ja & nein & nein\\
995 TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein}
996 \end{tabu}
997 \end{table}
998 \end{frame}
999 }
1000
1001 \defineUnit{formalesprachen}{%
1002 \begin{frame}[c]
1003 \frametitle{Formale Sprachen}
1004 \setbeamercovered{dynamic}
1005
1006 \begin{center}
1007 \begin{tikzpicture}[auto]
1008 \tikzstyle{rect} = [thick];
1009 \tikzstyle{caption} = [align=left, anchor=north west];
1010
1011 \langclass{brown}{}{0}{Formale Sprache - $\Sigma^*$};
1012 \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar};
1013 \langclass{tumgreen}{}{2}{Entscheidbar};
1014 \langclass{violet}{}{3}{LOOP, PR};
1015 \langclass{tumred}{}{4}{NP};
1016 \langclass{tumorange}{dashed}{5}{P};
1017 \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei};
1018 \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär};
1019 \langclass{tumblue!20!black}{}{8}{Endlich};
1020 \end{tikzpicture}
1021 \end{center}
1022 \end{frame}
1023 }
1024
1025 \defineUnit{klausur}{%
1026 \begin{frame}
1027 \frametitle{Obacht, Klausur!}
1028 \setbeamercovered{dynamic}
1029
1030 \begin{itemize}
1031 \item \structure{RE $\to$ $\epsilon$-NFA $\to$ NFA $\to$ DFA}
1032 \item \structure{(Produktautomat)}
1033 \item \structure{Quotientenautomat, Minimale DFAs}
1034 \item Reguläres Pumpinglemma
1035 \item \structure{CNF-Synthese}
1036 \item \structure{Nützliche Symbole, CYK}
1037 \item (Kellerautomaten)
1038 \item Kontextfreies Pumpinglemma
1039 \item Turingmaschinen
1040 \item LOOP und PR
1041 \item WHILE und $\mu$-Rekursion
1042 \item Berechenbarkeit, Entscheidbarkeit, Satz von Rice
1043 \item \structure{PCP}
1044 \item (P und NP, Verifikatoren)
1045 \item Reduktionen von und auf NP-Probleme
1046 \end{itemize}
1047 \end{frame}
1048 }