NP-complete, Chomsky-NF, layoutHEADmain

1 files changed, 101 insertions, 41 deletions

diff --git a/sheet.tex b/sheet.tex
index 2521c6e..3ef610c 100644
--- a/sheet.tex
+++ b/sheet.tex
@@ -41,7 +41,7 @@
 \section{Chomsky-Hierarchie}
 \hspace*{-.5cm}
 \begin{tabular}{ l l l l l }
-  Chomsky-Typ & Wortproblem & Definition & Bsp & Maschinenmodell \\
+  Chomsky & Wortproblem & Definition & Bsp & Maschinenmodell \\
 
   Typ 0 & 
   semi-entscheidbar &
@@ -53,7 +53,7 @@
   NP-Schwer &
   \makecell{$u \rightarrow v, |u| \leq |v|$ \\ $u \in V^+, S \notin V$ \\ $S \rightarrow \epsilon$ } &
   $L = \{ a^ib^ic^i | i \leq 1 \}$ &
-  \makecell{NTM mit Platzbedarf n \\ erkennt Wörter der Länge n in L \\ $\Rightarrow NTAPE(n)$ } \\
+  \makecell[l]{NTM mit Platzbedarf n \\ erkennt Wörter der Länge n in L \\ $\Rightarrow NTAPE(n)$ } \\
 
   Typ 2 & 
   polynomiell & 
@@ -70,11 +70,16 @@
 
 \subsection{Automaten}
 DEA $A = (Q, \Sigma, \delta: Q \times \Sigma \rightarrow Q, s \in Q, F \subseteq Q)$ \\
-NEA $A = (Q, \Sigma, \delta: Q \times (\Sigma \cup \{ \epsilon \} \rightarrow 2^Q, s \in Q, F \subseteq Q)$
-NPDA \\
+NEA $A = (Q, \Sigma, \delta: Q \times (\Sigma \cup \{ \epsilon \} \rightarrow 2^Q, s \in Q, F \subseteq Q)$ \\
+NPDA $M = (Q, \Sigma, \Gamma, q_0 \in Q, \delta: Q \times (\Sigma \cup
+\{\epsilon\}) \times \Gamma \rightarrow 2^{Q \times \Gamma*}, F \subseteq Q)$ \\
 DPDA \\
-DTM \\
-NTM \\
+DTM $M = (Q, \Sigma, \sqcup \notin \Sigma, \Gamma \supseteq \Sigma \cup
+\{\sqcup\}, s \in Q, \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times
+\{L, R, N \}, F \subseteq Q)$ \\
+NTM $M = (Q, \Sigma, \sqcup \notin \Sigma, \Gamma \supseteq \Sigma \cup
+\{\sqcup\}, s \in Q, \delta: Q \times (\Gamma \cup \{\epsilon\}) \rightarrow 2^{Q \times \Gamma \times
+\{L, R, N \}}, F \subseteq Q)$ \\
 
 \subsection{Pumping-Lemma}
 
@@ -95,9 +100,10 @@ Widerlegen:
 \end{itemize}
 \end{multicols}
 
-\begin{multicols}{2}
-Potenzmengenkonstuktion NEA $\rightarrow$ DEA
-
+\hspace{-1cm}
+\begin{minipage}[t]{.5\textwidth}
+   \subsubsection{Potenzmengenkonstuktion NEA $\rightarrow$ DEA}
+  \begin{minipage}{.5\textwidth}
 \begin{tabular}{c | c | c}
   Zustand & a & b \\
   \hline
@@ -108,13 +114,14 @@ Potenzmengenkonstuktion NEA $\rightarrow$ DEA
   $\{f, \underline{s}\}$ & $\{f, s, q_1\}$ & $\{f\}$ \\
   $\{f, \underline{s}, q_1\}$ & $\{f, s, q_1\}$ & $\{f, q_2\}$ \\
 \end{tabular}
-
+  \end{minipage}
+  \begin{minipage}{.4\textwidth}
 \begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto]
 
   \node[state,initial,accepting]  (S)                   {$S$};
   \node[state]                    (q_1) [right of=S]    {$q_1$};
-  \node[state]                    (q_2) [right of=q_1]  {$q_2$};
-  \node[state]                    (f)   [below of=q_1] {$f$};
+  \node[state]                    (q_2) [below of=q_1]  {$q_2$};
+  \node[state]                    (f)   [below of=S] {$f$};
 
   \path[->] 
     (S) edge [loop above] node {a} ()
@@ -129,11 +136,11 @@ Potenzmengenkonstuktion NEA $\rightarrow$ DEA
   ;
 
 \end{tikzpicture}
-\end{multicols}
-
-\begin{multicols}{2}
-Entfernen von $\epsilon$-Übergängen
-
+  \end{minipage}
+\end{minipage}
+\begin{minipage}[t]{.55\textwidth}
+   \subsubsection{Entfernen von $\epsilon$-Übergängen}
+  \begin{minipage}{.5\textwidth}
 \begin{tabular}{c | c | c}
   Zustand & a & b \\
   \hline
@@ -142,7 +149,8 @@ Entfernen von $\epsilon$-Übergängen
   $q_2$ & $q_1$ & $S, q_2, q_3$ \\
   $q_3$ & $q_1$ & $S, q_2, q_3$ \\
 \end{tabular}
-
+  \end{minipage}
+  \begin{minipage}{.5\textwidth}
 \begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto]
 
   \node[state,initial]   (S)                   {$S$};
