sheet.tex (10619B)
1 \documentclass[11pt, a4paper, twoside]{article} 2 \usepackage[ 3 a4paper, 4 headsep=5mm, 5 footskip=0mm, 6 top=12mm, 7 left=10mm, 8 right=10mm, 9 bottom=10mm 10 ]{geometry} 11 \usepackage{amsmath} 12 \usepackage{amsfonts} 13 \usepackage{makecell} 14 \usepackage{multicol} 15 \usepackage[noend]{algorithm2e} 16 \usepackage[utf8]{inputenc} 17 \usepackage{fancyhdr} 18 \usepackage{tikz} 19 \usetikzlibrary{arrows,automata,positioning, graphs, graphdrawing} 20 \usegdlibrary {trees} 21 \usepackage{hyperref} 22 \hypersetup{ 23 colorlinks=true, 24 linkcolor=blue, 25 filecolor=magenta, 26 urlcolor=cyan, 27 pdftitle={Overleaf Example}, 28 pdfpagemode=FullScreen, 29 } 30 31 \setlength{\algomargin}{0pt} 32 33 \begin{document} 34 \pagestyle{fancy} 35 \fancyhead{} 36 \fancyhead[L]{Theoretische Grundlagen der Informatik} 37 \fancyhead[R]{Gero Beckmann - \url{https://github.com/Geronymos/}} 38 \fancyfoot{} 39 \fancyfoot[R]{\thepage} 40 \newenvironment{definition}[1]{\noindent\textbf{#1:}}{} 41 \section{Chomsky-Hierarchie} 42 \hspace*{-.5cm} 43 \begin{tabular}{ l l l l l } 44 Chomsky & Wortproblem & Definition & Bsp & Maschinenmodell \\ 45 46 Typ 0 & 47 semi-entscheidbar & 48 \makecell{$G = (\Sigma, V, S, R)$ \\ $R beliebig$ }& 49 universelle Sprache & 50 NTM/DTM akzeptiert L \\ 51 52 Typ 1 & 53 NP-Schwer & 54 \makecell{$u \rightarrow v, |u| \leq |v|$ \\ $u \in V^+, S \notin V$ \\ $S \rightarrow \epsilon$ } & 55 $L = \{ a^ib^ic^i | i \leq 1 \}$ & 56 \makecell[l]{NTM mit Platzbedarf n \\ erkennt Wörter der Länge n in L \\ $\Rightarrow NTAPE(n)$ } \\ 57 58 Typ 2 & 59 polynomiell & 60 \makecell{$A \rightarrow v, A \in V$ \\ $v beliebig$} & 61 $L = \{ a^ib^i | i \leq 1\}$ & 62 CYK-Alg. erkennt L in polynom. Zeit, Chomsky-NF, NPDA \\ 63 64 Typ 3 & 65 linear & 66 \makecell{$A \rightarrow v, A \in V$ \\ $V \in \epsilon \cup \Sigma \cdot V$} & 67 $L = \{ a^i | i \leq 1 \}$ & 68 NEA/DEA erkennt L \\ 69 \end{tabular} 70 71 \subsection{Automaten} 72 DEA $A = (Q, \Sigma, \delta: Q \times \Sigma \rightarrow Q, s \in Q, F \subseteq Q)$ \\ 73 NEA $A = (Q, \Sigma, \delta: Q \times (\Sigma \cup \{ \epsilon \} \rightarrow 2^Q, s \in Q, F \subseteq Q)$ \\ 74 NPDA $M = (Q, \Sigma, \Gamma, q_0 \in Q, \delta: Q \times (\Sigma \cup 75 \{\epsilon\}) \times \Gamma \rightarrow 2^{Q \times \Gamma*}, F \subseteq Q)$ \\ 76 DPDA \\ 77 DTM $M = (Q, \Sigma, \sqcup \notin \Sigma, \Gamma \supseteq \Sigma \cup 78 \{\sqcup\}, s \in Q, \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times 79 \{L, R, N \}, F \subseteq Q)$ \\ 80 NTM $M = (Q, \Sigma, \sqcup \notin \Sigma, \Gamma \supseteq \Sigma \cup 81 \{\sqcup\}, s \in Q, \delta: Q \times (\Gamma \cup \{\epsilon\}) \rightarrow 2^{Q \times \Gamma \times 82 \{L, R, N \}}, F \subseteq Q)$ \\ 83 84 \subsection{Pumping-Lemma} 85 86 \begin{multicols}{2} 87 Erfüllt: 88 \begin{itemize} 89 \item["$\exists$"] Wähle $n = 2$ 90 \item["$\forall$"] Betrachte beliebiges $w \in L$ mit $|w| > 2$ 91 \item["$\exists$"] Wähle zerlegung $w = uvx$ mit $u = \epsilon, v = aa, x=a^{2(j-1)}$ 92 \item["$\forall$"] Für alle $i \in \mathbb{N}_0: uv^ix = a^{2i}a^2(j-1) = a^{2(i+j-1)} \in L$ 93 \end{itemize} 94 Widerlegen: 95 \begin{itemize} 96 \item["$\exists$"] Wähle $n = 2$ 97 \item["$\forall$"] Betrachte beliebiges $w \in L$ mit $|w| > 2$ 98 \item["$\exists$"] Wähle zerlegung $w = uvx$ mit $u = \epsilon, v = aa, x=a^{2(j-1)}$ 99 \item["$\forall$"] Für alle $i \in \mathbb{N}_0: uv^ix = a^{2i}a^2(j-1) = a^{2(i+j-1)} \in L$ 100 \end{itemize} 101 \end{multicols} 102 103 \hspace{-1cm} 104 \begin{minipage}[t]{.5\textwidth} 105 \subsubsection{Potenzmengenkonstuktion NEA $\rightarrow$ DEA} 106 \begin{minipage}{.5\textwidth} 107 \begin{tabular}{c | c | c} 108 Zustand & a & b \\ 109 \hline 110 $\{\underline{s}\}$ & $\{s, q_1\}$ & $\{f\}$ \\ 111 $\{\underline{s}, q_1\}$ & $\{s, q_1\}$ & $\{f, q_2\}$ \\ 112 $\{f\}$ & $\{f\}$ & $\{f\}$ \\ 113 $\{f, q_2\}$ & $\{f\}$ & $\{f, q_1, q_2\}$ \\ 114 $\{f, \underline{s}\}$ & $\{f, s, q_1\}$ & $\{f\}$ \\ 115 $\{f, \underline{s}, q_1\}$ & $\{f, s, q_1\}$ & $\{f, q_2\}$ \\ 116 \end{tabular} 117 \end{minipage} 118 \begin{minipage}{.4\textwidth} 119 \begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto] 120 121 \node[state,initial,accepting] (S) {$S$}; 122 \node[state] (q_1) [right of=S] {$q_1$}; 123 \node[state] (q_2) [below of=q_1] {$q_2$}; 124 \node[state] (f) [below of=S] {$f$}; 125 126 \path[->] 127 (S) edge [loop above] node {a} () 128 (S) edge node [below] {a} (q_1) 129 (S) edge node [left] {b} (f) 130 (q_1) edge [bend right] node [above] {a} (S) 131 (q_1) edge node [below] {b} (q_2) 132 (q_2) edge [bend right] node [above] {b} (q_1) 133 (q_2) edge [loop right] node {b} () 134 (q_2) edge node {a} (f) 135 (f) edge [loop left] node {a,b} () 136 ; 137 138 \end{tikzpicture} 139 \end{minipage} 140 \end{minipage} 141 \begin{minipage}[t]{.55\textwidth} 142 \subsubsection{Entfernen von $\epsilon$-Übergängen} 143 \begin{minipage}{.5\textwidth} 144 \begin{tabular}{c | c | c} 145 Zustand & a & b \\ 146 \hline 147 $S$ & $q_1$ & $S, q_1, q_2, q_3$ \\ 148 $q_1$ & $q_2, q_3$ & $q_3$ \\ 149 $q_2$ & $q_1$ & $S, q_2, q_3$ \\ 150 $q_3$ & $q_1$ & $S, q_2, q_3$ \\ 151 \end{tabular} 152 \end{minipage} 153 \begin{minipage}{.5\textwidth} 154 \begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto] 155 156 \node[state,initial] (S) {$S$}; 157 \node[state,accepting] (q_1) [right of=S] {$q_1$}; 158 \node[state,accepting] (q_2) [below of=q_1] {$q_2$}; 159 \node[state] (q_3) [below of=S] {$q_3$}; 160 161 \path[->] 162 (S) edge node {b} (q_1) 163 (S) edge node [above left] {$\epsilon$} (q_2) 164 (q_1) edge node {a} (q_2) 165 (q_1) edge [bend left] node [above right] {b} (q_3) 166 (q_2) edge node {\epsilon} (q_3) 167 (q_3) edge node [below left] {a} (q_1) 168 (q_3) edge node {b} (S) 169 (q_3) edge [loop left] node {b} () 170 ; 171 172 \end{tikzpicture} 173 \end{minipage} 174 \end{minipage} 175 \begin{minipage}{\textwidth} 176 \begin{minipage}[t]{.35\textwidth} 177 \vspace{0pt} 178 \begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto] 179 180 \node[state,initial] (S) {$S$}; 181 \node[state] (p) [right of=S] {$p$}; 182 \node[state] (q) [right of=p] {$q$}; 183 \node[state] (t) [below of=p] {$t$}; 184 \node[state,accepting] (r) [below of=q] {$r$}; 185 \node[state] (v) [below of=t] {$v$}; 186 \node[state] (u) [below of=r] {$u$}; 187 188 \path[->] 189 (S) edge [loop above] node {0} () 190 (S) edge node {1} (p) 191 (p) edge [loop above] node {1} () 192 (p) edge node {0} (q) 193 (q) edge [bend left] node {0} (S) 194 (q) edge node {1} (r) 195 (t) edge node [right] {0} (S) 196 (t) edge [bend right] node {1} (r) 197 (r) edge [bend right] node [above] {0} (t) 198 (r) edge node {1} (u) 199 (v) edge node {0} (S) 200 (v) edge node[left] {1} (r) 201 (u) edge node {0} (v) 202 (u) edge [loop right] node {1} () 203 ; 204 205 \end{tikzpicture} 206 \end{minipage} 207 \begin{minipage}[t]{.17\textwidth} 208 \vspace{1cm} 209 \begin{tikzpicture} [binary tree layout] 210 \node[align=center] (1) {s,p,q,r,t,a,v \\ $\epsilon$ trennt} 211 child { 212 node {r} 213 } 214 child { node[align=center] {s,p,q,t,u,v \\ 1 trennt} 215 child { node[align=center] {s,p,u \\ 0 trennt} 216 child { node {s} } 217 child { node {p,u} } 218 } 219 child{ 220 node {q,t,v} 221 } 222 }; 223 \end{tikzpicture} 224 \end{minipage} 225 \begin{minipage}[t]{.4\textwidth} 226 \vspace{0pt} 227 \subsection{Minimierung von Automaten} 228 \begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto] 229 230 \node[state,initial] (S) {$[S]$}; 231 \node[state] (p) [right of=S] {$[p]$}; 232 \node[state] (q) [right of=p] {$[q]$}; 233 \node[state,accepting] (r) [right of=q] {$[r]$}; 234 235 \path[->] 236 (S) edge [loop above] node {0} () 237 (S) edge node {1} (p) 238 (p) edge [loop above] node {1} (p) 239 (p) edge node {0} (q) 240 (q) edge[bend left] node {0} (S) 241 (q) edge node {1} (r) 242 (r) edge[bend right] node [above] {1} (p) 243 ; 244 245 \end{tikzpicture} 246 \end{minipage} 247 \end{minipage} 248 249 \subsection{Nerode-Relation} 250 251 \subsection{Chomsky-NF} 252 253 \begin{enumerate} 254 \item ersetze alle $a \in \Sigma$ in regeln durch neue Variable $Y_a$ und füge 255 $Y_a \rightarrow a$ hinzu. 256 \item ersetze $A \rightarrow B_1...B_m$ mit $m > 2$ durch $A \rightarrow B1C1, 257 C_i \rightarrow B_{i+1}C_{i+1}, C_{m-2} \rightarrow B_{m-1}B_m$ für $1 \leq 258 i < m-2$ 259 \item \begin{enumerate} 260 \item Finde die Menge V' aller Variablen A für die $A \rightarrow^* \epsilon$ existiert 261 \item Streiche alle Regeln $A \rightarrow \epsilon$; Für $A \rightarrow 262 BC$ füge ein $A \rightarrow B falls C \in V'$, $A \rightarrow B falls B \in V'$ 263 \end{enumerate} 264 \item \begin{enumerate} 265 \item Finde alle Kreise $A_1 \rightarrow A_2 \rightarrow ... 266 \rightarrow A_n \rightarrow A_1$. Ersetze alle $A_i$ durch $A_1$ (rechts und links) 267 \item Für jede regel $A \rightarrow B$ und jede Regel $B \rightarrow 268 C$ füge Regel $A \rightarrow C$ hinzu, lösche Regel $A \rightarrow B$ 269 \end{enumerate} 270 \end{enumerate} 271 Falls $S \rightarrow^* \epsilon$ existierte, füge Startsymbol S' mit Regel $S' 272 \rightarrow S | \epsilon$ hinzu. 273 274 \section{Kellerautomaten} 275 276 \section{NP-Vollständigkeit} 277 278 Falls $L_1, L_2 \in NP, L_1 \propto L_2$ und $L_1$ NP-Schwer, dann ist auch 279 $L_2$ NP-Schwer. "reduziere polynomiell von $L_1$ auf $L_2$" 280 281 \subsection{$4COLOR \in NP$} 282 Einen Lösungsvorschlag können wir in $O(|E|)$ verifizieren, indem wir für jede 283 Kante $\{u,v\}$ überprüffen, ob $c(u) \neq c(v)$. 284 285 \subsection{$3COLOR \propto 4COLOR$} 286 287 \subsubsection{Transformation} 288 289 Sei $G = (V,E)$ eine 3COLOR Instanz. Erstelle dann eine 4COLOR Instanz $G' = 290 (V', E')$ mit $V' = V \cup \{u\}, E' = E \cup \{\{w,u\} | u \in V\}$. Die 291 Transformation ist polynomial. 292 293 \subsubsection{Äquivalenz/Korrektheit} 294 Sei $G = (V,E)$ eine 3COLOR Instanz mit Lösung c. Dann ist c'(u) = c(u), u \in V 295 mit c'(w) = 3 eine Lösung für die 4COLOR Insanz G', da nach Voraussetzung kein 296 Nachbar von w die farbe 3 haben kann. 297 298 Sei $G' = (V', E')$ eine 4COLOR Instanz mit Lösung c. Dann ist $c = c'|_v$ eine 299 Lösung für die 4COLOR Instanz G' da per Konstruktion kein Knoten die leiche 300 Farbe wie w haben kann. 301 302 \section{Approximationsalgorithmen} 303 304 \begin{tabular}{l c c} 305 Approximationsalforithmen & Minimierungsproblem & Maximierungsproblem \\ 306 Absolute Approxomation (additiver Fehler) & $A(I) \leq OPT(I) + K$ & $A(I) \geq OPT(I) - K$ \\ 307 Relative Approxomation (multiplikativer Fehler) & $A(I) \leq OPT(I) \cdot K$ & $A(I) \geq \frac{OPT(I)}{K}$ \\ 308 $R_A(I)$ & $\frac{A(I)}{OPT(I)}$ & $\frac{OPT(I)}{A(I)}$ 309 \end{tabular} 310 311 \section{Huffman-Kodierung} 312 313 \end{document}