1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
|
\renewcommand{\P}{\mathcal{P}}
\newcommand{\NP}{\mathcal{NP}}
\section*{Endliche Automaten}
Ein \emph{deterministischer endlicher Automat} besteht aus endlichen Mengen von Zuständen, Eingabesymbolen und einer Übergangsfunktion.
Er entscheidet ob eine endliche Eingabe gültig ist.
\subsection*{Reguläre Ausdrücke}
\emph{Reguläre Ausdrücke} beschreiben \emph{reguläre Sprachen}.
Dies sind genau die Sprachen, die nach dem \emph{Satz von Kleene} von einem DEA aktzeptiert werden.
\subsection*{Nichtdeterministische Automaten}
Zustandsübergänge sind nichtdeterministisch.
Jeder NEA besitzt einen äquivalenten DEA.
Gebildet mit \emph{Potenzmengenkostruktion}.
\subsubsection*{$\epsilon$-Übergänge}
Jeder NEA mit $\epsilon$-Übergängen besitzt einen äquivalenten NEA ohne $\epsilon$-Übergänge, der nicht mehr Zustände benötigt.
\subsection*{Pumping-Lemma für reguläre Sprachen}
Sei $L$ reguläre Sprache.
Dann $\exists n \in \N \forall w \in L : |w| > n \implies w=uvx$ mit $|uv| \leq n, v \neq \epsilon$ und $\forall i \in \N_0 : uv^ix \in L$.
\subsection*{Äquivalenzklassenautomat}
Nicht erreichbare Zustände in $Q$ sind \emph{überflüssig}.
Diese sind in $\mathcal{O}(|Q|\cdot|\Sigma|)$ bestimmbar.
Ein Automat ohne überflüssige Zustände ist nicht zwingend minimal.
$p, q \in Q$ sind \emph{äquivalent} ($p \equiv q$), wenn $\forall w \in \Sigma^* : \delta(p,w) \in F \iff \delta(q,w) \in F$.
\section*{Entscheidbarkeit}
Eine Sprache $L \subseteq \Sigma^*$ ist \emph{rekursiv / entscheidbar}, wenn es eine Turing-Maschine gibt, die auf allen Eingaben hält und $w \in \L$ aktzeptiert gdw. $w \in L$.
\spacing
Eine Sprache $L \subseteq \Sigma^*$ ist \emph{rekursiv-aufzählbar / semi-entscheidbar}, wenn es eine TM gibt, die $w \in L$ aktzeptiert. Ihr Verhalten für $w \neq L$ ist undefiniert.
\spacing
Eine Funktion $f : \Sigma^* \to \Gamma^*$ ist \emph{(Turing)-berechenbar / totalrekursiv}, wenn es eine TM gibt, die für $w \in \Sigma^*$ das Wort $f(w) \in \Gamma^*$ ausgibt.
\spacing
Eine Sprache $L \subseteq \Sigma^*$ ist \emph{entscheidbar} gdw. ihre \emph{charakteristische Funktion} berechenbar ist.
\subsection*{Church'sche These}
Die Menge der Turing-berechenbaren Funktionen ist genau die Menge der im intuitiven Sinne überhaupt berechenbaren Funktionen.
\subsection*{Universelle Turing-Maschinen}
Sei $\mathcal{M} := (Q,\Sigma,\Gamma,\delta,s,F)$ eine Turing-Maschine.
Ihre \emph{Gödelnummer} $\langle M \rangle$ ist definiert als:
\spacing
$\mathcal{M}$ wird durch $111\text{code}_1 11\text{code}_2 11 \dots 11\text{code}_z 111$ kodiert, $\text{code}_i$ stellt $z$ Funktionswerte von $\delta$ dar:
\spacing
Kodiere $\delta(q_i,a_j) = (q_r,a_s,d_t)$ mit $0^i10^j10^r10^s10^t$ wobei $d_t \in \{d_1,d_2,d_3\}$ für $L$, $R$ bzw. $N$ steht.
\spacing
\emph{Universelle Turing-Maschine} aktzeptiert $(\langle \mathcal{M} \rangle, w)$ und simuliert $\mathcal{M}$ auf $w$.
\subsubsection*{Diagonalsprache}
$T_w$ ist TM mit Gödelnummer $w \in \{0,1\}^*$.
Sei $w_i \in \{0,1\}^*$ für $i = 0,1\dots$.
\spacing
Die \emph{Diagonalsprache} ist definiert durch:
$L_d := \{ w_i | \mathcal{M}_i \text{ aktzeptiert } w_i \text{ nicht} \}$.
$L_d$ enthält Wörter $w_i$ die sich als Gödelnummer interpretiert nicht selbst aktzeptieren.
\spacing
$L_d$ und $L_d^c$ sind nicht entscheidbar.
\subsubsection*{Halteproblem}
\[ \mathcal{H} := \{ wv | T_w \text{ hält auf Eingabe } v \} \]
$\mathcal{H}$ ist nicht entscheidbar.
\subsubsection*{Universelle Sprache}
\[ L_u := \{ v \in L(T_w) \} \]
d.h. die Menge der Wörter $wv$ s.d. $T_w$ für Eingabe $v$ hält und diese aktzeptiert.
$L_u$ ist nicht entscheidbar aber semi-entscheidbar.
\subsubsection*{Satz von Rice}
Sei $R$ die Menge aller von TM berechenbaren Funktionen und $S \subseteq R$ nicht trivial. Dann:
\vspace*{-4mm}
\[ L(S) := \{ \langle\mathcal{M}\rangle | \mathcal{M} \text{ berechnet Funktion aus } S \} \]
$L(s)$ ist nicht entscheidbar.
\subsection*{(Semi-)entscheidbare Sprachen}
Entscheidbare Sprachen sind abgeschlossen unter Komplementbildung, Schnitt und Vereinigung.
\spacing
Semi-entscheidbare Sprachen sind abgeschlossen unter Schnitt und Vereinigung.
\section*{Komplexitätsklassen}
Sind nichtdeterministische TM wesentlich effizienter als deterministische TM? $\P \neq \NP$?
\subsection*{Nichtdeterministische Turing-Maschinen}
Übergangsfunktion $\delta$ bietet Wahlmöglichkeiten und $\epsilon$-Übergänge vergleichbar mit NEAs.
\subsection*{$\NP$-vollständige Probleme}
$\P \subseteq \NP$ trivial, $\P \neq \NP$ d.h. $\P \subset \NP$ vermutet.
\spacing
Eine \emph{polynomiale Transformation} von $L_1 \subseteq \Sigma_1^*$ nach $L_2 \subseteq \Sigma_2^*$ ist $f : \Sigma_1^* \to \Sigma_2^*$ s.d. eine DTM mit polynomialer Laufzeit existiert, die $f$ berechnet und $\forall x \in \Sigma_1^* : x \in L_1 \iff f(x) \in L_2$.
Geschrieben: $L_1 \propto L_2$.
\subsubsection*{$\NP$-Vollständigkeit}
Eine Sprache $L$ ist \emph{$\NP$-vollständig}, wenn $L \in \NP$ und $\forall L' \in \NP : L' \propto L$.
\subsubsection*{Erfüllbarkeitsproblem (SAT)}
Prüfe ob Belegungen von booleschen Variablen existiert s.d. gegebene Klauseln erfüllt werden.
\spacing
\emph{SAT} ist $\NP$-vollständig. Insb. ist \emph{3SAT} für Klauseln mit genau drei Literalen $\NP$-vollständig.
\subsubsection*{Erfüllbarkeitsproblem (Max2SAT)}
Prüfe ob Belegung ex. s.d. mind. $K$ Klauseln mit jeweils genau zwei Literalen erfüllt werden.
\emph{Max2SAT} ist $\NP$-vollständig.
\subsubsection*{Cliquen in Graphen (CLIQUE)}
Prüfe ob Clique der Größe mind. $K$ existiert.
\emph{CLIQUE} ist $\NP$-vollständig.
\subsubsection*{Graphenfärbung (COLOR)}
Prüfe ob Knotenfärbung mit max. $K$ Farben ex.
\emph{3COLOR} ist $\NP$-vollständig.
\subsubsection*{EXACT COVER}
Sei $X$ endl. Menge und $\mathcal{S}$ Familie von Teilmengen.
Prüfe ob $\mathcal{S}' \subseteq \mathcal{S}$ ex. s.d. $\forall a \in X \exists! A \in \mathcal{S}' : a \in A$.
\emph{EXACT COVER} ist $\NP$-vollständig.
\subsubsection*{SUBSET SUM}
Sei $M$ endl. Menge, $w : M \to \N_0$ und $K \in \N_0$.
Prüfe ob $M' \subseteq M$ ex. s.d. $\sum_{a \in M'} w(a) = K$.
\emph{SUBSET SUM} ist $\NP$-vollständig.
\subsubsection*{PARTITION}
Sei $M$ endl. Menge und $w : M \to \N_0$.
Prüfe ob $M' \subseteq M$ ex. s.d. $\textstyle\sum\limits_{a \in M'} w(a) = \textstyle\sum\limits_{a \in M \setminus M'} w(a)$.
\emph{PARTITION} ist $\NP$-vollständig.
\subsubsection*{KNAPSACK}
Sei $M$ endl. Menge, $w : M \to \N_0$ Gewichtsfkt., $c : M \to \N_0$ Kostenfkt. und $W,C \in \N_0$.
Prüfe ob $M' \subseteq M$ existiert s.d. $\sum_{a \in M'} w(a) \leq W$ und $\sum_{a \in M'} c(a) \geq C$.
\emph{KNAPSACK} ist $\NP$-vollständig.
\subsection*{Suchprobleme}
\emph{Suchproblem} $\Pi$ ist geg. mit Menge von Beispielen $D_\Pi$ und für $I \in D_\Pi$ Menge $S_\Pi(I)$ aller Lsg. von $I$.
Die Lösung eines Suchproblems ist die Angabe von $S_\Pi(I)$ für $I \in D_\Pi$ mit $S_\Pi(I) \neq \emptyset$ falls möglich.
\spacing
Beispiele sind Bestimmung einer optimalen Tour in Graph (TSP) oder eines Hamilton-Kreises.
\subsection*{Aufzählungsprobleme}
\emph{Aufzählungsproblem} $\Pi$ ist geg. mit Menge von Beispielen $D_\Pi$ und für $I \in D_\Pi$ Menge $S_\Pi(I)$ aller Lsg.
Lösung eines Aufzählungsproblems ist $|S_\Pi(I)|$.
\spacing
z.B. wie viele Hamilton-Kreise gibt es?
\subsubsection*{$\NP$-Schwere}
Ein Suchproblem $\Pi$ ist \emph{$\NP$-schwer}, wenn $\NP$-vollständige Sprache $L$ ex. s.d. $L \propto_T \Pi$.
$\NP$-schweres Problem ist nicht zwingend in $\NP$.
Ein bel. Problem ist $\NP$-schwer, wenn es mind. so schwer ist, wie alle $\NP$-vollständigen Probleme.
\spacing
Die Klasse der $\NP$-schweren Probleme ist bzgl. Komplementbildung abgeschlossen.
\subsection*{INTEGER PROGRAMMING}
Sei $a_{ij}, b_i, c_j, b \in \Z_0$ für $1 \leq i \leq m$ und $1 \leq j \leq n$.
Prüfe ob $x_i, \dots, x_n \in \N_0$ ex. s.d. $\sum_{j=1}^n c_j \cdot x_j = B$ und $\forall 1 \leq i \leq m : \sum_{j=1}^n a_{ij} \cdot x_j \leq b_j$ (d.h. $A \cdot \vec{x} \leq \vec{b}$).
\emph{INTEGER PROGRAMMING} ist $\NP$-schwer.
\section*{Chomsky-Hierarchie}
\begin{description}[leftmargin=!,labelwidth=8mm]
\item[Typ 0] Rekursiv aufzählbar, Turing-Maschine
\item[Typ 1] Kontextsensitiv, nichtdet. TM
\item[Typ 2] Kontextfrei, nichtdet. Kellerautomat
\item[Typ 3] Regulär, Endlicher Automat (DEA, NEA)
\end{description}
\subsection*{Chomsky-Normalform}
|