@@ -162,9 +170,11 @@ Entfernen von $\epsilon$-Übergängen
   ;
 
 \end{tikzpicture}
-\end{multicols}
-
-Minimierung von Automaten
+  \end{minipage}
+\end{minipage}
+\begin{minipage}{\textwidth}
+  \begin{minipage}[t]{.35\textwidth}
+    \vspace{0pt}
 \begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto]
 
   \node[state,initial]  (S)                   {$S$};
@@ -193,7 +203,28 @@ Minimierung von Automaten
   ;
 
 \end{tikzpicture}
-
+\end{minipage}
+  \begin{minipage}[t]{.17\textwidth}
+\vspace{1cm}
+\begin{tikzpicture} [binary tree layout]
+  \node[align=center] (1) {s,p,q,r,t,a,v \\ $\epsilon$ trennt}
+  child { 
+    node {r}
+  }
+  child { node[align=center] {s,p,q,t,u,v \\ 1 trennt}
+    child { node[align=center] {s,p,u \\ 0 trennt}
+      child { node {s} }
+      child { node {p,u} }
+    }
+    child{
+      node {q,t,v}
+    }
+  };
+\end{tikzpicture}
+\end{minipage}
+\begin{minipage}[t]{.4\textwidth}
+\vspace{0pt}
+\subsection{Minimierung von Automaten}
 \begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto]
 
   \node[state,initial]  (S)  {$[S]$};
@@ -212,42 +243,71 @@ Minimierung von Automaten
   ;
 
 \end{tikzpicture}
-
-
-
-\begin{tikzpicture} [binary tree layout]
-  \node[align=center] (1) {s,p,q,r,t,a,v \\ $\epsilon$ trennt}
-  child { 
-    node {r}
-  }
-  child { node[align=center] {s,p,q,t,u,v \\ 1 trennt}
-    child { node[align=center] {s,p,u \\ 0 trennt}
-      child { node {s} }
-      child { node {p,u} }
-    }
-    child{
-      node {q,t,v}
-    }
-  };
-\end{tikzpicture}
+\end{minipage}
+\end{minipage}
 
 \subsection{Nerode-Relation}
 
 \subsection{Chomsky-NF}
 
