\renewcommand{\P}{\mathcal{P}}
\newcommand{\NP}{\mathcal{NP}}
\newcommand{\NPC}{\mathcal{NPC}}
\newcommand{\NPI}{\mathcal{NPI}}

\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$.

\emph{Äquivalenzklassenautomat} $\mathcal{A}^\equiv$ zu $\mathcal{A}$ ist minimal.

\section*{Turing-Maschinen}

\emph{Deterministische Turing-Maschine} ist def. als:

\vspace*{-2mm}
\[ \mathcal{M} := (Q,\Sigma,\textvisiblespace,\Gamma,s,\delta,F) \]

Hier sind $Q$ Zustandsmenge, $\Sigma$ Eingabealphabet, $\textvisiblespace \notin \Sigma$ Blanksymbol, $\Sigma \cup \{\textvisiblespace\} \subseteq \Gamma$ Bandalphabet, $s \in Q$ Startzustand, $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L,R,N\}$ Übergangsfunktion und $F \subseteq Q$ Endzustände.

Alle Mengen sind in einer $(D)TM$ endlich.

\subsection*{Church'sche These}

Die Menge der Turing-berechenbaren Funktionen ist genau die Menge der im intuitiven Sinne überhaupt berechenbaren Funktionen.

\subsection*{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 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*{Nichtdeterministische Turing-Maschinen}

Übergangsfunktion $\delta$ bietet Wahlmöglichkeiten und $\epsilon$-Übergänge vergleichbar mit NEAs.

\subsection*{Orakel-Turing-Maschinen}

Deterministische TM mit Orakelband zu Orakel $G$ sowie Fragezustand $q_f$ und Antwortzustand $q_a$.

\spacing

Wird $q_f$ angenommen wenn Kopf sich auf Pos. $i$ des Orakelbandes befindet, ergibt sich Fehler, falls Wort $y$ auf Pos. $1$ bis $i$ nicht in $\Sigma^*$ ist. Sonst wird Orakelband mit $G(y)$ überschrieben, Kopf springt auf Pos. $1$ zurück und Folgezustand ist $q_a$.

\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*{Post'sches Korrespondenzproblem}

Sei $K := ((x_1,y_1),\dots,(x_n,y_n))$ endliche Folge von Wortpaaren über $\Sigma$ mit $x_i, y_i \neq \epsilon$.

\spacing

Gesucht ist Indizesfolge $i_1,\dots,i_j \in \{1,\dots,n\}$ s.d. $x_{i_1}\dots x_{i_k} = y_{i_1}\dots y_{i_k}$ gilt.

\spacing

Das PKP ist nicht entscheidbar.

\subsubsection*{Universelle Sprache}

\[ L_u := \{ wv | v \in L(T_w) \} \]

d.h. die Menge der Wörter $wv$ s.d. $T_w$ für Eingabe $v$ hält und $v$ 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*{$\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*{Mengenabdeckung (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*{Teilmengensumme (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*{Mengenpartitionierung (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*{Rucksackproblem (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*{Komplementsprachen}

$\NPC$ ist Klasse der $\NP$-vollständigen Sprachen.

$\NPI := \NP \setminus (\P \cup \NPC)$ enthält nicht-$\NP$-vollständige Sprachen in $\NP$.

$co-\P$: $\Sigma^* \setminus L$ für $L \subseteq \Sigma^*$ und $L \in \P$.

$co-\NP$: $\Sigma^* \setminus L$ für $L \subseteq \Sigma^*$ und $L \in \NP$.

\subsubsection*{Graphenisomorphie}

Prüfen von Graphen auf Isomorphie liegt in $\NP$ und $co-\NP$, ist Kandidat in $\NPI$ zu liegen.

\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?

\subsection*{Turing-Reduktion}

Eine \emph{Turing-Reduktion} $\propto_T$ von Relationen $R \propto_T R'$ über $\Sigma^*$ ist eine Orakel-Turing-Maschine $\mathcal{M}$ deren Orakel $R'$ realisiert und in polynomialer Zeit die $R$ realisierende Funktion berechnet.

\subsection*{$\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.

\subsubsection*{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.

\subsection*{Raumkomplexität}

Die Klasse der mit polynomialen Speicherplatz lösbaren Probleme ist $\mathcal{PSPACE}$.

\spacing

Es gilt: $\P \subseteq \NP \subseteq \mathcal{PSPACE}$

\subsection*{Pseudopolynomiale Algorithmen}

Ein Algorithmus ist \emph{pseudopolynomial}, wenn er bei Unärkodierung polynomial in Eingabelänge ist.

\spacing

Für KNAPSACK gibt es einen pseudopolynomialen Lösungsalgorithmus.

Falls $\P \neq \NP$ gilt, gibt es für TSP keinen pseudopolynomialen Lösungsalgorithmus.

TSP ist \emph{stark $\NP$-vollständig}.

\subsection*{Approximationsalgorithmen}

Polynomiale Algorithmen für $\NP$-vollständige Optimierungsprobleme, deren Ausgabe nicht optimal aber beweisbar gut ist.

\spacing

Dazu wird die Güte einer worst-case Lösung $\mathcal{A}(I)$ von Algorithmus $\mathcal{A}$ für $\Pi$ mit der Optimallösung $OPT(I)$ für $I \in D_\Pi$ verglichen.

\subsubsection*{Absolute Approximationsalgorithmen}

Sei $\Pi$ Optimierungsproblem.

Polynomialer Algorithmus $\mathcal{A}$ ist \emph{Approximationsalgorithmus mit Differenzengarantie} oder \emph{absoluter Approximationsalgorithmus}, wenn für $K \in \N_0$ gilt:

\vspace*{-2mm}
\[ \forall I \in D_\Pi : | OPT(I) - A(I) | \leq K \]

Für $\NP$-schweres KNAPSACK gibt es vermutlich keinen absoluten Approximationsalgorithmus.

Falls $\P \neq \NP$ gibt es für KNAPSACK, CLIQUE definitiv keinen absoluten Approximationsalgo.

\subsubsection*{Relative Approximationsalgorithmen}

Sei $\Pi$ Optimierungsproblem und $\mathcal{R_A}$:

\vspace*{-4mm}
\[ \mathcal{R_A}(I) := \begin{cases} \frac{\mathcal{A}(I)}{OPT(I)} & \Pi \text{ ist Minimierungsproblem} \\ \frac{OPT(I)}{\mathcal{A}(I)} & \Pi \text{ ist Maximierungsproblem} \end{cases} \]

Polynomialer Algorithmus $\mathcal{A}$ ist \emph{Approximationsalgo. mit relativer Gütegarantie}, falls für $K \in \N$ gilt:

\vspace*{-2mm}
\[ \forall I \in D_\Pi : \mathcal{R_A}(I) \leq K \]

$\mathcal{A}$ ist \emph{$\epsilon$-approximativ}, wenn:

\vspace*{-2mm}
\[ \forall I \in D_\Pi : \mathcal{R_A}(I) \leq 1 + \epsilon \]

\subsubsection*{Greedy-Algorithmus für KNAPSACK}

Sei $w : M \to \N_0$ Gewichtsfunktion, $c : M \to \N_0$ Kostenfunktion und $W \in \N_0$.

\spacing

Definiere Gewichtsdichten $p_i := \frac{c_i}{w_i}$.

Sortiere $p_1 \geq \dots \geq p_n$ in $\mathcal{O}(n \log n)$.

Für $i \in \{1,\dots,n\}$ setze $x_i := \left\lfloor \frac{W}{w_i} \right\rfloor, W := W - \left\lfloor \frac{W}{w_i} \right\rfloor \cdot w_i$

\spacing

Dieser Greedy-Algorithmus $\mathcal{A}$ läuft in $\mathcal{O}(n \log n)$.

\spacing

Für $\mathcal{A}$ gilt: $\forall I \in D_\text{KNAPSACK} : \mathcal{R_A}(I) \leq 2$

\vfill\null
\columnbreak

\section*{Chomsky-Hierarchie}

\begin{description}[leftmargin=!,labelwidth=8mm]
	\item[Typ 3]
	\begin{description}[leftmargin=!,labelwidth=22mm]
		\item[Sprachklasse] Regulär
		\item[Rechenmodell] Endlicher Automat
		\item[Wortproblem]  entscheidbar
	\end{description}
	\item[Typ 2]
	\begin{description}[leftmargin=!,labelwidth=22mm]
		\item[Sprachklasse] Kontextfrei
		\item[Rechenmodell] ndet. Kellerautomat
		\item[Wortproblem]  entscheidbar
	\end{description}
	\item[Typ 1]
	\begin{description}[leftmargin=!,labelwidth=22mm]
		\item[Sprachklasse] Kontextsensitiv
		\item[Rechenmodell] ndet. TM in $\mathcal{NTAPE}$
		\item[Wortproblem]  entscheidbar
	\end{description}
	\item[Typ 0]
	\begin{description}[leftmargin=!,labelwidth=22mm]
		\item[Sprachklasse] Rekursiv aufzählbar
		\item[Rechenmodell] bel. Turing-Maschine
		\item[Wortproblem]  nicht entscheidbar
	\end{description}
\end{description}

Es gilt $\mathcal{L}_3 \subset \mathcal{L}_2 \subset \mathcal{L}_1 \subset \mathcal{L}_0$.

\subsection*{Kontextfreie Sprachen}

Die Klasse kontextfreier Sprachen ist abgeschlossen ggü. Vereinigung, Konkatenation und Kleenschem Abschluss. Sie ist nicht abgeschlossen ggü. Komplementbildung und Durchschnitt.

\spacing

Für eine kontextfreie $G$ kann in polynomialer Zeit entschieden werden, ob $L(G)$ endlich ist.

\subsubsection*{Chomsky-Normalform}

Eine kontextfreie Grammatik ist in \emph{Chomsky-Normalform}, wenn alle Regeln von Form $A \to BC$ oder $A \to a$ mit $A,B,C \in V$ und $a \in \Sigma$ sind.

\spacing

Jede nicht $\epsilon$ erzeugende kontextfreie Grammatik ist in Chomsky-Normalform überführbar:

\begin{enumerate}
\item Regeln ergeben nur Variablen oder genau ein $a \in \Sigma$. Mit Hilfsvariablen erreichbar.
\item Alle Regeln haben Länge $\leq 2$
\item Elimination von Regeln $A \to \epsilon$
\item Ersetzen von Kettenregeln (Kreise, DFS)
\end{enumerate}

\subsubsection*{Cocke-Younger-Kasami Algorithmus}

Entscheidet für kontextfreie Grammatik $G$ in Chomsky-Normalform und Wort $w \in \Sigma^*$ das Wortproblem in Zeit $\mathcal{O}(|R|\cdot |w|^3)$ wobei $|R|$ Anzahl der Regeln in $G$ ist.

\subsubsection*{Pumping-Lemma (kontextfreie Sprachen)}

Für kontextfreie Sprachen $L$ gilt: $\exists n \in \N \forall z \in L :$

\spacing

$|z| \geq n \implies \exists u,v,w,x,y \in L : z=uvwxy$ s.d. $|vx| \geq 1, |vwx| \leq n$ und $\forall i \in \N : uv^iwx^iy \in L$

\subsubsection*{Greibach-Normalform}

Eine kontextfreie Grammatik ist in \emph{Greibach-Normalform}, wenn alle Regeln von Form $A \to a\alpha$ für $A \in V, a \in \Sigma$ und $\alpha \in V^*$ sind.

\spacing

Jede nicht $\epsilon$ erzeugende kontextfreie Grammatik ist in Greibach-Normalform überführbar.

\spacing

Für jede Grammatik $G$ in Greibach-Normalform kann ein Kellerautomat (PDA) gebildet werden, der $L(G)$ mit leerem Stack aktzeptiert.

\subsubsection*{Unentscheidbare Probleme}

Seien $G, G_1, G_2$ kontextfreie Grammatiken.

Die folgenden Probleme sind nicht entscheidbar:

\begin{enumerate}
\item Gilt $L(G_1) \cap L(G_2) = \emptyset$
\item $\forall w \in L(G) : $ Syntaxbaum von $w$ ist eindeutig
\item Ist $(L(G))^c$ kontextfrei
\item Ist $L(G_1) \cap L(G_2)$ kontextfrei
\item Gilt $L(G) = \Sigma^*$
\item Gilt $L(G_1) = L(G_2)$
\item Gilt $L_(G_1) \subseteq L(G_2)$
\end{enumerate}