-\section{NP-Vollständigkeit}
+\begin{enumerate}
+  \item ersetze alle $a \in \Sigma$ in regeln durch neue Variable $Y_a$ und füge
+    $Y_a \rightarrow a$ hinzu. 
+  \item ersetze $A \rightarrow B_1...B_m$ mit $m > 2$ durch $A \rightarrow B1C1,
+    C_i \rightarrow B_{i+1}C_{i+1}, C_{m-2} \rightarrow B_{m-1}B_m$ für $1 \leq
+    i < m-2$
+  \item \begin{enumerate}
+      \item Finde die Menge V' aller Variablen A für die $A \rightarrow^* \epsilon$ existiert
+      \item Streiche alle Regeln $A \rightarrow \epsilon$; Für $A \rightarrow
+        BC$ füge ein $A \rightarrow B falls C \in V'$, $A \rightarrow B falls B \in V'$
+  \end{enumerate}
+      \item \begin{enumerate}
+          \item Finde alle Kreise $A_1 \rightarrow A_2 \rightarrow ...
+            \rightarrow A_n \rightarrow A_1$. Ersetze alle $A_i$ durch $A_1$ (rechts und links)
+          \item Für jede regel $A \rightarrow B$ und jede Regel $B \rightarrow
+            C$ füge Regel $A \rightarrow C$ hinzu, lösche Regel $A \rightarrow B$
+      \end{enumerate}
+\end{enumerate}
+Falls $S \rightarrow^* \epsilon$ existierte, füge Startsymbol S' mit Regel $S'
+\rightarrow S | \epsilon$ hinzu. 
 
 \section{Kellerautomaten}
 
+\section{NP-Vollständigkeit}
+
+Falls $L_1, L_2 \in NP, L_1 \propto L_2$ und $L_1$ NP-Schwer, dann ist auch
+$L_2$ NP-Schwer. "reduziere polynomiell von $L_1$ auf $L_2$"
+
 \subsection{$4COLOR \in NP$}
+Einen Lösungsvorschlag können wir in $O(|E|)$ verifizieren, indem wir für jede
+Kante $\{u,v\}$ überprüffen, ob $c(u) \neq c(v)$.
 
 \subsection{$3COLOR \propto 4COLOR$}
 
 \subsubsection{Transformation}
+
+Sei $G = (V,E)$ eine 3COLOR Instanz. Erstelle dann eine 4COLOR Instanz $G' =
+(V', E')$ mit $V' = V \cup \{u\}, E' = E \cup \{\{w,u\} | u \in V\}$. Die
+Transformation ist polynomial.
+
 \subsubsection{Äquivalenz/Korrektheit}
+Sei $G = (V,E)$ eine 3COLOR Instanz mit Lösung c. Dann ist c'(u) = c(u), u \in V
+mit c'(w) = 3 eine Lösung für die 4COLOR Insanz G', da nach Voraussetzung kein
+Nachbar von w die farbe 3 haben kann. 
+
+Sei $G' = (V', E')$ eine 4COLOR Instanz mit Lösung c. Dann ist $c = c'|_v$ eine
+Lösung für die 4COLOR Instanz G' da per Konstruktion kein Knoten die leiche
+Farbe wie w haben kann. 
 
 \section{Approximationsalgorithmen}
 
+\begin{tabular}{l c c}
+  Approximationsalforithmen & Minimierungsproblem & Maximierungsproblem \\
+  Absolute Approxomation (additiver Fehler) & $A(I) \leq OPT(I) + K$ & $A(I) \geq OPT(I) - K$ \\
+  Relative Approxomation (multiplikativer Fehler) & $A(I) \leq OPT(I) \cdot K$ & $A(I) \geq \frac{OPT(I)}{K}$ \\
+  $R_A(I)$ & $\frac{A(I)}{OPT(I)}$ & $\frac{OPT(I)}{A(I)}$
+\end{tabular}
+
 \section{Huffman-Kodierung}
 
 \end{document}