\documentclass[a4]{article}
\usepackage[german]{babel}
\usepackage{amsmath, amssymb}
\usepackage{calc}
\usepackage{a4wide}

\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\setlength{\topmargin}{0pt}
\setlength{\textwidth}{430pt}

\newcommand{\entrylabel}[1]{\mbox{\textbf{\textsf{#1:}}}\hfil}
\newenvironment{entry}
  {\begin{list}{}
    {\renewcommand{\makelabel}{\entrylabel}
	 \setlength{\topsep}{0pt}
     \setlength{\labelwidth}{20pt}
     \setlength{\leftmargin}{\labelwidth + \labelsep}
    }
  }
{\end{list}}

\newcommand{\typelabel}[1]{\mbox{\textbf{- #1:}}}
\newenvironment{type}
  {\begin{list}{}
    {\renewcommand{\makelabel}{\typelabel}
	 \setlength{\topsep}{0pt}
     \setlength{\labelwidth}{5pt}
	 \setlength{\leftmargin}{\labelsep+15pt}
    }
  }
{\end{list}}

\begin{document}
%=====================================
\section{Fragen zu Theoretischer Informatik 1}
%=====================================

%----------------------------------
\subsection{Laufzeitanalyse}
%----------------------------------
\begin{type}
\item[Lauzeitverhalten] Existiert der Limes der Folge $\frac{f(n)}{g(n)}$ mit
$\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}=c$, dann gilt:
\begin{align*}
c=0 & \Rightarrow f=o(g) \\
0<c<\infty & \Rightarrow f=\Theta(g)\\
c=\infty & \Rightarrow f=w(g) \\
0 \leq c < \infty & \Rightarrow f=O(g) \\
0 < c \leq \infty & \Rightarrow f=\Omega (g)
\end{align*}

\item[Mastertheorem (formal)]
Es sei $T(1)=c$, $T(n)=a \cdot T(\frac{n}{b})+f(n)$ mit $n=b^{x \in \mathbb{Z}}$,
$b \in \mathbb{N}_{>1}$, $a \geq 1$, $c>0$ und $f:\mathbb{N} \rightarrow \mathbb{R}$,
$\epsilon > 0$:
\begin{align}
f(n)=O(n^{(\log_b a)-\epsilon}) & \Rightarrow T(n)= \Theta(n^{\log_b a}) \notag \\
f(n)=\Theta (n^{\log_b a}) & \Rightarrow T(n)= \Theta(n^{\log_b a } \cdot \log_b n) \notag \\
f(n)=\Omega(n^{(\log_b a)+\epsilon}) , a \cdot f(\frac{n}{b}) \leq \alpha f(n), \a	lpha >1  &
\Rightarrow T(n)=\Theta (f(n)) \notag
\end{align}
\end{type}

%----------------------------------
\subsection{Elementare Datenstrukturen}
%----------------------------------
\begin{type}

\item[B"aume allgemein]
%----------------------------------
"`Ein wesentliches Hilfsmittel zur Strukurierung von Daten"¡.
Ein Baum $T=(V,E)$ mit $E \subseteq V \times V - \left\{(i,i)|i \in V\right\}$ besitzt einen Knoten ohne
Vater ( \textbf{Wurzel} ). Jeder Knoten hat genau einen Vater und maximal $k$ Kinder, wenn es sich
um einen $k$-"aren Baum handelt. Die \textbf{Tiefe} eines Baumes ist die L"ange des l"angsten Weges
von von $r$ nach $v$ (also die maximale Anzahl an Kanten auf dem Weg). Die \textbf{H"ohe} eines 
Baumes ist die L"ange des l"angsten Weges von von $v$ zu einem Blatt. $T$ hei"st geordnet, wenn
das $x-te$ Kind seines Vaters zu erkennen ist.
\begin{entry}
\item[Operationen] Wurzel(), Vater($v$), Kinder($v$), Tiefe($V$), H"ohe($v$), Baum($v,T_1, \ldots ,T_m$), Suche($x$)
\item[Implementierungen] Array (Vaterrepr"asentation), Adjazenzliste (Zeiger auf (sortierte) Kinder - gut bei Graphen!),
Bin"arbaum (Zeiger auf linkes bzw. rechtes Kind - gut bei Bin"aren B"aumen), Kind-Geschwister (Zeiger auf erstes
(linkestes) Kind und auf n"achsten Geschwister-Knoten - gut bei allgemeinen B"aumen)
\item[Durchlaufstrategien] Postorder, Preorder, Inorder (rekursiv oder mit Stack) in Zeit $O(n)$
\end{entry}

\item[Topologisches Sortieren]
%----------------------------------
"`Datenstruktur "ahnlich der Queue, nur m"ochte man nicht das "alteste, sondern das Element mit der h"ochsten
Priorit"at entfernen¡"
\begin{entry}
\item[Operationen] insert(Priorit"at), delete\_max(), change\_priority(wo, neue Priorit"at), remove(wo)
\end{entry}

\item[Heaps]
%----------------------------------
\begin{entry}
\item[Struktur] Bei einem Baum T der Tiefe $t$ haben alle Knoten der Tiefe h"ochstens $t-2$ genau 2 Kinder. Wenn ein Knoten $v$
der Tiefe $t-1$ weniger als 2 Kinder hat, so haben alle Knoten rechts von $v$ kein Kind. Wenn $v$ genau ein Kind hat,
so handelt es sich dabei um ein linkes Kind.
\item[Heap-Ordnung] Baum $T$ (geordnet und bin"ar), wobei jeder Knoten eine Priorit"at $p(v)$ besitzt und f"ur
jedes Kind $w$ von $v$ gilt: $p(v) \geq p(w)$
\item[Implementierung] Array, bei dem $H[1]=p(r)$ die Wurzel ist und wenn $H[i]$ die Priorit"at von $v$ speichert,
dann speichert $H[2 \cdot i]=p(v_L)$ und $H[2 \cdot i +1]=p(v_R)$. Beim Einf"ugen von Knoten mu"s ein \textbf{repair\_up}
(nach oben schieben eines Knoten, bis der Vater gr"o"ser ist als der Knoten) und beim Entfernen ein \textbf{repair\_down}
(Vertauschen der Wurzel mit dem letzten Kind, dann nach unten sinken lassen, indem man immer mit dem gr"o"sten
Kind vertauscht) durchgef"uhrt werden.
\item[Aufwand] insert, delete\_max, change\_priority, remove in $O(\log_2 n)$, Build-heap in $O(n)$ und
Heapsort in $O(n \log_2 n)$
\item[Anwendung] Im Disjkstra-Algorithmus
\end{entry}

\end{type}

%----------------------------------
\subsection{Sortieren}
%----------------------------------
\begin{type}

\item[Bubblesort]
%----------------------------------
Erwartete Laufzeit / best- und worst-case $\Theta (n^2)$, da alle
Permutationen gleichwahrscheinlich. Gut f"ur fast sortierte Eingaben
(Elemente, die bereits in der N"ahe Ihrer endg"ultigen Position stehen). Auch
gut bei wenig Zahlen.

\item[Selectionsort]
%----------------------------------
Laufzeit wie Bubblesort - gut bei kurzen Arrays mit langen Datens"atzen

\item[Insertionsort]
%----------------------------------
Laufzeit wie Bubblesort - gut bei kleinen Datenmengen und fast sortierte Eingabefolgen

\item[Quicksort]
%----------------------------------
Wichtig ist die Funktion \texttt{partition(p, links, rechts)} und vor allem die Pivot-Wahl-Strategie. \\
Die Invariante bei \texttt{partition} ist zu Anfang \textit{"`Alle Zellen links von $l$ (einschlie"slich $l$) besitzen nur
Zahlen $\leq \alpha$, alle Zellen rechts von $r$ (einschlie"slich $r$)
besitzen nur Zahlen $\geq \alpha$."´}
Die Laufzeit ist im worst-case $\Theta (n \log_2 n)$ und im best-case $\Theta (n \log_2 n)$ \\
Verbessert werden kann die Laufzeit durch die Wahlstrategie f"ur das Pivot-Element z.B. durch Wahl des Median aus
$A[1]$, $A[\frac{n}{2}]$ und $A[n]$ oder durch Zufallswahl (in diesem Fall ist die erwartete Laufzeit $\Theta (n \log n)$
f"ur jede Eingabe). Die Zufallszahl kann z.B. mittles linearer Kongruenzen gew"ahlt werden: $x_{i+1} = (a \cdot x_i + b)
\mod m$, wobei $m$ prim sein sollte. \\
Weitere Verbesserungen kann bringen: Beseitigung der Rekursion und Herunterdr"ucken der Rekursionstiefe von
$n$ auf $n \log n$ (Implementierung mittels Stack, wobei immer das l"angere Teilproblem auf den Stack gelegt wird 
$\rightarrow$ die Stackh"ohe kann $\log n$ nicht "uberschreiten) und Sonderbehandlung kleiner Teilarrays (Teilprobleme
$\leq 25$ werden mittels Insertion-Sort sortiert). \\
Auch das Auswahlproblem kann so einfach implementiert werden, so da"s es in $O(n)$ gel"ost werden kann. \\
Offene Fragen:
\begin{itemize}
\item Ist QS ein $in-place$-Algorithmus?
\item Gibt es einen Zusammenhang zwischen QS und Bin"arbaumsuche?
\item Mergesort hat bessere Konstante gegn"uber QS, daf"ur aber doppelter Speicherplatz!
\end{itemize}

\item[Mergesort] 
%----------------------------------
Besonders geeignet f"ur \textbf{externes Sortieren} (Daten auf Platte oder Band). Die Eingabefolge wird in zwei
gleich gro"se Folgen zerlegt, die dann sortiert und wieder \textbf{zusammengemischt} werden. \\
Die best-, worse- und average-case Laufzeiten sind alle gleich $\Theta (n \log n)$, da die Rekursionsgleichung
$M(n)=2M(\frac{n}{2})+c \cdot n$ ist. Der Rekursionsbauom wird in Postorderreihenfolge abgearbeitet, da zuerst die
Teilprobleme gel"ost werden und dann die L"osungen zusammengesetzt werden. Ein gro"ser Nachteil im Vergleich
zu Quicksort ist die Verwendung eines zus"atzlichen Arrays zum Mischen der Daten.

\item[Ausgeglichenes Mehrwegemischen] 
%----------------------------------
Es stehen $2b$ B"ander zur Verf"ugung, wobei $m$ der $n$ Daten simultan im Hauptspeicher gehalten werden
k"onnen. Beim \textit{Vorsortieren} werden alle $n$ Daten in Bl"ocken der L"ange $n/m$ sortiert und auf die B"ander
$i \mod b$ zur"uckgeschrieben. Dann werden die Daten durch \textit{Minimumbestimmung} sortiert auf Band $b$ sortiert 
gespeichert, und zwar ein Block nach dem anderen. Zuletzt enthalten die B"ander $b,b+1, \ldots , 2b-1$ sortierte Bl"ocke
der L"ange $m$, die dann in er n"achsten Phase zu den neuen Eingabeb"andern werden. \\
\textbf{Laufzeit}: Bei $n$ Daten, $2b$ B"andern und Hauptspeicherkapazit"at $m$ ben"otigt das Vorsortieren
$\left\lceil \log_b(n/m)\right\rceil$ Phasen, es wird also auf jede Zahl nie mehr als $1+\left\lceil \log_b (n/m) \right\rceil$-mal
zugegriffen.

\item[Laufzeit Vergleichs-orientierter Sortierverfahren - Vergleichsbaum]
%----------------------------------
F"ur $n$ Eingaben $x_1 \ldots x_n$ ist ein bin"arer Baum, so da"s jedem inneren Knoten ein
Vergleich der Form $x_i < x_j$ zugeordnet ist. F"ur eine Eingabe $(a_1 \ldots a_n)$ wird der Baum von der Wurzel
an durchlaufen. Der Vergleichsbaum hei"st sortiert, wenn alle Eingaben, die dasselbe Blatt erreichen denselben 
Ordnungstyp besitzen $\rightarrow$ Sortierbaum. Ein \textit{Ordnungtyp} ist die Permutation $\pi$, die die Eingabe $a$
sortiert. \\
Da ein Sortierbaum mindestens $n!$ viele Bl"atter besitzt, hat er also mindestens eine Tiefe von 
$\log_2(n!) \geq \frac{n}{2} \log_2 (\frac{n}{2})$

\item[Distribution Counting]
%----------------------------------
Die zu sortierenden Zahlen d"urfen nur aus dem Intervall $[0,m-1]$ sein. in dem Array $Zaehle$ wird f"ur jede Zahl
die Anzahl derer Vorkommen festgehalten, soda"s die Lauftzeit mit $=(n+m)$ sehr g"unstig ausf"allt. \\
DC ist nur sinnvoll f"ur $m=O(n \log_2 n)$.

\item[Radix-Exchange]
%----------------------------------
Die Zahlen werden in $b$-"arer Darstellung vorgehalten. Damit steigt der Programmieraufwand. \\
Zuerst werden die Zahlen in die $b$-"are Darstellung umgeformt. Dann findet eine \textit{Verteilungsphase}
statt, in der die Zahlen auf $b$ Queues verteilt werden (entsprechend der $i$-ten Ziffer). In der \textit{Sammelphase}
werden dann die Elemente der Queues wieder in A entleert. \\
Wichtig ist die Stabilit"at, damit bei gleichen hochwertigen Ziffern die restlichen Ziffern "uber die Sortierung entscheiden.
Die Laufzeit betr"agt $O((n+b)\cdot \log_b m)$, wobei man immer $b \leq n$  w"ahlen sollte. Radixsort versagt also
f"ur zu gro"se Zahlen.

\item[Fragen]

\begin{itemize}

\item Radixsort
%----------------------------------
\begin{itemize}
\item (Zahlen von $1 \ldots n^k$) - welche Basis? ($b=n$, da $\log_b n^k = k$)
\item Laufzeit?
\item Zahlen aus beschr"anktem Zahlenintervall
\item Beweis: LZ $O((n+b)\log_b m)$
\end{itemize}

\item Welche Algorithmen f"ur Zahlen $1\ldots\sqrt{n}$ ($\rightarrow$Distribution Counting) und $1 \ldots n^7$ ($\rightarrow$Radixsort)?
\item Insertion-Sort (Bin"ares einf"ugen; Warum $k$ Vergleiche?)

\item Quicksort
%----------------------------------
\begin{itemize}
\item Divide et impera
\item Implementierung von Quicksort nicht rekursiv ( - mit Stack; Was ist mit H"ohe des Stacks?)
\item Wie kann man die rek. Aufrufe beim QS optimieren? Gau"ssche Glockenkurve
\item Ist QS ein $in-place$-Algorithmus?
\item Erwartete Laufzeit?
\item Gibt es einen Zusammenhang zwischen QS und Bin"arbaumsuche?
\item Mergesort hat bessere Konstante gegn"uber QS, daf"ur aber doppelter Speicherplatz!
\end{itemize}

\item Untere Schranke f"ur Sortierung mit Vergleichen (Beweis)?
\item Externes Sortieren?
\item Nicht vergleichsorientierte Algorithmen?
\item Laufzeitanalyse von Mergesort
\item Batcher-Sort (LZ)
\end{itemize}

\end{type}

%----------------------------------
\subsection{W"orterbuchproblem}
%----------------------------------
Bei einer gegebenen Menge $S$ und einem Schl"ussel $x$ m"ochten wir folgende Mengenoperationen unterst"utzen:
\begin{entry}
\item[insert($x$)]  $S=S \cup \{ x \}$
\item[remove($x$)] $S=S- \{ x \}$
\item[lookup($x$)] finde heraus, ob $x \in S$ und greife gegebenenfalls auf den Datensatz von $x$ zu.
\item[select($x$)] bestimme den $k$-kleinsten Schl"ussel
\item[rang($x$)] bestimme den Rang von $x$, wobei rang($x$)=$k$ genau dann, wenn $x$ der $k$-kleinste Schl"ussel ist.
\item[interval($a,b$)] bestimme, in aufsteigender Reihenfolge, alle Schl"ussel $y \in S$ mit $a \leq y \leq b$.
\end{entry}
Ein \textbf{statisches W"orterbuch} besteht nur aus der Operation \textit{lookup} und kann z.B. mittels eines sortierten
Arrays oder einer sortierten Liste implementiert werden (lookup ben"otigt dann $O(n \log_2 n)$ Zeit). \\
Ein \textbf{(nicht geordnetes) W"orterbuch} besteht dabei nur aus den Operationen \textit{insert, remove, lookup}. Als
Datenstrukuren k"onnen folgende verwendet werden:

\begin{type}

\item[Bin"are Suchb"aume]
%----------------------------------
\begin{entry}
\item[Definition] Sei $T$ ein geordneter bin"arer Baum, so da"s jedem Knoten $v$ von $T$ ein Paar 
$daten(v)=(Schl"ussel(v),Info(v))$ zugeordnet sei. F"ur jeden Schl"usselwert $x$ in $T$ gibt es dann h"ochstens einen
Knoten $v$ mit $Schl"ussel(v)=x$ und f"ur jeden Knoten $v_{links}$ im linken Teilbaum von $v$ und jeden Knoten
$v_{rechts}$ im rechten Teilbaum von $v$ ist $Schl"ussel(v_{links})<Schl"ussel(v)<Schl"ussel(v_{rechts})$.
\item[Laufzeit] Die erwartete Laufzeit ist logarithmisch (da jede Permutation der Schl"ussel gleichwahrscheinlich ist, und
somit gilt $L(n)=\frac{1}{n} \sum _{x \in S} T(x) \Rightarrow
L^\ast (n)=n + \frac{1}{n} \sum _{k=1}^n ( L^\ast (k-1)+L^\ast (n-k) )$). Das erst eingef"ugte Element spielt
also eine "ahnliche Rolle wie das Pivotelement im Quicksort. Wir erhalten eine best-case Laufzeit f"ur tiefenbalancierte
B"aume, in denen sich die Tiefe um h"ochstens 1 unterscheidet. \\
Damit ist die worst-case Laufzeit von insert, remove und lookup $\Theta (Tiefe(T))$. Wenn $T$ $n$ Knoten hat, dann
ist bestenfalls Tiefe($T$)=$\lfloor \log_2 n \rfloor$ und schlechtestenfalls Tiefe($T$)=$n-1$. Die erwartete Laufzeit
einer erfolgreichen lookup-Operation in bin"aren Suchb"aumen von $n$ Schl"usseln ist $O(\log_2 n)$.
\end{entry}

\item[AVL-B"aume]
%----------------------------------
\begin{entry}
\item[Definition] Sei $T$ bin"arer Suchbaum, dann ist $T$ AVL-Baum, wenn f"ur jeden Knoten $v$ mit linkem Teilbaum $T_L(v)$
und rechtem Teilbaum $T_R(v)$ gilt: $|Tiefe(T_L(v))-Tiefe(T_R(v))| \leq 1|$. Dabei hei"st $b(v)=Tiefe(T_L(v))-Tiefe(T_R(v))$
der \textbf{Balance-Grad} von $v$ (im AVL-Baum stets $b(v) \in \{ -1,0,1 \}$) \\
Bei $n$ Knoten hat ein AVL-Baum h"ochstens die Tiefe $2 \log_2 n$.
\item[Operationen] Anstatt gleich ein \textit{remove} durchzuf"uhren, kann ein \textit{lazy-remove} durchgef"uhrt werden,
bei dem die gle"oschten Knoten lediglich markiert werden und erst gel"oscht werden, wenn mehr als 50 % aller Knoten
als gel"oscht markiert sind. \\
Bei einem \textit{insert} wird der Schl"ussel wie beim bin"aren Suchbaum nach Suche einfach eingef"ugt. Ist dann die
Balance-Eigenschaft verletzt, so f"uhren wir Rechts- bzw. Linksrotationen aus.
\item[Laufzeit] Die Operationen \textit{lookup} und \textit{insert} haben die worst-case Laufzeit $O(\log_2 n)$.
\end{entry}

\item[Splay-B"aume]
%----------------------------------
\begin{entry}
\item[Vorteile] Ben"otigen keine zus"atzrlichen Informationen, geringer Programmieraufwand, "`passen sich den Daten an"¡, 
amortisierte Laufzeit $O(n \log_2 n)$
\item[Nachteil] miserable worst-case Laufzeit $\Theta (n)$,
\item[Operationen] Die Splay-Operatione f"uhrt zuerst eine bin"are Suche nach $x$ durch, bringt $y$, mit entweder $y=x$
oder $y$ gr"o"ster Schl"ussel kleiner $x$, an die Wurzel. Alle Operationen lassen sich auf die Splay-Operation 
zur"uckf"uhren.
\item[Laufzeit] Wiederholte Anwendung der Splay-Operation f"uhrt dazu, da"s die Knoten des Suchpfades der Wurzel
fast um die H"alfte n"aher r"ucken ($\rightarrow$ \textbf{Suchpfadeigenschaft}). \\
Wenn $n$ Splay-Operationen in einem anf"anglich leeren Splay-Baum durchgef"uhrt werden, so betr"agt die worst-case
Laufzeit $O(n \log_2 n)$.
\end{entry}

\item[$(a,b)$-B"aume]
%----------------------------------
\begin{entry}
\item[Definition] $a,b \in \mathbb{N}$ mit $a \geq 2$ und $b \geq 2a-1$. Baum $T$ hat dann $(a,b)$-Eigenschaft, wenn
alle Bl"atter von $T$ die gleiche Tiefe besitzen, alle Knoten h"ochstens $b$ und mindestens $a$ Kinder haben (nur 
die Wurzel hat mindestens zwei Kinder). \\
Ein $(a,b)$-Baum hat $(a,b)$-Eigenschaft, wobei jeder Schl"ussel $S$ in genau einem Knoten gespeichert wird und jeder
Knoten seine Schl"ussel in aufsteigender Reihenfolge speichert. Jeder innere Knoten speichert dabei genau $k-1$
Schl"ussel, und jedes Blatt zwischen $a-1$ und $b-1$). Ein innerer Knoten $v$ mit Schl"usseln $x_1, \ldots , x_c$
speichert dann in dem $i$-ten Teilbaum ($2 \leq i \leq c$) Schl"ussel aus dem Intervall $(x_{i-1}, x_i)$, bzw. $(-\infty, x_1)$
und $(x_c, \infty)$.
\item[B-B"aume] $(a,b)$-B"aume mit $b=2a-1$ hei"sen B-B"aume. Sie sind besonders gut, wenn die Daten auf einem
Hintergrund-Speicher abgelegt sind, da h"ochstens $O(\log_a n)$ Knoten bei der Ausf"uhrung einer
W"orterbuch-Operation besucht werden.
\item[Operationen] Bei einem \textbf{insert} kann es vorkommen, da"s ein Knoten zuviele Schl"ussel bekommt.
In diesem Fall wird ein neuer Knoten $v$ mit $v_{links}$ Knoten $x_1, \ldots , x_{\lceil b/2 \rceil -1}$ und
$v_{rechts}$ Knoten $x_{\lceil b/2 \rceil +1}, \ldots , x_b$ ("`bottom-up"¡). \\
Beim "`top-down"¡ zerlegen wir alle Knoten auf dem Weg mit $b$ Kindern, was zu unn"otigen Tiefenerh"ohungen
f"uhren kann. \\
Bei \textbf{remove} kann es passieren, da"s ein Knoten zu wenig Schl"ussel hat. Dann versuchen wir von dem linken
oder rechten Geschwisterknoten (mit mindestens $a$ Schl"usseln) einen zu klauen. Wenn dies nicht geht, weil beider
Geschwisterknoten nur $a-1$ Schl"ussel haben, so veschmelzen wir den Knoten mit einem Geschwisterknoten, so da"s
ein neuer Knoten mit maximal $(a-1)+1+(a-2)=2a-2 \leq b-1$ Schl"usseln entsteht. Wenn jetzt ein Schl"ussel zu wenig im
Knoten bleibt, m"ussen wir die Prozedur rekursiv nach oben fortsetzen.
\item[Laufzeit] F"ur einen $(a,b)$-Baum gilt $\log_b(n)-1 < Tiefe(t) < \log_a (\frac{n-1}{2})+1$ \\
F"ur die \textit{lookup}- und \textit{insert} Operation ben"otigen wir damit $Tiefe(T)+1$ und
f"ur die \textit{remove}-Operation $4(Tiefe(T)+1)$ Speicherzugriffe.
\end{entry}

\item[Hashing]
%----------------------------------
Wenn die Menge $U$ von vorneherein bekannt ist und in den Hauptspeicher pa"st, so ist das W"orterbuchproblem
trivial und kann durch eine \textbf{Bitvektor-Datenstruktur} gel"ost werden (Array , da"s f"ur jedes $u \in U$ speichert,
ob $u$ pr"asent ist). Beim Hashing gibt es eine Funktion $h:U \rightarrow \{0,1, \ldots , m-1\}$, wobei $m$ die Gr"o"se
einer (internen) Tabelle ist. Da meistens gilt $m<|U|$, kann es zu Kollisionen kommen, d.h. $h(u)=h(v) \forall u,v \in U$.
Hierauf kann verschieden reagiert werden:
\begin{entry}
\item[Hashing mit Verkettung] Jede Zelle $i$ enth"alt einen Zeiger auf eine Liste mit Elementen (anf"anglich leer). \\
Bei einer Hashfunktion $h(x)=x \mod m$ haben sich Primzahlen f"ur $m$ als sehr gute Wahl erwiesen. Dabei ist
$\lambda = \frac{n}{m}$ der \textbf{Auslastungsfaktor} der Tabelle. Die worst-case-Laufzeit ist $\Theta (n)$,
w"ahrend die erwartete Laufzeit h"ochstens $2 \cdot (1+ \lambda)$.
\item[c-universell] Eine Menge $H \subseteq \{h|h:U \rightarrow \{0, \ldots , m-1\} \}$ ist c-universell, falls
$\forall x,y \in U$ mit $x \not = y$ gilt: $| \{ h \in H | h(x)=h(y) \} | \leq c \cdot \frac{|H|}{m}$.
Wenn $H$ c-universell ist, dann gibt es keine zwei Schl"ussel, die mit Wahrscheinlichkeit gr"o"ser als $\frac{c}{m}$
auf die gleiche Zelle abgebildet werden. \\
Beispiel: $U=\{ 0,1,2, \ldots , p-1\}$ mit $p$ prim und $H=\{ h_{a,b} | 0 \leq a, b<p, h_{a,b}(x)=((ax+b) \mod p) \mod m\}$ mit
$c=( \lceil \frac{p}{m} \rceil / \frac{p}{m})^2$
\item[Universelles Hashing] Zuf"alliges Ausw"ahlen einer Hashfunktion $h \in H$ . Damit wird verhindert, da"s man f"ur
die Hashfunktion eine worst-case Laufzeit von $\Theta (n)$ erzwingen kann. Durch Wahle einer c-universellen Klassen
von Hashfunktionen ergibt sich dann eine erwartete Laufzeit f"ur $n$ Operationen von h"ochstens
$n(1+\frac{c}{2} \cdot \frac{n}{m})$.
\item[Hashing mit offener Adressierung] Wenn $h(x)=i$ besetzt ist, wird mit einer weiteren Hash-Funktion aus
$h_0, \ldots ,h_{m-1} : U \rightarrow \{0, \ldots , m-1\}$ gehasht. Dieses Verfahren ist speichereffizienter als mit
Verkettung, allerdings mu"s vorher eine gute obere Schranke der maximalen Anzahl einzuf"ugender Elemente bekannt
sein (man kann aber auch z.B. die Tabellen sukzessive um den Faktor 2 wachsen lassen). Bei fast gef"ullten Tabellen ist
die Laufzeit allerdings sehr schlecht. \\
\item[Beispiel] $h_i (x) = (x+i) \mod m$ ("`lineares Austesten"¡) oder $h_i (x) = (f(x)+i \cdot g(x)) \mod m$ mit $f$ und $g$
Hashfunktion und $m$ am besten prim (da $\{ h_i (x) | 0 \leq i<m \}=\{0, \ldots ,m-1\}$), z.B. mit $f(x)=x \mod m$ und
$g(x)=m^\ast -(x \mod m^\ast)$ mit $m^\ast <m$.\\
Problem: Was ist, wenn bei lookup im ersten Schritt der Schl"ussel nicht gefunden wird? -Man sollte also diese Hashing-
Strategie nicht verwenden, wenn wahrscheinlich viele Schl"ussel wieder entfernt werden. Die erwartete Laufzeit einer
erfolglosen lookup-Operation ist dann durch $\frac{1}{1- \lambda}$ nach oben beschr"ankt.
\end{entry}

\item[Fragen]
%----------------------------------
\begin{itemize}
\item Hashing:
%----------------------------------
\begin{itemize}
\item Was ist Hashing? (1000 Kunden - wie hashen?)
\item Double Hashing? (Funktion hinschreiben) Wie sieht Hashfkt. $h(x)=x \mod m$ aus?
\item Hashing mit Verkettung? (detailliert; Belegungsdichte=erwartete Tabellenl"ange)
\item Laufzeit f"ur Chaining?
\item Erwartete Laufzeit f"ur Hashing mit Chaining?
\item Hashen mit offener Adessierung (m"ogliche Kollisionsbeseitigung; Laufzeit; gute Hashfunktionen?)
\item Wann Hashing statt AVL-B"aume?
\item Direktes Hashing? Bitvektor?
\item Was ist $\lambda$? ($\lambda >1$ nur f"ur verkettete Listen)
\item Laufzeit f"ur Hashingsort $O(1+\alpha)$, da zun"achst gepr"uft werden mu"s, ob das einzuf"ugende Objekt bereits enthalten ist!
\item Definition: c-universell (Beispiel)
\item Vergr"o"serung der Hash-Tabelle
\end{itemize}

\item B"aume allgemein
\item F"ur was sind B-B"aume gut?
\end{itemize}

\end{type}

%----------------------------------
\subsection{Graphalgorithmen}
%----------------------------------

\begin{type}
\item[Ungerichteter Graph] $G=(V,E)$ besteht aus einer endlichen Knotenmenge $V$
und einer Kantenmenge $E \in \{ \{ i,j \} | i,j \in V, i \not = j\}$

\item[Gerichteter Graph] $G=(V,E)$ besteht aus einer endlichen Knotenmenge $V$
und einer Kantenmenge $E \in \{ (i,j) | i,j \in V, i \not = j\}$

\begin{entry}
\item[Adjazente Knoten] Knoten, die durch eine Kante verbunden sind

\item[Inzidenz] Eine Kante ist mit einem Knoten inzident, wenn der
Knoten ein Endpunkt der Kante ist.

\item[Weg in $G$] Eine Folge von Knoten $(v_0, v_1, \ldots ,v_m)$, f"ur die
f"ur jedes $i$ $(0 \leq i \leq m)$ gilt, da"s $(v_i , v_{i+1} \in E$ (bei
gerichteten Graphen) und $\{ v_i, v_{i+1} \} \in E$ (f"ur ungerichtete
Graphen.

\item[Wegl"ange] ist die Anzahl der Kanten wobei ein Weg \textbf{einfach}
hei"st, wenn kein Knoten zweimal auftritt und \textbf{Kreis}, wenn der
Endknoten ungleich dem Anfangsknoten und der Weg einfach ist.
\item[Azyklisch] ist ein gerichteter Graph, wenn er keine Kreise besitzt.

\item[Zusammenh"angend] hei"st f"ur einen ungerichteten Graph, da"s es f"ur
je zwei Knoten $v,w \in V$ einen Weg von $u$ nach $v$ gibt.

\item[Stark zusammenh"angend] ist ein gerichteter Graph, wenn es f"ur je
zwei Knoten $v,w \in V$ sowohl einen Weg von $v$ nach $w$ als auch von $w$
nach $v$ gibt.

\item[Induzierter Graph] Sei $G$ ein ungerichteter Graph, dann gilt f"ur $V'
\subseteq V$, da"s $G(V')$ der von $V'$ induzierte Graph ist. D.h., da"s
$G(V')$ die Knotenmenge $V'$ und alle Kanten von $G$ besitzt, deren Endpunkte
in $V'$ liegen.\\
Wenn $G(V')$ zusammenh"angend ist und $V'$ eine gr"o"ste zusammenh"angende
Knotenmenge bzgl. der Inklusion ist (wenn also die Hinzunahme jedes weiteren
Knotens den Zusammenhang st"ort), nennen wir $V'$ eine
\textbf{Zusammenhangskomponente} von G.

\item[Knoten-Beziehungen] F"ur ungerichtete Graphen gilt: $\{ u,v \} \in E$ $\Rightarrow$ $u$ ist
\textbf{Nachbar} von $v$. \textbf{Grad($v$)} beschreibt die Anzahl der
Nachbarn von $v$. \\
Bei gerichtete Graphen ist: $u$ der \textbf{Vorg"anger} von $v$, wenn $(u,v
\in E$, und die Anzahl der Vorg"anger \textbf{outgrad($v$)}
\end{entry}

\item[Implementierung von Graphen] Mittels einer \textbf{Adjazenzmatrix} $A_G$ mit
$$A_G[u,v]=\begin{cases}1 & \text{, wenn }\{u,v\} \in E \\ 0 & \text{, sonst}
\end{cases}$$ mit Platzbedarf $\Theta (n^2)$ und Zeit f"ur Bestimmung der
Nachbarn bzw. Vorg"angern $O(n)$. \\
Bei der \textbf{Adjazenzliste} listet das element $A[v]$ alle Nachbarn bzw.
Nachfolger von $v$ auf mit Speicherbedarf $\Theta (n+|E|)$. Diese Darstellung
ist vor allem bei d"unnen Graphen der Adjazenzmatrix "uberlegen und liefert
eine schnellere Implementierung der Nachbar- oder Nachfolger-Operation.

\item[K"onigsberger Br"uckenproblem / Euler-Kreis] Finde einen Weg in einem Graphen, der jede
Kante genau einmal durchl"auft und an seinem Anfangspunkt endet.

\item[Tiefensuche (DFS)] Ist ein Preorderlauf (+ Markierung) auf
(un-)gerichteten Graphen. Um zu verhindern, da"s Knoten zweimal besucht
werden, wir ein boolesches Array ben"otigt, in dem vermerkt wird, ob ein
Knoten bereits besucht wurde. Die Laufzeit betr"agt $O(|V|+|E|)$. Damit kann
in $O(|V|+|E|)$ "uberpr"uft werden, ob G zusammenh"angend ($\Leftrightarrow$
$tsuche(0)$ besucht alle Knoten) und ein Baum ist ($\Leftrightarrow$ es
existieren keine R"uckw"artskanten). \\
Wenn $v$ ein Knoten in $G$ ist, dann enth"alt der Baum von $v$ alle Knoten der
Zusammenhangskomponente von $v$. \\
Zur Implementierung k"onnen wir, sofern der Algorithmus nicht rekursiv laufen
soll, einen Stack verwenden.
\begin{entry}
\item[Kantenbezeichnungen] \textbf{Ungerichtete Graphen} Kanten, die im Aufrufbaum der Tiefensuche, und im
Graphen enthalten sind hei"sen \textbf{Baumkanten}. \textbf{R"uckw"artskanten}
w"urden im Graphen einen Knoten mit einem seiner Vorg"anger verbinden \\
\textbf{Gerichtete Graphen} Baumkanten, R"uckw"artskantenm, Vorw"artskanten
(w"urden im Aufrufbaum einen Knoten mit einem Nachfolger verbinden) und
Querkanten (verbinden zwei Knoten im Aufrufbaum, die weder Vor- noch Nachfahre
f"ureinander sind.
\item[Eigenschaften der Tiefensuche] \textbf{Ungerichtete Graphen} Sei $G=(V,E)$, $(u,v) \in E$ und $W_G$
der durch die Tiefensuche auf $G$ definierte Wald der Aufrufb"aume. Wenn
$tsuche(u)$ vor $tsuche(v)$ aufgerufen wird, dann is $v$ ein Nachfahre von $u$
(in $W_G$). $u$ und $v$ geh"oren immer zum selben Baum in $W_G$ und $G$ besitzt nur Baum-
und R"uckw"artskanten.
\textbf{Gerichtete Graphen} $G$ azyklisch $\Leftrightarrow$ $G$ besitzt keine
R"uckw"artskanten und $e=(u,v)$ is eine Baumkante $\Leftrightarrow$ $tsuche(v)$ wird
unmittelbar aus $tsuche(u)$ aufgerufen. Um die Kanten sicher erkennen zu
k"onnen mu"s dem Algorithmus ein Integer-Array $Anfang\_nr$ und $Ende\_nr$ zur
Verf"ugung gestellt werden (anstelle von $besucht$), in denen am Anfang und am
Ende der Rekursion die Knotennummern abgespeichert werden.
\end{entry}

\item[Breitensuche (BFS)] F"ur jeden Knoten werden zuerst alle Nachfolger besucht,
gefolgt von der Generation der Enkel usw. Die Knoten werden also in der
Reihenfolge ihres Abstandes von $v$, dem Startknoten der Breitensuche,
erreicht. \\
Zur Implementierung verwenden wir eine Queue, in der wir die unbesucheten
Nachbarknoten eintragen und markieren. Die Laufzeit betr"agt h"ochstens
$O(|V_w|+|E_w|)$, womit BFS genauso schnell ist wie DFS, definiert aber den
Baum $T_w$ von k"urzesten Wegen f"ur $G$.

\item[SSSP-Problem (Disjkstra)] Jeder Kante eines Graphen wird durch die Funktion
$l"ange:E \rightarrow \mathbb{R}_{\geq 0}$ eine L"ange $\geq 0$ zugewiesen. \\
Sei $S \subseteq V$ und $s \in S$, dann nehmen
wir an, da"s wir f"ur jeden Knoten $w \in V-S$ den Wert \textbf{distanz($w$)}=
L"ange eines k"urzesten Weges $W$ von $s$ nach $w$, so da"s $W$, mit Ausnahme des
Endknotens $w$, nur Knoten in $S$ durchl"auft kennen. Der Algorithmus sucht
nun einen Knoten $v \in V-S$ mit kleinstem Distanzwert und behauptet, da"s
distanz[$v$]=L"ange eines k"urzesten Weges von $s$ nach $v$ ist. Der Knoten
wird dann der Menge $S$ hinzugef"ugt und die Distanz-Werte f"ur Knoten in
$V-S$ werden aktualisiert. Knoten, die von $S$ aus gar nicht erreichbar sind
haben einen Distanzwert von $\infty$. \\
Algorithmus:
\begin{itemize}
\item Setze $S=\{s\}$ und
$$distanz[v]=\begin{cases} \text{l"ange}(s,v) & \text{wenn } (s,v) \in E \\
\infty & \text{sonst.} \end{cases}$$
\item Solange $S \not = V$ wiederhole
\begin{itemize}
\item w"ahle einen Knoten $w \in V-S$ mit kleinstem Distanzwert
\item F"uge $w$ in $S$ ein.
\item Berechne die neuen Distanz-Werte der Nachfolger von $w$. Insbesondere
setze f"ur jeden Nachfolger $u \in V \ S$ von $w$
\begin{align*}
c & = distanz[w] + laenge(w,u); \\
distanz[u] & = (distanz[u]>c) \text{ ? } c : distanz[u];
\end{align*}
\end{itemize}
\end{itemize}
Die Korrektheit kann man mit Hilfe eines konstruierten Weges beweisen (erster
Knoten, der nicht mehr zu $S$ geh"ort, weiter weg als $w$ usw.). Die Laufzeit
betr"agt $O((|V|+|E|) \log_2 |V|)$ (da $|V|-1$-mal Knoten mit kleinstem
Distanz-Wert gew"ahlt und die neuen Distanzwerte der Nachfolger berechnet
werden; der kleinste Distanz-Wert wird durch Verwendung eines Heaps berechnet,
wobei die Priorit"at durch den Distanz-Wert definiert ist und die Ordnung
umgekehrt wird, damit die Operationen \texttt{insert} und \texttt{deletemin}
unterst"utzt werden; es werden maximal $|E|$ Neuberechnungen durchgef"uhrt und
der Heap besitzt nie mehr als $|V|+|E|$ Elemente, d.h. eine Heap-Operation
ben"otigt Zeit $O(\log_2(|V|+|E|))=O(\log_2|V|)$). \\
Der Dijkstra Algorithmus ersetzt also im wesentlichen nur die Schlange der
Breitensuche durch eine Priorit"atswarteschlange. Die k"urzesten Wege selbst
k"onnen "uber eine Speicherung des unmittelbaren Vorg"angers rekonstruiert
werden.

\item[Minimale Spannb"aume] Sei $G=(V,E)$ ein ungerichteter Graph. Ein Baum
$T=(V',E')$ hei"st Spannbaum, falls $V'=V$ und $E' \subset E$.
\begin{entry}
\item[Prim's Algorithmus] Mit Laufzeit $O(|E| \cdot \log_2 |V|)$. Dabei werden
die kreuzenden Kanten in einem Heap verwaltet und "uber die
\texttt{deletemin}-Operation entfernt.
\begin{itemize}
\item Setze $S=\{0\}$ und $E'=\emptyset$
\item Solange $S \not = V$, wiederhole: \\
Bestimme eine k"urzeste kreuzende Kante $e \in E$, die also einen Endpunkt in
$S$ und einen in $S-V$ besitzt und eine l"ange(e)=min\{l"ange($e'$)|$e' \in E$
und $e'$ besitzt jeweils einen Endpunkt in $S$ und $V-S$\} \\
Sei $E=\{ u,v \}$ mir $u \in S$ und $e \in V-S$. Setze $S=S \cup \{ v \}$ und
$E'=E' \cup \{ e \}$.
\end{itemize}
\item[Kruskals Algorithmus] Mit Laufzeit $O(|E| \cdot \log_2 |V|)$. Der Wald
wird dabei mittels eines Arrays und der Vater-Rep"asentation gespeichert. Die
Operation \texttt{union(i,j)} h"angt dann immer den kleineren Baum unter die
Wurzel des gr"o"seren (damit kann der Baum h"ochstens $\log_2(|V|)$
tief werden).
\begin{itemize}
\item Sortiere die Kanten gem"a"s aufsteigendem L"angenwert. Sei $W=(V,E')$
der leere Wald, also $E'=\emptyset$.
\item Solange $W$ kein Spannbaum ist, wiederhole: \\
Nimm die gegenw"artig k"urzeste Kante $e$ und entferne sie aus der sortierten
Folge und verwerfe $e$, falls $e$ einen Kreis in $W$ schlie"st. Anonsten
akzeptiere $e$ und setze $E'=E' \cup \{e\}$
\end{itemize}
\end{entry}

\item[Fragen]
%----------------------------------
\begin{itemize}
\item Welcher Alg. im ungewichteten Graph f"ur "'K"urzeste Wege"' und "'Bipartiter Graph"'?
\item Warum funktionieren Dijkstra und Prim

\item Dijkstra-Algorithmus f"ur k"urzeste Wege?
%----------------------------------
\begin{itemize}
\item Datenstruktur?
\item Definition von $distanz[v]$?
\item Korrektheitsbedingung?
\item Wie Distanzen im Heap aktualisieren?
\item Wo sind Informationen enthalten?
\item Mit Priorit"atswarteschlange vgl. mit BFS?
\item Was ist wenn alle $distanz=1$ haben? (BFS)
\item Wie implementiert man $V$ und $V\backslash S$?
\item Was wissen wir "uber $w \in V\backslash S$?
\end{itemize}

\item Kruskal-Algorithmus (minimale Spannb"aume)
%----------------------------------
\begin{itemize}
\item detailliert - wie funktioniert $union()$? (mu"s schnell sein!)
\item wie w"ahle man m? -Prim!
\item Datenstruktur f"ur Kruskal? (Vaterrepr"asentation)
\item Funktioniert der Algorithmus auch mit negativen Kanten? -Ja (aber nicht Dijkstra)
\end{itemize}

\item Algorithmus von Prim?
\item Wie stelle ich Bipartiten Graph fest?
\item Ford-Fulkerson (Minimaler Schnitt = Maximaler Flu"s)
\item Kantentypen bei DFS
\item Fouriertransformation, n-te Einheitswurzel

\end{itemize}

\end{type}

%----------------------------------
\subsection{Entwurfsmethoden f"ur Algorithmen}
%----------------------------------

\begin{type}
\item[Divide and Conquer]
%----------------------------------
Das gegebene Problem wird in kleinere Teilprobleme
zerlegt, deren L"osung eine L"osung des Ausgangsproblems bedingt (Beispiel:
Bin"arsuche, Quicksort/Mergesort, Durchsuchungsmethoden f"ur B"aume und Graphen)
\begin{entry}
\item[Multiplikation ganzer Zahlen] Es werden nur drei Multiplikationen
ben"otigt, was zu einer Laufzeit von $O(n^{\log_2 3})$ f"uhrt)
\item[Multiplikation von Matrizen] Zerlegung der Matrizen in vier gleich gro"se Teilmatrizen und Durchf"uhrung
von 7 Matrizenmultiplikationen, Laufzeit $\Theta (n^{\log_2 7})$, erst sinnvoll ab
mehreren hundert Zeilen/Spalten
\end{entry}

\item[Dynamisches Programmieren]
%----------------------------------
Im Unterschied zu Divide and Conquer werden
L"osungen f"ur Teilprobleme mehrmals ben"otigt, deshalb werden sie abgespeichert.
\begin{entry}
\item[Floyd's Algorithmus zur Bestimmung aller k"urzesten Wege] Es mu"s das
Teilproblem 
$$distanz_k [u][v]=\text{L"ange des k"urzesten Weges von u nach v},$$
dessen innere Knoten nur aus Knoten in $\{0,1, \ldots,k\}$ bestehen berechnet
weden. Dabei ist das einfachste Problem
$$distanz_{-1}[u][v]=\begin{cases} \text{l"ange}(u,v) & (u,v) \in E \\
\infty & \text{sonst} \end{cases}$$
wobei sich damit rekursiv ergibt:
$$distanz_k [u][v]=min\{ distanz_{k-1}[u][v], distanz_{k-1}[u][k]+distanz_{k-1}[k][v]\}$$
Zur Implementation verwenden wir ein 3-dimensionales Array distanz., wobei angenommen
wird, da"s $G$ als Adjazenzmatrix vorliegt. Wegen einer Laufzeit von $\Theta (n^3)$
empfiehlt sich der Algorithmus vor allem f"ur dichte Graphen, da sonst Dijkstra eine
bessere Alternative darstellt.
\item[Warshall's Algorithmus f"ur die Berechnung der transitiven H"ulle eines gerichteten
Graphen] Hier kann man ein Teilproblem als $H"ulle_k[u,v]=1$ $\Leftrightarrow$ Es gibt
einen Weg von $u$ nach $v$, dessen innere Knoten nur aus Knoten in $\{ 0, \ldots ,k\}$
bestehen. Damit ist
$$H"ulle_{-1}[u,v]= \begin{cases} 1 & (u,v) \in E \\ 0 & \text{sonst.} \end{cases}$$
mit dem rekursiven Schritt
$$H"ulle_k [u,v]=H"ulle_{k-1}[u,v] \vee (H"ulle_{k-1}[u,k] \wedge H"ulle_{k-1}[k,v])$$
Was dann zu einer Laufzeit von $O(|V|^3)$ f"uhrt. \\
Auch hier ist die $n$-malige Anwendung der Tiefensuche ein scharfer Konkurrent,
weshalb der Algorithmus nur f"ur dichte Graphen ($|E|= \Omega (|V|^2)$ benutzt
werden sollte.
\item[Multiplikation von $n$ Matrizen] Da die Klammerung hier eine sehr wichtige
Rolle spielt, l"a"st sich der Rekursionsschritt durch 
\begin{multline*}
Kosten[i][i+k+1]=min\{Kosten[i,s]+Kosten[s+1,i+k+1]+r_{i-1} \cdot r_s \cdot
r_{i+k+1} \\
| i \leq s \leq i+k\}
\end{multline*}
definieren. Damit wird Zeit $O(n^3)$ ben"otigt.
\end{entry}

\item[Greedy-Algorithmen]
%----------------------------------
Konstruieren den L"osungsvektor Komponente nach
Komponente, wobei ein gesetzter Wert niemals zur"uckgenommen wird. Beispiele
sind Prim, Kruskal und Dijkstra.
\begin{entry}
\item[Non-preemptive Scheduling] Mehrere Aufgaben mit Startzeiten $s_i$ und
Terminierungszeiten $t_i$. Implementierung: Alle Aufgaben nach Startzeit sortieren
und dann Aufgaben der Reihe nach ausw"ahlen und immer die l"oschen, deren
Startzeit vor der gew"ahlten Terminierungszeit liegt $\rightarrow$ Laufzeit $O(n \log_2n)$.
\item[Huffman-Codes] Pr"afixcode, der auch durch einen Bin"arbaum dargestellt werden
kann. Die Implementierung erfolgt mittels eines Heaps , wobei f"ur je zwei (minimale)
Buchstaben, die entfernt werden, wieder ein neuer mit der Summe hinzugef"ugt wird.
Die Laufzeit betr"agt $O(n \log_2 n)$
\item[Binpacking-Problem] Da das Problem NP-Vollst"andig ist, kann ein Greedy-Algorithmus
mittels best-fit.
\end{entry}

\item[Backtracking]
%----------------------------------
Es wird versucht, systematisch alle L"osungen im L"osungraum
systematisch aufzulisten (Ziel: Zusammenfassung "aquivalenter L"osungen, fr"uhzeitige
Erkennung, da"s bestimmte partielle L"osungen nicht zu einer Gesamtl"osung
erweiterbar sind).

\item[Branch and Bound]
%----------------------------------
F"ur jede partielle L"osung werden gute untere und obere
Schranken ben"otigt.

\end{type}


%=====================================
\section{Fragen zu Theoretischer Informatik 2}
%=====================================

%----------------------------------
\subsection{Grundlagen}
%----------------------------------
\begin{entry}
\item[Alphabet $\Sigma$] Menge von Buchstaben. $\Sigma ^n=\{(a_1,\ldots ,a_n)|a_i \in \Sigma\}$
ist die Menge aller Worte der L"ange $n$ (mit $\Sigma ^0=\epsilon$ "`leere Wort"¡ und
$\Sigma ^\ast = \bigcup_n=0 ^\infty \Sigma^n$ "`Menge aller Worte "uber $\Sigma$)
\item[Konkatenation] $\Sigma$ Alphabet, $u,v, \in \Sigma^\ast \Rightarrow u \cdot v
=u_1 \ldots u_n v_1 \ldots v_m=uv$
\item[Teilwort] $u$ Teilwort von $v$ $\Rightarrow$ $\exists u_1, u_2 \in \Sigma^\ast :
v=u_1 \cup u_2$
\item[Pr"afix] $u$ Pr"afix von $v$ $\Rightarrow$ $\exists u_1 \in \Sigma^\ast : v=u1 \cup u_2$
\item[Konkatenation von Sprachen] $L_1,L_2$ Sprachen $\Rightarrow$ $L_1 \circ L_2
=\{uv|u \in L_1 , v \in L_2\}$.\\
$L$ Sprache "uber $\Sigma$ $\Rightarrow$ $L^n =\{ u_1 \ldots u_n | u_1, \ldots , u_n \in L\},
L^\ast = \bigcup_{n=0} ^\infty L^n, L^+ = \bigcup_{n=1} ^\infty L^n$
\item[Regul"are Ausdr"ucke] Definiert durch
\begin{itemize}
\item $\emptyset , \epsilon$ und $a(\in \Sigma)$ sind regul"ar (leere Sprache, Sprache
des leeren Wortes, Sprache des einbuchstabigen Wortes)
\item $A_1,A_2$ regul"are Ausdr"ucke $\Rightarrow$ $(A_1)+(A_2),(A_1)\circ(A_2),
(A_1)^\ast$ sind regul"ar
\item Alle regul"aren Ausdr"ucke lassen sich durch endlich viele Anwendungen von
obigen Regeln erzeugen
\end{itemize}
Probleme gibt es z.B. mit regul"aren Klammerausdr"ucken.
\end{entry}


%----------------------------------
\subsection{Berechenbarkeit}
%----------------------------------
Ziel ist die Formalisierung der Berechenbarkeit einer Funktion $F:\Sigma_1^\ast \rightarrow \Sigma_2^\ast$
bzw. eine Formalisierung der Entscheidbarkeit einer Sprache $L$.
\begin{type}
\item[Turingmaschinen]
Formal ein 6-Tupel $(Q,\Sigma,\delta,q_0,\Gamma,F)$.
\begin{entry}
\item[Architektur] Beidseitig unendliches Band bestehend aus Speicherzellen mit
Adressen aus $\{\ldots , -2,-1,0,1,2,\ldots \}$, die ein Symbol aus dem \textbf{Bandalphabet
$\Gamma$} speichern.
\item[Eingabekonvention] Eingaben sind Worte "uber dem \textbf{Eingabealphabet $\Sigma$}
mit $\Sigma \subseteq \Gamma$. Alle Zellen des Bandes, die keine Buchstaben aus dem
Eingabealphabet gespeichert haben, speichern das \textbf{Blanksymbol $B$} mit $B \in \Gamma$.
\item[Programm] Eine Menge von Befehlen $(q,a,q',b,wohin)$ bilden ein Programm mit
$q,q' \in Q$ , Zustand einer (endlichen) Zustandsmenge $Q$, $a,b \in \Gamma$ und
$wohin \in \{ links,bleib,rechts \}$.\\
Ein Programm ist also formal eine Zustands"uberf"uhrungsfunktion
$$\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{links,bleib,rechts\},$$
die jedem Paar $(q,a) \in Q \times \Gamma$ nur eine Anweisung zuordnet.
\item[Ausgabekonvention] Eine Turingmaschine h"alt auf eine Eingabe $w$ $\Leftrightarrow$
die Maschine hat einen Zustand $q$ erreicht und liest ein Symbol $q \in \Gamma$, so da"s
$\delta (q,a)=(q,a,bleib)$.\\
\textbf{Funktionsberechnung:} Ausgabe ist das Wort bestehend aus allen Buchstaben
der gegenw"artig gelesenen Zelle bis (ausschlie"slich) zu ersten Zelle rechts von der
gegenw"artigen Zelle, die $B$ speichert. Formal 5-Tupel $(Q\Sigma,\delta,q_0,\Gamma)$.\\
Wenn $M$ eine Funktion berechnet, dann bezeichnet
$f_M:\Sigma^\ast \rightarrow \Gamma^\ast$ mit
\begin{align}
f_M(w)=u & \Leftrightarrow M \text{ gibt, f"ur Eingaben } w \text{, die Ausgabe } u \notag \\
f_M(w)=undefiniert & \Leftrightarrow M \text{ h"alt nicht auf Eingabe } w \notag
\end{align}
die von $M$ berechnete Funktion \\
\textbf{Spracherkennung:} Menge der akzeptierenden Zust"ande $F \subseteq Q$. Die
von $M$ erkannte Sprache $L(M)$ ist dann $L(M)=\{w \in \Sigma^\ast | M \text{ akzeptiert } w\}$.
\item[Berechenbarkeit] Eine Funktion $f:\Sigma_1^\ast \rightarrow \Sigma_2^\ast$ hei"st
berechenbar $\Leftrightarrow$ $\exists$ TM $M$ $\forall w\in \Sigma_1^\ast$ h"alt mit
Ausgabe $f(x)$ (also ist $f=f_M$ und $f_M (w) \not =$ undefiniert $\forall w \in \Sigma_1^\ast$).
\item[$k$-Band-Turingmaschinen] TM mit $k$ B"andern, wobei die Eingabe auf Band 1 
gespeichert ist. Ein Befehl wird in Abh"angkeit der Eingabe und den Inhalten der $k$
gelesenen Zellen ausgew"ahlt. Der zu druckende Buchstabe wird f"ur jedes Band separat
festgelegt. \\
Eine $k$-Band-TM, die auf Eingaben der L"ange $n$ nach h"ochstens $T(N)$ Schritten
h"alt kann durch eine TM $M'$ simuliert werden, die nach h"ochstens $O(T^2(n))$
Schritten h"alt, wobei $M$ und $M'$ dieselbe Funktion berechnen bzw. dieselbe Sprache
erkennen (Beweis durch Spuren).
\end{entry}
TM k"onnen das gleiche wie reale Rechner, nur langsamer. Die einzelnen
Rechenschritte wirken nur lokal, so da"s Rechnungen einfacher zu verfolgen
sind. In Fragen der Berechenbarkeit sind TM "aquivalent zu allen bekannten
Rechnermodellen.

\item[Entscheidbarkeit/Rekursivit"at] Eine Sprache $L \subseteq \Sigma^\ast$ entscheidbar $\Leftrightarrow$
$\exists$ TM $M$, die $\forall x \in \Sigma^\ast$ h"alt mit: $x \in L \Leftrightarrow M
\text{ akzeptiert } x$ (also $L=L(M)$ und $M$ h"alt stets).

\item[Registermaschinen] Besteht aus Eingabe- und Ausgabeband(in Zellen unterteilt),
Speicher (Akkumulator und unendlich viele Register speichern ganze Zahlen). Befehle
werden durch Label identifiziert (Lese-/Schreib-, Speicher-, arithmetische und Goto-Befehle,
Verleichsoperationen).  Zu Anfang steht die Eingabe linksb"undig auf dem Eingabeband,
der Lese-/Schreibkopf steht auf der ersten Zelle und alle Register sind mit 0 initialisiert. \\
Eine RM kann von einer TM in Zeit $O=(T^6(n))$ Schritten simuliert werden (Beweis durch $k$-Band
TM in Zeit $O(T^3(n))$). \\
Was RM k"onnen, k"onnen reale Rechner erst recht. Bei der Rechenzeit m"ussen
allerdings Operationen auf sehr langen Zahlen fair, d.h. mit dem
logarithmischen Kostenma"s, bewertet werden. Umgekehrt bieten reale Rechner
weit mehr Komfort, wobei sich die auf realen Rechnern m"oglichen Operationen
auf RM ohne wesentlichen Zeitverlust nachbilden lassen. RM sind ein
realistischen, assemblernahes Rechnermodell.

\item[Churchsche These] \textit{Die Klasse der intuitiv berechenbaren Funktionen ist
gleich der Klasse der Turingberechenbaren Funktionen.} Mit der Existenz von Rechnern ist nachgewiesen, da"s die
Turing-berechenbaren Funktionen tats"achlich berechenbar sind. Die Umkehrung ist
prinzipiell nicht beweisbar, da der Begriff "`intuitiv berechenbar"¡ nicht wohldefiniert ist.
Nur ein Gegenbsp. k"onnte die Chruchsche These widerlegen! \\
$\Rightarrow$ F"ur Fragen der Berechenbarkeit ist die Wahl des Rechnemodells
unerheblich, solange es soviel kann wie Turingmaschinen.

\item[Universelle TM] Eine TM $U$, die ein (geeignet kodiertes) Turingmaschinenprogramm
$P$ und eine Eingabe $w$ f"ur $P$ als Eingabe annimmt und sodann das Programm $P$
auf der Eingabe $w$ simuliert. Dabei kodiere man die Eingabe in das bin"are Zahlensystem
und speichere die Eingabe in den Zust"anden ab. Der Startzustand und gleichzeitig
einzige akzeptierende Zustand ist $q_0$ und die Funktion $\delta$ mit ihrer endlichen
Funktionstabelle l"a"st sich durch eine \textbf{G"odelnummer} beschreiben:
$$1^{|Q|}0code(\delta)00$$
Die G"odelnummer der TM $M$ wird mit $<M>$ bezeichnet. und beschreibt das
Programm von $M$, wobei $\delta(q,a)=(q',b,wohin)$ durch das Wort
$$1^{q+1}01^{Zahl(a)}01^{q'+1}01^{Zahl(b)}01^{Zahl(wohin)}0$$
kodiert wird (mit Zahl(0)=1, Zahl(1)=2, Zahl(B)=3, Zahl(links)=1, Zahl(rechts)=2,
Zahl(bleib)=3). \\
Die Simulation von $M$ auf $w$ funktioniert mit einer 3-Band-TM: (1) G"odelnummer von
Band 1 l"oschen und auf Band 2 schreiben, (2) pr"ufen, ob $<M>$ syntaktisch korrekt
ist, falls ja (3) Zustand 0 auf Band 3 schreiben und schrittweise Simulation durchf"uhren,
wobei immer Band 3 den gegenw"artigen Zustand speichert. \\
F"ur eine universelle TM $U$ bedeutet dies:
$$M \text{ akzeptiert } w \Leftrightarrow U \text{ akzeptiert } <M>w.\\
M \text{ h"alt auf Eingabe } w \Leftrightarrow U \text{ h"alt auf Eingabe } <M>w.$$

\item[Reduzierbarkeit $\leq$] $L_1$ und $L_2$ sind Sprachen "uber $\Sigma _1$ bzw. $\Sigma _2$.
$L_1$ ist auf $L_2$ reduzierbar ($L_1 \leq L_2$) $\Leftrightarrow$ $\exists$ eine stets
haltenden TM $T$ $\forall w \in \Sigma_1 ^\ast : w\in L_1 \Leftrightarrow T(w) \in L_2$. \\
$L$ sei unentscheidbar $\Rightarrow$ $\overline{L}$ ist unentscheidbar und $K$ ist
unentscheidbar, wenn $L \leq K$. \\
Aus $A\leq B$ folgt:
\begin{itemize}
\item $B$ rekursiv $\Rightarrow$ $A$ rekursiv
\item $A$ nicht rek. $\Rightarrow$ $B$ nicht rek.
\end{itemize}
Beispiel: $\overline{D}\leq U$.
\begin{entry}
\item[Diagonalsprache $D$] $D=\{<M>|M \text{ akzeptiert die Eingabe } <M> \text{ nicht. }\}$
ist nicht entscheidbar.
\item[Halteproblem] $H=\{ <M>w|M \text{ h"alt auf Eingabe } w\}$ (nicht entscheidbar,
Beweis mittels $U \leq H$)
\item[Spezielles Halteproblem] $H_\varepsilon =\{ <M>|M \text{ h"alt auf dem leeren Wort } \varepsilon\}$
(nicht entscheidbar, Beweis mit mit $H \leq H_\varepsilon$)
\item[Universelle Sprache] $H=\{ <M>w|M \text{ akzeptiert } w\}$ (nicht entscheidbar,
Beweis mit $\overline{D}=\{ w\in \{0,1\}^\ast | (w=<M> \text{ und M akzeptiert Eingabe }
<M>)\text{ oder (w ist keine G"odelnummer)} \}$ und $\overline{D} \leq U$).\\
Es gib also keinen Compiler, der stets korrekt voraussagt, ob ein Programm eine vorgelegte
Eingabe akzeptiert.
\end{entry}

\item[Satz von Rice] "`Jede nicht-triviale Eigenschaft von TM f"uhrt zu einem nicht-trivialen
Problem"¡ oder: Sei $f_M$ die (partielle) Funktion der TM $M$ mit
$F=\{ f_M | M \text{ ist eine Turingmaschine} \}$ und $S \subseteq F$, dann ist die Sprache
$$TM(S)=\{ <M> | M \text{ berechnet eine Funktion in } S\}$$
nicht entscheidbar, falls $S \not = \emptyset$ und $S \not = F$ (Beweis mit
$\overline{H_\varepsilon} \leq TM(S)$ "uber die "uberall undefinierte Funktion). L"a"st
sich sehr gut anwenden auf:
\begin{itemize}
\item $L_1=\{ <M> | M \text{ h"ault f"ur keine Eingabe} \}$
\item $L_2=\{ <M> | M \text{ gibt entweder stets die Ausgabe 0 oder 1} \}$
\item $L_3=\{ <M> | M \text{ berechnet die Identit"atsfunktion} \}$
\item $L_4=\{ <M> | M \text{ akzeptiert alle Eingaben} \}$
\end{itemize}

\item[Entscheidbarkeit] $L_1$ und $L_2$ seien entscheidbar $\Rightarrow$ $L_1 \cup L_2$,
$L_1 \cap L_2$ und $\overline{L_1}$ entscheidbar

\item[Rekursiv aufz"ahlbar] Die Sprache $K$ hei"st r.a. $\Leftrightarrow$ $\exists$ TM $M$
mit $K=L(M)$ (d.h. $w \in K \Leftrightarrow M$ akzeptiert $w$). Die TM $M$ mu"s also
nicht f"ur jede Eingabe halten. Wenn $w$ nicht zur Sprache gerh"ort, darf sie $w$ niemals
akzeptieren, mu"s es aber auch nicht erkennen. \\
$H,H_\varepsilon$ und $U$ sind rekursiv aufz"ahlbar aber nicht entscheidbar. \\
$L_1$ und $L_2$ seien rekursiv aufz"ahlbar $\Rightarrow$ $L_1 \cup L_2$ und
$L_1 \cap L_2$ rekursiv aufz"ahlbar. \\
$L$ und $\overline{L}$ rek. aufz. $\Rightarrow$ $L$ ist entscheidbar. \\
$\overline{H},\overline{H_\varepsilon}$ und $\overline{U}$ sind nicht rekursiv
aufz"ahlbar.\\

\begin{center}
\begin{tabular}{l|c c }
Sprache & Rekursiv & Rekursiv aufz"ahlbar \\
\hline
$H$                        & $-$ $(U\leq H$)             & $+$ \\
$\overline{H}$             & $-$                         & $-$ \\
$H_\varepsilon$            & $-$ $(H_leq H_\varepsilon)$ & $+$ \\
$\overline{H_\varepsilon}$ & $-$                         & $-$ \\
$U$                        & $-$                         & $+$ \\
$\overline{U}$             & $-$                         & $-$ \\
$D$                        & $-$                         & $-$ \\
$\overline{D}$             & $-$ ($\overline{D}\leq U$)  & $+$ (?) \\
\end{tabular}
\end{center}

F"ur eine Sprache $L$ gilt genau eine der folgenden 3 Eigenschaften:
\begin{enumerate}
\item $L$ und $\overline{L}$ sind rek. (und damit auch rek. aufz.)
\item $L$ und $\overline{L}$ sind nicht rek. aufz. (und damit auch nicht rek.)
\item Genau eine der beiden Sprachen $L$ und $\overline{L}$ ist rek. aufz.,
aber nicht rek., die andere ist nicht rek. aufz"ahlbar.
\end{enumerate}

\item[$\mu$-rekursive Funktionen] Neuer Formalismus, der wiederum das Konzept
der turing-berechenbaren Funktionen liefert ($\rightarrow$ Church'sche These).
Durch den vorgestellten Formalismus erhalten wir einen konstruktiven Beweis
der Berechenbarkeit dieser neuen Klasse von Funktionen. \\
\textbf{G"odelscher Unvollst"andigkeitssatz:} \textit{"`Jede rekursiv aufz"ahlbare
Axiomatisierung der Zahlentheorie beitzt wahre, aber nicht beweisbare
Aussagen."¡}. Ein Formalismus kann eine komplexere Realit"at also nicht exakt
widerspiegeln. \\
\begin{entry}
\item[Indikatorfunktion] oder charakteristische Funktion $f_L : \Sigma^\ast
\rightarrow\{0,1 \}$ von $L \subseteq \Sigma^\ast$ wenn gilt
$$\forall x \in \Sigma^\ast : x \in L \Leftrightarrow f(x)=1$$
Z.B. $f(w)=1-(\Sigma_{i=1}^{|w|}w_i)\mod 2$ f"ur die Menge der Worte mit
gerader Anzahl von Einsen.
\item[Grundfunktionen] Nachfolgefunktion: $S(x)=x+1$, Konstantenfunktion:
$C_q^k(x_q,x_q,\ldots,x_k)=q$, Projektionsfunktion:
$P_i^k(x_1,x_2,\ldots,x_i,\ldots,x_k)=x_i$
\item[Einsetzung] Seien $\psi,\chi_1,\chi_2,\ldots,\chi_m$ Funktionen mit
$\chi_i:\mathbb{N}^n\rightarrow\mathbb{N} \forall i$ und mit
$\psi:\mathbb{N}^m\rightarrow\mathbb{N}$, so hei"st $\rho :\mathbb{N}^n
\rightarrow \mathbb{N}$ mit
$$\rho(x_1,x_2,\ldots,x_n)=\psi(\chi_1(x_1,x_2,\ldots,x_n),\ldots,\chi_m(x_1,x_2,\ldots,x_n))$$
die durch Einsatzung von $\chi_1,\chi_2,\ldots,\chi_m$ in $\psi$ erhaltene
Funktion.
\item[Induktion] Ist $\chi :\mathbb{N}^{n+1}\rightarrow\mathbb{N}$ und
$\psi :\mathbb{N}^{n-1}\rightarrow\mathbb{N}$ Funktion, so ist
$\rho :\mathbb{N}^n\rightarrow\mathbb{N}$ definiert als:
$$\begin{cases}
\rho (0,x_2,\ldots,x_n) & = \psi(x_2,\ldots,x_n) \\
\rho (S(x_1),x_2,\ldots,x_n) & = \chi(x_1,\rho(x_1,x_2,\ldots,x_n),x_2,\ldots,x_n)
\end{cases}$$
dir durch Indunktion aus $\chi$ mit Anfangsfunktion $\psi$ hervorgegangene
Funktion.
\item[Primitiv Rekursiv] Eine Funktion hei"st so, wenn sie durch endlich viele
Anwendungen von Einsetzungen und Induktion basierend auf den Grundfunktionen
darstellen l"a"st.\\
Ein Pr"adikat hei"st primitiv rekursiv, wenn seine Indikatorfunktion primitiv
rekursiv ist. \\
\textit{Jede primitiv rekursive Funktion ist berechenbar und jedes Pr"adikat
(jede Sprache) mit primitiv rekursiver Indikatorfunktion ist entscheidbar.}
\item[Beispiele] Addition, Multiplikation, Potenzierung, Fakult"at,
Vorg"angerfunktion, modifizierte Differenz, jede Minimums-/Maximumsfunktion,
die Signum-Funktion, die Differenz, $\mod(x_1,x_2)$, $div(x_q,x_w$, die
Pr"adikate gerade, ungerade, Teiler, vielfaches, $<$, $>$ etc., alle booleschen
Ausdr"ucke
\item[Endliche Summe "uber $\psi$]
$\psi:\mathbb{N}^{n-+1}\rightarrow\mathbb{N}$ sei primitiv rekursiv, dann ist 
$$\psi_\Sigma(z,x_1,\ldots,x_n):=\Sigma_{y<z}\psi(x_1,\ldots,x_n,y)$$
auch primitiv rekursiv.
\item[Beschr"ankte Eigenschaften] Genauso gilt wenn $A$ primitiv rekursives Pr"adikat
auf sind $\mathbb{N}^n$ ist: $\exists_{y<x}A(x_1,\ldots,x_{n-1},y)$
und $\forall_{y<x}A(x_1,\ldots,x_{n-1},y)$ primitiv rekursive Pr"adikate auf
$\mathbb{N}^n$.
\item[Beschr"ankte eindeutige Existenzeigenschaft] $A$ sie wieder primitiv
rekursives Pr"adikat auf $\mathbb{N}^n$. Dann ist auch primitiv rekursiv
$\exists_{y<z}^1 A(x_1,\ldots,x_{n-1},y)$
\end{entry}

Es stellt keine Einschr"ankung dar, da"s wir bei Turingmaschinen stets
Eingabeworte haben, die aus Elementen eines endlichen Eingabealphabets
zusammengesetzt sind, und bei p. r. Funktionen nur mit nat"urlichen Zahlen
rechnen, da man diese Elemente in eine $(n+1)$-"are Darstellung (bei $n$
Elementen im Eingabealphabet) verstehen kann.

\begin{entry}
\item[Goldbachsche Vermutung] $\forall_{a>2}(a \text{ gerade}): \exists_{x<a}
x \text{ prim} \wedge (a \dot{-} x) \text{ prim}$
\item[Beschr"ankter $\mu$-Operator] Sei $A(x_1,\ldots,x_{n-1},y)$ p.r.
Pr"adikat. Dann ist 
$$\mu_{y<z}A(x_1,\ldots,x_{n-1},y)=
\begin{cases}
min\{y<x|A(x_1,\ldots,x_{n-1},y)\} & \text{falls ein solches y existiert} \\
z & \text{sonst} \\
\end{cases}$$
$\mu_{y<z}A(x_1,\ldots,x_{n-1},y)$ ist primitiv rekursiv.
\item[Ackermannfunktion] Die Funktion $a:\mathbb{N}^2\rightarrow\mathbb{N}$
ist definiert als
\begin{align}
a(0,y) & = y+1 \notag \\
a(x+1,0) & = a(x,1) \notag \\
a(x+1,y+1) & = a(x,a(x+1,y)) \notag
\end{align}
mit den Eigenschaften:
\begin{enumerate}
\item $a(x,y)>x$
\item $a(x,y)>y$
\item Monotonie in $x$: $x_2 > x_1 \rightarrow a(x_2,y)\geq a(x_1,y)$
\item $a(x,y+1)>a(x,y)$
\item Monotonie in $y$: $y_2 > y_1 \rightarrow a(x,y_2)> a(x,y_1)$
\item $a(x+1,y)\geq a(x,y+1)$
\item $a(x+2,y)\geq a(x,2y)$
\end{enumerate}
Die Ackermannfunktion w"achst schneller als jede primitiv rekursive Funktion.
Formal: $f:\mathbb{N}^n\rightarrow\mathbb{N}$ primitiv rekursiv, dann gibt es
einen Tempoparameter $k$, so da"s
$$\forall_{\vec{x}\in\mathbb{N}^n}f(\vec{x})<a(k,MAX\{x_1,\ldots,x_n\})$$
Die Ackermannfunktion ist primitiv rekursiv.
\item[Unbeschr"ankter $\mu$-Operator] Sei $A(x_1,\ldots,x_{n-1},y)$ p.r.
Pr"adikat. Dann ist 
$$\mu A(x_1,\ldots,x_{n-1},y)=
\begin{cases}
min\{y\in\mathbb{N}|A(x_1,\ldots,x_{n-1},y)\} & \text{falls ein solches y existiert} \\
0 & \text{sonst} \\
\end{cases}$$
Durch Hinzunahme des unbeschr"ankten $\mu$-Operator wird die Menge der
primitiven $\mu$-rekursiven Funktionen zur Menge der $\mu$-rekursiven
Funktionen erweitert. Die Menge der mit dem unbeschr"ankten $\mu$-Operator
entscheidbaren Pr"adikate entspricht genau den rekursiv aufz"ahlbaren
Sprachen.
\item[G"odels Unvollst"andigkeitssatz] Nach der Definition der Formel $\rho_L$
der Peano-Arithmetik f"ur jede rekursiv aufz"ahlbare Sprache $L$ gilt, da"s
$$x\in L\Leftrightarrow\rho_L(x)\text{ ist wahr}$$
Wenn nun Wahrheit und Beweisbarkeit "ubereinstimmen folgt also
$$x\in L\Leftrightarrow\rho_L(x)\text{ ist aus Peanos Axiomen ableitbar}$$ und
damit 
\begin{align}
x\not\in L & \Leftrightarrow \neg\rho_L(x)\text{ ist wahr} \notag \\
& \Leftrightarrow(\neg\rho_L(x))\text{ ist ableitbar} \notag
\end{align}
Damit w"are aber $\overline{L}=\{x|(\neg\rho_L(x))\text{ ist ableitbar}\}$ und
damit ist $\overline{L}$ rekursiv aufz"ahlbar.\\
Also ist f"ur jede rekursiv aufz"ahlbare Sprache $L$ auch ihr Komplement
rekursiv aufz"ahlbar und jede rekursiv aufz"ahlbare Sprache ist auch rekursiv,
was ein Widerspruch w"are, da $\overline{D}$ rekursiv aufz"ahlbar ist, wir
aber die Nicht-Rekursivit"at nachgewiesen haben.
\item[Probabilistische Turingmaschinen und Quantenrechner] Turingmaschinen und
Registermaschinen sind gleichm"achtig, wobei die Turingmaschinen sogar nur
polynomiell langsamer sind. Auch parallele Registermaschinen k"onnen durch
Turingmaschinen simuliert werden und zwar in Zeit $poly(n+t(n))+p(n)$ bei
Laufzeit von $t(n)$ der parallelelen RM $\rightarrow$ ein weiterer Grund f"ur
die Annahme, da"s die Churchsche These richtig ist. \\
Nichtdeterministische Maschinenmodelle dienen nicht zur Rechenzeitmessung
realer Rechner. Sie bilden ein Rechnermodell f"ur die Klasse $NP$ und
unterst"utzen die komplexit"atstheoretische Klassifikatione von Problemen.\\
\item[Probabilistische TM] M wird beschrieben durch den Vektor
$$M=(Q,\Sigma,\delta,q_0,\Theta,F)\text{ bzw. }M=(Q,\Sigma,\delta,q_0,\Theta)$$
Dabei ist $\delta:\Theta\times Q\times\Theta\times
Q\times\{links,rechts,bleib\}\rightarrow[0,1]\cap\mathbb{Q}$ und wei"st jedem
m"oglichen "Ubergang eine Wahrscheinlichkeit zu. Dabei gilt
$$\Sigma_{(\gamma',q',Richtung)\in\Theta\times Q\times\{links,bleib,rechts\}}
\rho(\gamma,q,\delta',q',Richtung)=1$$
\textbf{Die von M akzeptierte Sprache} ist dann $L_M=\{x\in\Sigma^\ast |p_x>
\frac{1}{2}\}$. \\
Falls $\forall x\not\in L \exists\varepsilon >0:
p_x\leq\frac{1}{2}-\varepsilon$ und $\forall x\in L \exists\varepsilon >0:
p_x\geq\frac{1}{2}+\varepsilon$, dann hat $M$ einen \textbf{beschr"ankten
Fehler}. Damit wird bei $k$-maligem Anwenden der Turingmaschine auf eine
Eingabe $x$ ein Fehler mit einer Wahrscheinlichkeit von h"ochstens
$2^{-\Omega(k)}$ auftreten.
\item[Quantenrechner] Die Struktur "ahnlet der der probabilistischen
Turingmaschine, jedoch ist $\delta$ wie folgt definiert:
$$\delta :\Theta\times Q\times\Theta\times Q\times\{links,bleib,rechts\}
\rightarrow\mathbb{C}\cap\mathbb{Q}+i\mathbb{Q}$$
allerdings nur mit komplexen Zahlen der L"ange von h"ochstens 1. Diesmal mu"s
gelten
$$\sigma_{\gamma,q,\gamma',q',Richtung}|\rho(\gamma,q,\gamma',q',Richtung|^2=1$$
Wenn ein Quantenrechner $Q$ in Zeit $t(n)$ rechnet, dann gibt es eine
deterministische Turingmaschine $M$, die auf Platz $O(t^2(n))$ die Sprache
$L_Q$ erkennt. Hierzu ist aber die Forderung einesbeschr"ankten Fehlers ebenso
notwendig wie die Forderung, da"s die Konfigurationsmatrix $A_Q$ unit"ar ist.
\end{entry}

\item[Fragen]
\begin{itemize}
\item Beispiele: "'berechenbar"'? Wichtige Punkte!
\item Definition: r.a. und entscheidbaren Sprachen
\item Definition: entscheidbar
\item Definition: $H_\epsilon$ und $\overline{H_\epsilon}$?
\item Reduktion von $H \leq_p H_\epsilon$?
\item Beispiel: Sprachen, die weder selbst noch ihr Komplement rekursiv aufz"ahlbar sind? ($L=\left\{<M> | M \text{ h"alt immer} \right\}$)
\item Beweis: $\overline{L}$ nicht r.a. (mit Reduktion $\overline{H_\epsilon} \leq \overline{L}$)
\item Beispiel: rekursiv aufz"ahlbare Sprachen! ($\left\{<M>|M \text{ h"alt auf mindestens einem} w\in \Sigma^\ast \right\}$)
\item Beispiel: nicht rekursiv aufz"ahlbare Sprachen!
\item Halteproblem (Komplement auch r.a.? -Nein, weil sonst entscheidbar; Beweis: 2 Turingmaschinen verzahnt laufen lassen) 
\item Beweis: $L$ r.a. und $L$ nicht entscheidbar $\Rightarrow$ $\overline{L}$ nicht r.a.
\item Beispiel: Sprache, die weder rekursiv, noch r.a. ist?
\item Beispiel: Sprache $L$, f"ur die weder $L$ noch $\overline{L}$ r.a. ist! ($\left\{<h>|h \text{ h"alt nicht}\right\}$)
\item Satz von Rice
\item Rekursionstheorem
\item Church'sche These? Kann sie widerlegt werden (BILD)?
\item M"achtigkeit der rekursiv aufz"ahlbaren Sprachen?
\item Reduktion m-Band TM auf 2 Band-TM
\item G"odelscher Unvolst"andigkeitssatz
\end{itemize}
\end{type}

%----------------------------------
\subsection{$NP$-vollst"andigkeit}
%----------------------------------
Welche Probleme sind effizient berechenbar, welche nicht? \\
Wir unterscheiden 3 Varianten von Optimierungsproblemen:
\begin{itemize}
\item Maximierungs-/Minimierungsproblem: Berechnung einer L"osung deren
Wert maximal/minimal ist.
\item Zahlvariante: Es soll der Wert einer optimalen L"osung berechnet werden.
\item Entscheidungsvariante: F"ur ein Limit soll entschieden werden, ob es
oberhalb (bei Maximierungsproblemen) oder unterhalb (bei
Minimierungsproblemen) der optimalen L"osung liegt.
\item M
\end{itemize}
\begin{type}
\item[Komplexit"atsklasse $P$] Menge aller Sprachen $L$, die sich in
polynomieller Zeit berechnen lassen:
$L\in P \Leftrightarrow \exists$ (stets haltende) Turingmaschine $M$ und
eine Konstante $k$ mit $L=L(M)$ und $Zeit_M(n)=O((n+1)^k)$ (die
worst-case-Laufzeit ist also polynomiell in der Eingabel"ange).\\
$L$ ist effizient berechenbar $\Leftrightarrow$ $L\in P$ (Achtung: ist in
allen Rechnermodellen dasselbe!). \\
Ein Problem ist sicher nicht in $P$, wenn es nicht rekursiv ist, oder die
L"ange der Ausgabe nicht polynomiell beschr"ankt ist. Man kann aber auch
zeigen, da"s alle Algorithmen zur Probleml"osung mehr als polynomielle Zeit
ben"otigen, was aber sehr schwer ist. \\
Beispiele: 
\begin{align*}
&Zh=\{code(G)|G\text{ ist ein ungerichteter, zusammenh"angender Graph}\} \\
&Bipartit=\{code(G)|G\text{ ist ein ungerichteter, bipartiter Graph}\} \\
&Match=\{1^k0code(G)|G\text{ besitzt k Kanten, die keinen Endpunkt gemeinsam haben.}\}
\end{align*}
Oder: $L\in NP$ $\Rightarrow$ Es gibt eine (deterministische) TM $M$, mit
$L=L(M)$ und $Zeit_M(n)\leq 2^{polynom(n)}$.

\item[Komplexit"atsklasse $NP$] Probleme, die sie (wahrscheinlich) nicht
effizient l"osen lassen, aber effizient l"osbar sind, wenn geraten werden
darf, da sich dann eine richtige L"osung kurz und effizient verifizieren
l"a"st. \\
Die Sprache $L$ geh"ort zur Komplexit"atsklasse $NP$, wenn es eine
nichtdeterministische TM $M$ gibt mit $L=L(M)$ und $Zeit_M=O((n+1)^k)$ (bei
Eingabl"angen $n$ f"ur eine nat"urliche Zahl $k$).

\item[Nichtdeterministische TM] $(Q,\Sigma,\delta,q_0,\Gamma,F)$, wobei
$\delta\subseteq Q\times\Theta\times
Q\times\Theta\times\{links,bleib,rechts\}$. F"ur eine gegebenen Zustand $q$
und ein gelesenes Zeichen kann es also m"oglicherweise mehrere anwendbare
Befehle geben, aus denen $M$ ausw"ahlen kann.
\begin{entry}
\item[$M$ akzeptiert $w\in\Sigma^\ast$] $\Leftrightarrow$ Es gibt eine
Berechnung von $M$, die auf Eingabe $w$ in einem akzeptierenden Zustand h"alt
(umgekehrt genauso).
\item[Die von $M$ akzeptierte Sprache] $L(M)=\{w\in\Sigma^\ast|M\text{
akzeptiert }w\}$
\item[Laufzeit] Worst-case: f"ur Eingabel"ange $n$ das Maximum der Laufzeiten
aller akzeptierten Eingaben der L"ange $n$.\\
$Schritte_M(w)=$die minimale LAufzeit einer akzeptierenden Berechnung von $M$
auf Eingabe $w$\\
$Zeit_M(n)=max\{Schritte_M(w)|w\in\Sigma^n\}$
\end{entry}

\item[CLIQUEN-Problem] F"ur einen ungerichteten Graphen $G$ und eine Zahl
$k\in\mathbb{N}$ ist gefragt, ob es eine Knotenteilmenge der Gr"o"se $k$ von
$G$ gibt, in der je zwei Knoten durch eine Kante verbunden sind.

\item[Vertex Cover-Problem] $VC=\{code(G,k)|$Es gibt eine Knotenmenge "U von
h"ochstens k Knoten, so da"s jede Kante mindestens einen Endpunkt in "U
besitzt$\}$

\item[Set Cover] $SC=\{code(A_1,\ldots,A_r,k)|$Es gibt h"ochstens $k$ Mengen
$A_{i_1},\ldots,A_{i_k}$ mit $\bigcup_{j=1}^k A_{i_j}=\bigcup_{l=1}^r A_l\}$.

\item[Independent Set-Problem] $IS=\{code(G,k)|$Es gibt eine Knotenmenge $U$
von mindestens $k$ Knoten, so da"s keine zwei Knoten von $U$ durch eine Kante
verbunden sind$\}$.

\item[Null-Eins-Programmierproblem] Eine Matrix $A$ mit $n$ Zeilen und $m$
Spalten ist gegeben mit zwei Vektoren $b=(b_1,\ldots,b_n)$ und
$c=(c_1,\ldots,c_m)$, sowie eine Zahl $k$ uns es ist gefragt, ob ein
$x\in\{0,1\}^m$ existiert mit $A\cdot x\leq b$ komponentenweise und
$\Sigma_{i=1}^m c_i\cdot x_i\geq k$.\\
Beim ganzzahligen Programmierproblem ist $x\in\mathbb{N}^m$.

\item[Traveling Salesman Problem] Vollst"andiger Graph
$V_n=(\{1,\ldots,n\},\{\{i,j\}|i\not =j\})$ mit $n$ Knoten. Jede Kante $e$ hat
eine L"ange $l"ange(e)$ und $G$ hat eien Tour der L"ange h"ochstens $B$m falls
es einen Kreis gibt, der jeden Knoten genau einmal furchl"auft und dessen
Summe der Kantenl2angen h"ochstens $B$ ist.

\item[Hamiltonsches Kreis-Problem] Ungerichteter Graph $G$. Ein $HC$ ist ein
Kreis, der jeden Knoten genau einmal durcl"auft, damit ist
$HC=\{code(G)|G$ besitzt einen Hamiltonschen Kreis$\}$. \\
Das Analoge Problem im gerichteten Graph wird $DHC$ genannt.

\item[L"angste Wege] $LW=\{code(G,k)|G$ besitzt einen Weg der L"ange
mindestens $k\}$.

\item[MINIMUM-COVER-Problem] Sei $M=\{M_1,\ldots,M_m\}$ mit $M_1\ldots M_m\subseteq
U$. Gibt es ein minimales $C\subseteq U$ mit $\bigcup_{M_i\in C}M_i=U$?
Ebenfalls $NP$-volst"andig.

\item[$P\subseteq NP$] Eine deterministische TM ist auch eine
nichtdeterministische TM.

\item[Polynomiell reduzierbar] $L_1\subseteq\Sigma_1$ und $L_2\subseteq\Sigma_2$
seien zwei Sprachen. $L_1$ ist auf $L_2$ reduzierbar (also: $L_1\leq_p L_2$),
wenn es eine TM $M$ gibt mit:
\begin{itemize}
\item $M$ l"auft in polynomieller Zeit
\item $M$ gibt f"ur alle $w\in\Sigma_1^\ast$ die Ausgabe
$M(w)\in\Sigma_2^\ast$, wobei gilt: $w\in\L_1\Leftrightarrow M(w)\in L_2$
\end{itemize}
Die Relation $\leq_p$ ist reflexiv und transitiv. Es gilt: $L_1\leq_p L_2
\wedge L_2\in P \Rightarrow L_1\in P$. \\
Das Reduktionskonzept $\leq_p$ bezieht sich nur auf Entscheidungsprobleme,
$\leq_T$ dagagen auf allgemeinere Probleme.

\item[$NP$-vollst"andig] $L$ ist $NP$-vollst"andig $\Leftrightarrow$
$L\in NP \wedge \forall K\in NP: K\leq_p L$

\item[$NP$-hart] $L$ ist $NP$-hart $\Leftrightarrow$ $\forall k\in NP:
K\leq_p L$

\item[S"atze] $L_1$, $L_2$, $L_3$ und $L$ Sprachen.
\begin{enumerate}
\item $L_1\leq_p L_2$ und $L_2\in P$ $\Rightarrow$ $L_1\in P$
\item $L$ ist $NP$-volst"andig und $P\not = NP$ $\Rightarrow$ $L \not \in P$
\item $L_1\leq_p L_2$ und $L_2\leq_p L_3$ $\Rightarrow$ $L_1\leq_p L_3$
\item $L_1$ $NP$-vollst"andig und $L_1\leq_p L_2$ $\Rightarrow$ $L_2$ ist
$NP$-hart. Wenn gilt $L_\in NP$, dann $L_2$ ist $NP$-vollst.
\end{enumerate}

\item[KNF-SAT] $KNF-SAT=\{code(\alpha)|\alpha \text{ ist eine Formel in
konjunktiver Normalform und } \alpha \text{ ist erf"ullbar}\}$ also
$\alpha \equiv k_1\wedge k_2\wedge \ldots \wedge k_r$ mit $k_i$ Disjunktion
von Literalen.

\item[$k$-SAT] $k-SAT=\{code(\alpha)\in KNF-SAT|\alpha\text{ besitzt h"ochstens
k Literale pro Klausel}\}$ ist eine Abschw"achung  von $KNF-SAT$.

\item[Praktische Beispiele] 
\begin{entry}
\item[VLSI-Entwurf] Das Problem der
Schaltkreisminimierung ist $NP$-hart(weil der Algortihmus eine nucht
erf"ullbare Formel auf die 0 minimieren w"urde). Das Problem zu entscheiden, ob zwei
vorgelegte Schaltkreise verschieden Funktionen berechnen sogar
$NP$-vollst"andig (Vorgehen "ahnlich, Vergleich mit 0).
\item[Ressourcenverteilung in Betriebssystemen] \textbf{PARTITION-Problem}:
$\Sigma_{i\in I}t_i=\Sigma_{i\in\{1,\ldots,n\}\backslash I}t_i$ \\
\textbf{SUBSET-SUM-Problem}:
$\Sigma_{i\in I}=Z$ wobei gilt: SUBSET-SUM$\leq_p$PARTITION, da man die Summe
aller Werte von $T+1$ auf $2T+2$ erh"ohen kann; dann ist eine Zerlegung in
zwei Teilmengen der Gr"o"se $T+1$ m"oglich.
\item[Datenbanken (Schl"ussel)] Anwendung des MINIMUM-COVER-Problems:
MINIMUM-COVER$\leq_p$KEY-FIND (Sei $U=\{u_1,\ldots,u_k\}$ und
$M=\{M_1,\ldots,M_m\}$ und $k$ die erlaubte Gr"o"se des Covers. Nun richte man
f"ur jede Menge in $M$ ein Attribut ein und f"ur jedes $u_i\in U$ zwei
Datens"atze $d_i$ und $d'_i$ mit Attribut $n$, wenn $u_i$ nicht in $M_n$
enthalten ist, ansonsten erhalten $d_i$ und $d'_i$ die Werte $i$ bzw. $-i$.
\item[Gewinnstrategien bei Spielen] Finden der optimalen Gewinnstrategie:
$$F=\forall_{x_1}\exists_{x_2}\forall_{x_3}\exists_{x_4}\ldots\forall{x_{n-1}}
\exists_{x_n}E(x_1,\ldots,x_n)$$
wobe $E$ ein Pr"adikat der Aussagenlogik ist, das wahr ist. Das Finden einer
Belegung von $F$ die zu einem wahren Ergebnis f"uhrt ist $NP$-hart.
\end{entry}

\item[$NP$-Vollst"andigkeits-Nachweise]
Beim Nachweis der $NP$-Vollst"andigkeit verwendet man verschiedene
Strategien der polynomiellen Reduktion: die Restriktion, die lokale
Ersetzung und die Transformation mit verbundenen Komponenten:\\
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
Restriktion & lokale Ersetzung & Transformation \\
\hline \hline
SAT$\leq_p$SAT$^\ast$ (trivial) & SAT$\leq_p$3-SAT & 3-SAT$\leq_p$CLIQUE \\
KP$^\ast\leq_p$KP (trivial) & DHC$\leq_p$HC & 3-SAT$\leq_p$DHC \\
PAR$\leq_p$BPP & 3-SAT$\leq_p$KP$^\ast$ & \\
HC$\leq_p$TSP & & \\
KP$^\ast$ $\leq_p$PAR & & \\
\hline
\end{tabular}
\end{center}

\begin{entry}
\item[Restriktion] Geeignet, um recht "ahnliche Probleme aufeinander zu
reduzieren, insbesondere, wenn das Problem, von dem die Restriktion
ausgeht, ein (im weiteren Sinne) Spezialfall des anderen Problems ist.
\item[Lokale Ersetzung] Wieder gut f"ur "ahnliche Probleme, besonders
geeignet, wenn ein allgemeines Problem auf einen Spezialfall oder ein
Spezialfall auf einen anderen reduziert werden soll.
\item[Transformation] Geeignet, um verschiedenartige Probleme aufeinander
zu reduzieren. Es werden h"aufig Komponenten mit sehr speziellen
Eigenschaften ben"otigt.
werden soll.
\item[CLIQUE$\in$NP] Entwerfe nichtdet. 3-Band-TM $M$, Eingabe
$w\in\{0,1\}^\ast$ auf Band 1.
\begin{enumerate}
\item $M$ "uberpr"uft, ob $w=1^k01^n0code(G)$ (wobei
$code(G)$ die Adjazenzmatrix des Graphen $G$ zeilenweise hintereinander
geschrieben $\rightarrow$ 0-1-Bitvektor der L"ange $n^2$) also
$|code(G)|=n^2$ $\rightarrow$ geht in Zeit polynomiell in $n$
\item $M$ r"at Knotenmenge und speichert zugeh"origen Inzidenzenvektor auf
Band 2 und Band 3 (dabei bleibt der erste Kopf stehen und die anderen beiden
schreiben die (gleiche) Vermutung auf Band 2 und 3)
\item $M$ verifiziert, ob geratene Knotenmenge einer Clique der Gr"o"se mind.
$k$ entspricht, pr"uft also, ob $n$ Bits auf Band 2 geschrieben wurden,
mindestens $k$ Einsen geraten wurden und geratene Knotenmenge eine Clique ist
(Kopf 1 l"auft pro Takt einen Schritt nach rechts, Kopf 2 l"auft alle $n$
Takte einen Schritt nach rechts und Kopf 3 l"auft pro Takt einen Schritt nach
rechts, wird allerdings alle $n$ Takte auf die $i-te$ Position zur"uck).
\end{enumerate}

\item[KNF-SAT ist $NP$-vollst"andig (Satz von Cook)] Sei $L\in NP$, dann existiert eine
nichtdeterministische TM $M_L$ mit $L=L(M_L)$ und $M_L$ hat polynomielle
Laufzeit und es gibt f"ur jedes Wort $w\in L$ eine akzeptierende Berechnung
der L"ange h"ochstens $polynom(|w|)$.\\
Sie $Q=\{0,q,\ldots,q\}$ und $\Gamma=\{0,1,B\}$ mit 0 ist Anfangszustand und 1
der einzig akzeptierende Zustand und $M_L$ h"alt stets, wenn Zustand 1
erreicht wird. Zu zeigen: F"ur jede Eingabe $w$ kann eine Formel $\alpha_w$ in
konjunktiver Normalform konstruiert werden, so da"s: $\alpha_w\in$KNF-SAT
$\Leftrightarrow$ Es gibt eien Berechnung von $M_L$, die $w$ akzeptiert, wobei
die Funktion $w\mapsto\alpha_w$ von einer transformierenden TM $M$ in
(deterministisch) polynomieller Zeit konstruierbar sein mu"s. Nun konstruieren
wir eine Formel $\alpha$, die alle Bedingungen an die TM $M$ ausdr"uckt. \\
Der Beweis enth"alt zun"achst eine "Ubertragung von nichtdeterministischen
Turingmaschinen in den Rate-Verifikations-Modus und dann die Codierung
polynomiell langer Rechenwege durch die Konjunktion polynomiell vieler in
polynomieller Zeit berechenbarer Klauseln. Dabei sind die Klauseln genau dann
gemeinsam erf"ullbar, wenn es einen akzeptierenden Rechenweg der gegebenen TM
gibt. \\
Die nichtdeterministische TM, die das Problem aus NP l"ost wird durch die
Variablen des Boolschen Ausdrucks beschrieben: Die Kopfposition, der
Bandinhalt an der aktuellen Position und der aktuelle Zustand.


\item[KNF-SAT$\leq_p$3-SAT] Sei die Eingabe $\alpha\equiv
k_1\wedge\ldots\wedge k_r$ und $M$ transformiert eine Klausel $k_i$ in eine
Konjunktion $k_{i,1}\wedge\ldots\wedge k_{i,r_i}\equiv\alpha_i$ von Klauseln
mit h"ochstens drei Literalen, wobei $k_i$ wenn $k_i=y_1\vee\ldots\vee y_l$ mehr
als 3 Literale besitzt in neue Klauseln umgeformt wird:
\begin{align}
k_{i,1} & \equiv y_1 \vee y_2 \vee z_{i,1} \notag \\
k_{i,2} & \equiv \neg z_{i,1} \vee y_3 \vee z_{i,2} \notag \\
k_{i,3} & \equiv \neg z_{i,2} \vee y_4 \vee z_{i,3} \notag \\
        & \vdots \notag \\
k_{i,l-3} & \equiv \neg z_{i,l-4} \vee y_{l-2} \vee z_{i,l-3} \notag \\
k_{i,l-2} & \equiv \neg z_{i,l-3} \vee y_{l-1} \vee y_l \notag
\end{align}
Damit sind alle Klauseln $k_{i,1},\ldots ,k_{i,l-2}$ wahr f"ur $z_{i,1}=\ldots
=z_{i,j-2}=wahr$ und $z_{i,j-1}=\ldots =z_{i,l-3}=falsch$. \\
Also ist
\begin{align}
& \alpha\in KNF-SAT \notag \\
\Leftrightarrow & \text{Es existiert eine Belegung, die jede der Klauseln }
k_1,\ldots,k_r \text{ wahr macht.} \notag \\
\Leftrightarrow & \text{Es gibt eine Belegung, die alle Formeln }
\alpha_1,\ldots,\alpha_r \text{ wahr macht.} \notag \\
\Leftrightarrow & M(\alpha)\in 3-SAT \notag
\end{align}

\item[3-SAT$\leq_p$CLIQUE] TM $M$ konstruieren, so da"s gilt:
$$\alpha\in 3-SAT \Leftrightarrow M(\alpha)\in CLIQUE$$
Sei $\alpha\equiv k_1\wedge\ldots\wedge k_r$ mit $k_i\equiv
l_{i,1}\vee l_{i,2}\vee l_{i,3}$, wobei $M$ der Formel $\alpha$ einen Graphen
$G(\alpha)$ zuweist, der f"ur jede Klausel $k_i$ eine Gruppe
$g_i=\{(i,1),(i,2),(i,3)\}$ von 3 Knoten besitzt und damit $\bigcup_{i=1}^r
g_i=V$. Die Knoten einer Gruppe sind nicht mit Kanten verbunden und wir
verbinden die Knoten $(i,r)$ und $(j,s)$ mit $i\not = j$ nur dann nicht, wenn
$l_{i,r}\equiv\neg l_{j,s}$ (wenn also $l_{i,r}$ und $l_{j,s}$ nicht beide
simultan erf"ullbar sind). Es ist also $M(\alpha):=(r,3r,G(\alpha))$

\item[CLIQUE$\leq_p$IS] Wenn $G=(V,E)$, dann ist
$\overline{G}=(V,\overline{E})$ mit $\overline{E}=\{\{i,j\}|i\not = j \text{
und } \{i,j\}\not\in E\}$ und damit: $C$ ist CLIQUE in $G$ $\Leftrightarrow$
$C$ ist unabh"angige Menge f"ur $\overline{G}$, also
$M((G,k))=(\overline{G},k)$

\item[IS$\leq_p$VC] $I$ ist unabh"angige Menge $\Leftrightarrow$ $V\setminus I$
ist Knoten"uberdeckung. und somit $M((G,k))=(G,|V|-k)$.

\item[VC$\leq_p$SC] Sei $(G,k)$ die Eingabe und $A_i=\{e\in E|e \text{ besitzt
i als Endpunkt}\}$. Dann ist: $"U\subseteq V$ Knoten"uberdeckung
$\Leftrightarrow$ $\forall e\in E$ besitzt Endpunkt in "U $\Leftrightarrow$
$\bigcup_{i\in "U}A_i=\bigcup_{j=1}^n A_j=E$. Also
$M((G,k))=(A_1,\ldots,A_n,k)$

\item[KNF-SAT$\leq_p$Null-Eins-Programmierung] Sei $\alpha\equiv
k_1\wedge\ldots\wedge k_t$ mit $k_i =x_{i_1}\vee x_{i_2}\vee\ldots\vee x_{i_m}$ mit
$x_{i_j}\in\{b_1,\overline{b_1},\ldots,b_n,\overline{b_n}\}$ und wir
transformieren ein Null-Eins-Programm mittels $\Phi(code(\alpha))=(A,b,c,k)$.
Jede Klausel $k_i$ der Formel $\alpha$ wird umschrieben durch
$\Sigma_{i\in J}x_i + \Sigma_{i\not\in J}(1-x_i)\geq 1$ mit
$J\subseteq\{1,\ldots,n\}$ die Menge der Variablen, die nicht negiert in $k_i$
vorkommen. Aus den Gleichungen$(\ast)_i$ mit $1\leq i\leq t$ f"ur alle
Klauseln erh"alt man die Matrix $-A$, der Vektor $b=-I=(-1,\ldots,-1)$. F"ur
die Bildung von $c$ und $k$ kann man einfach die Ungleichung f"ur $k_1$ nehmen
und von dieser $c^T$ und $k$ ableiten.

\item[Null-Eins-Programmierung$\leq_p$Ganzzahlige Programmierung] ?

\item[DHC$\leq_p$HC] Aus dem gerichteten Graphen $G=(V,E)$ konstruieren wir
einen ungerichteten Graphen $G'=(V',E')$, so da"s $G$ einen HC besitzt
$\Leftrightarrow$ $G'$ einen besitzt. Dazu spalten wir jeden Knoten $v$ in $G$
in drei Knoten auf: $(v,ein),(v,mitte),(v,aus)$. 

\item[HC$\leq_p$TSP] F"ur eine Eingabe $G$ mit Knotenmenge $V=\{1,\ldots,n\}$
w"ahlen wir den vollst"andigen Graphen $V_n$ und definieren
$$l"ange(\{i,j\})=\begin{cases}
1 & \text{wenn } \{i,j\}\in E \\
2 & \text{sonst} \end{cases} $$
mit $B=n$. Somit ist $M(G)=(V_n,l"ange,B)$

\item[HC$\leq_p$LW] Sei $G$ ungerichtet, $V=\{1,\ldots,n\}$. $G$ besitzt genau
dann einen HC, wenn $G$ einen Weg der L"ange $n-1$ besitzt, der in Knoten 1
beginnt und mit Nachbarn vom Knoten 1 endet. Jetzt erfinden wir einen neuen Knoten $1'$, den wir zu $G$ hinzuf"ugen und
verbinden ihn mit allen Nachbarn von 1. Dann erfinden wir zwei weitere Knoten
0 und $0'$ und verbinden 0 mit 1 und $0'$ mit $1'$. Sie nun
$G'=\{0,1,\ldots,n,0',1'\}$, dann folgt
\begin{align}
G \in HC & \Leftrightarrow \text{G hat einen Weg der L"ange n-1, der in 1
beginnt und mit einem Nachbarn von 1 endet} \notag \\
& \Leftrightarrow \text{G' hat einen Weg der L"ange n+2} \notag
\end{align}

\item[3-SAT$\leq_p$DHC] Gegeben ist die Fromel $\alpha_i\equiv l_{i,1} \vee
l_{i,2}\vee l_{i,3}$ mit $\alpha_i\equiv l_{i,1}\vee l_{i,2}\vee l_{i,3}$,
Dabei sei angenommen, da"s genau die Variablen $X_1,\ldots,x_n$ (bzw. ihre
Negation) in $\alpha$ vorkommen. Nun konstruieren wir den gerichteten Graphen
$G(\alpha)$ in polynomieller Zeit, so da"s gilt: $\alpha$ ist erf"ullbar
$\Leftrightarrow$ $G(\alpha)$ besitzt einen Hamiltonschen Kreis. \\
$G(\alpha)$ besteht aus den Variablenknoten $x_1,\ldots,x_n$ und $r$
Teilgraphen $G_1,\ldots,G_r$, wobei $G_i$ der Klausel $\alpha_i$ entspricht.
Jett f"ugren wir die Knoten wie folgt ein:\\
Alle $x_i$ haben zwei ausgehende Kanten (pos. und neg.). Die positive
bzw. negative Kante wird auf die erste Klausel gesetzt, in der $x_i$ bzw.
$\neg x_i$ vorkommt.\\
Dabei nehmen wir die Kante des ersten, zweiten oder dritten Literals, je
nachdem, an welcher Stelle $x_i$ vorkommt und verbinden sie mit $x_i$, dann
verbinden wir $1'/2'/3'$ mit der n"achsten Klausel, in der $x_i$ vorkommt.
Gibt es so eine nicht mehr, so verbinden wir die Kante mit $x_{i+1}$. \\
$G$ besitzt also $n+6m$ Knoten.

\item[3SAT$\leq_p$SUBSET-SUM] Sei $F=K_1\wedge K_2\wedge\ldots\wedge K_m$ mit
$K_i=(l_{i,1}\vee l_{i,2}\vee l_{i,3})$ mit
$l_{i,j}\in\{x_1,\overline{x_1},x_2,\ldots,x_n,\overline{x_n}\}$. Nun
konstruiere $Z=\underbrace{44\ldots 4}_{m-mal}\underbrace{11\ldots
1}_{n-mal}$. Die Menge $I$ mit den Zahlen, "uber denen die Summe gebildet
werden soll besteht aus $pos_1,\ldots,pos_n$ (Literal $x_i$: im linken, $m$
Stellen breiten Ziffernblock enth"alt $pos_i$ an Stelle $j$ eine 1, falls $x_i$
in Klausel $j$ auftaucht; im rechten Ziffernblock steht an Position $i$ eine
1), $neg_1,\ldots,neg_n$ (gleiches wie bei $pos_i$ nur f"ur $\overline{x_i}$),
$small_1,\ldots,small_m$ ($small_i$ enth"alt an Stelle $i$ im ersten
Ziffernblock eine 1) und $big_1,\ldots,big_m$ ($big_i:=2\cdot small_i$). \\
Also sind PARTITION und SUBSET-SUM $NP$-vollst"andig.

\item[Zusammenfassung]
$$SAT \begin{cases}
\leq_p^1 & SAT^\ast \\
\leq_p^2 & 3-SAT \begin{cases}
\leq_p^3 DHC \leq_p^2 HC \leq_p^1 TSP \\
\leq_p^3 CLIQUE \\
\leq_p^{2?} KP \begin{cases}
\leq_p^1 KP \\
\leq_p^{1?} PAR \leq_p^1 BPP
\end{cases}
\end{cases}
\end{cases}$$
\end{entry}


\item[Fragen]
%----------------------------------
\begin{itemize}
\item Was ist $NP$?
\item Wann ist eine Sprache $NP$-vollst.?
\item Gibt es "'vern"unftige"' Probleme $\not\in NP$? (z.B. Ist eine gegebene Zugfolge in einem Spiel optimal?)
\item Polynomielle Reduktion $\leq_p$ (formal, detailliert)
\item Sind alle Probleme in $NP$-entscheidbar? Ja, weil NDTM in DTM umwandelbar
\item Polynomielle Reduktion 3-SAT auf CLIQUE
\item Polynomielle Reduktion CLIQUE auf SAT
\item Satz von Cook (Beweisidee)
\item Was ist SAT?
\item Ist KNF-SAT NP-vollst"andig? (Grundidee)
\item Gibt es kontextfreie Sprachen, die $NP$-vollst. sind? (nein ,wegen CYK)
\item 4-SAT$\leq_P$CLIQUE
\item Gibt es eine kontextfreie Sprache, die NP-vollst. ist?
\item Wie kann man das TSP apporximieren?
\item Reduktion HC auf TSP
\end{itemize}

\end{type}

%----------------------------------
\subsection{Endliche Automaten}
%----------------------------------
Endliche Automaten bilden f"ur viele praxisrelevante Probleme das passende
Modell. Alle Schaltwerke lassen sich durch endliche Automaten darstellen und
schlie"slich bilden endliche Automaten Modelle f"ur VLSI-Chips und ganze
Rechner ohne virtuellen Speicher. Dabei sind Anzahl der Zust"ande und Speicher
austauschbare Begriffe (wenn $k$ Zust"ande ausreichen, gen"ugt eine Speicher,
der $k$ Informationen aufnehmen kann).
\begin{type}
\item[Endlicher Automat] $A=(Q,\Sigma,\delta,q_0,F)$ mit Eingabealphabet
$\Sigma$, endliche Menge $Q$ von Zust"anden, Anfangszustand $q_0$, Menge $F$
der akzeptierenden Zust"ande, Programm $\delta:Q\times\Sigma\rightarrow Q$. \\
$A$ liest nun eine Wort $w\in\Sigma^\ast$ von links nach rechts und wechselt
seine Zust"ande gem"a"s $\delta$. Bezogen auf Wort ist also
$\delta:Q\times\Sigma^\ast\rightarrow Q$ und $\delta(q,\varepsilon)=q$ und
$\delta(q,w_1\ldots w_{n+1})=\delta(\delta(q,w_1\ldots w_n),w_{n+1})$. \\
$A$ akzeptiert $w\in\Sigma^\ast$ $\Leftrightarrow$ $\delta(q_0,w)\in F$, wobei
$L(A)=\{w\in\Sigma^\ast|A\text{ akzeptiert }w\}$ die von $A$ akzeptierte
Sprache ist. \\
$L\subseteq\Sigma^\ast$ hei"st \textbf{regul"are Sprache} $\Leftrightarrow$ $\exists$ Automat
$A$ mit $L=L(A)$. \\
Der Automat l"a"st sich am besten durch ein Zustandsdiagramm verdeutlichen mit
Knoten $q_i$ und Kanten $(q,q')$, wenn $\delta(q,a)=q'$, und der
Kantenbeschriftung $a$.

\item["Aquivalente Zust"ande] Zwei Zust"ande $p,q\in Q$ hei"sen "aquivalent
($p\equiv_A q$) $\Leftrightarrow$ $\forall w\in \Sigma^\ast$ gilt:
$\delta(p,q)\in F\Leftrightarrow\delta(q,w)\in F$ \\
Dabei ist $\equiv_A$ eine "Aquivalenzrelation.

\item["Aquivalenzklassen] Mit $A=(Q,\Sigma,\delta,q_0,F)$ sei f"ur $p\in Q$:
$[P]=\{q\in Q|p\equiv_A q\}$ die \textbf{"Aquivalenzklasse} von $p$.\\
Der \textbf{"Aquivalenzklassenautomat} $A'$ von $A$ besitzt $Q=\{[p]|p\in Q\}$
mit Anfangszustand $[q_0]$ und $F'=\{[p]|p\in F\}$. Dabei ist
$\delta'([p],a)=[\delta(p,a)]$. $A'$ ist wohldefiniert und "aquivalent zu $A$.
\\
Oft ist es einfacher zu zeigen, da"s zwei Zust"ande nicht "aquivalent sind
anstatt umgekehrt. Daf"ur kann man sog. \textbf{Zeugen} $w\in\Sigma^\ast$
finden.

\item[Bestimmung "aquivalenter Zust"ande] Man konstruiere eine
Adjazenzlistendarstellung von $G$ und markiere alle Paare $\{p,q\}$ mit $p\in
F, q\not\in F$ oder $p\not\in F,q\in F$. F"uhre dann eine Tiefensuche an den
markierten Knoten durch, die alle besuchten Knoten markiert. \\
Die Laufzeit ist dann $O(|Q|^2\cdot |\Sigma|)$ (Korrektheit mit k"urzestem
Zeugen und Laufzeit mit Initialisierung $O(|Q|^2\cdot|\Sigma|)$, weil $G$
$\binom{|Q|}{2}=\Theta(|Q|^2)$ Knoten und h"ochstens
$\binom{|Q|}{2}\cdot|\Sigma|$ Kanten besitzt und dehalb die Tiefensuche
maximal Zeit $=(|Q|^2+|Q|^2\cdot|\Sigma|)=O(|Q|^2\cdot|\Sigma|)$ ben"otigt).

\item[Nerode-Relation $\equiv_L$] $L$ sei Sprache "uber $\Sigma$. Die
Nerode-Relation $\equiv_L$ f"ur Worte in $\Sigma^\ast$ ist wie folgt
definiert:
$$x\equiv_L y \Leftrightarrow (\forall w\in\Sigma^\ast: xw\in L\Leftrightarrow
yw\in L)$$
Mit dem \textbf{Index von $L$} definieren wir die Anzahl der
"Aquivalenzklassen von $\equiv_L$. Er beschreibt die Anzahl der Zust"ande des
minimalen endlichen Automaten, den wir aus der Nerode-Relation bauen k"onnen.

\item["Aquivalenzrelation $R_A$] $R_A$ ist eine rechtsinvariante
"Aquivalenzrelation (also: $u R_A v\Rightarrow uz R_A vz \forall x\in
\Sigma^\ast$ und reflexiv, transitiv, symmetrisch).\\
Sei $L=L(A)$, dann ist $x R_A y
\Leftrightarrow \delta(q_0,x)=\delta(q_0,y)$ mit $q_0$ Anfangszustand von
$A$. Dann:
\begin{itemize}
\item entsprechen die "Aquivalenzklassen von $R_A$ den nicht "uberfl"ussigen
Zust"anden von $A$.
\item gilt: $x R_A y \Rightarrow x\equiv_L y$
\item gilt mit der Zustandsmenge $Q$ von $A$: $|Q|\geq$Index von $L$
\end{itemize}

\item[Nerode-Automat $N_L$ f"ur $L$] 
\begin{itemize}
\item Die Zust"ande von$N_L$ sind "Aquivalenzklassen von $\equiv_L$
\item Anfangszustand ist $[\varepsilon]$
\item Akzeptierende Zust"ande: $F=\{[x]|x\in L\}$
\item Programm: $\delta([x],a)=[xa]$
\end{itemize}
$L=L(N_L)$ und $N_L$ ist minimal: Jeder Automat, der $L$ akzeptiert hat
mindestens so viele Zust"ande wie $N_L$. Dabei sind der
"Aquivalenzklassenautomat und der Nerode-Automat isomorph.

\item[Satz von Nerode] $L$ regul"ar $\Leftrightarrow$ Der Index von $L$ ist
endlich. \\
Damit ist dies eine hinreichende Bedingung f"ur die Regularit"at der
Sprache $L$.

\item[Minimierung endlicher Automaten] Sei $A=(Q,\Sigma,\delta,q_0,F)$.
\begin{enumerate} 
\item Alle Zust"ande, die von $q_0$ nicht erreicht werden k"onnen
sind "uberfl"ussig und k"onnen entfernt werden (Tiefensuche von $q_0$
durchf"uhren).
\item Konstruiere den "Aquivalenzklassenautomat (Markierungsalgorithmus) in
Zeit $O(|Q|^2\cdot |\Sigma|)$. Dabei bilden wir alle m"oglichen Paare von
Zust"anden und markieren zun"achst die Paare, die akzeptierende und nicht
akzeptierende Zust"ande beinhalten. Dann betrachten wir Zust"ande mit Zeugen
der L"ange 1 und markieren die Paare, die Zust"ande enthalten, die mit der
Eingabe eines Buchstabens in einen akzeptierenden bzw. nicht akzeptierenden
Zustand kommen usw. Die am Ende nicht markierten Paare bilden dann
"Aquivalenzklassen.
\end{enumerate}
Die Minimierungen, die vorgenommen werden sind naheliegend. Erst der Satz von
Nerode belegt, da"s der Automat auch minimal ist.

\item[Pumping-Lemma] Wann ist eine Sprache nicht regu"are (sprengt also die
Grenzen der Berechnungskraft endlicher Automaten)? \\
Sei $L$ regul"are. Dann ex. eine Pumpingkonstante $n$, so da"s jedes Wort
$z\in L$ mit $|Z|\geq n$ eine Zerlegung mit den folgenden Eigenschaften
besitzt:
\begin{itemize}
\item $z=uvw$, $|uv|\leq n$ und $|v|\geq 1$
\item $uv^i w\in L$ f"ur jedes $i\geq 0$
\end{itemize}
Wenn also die Worte der Sprache lang genug sind, dann gibt es ein nicht-leeres
Teilwort $v$, das "`aufgepumpt"¡ ($i\geq 1$) oder "`abgepumpt"¡ ($i=0$) werden
kann.) $\rightarrow$ Beweis mit endlichem Automat $A$ und Pumpingkonstante
$n=|Q|$ und $z\in L$ mit $z=z_1 z_2 \ldots z_s$ und $|z|=s\geq n$ beliebig,
also mu"s bei der Erkennung von $z$ ein Schleife durchlaufen worden
sein. \\
Um zu zeigen, da"s eine Sprache $L$ nicht regul"ar ist, m"ussen wir das
Pumping-Lemma falsifizieren:
\begin{itemize}
\item $\exists$(unbekannte) Pumpingkonstantre $n$
\item Wir w"ahlen "`geeignetes Wort"¡ $z\in L$ mit $|z|\geq n$
\item F"ur $z$ gibt es eine Zerlegung $z=uvw$ ($|uv|\leq n$, $|v|\geq 1$), so
da"s $uv^i w\in L$. Wir m"ussen also f"ur
jede m"ogliche Zerlegung $z=uvw$ ein $i$ finden, so da"s $uv^i w\not\in L$.
\end{itemize}
Formal gilt also:
$$L\text{ regul"ar}\Rightarrow\exists N\in\mathbb{N}\forall z\in L,|z|\leq N
\exists\text{Zerlegung } z=uvw,|uv|\leq N,|v|\geq 1\forall i\geq 0:uv^iw\in
L$$
Da das Pumping-Lemma eine notwendige, aber nicht hinreichende Bedingung f"ur
die Regularit"at von $L$ ist, l"a"st sich die nicht-Regularit"at von $L$
nachweisen, durch:
$$\forall N\in\mathbb{N} \exists z\in L,|z|\geq N
\forall\text{Zerlegung } z=uvw,|uv|\leq N,|v|\geq 1\exists i\geq 0:uv^iw\not\in
L\Rightarrow L\text{ nicht regul"ar}$$
Gutes Beispiel: $L=\{0^n 1^n|n\in\mathbb{N}\}$ mit $N=n$.

\item[Nichtdeterministischer endlicher Automat] $A=(Q,\Sigma,\delta,q_0,F)$
mit $\delta:Q\times\Sigma\rightarrow P(Q)$, wobei $P(Q)$ die Potenzmenge von
$Q$ ist. \\
Das Programm eines nichtdeterministischen Automaten weist also jeder
"`Konfiguration"¡ $(p,a)$ von Zustand und Buchstaben eine Menge von Zust"anden
zu.
\begin{entry}
\item[Fortsetzung] $\delta:Q\times\Sigma^\ast\rightarrow P(Q)$ sie die
Fortsetzung con $\delta$ mit: $\delta(q,\varepsilon)=\{q\}$ und
$\delta(q,wa)=\bigcup_{p\in\delta(q,w)}\delta(p,a)$ (der Zustand $r\in Q$ ist 
also durch Eingabe $wa$ vom Zustand $q$ aus erreichbar, falls ein Zustand $p$
durch Eingabe $w$ vom Zustand $q$ erreichbar ist und $r\in \delta(p,a)$.
\item[$N$ akzeptiert $w$] $\Leftrightarrow$ $\exists p\in F$ mit
$p\in\delta(q_0,w)$
\item[Die von $N$ akzeptierte Sprache] $L(N)=\{w\in \Sigma^\ast|N\text{
akzeptiert }w\}$
\end{entry}
Es kann sein, da"s man f"ur einen DFA $2^k$ Zust"ande ben"otigt und die
gleiche Sprache mit einem NFA und $k+1$ Zust"anden darstellen kann (z.B. bei
dem Automat der die Sprache erkennt, deren W"orter als $k$-t letzten
Buchstaben eine 1 haben) . NFA's
k"onnen in DFA umgebaut werden, die erkannte Sprache ist also auch regul"ar:
Wir simulieren dabei alle Berechnungen von $N$ gleichzeitig und w"ahlen
Teilmengen aus $Q$ als Zust"ande. Ein Zustand $s\subseteq Q$ ist dann
$$s=\{p\in Q|\text{Es gibt eine Berechnung von N f"ur w, die in p
endet}\}=\delta_N(q_0,w)$$
NFA sind einfacher bei den Operationen Vereinigung, Konkatenation und
Kleenescher Abschlu"s einsetzbar. Diese Operationen sind implizit
nichtdeterminitisch defininiert, da sie einen Existenzquantoren enthalten.

\item[DFA $\Leftrightarrow$ NFA] Sei $N$ NFA
$A=(Q_N,\Sigma,\delta_N,q_0,F_N)$. Der DFA $A$ hat dann Komponenten:
\begin{itemize}
\item $Q_A=\{t|t\subseteq Q_N\}$
\item Anfangszustand $\{q_0\}$
\item $F_A=\{t\in Q_A|t\text{ enth"alt einen Zustand aus }F_N\}$
\item $\delta_A$ ist definiert durch $\delta_A=(t,a)=\{p\in Q_N|\text{Es gibt
}q\in t\text{ mit }p\in\delta_N(q,a)\}$
\end{itemize}
Dann sind $N$ und $A$ "aquivalent, d.h. $L(N)=L(A)$. Aus einem NFA kann also
ein DFA mittels Potenzmengenkonstruktion erstellt werden.

\item[NFA mit $\varepsilon$-"Uberg"angen] ist wie ein DFA definiert, nur da"s
$\delta:Q\times(\Sigma\cup\{\varepsilon\})\rightarrow P(Q)$. Diese Eigenschaft
hat keinen Einflu"s auf die Regularit"at der erkannten Sprache.

\item[Leerheitstest] Test, ob ein akzeptierender Zustand erreichbar ist.

\item[Vollst"andigkeitstest] Test, ob alle Worte entschieden werden. Dabei
gen"ugt es nicht zu zeigen, da"s ein nichtakzeptierender Zustand erreicht
wird, da eine andere Berechnung zu einem akz. zustand f"uhren kann. Der Test
ist bei NFA's also $NP$-hart.

\item[Gleichheitstest] Es soll entschieden werden, ob zwei endliche Automaten
$A_1$ und $A_2$ die gleiche Sprache akzeptieren. Das kann in Zeit $O(|Q_1|
|Q_2| |\Sigma|)$ erreicht werden, da es gen"ugt zu zeigen, da"s
$L_1\cap\overline{L_2}=\emptyset$ und $\overline{L_1}\cap L_2=\emptyset$ ist.

\item[Regularit"at] Seien $L,L_1$ und $L_2$ regul"ar, dann sind regul"ar:
$\overline{L}$, $L_1\cup L_2$ und $L_1\cap L_2$, $L_1\circ L_2$ und $L^\ast$.\\
Regul"are Sprachen sind also unter den Operationen textit{Vereinigung, Durchschnitt,
Komplement, Konkatenation, Kleene-Abschlu"s} abgeschlossen.

\item[Regul"are Ausdr"ucke] Beschreibungsschema f"ur regul"are Sprachen mit
Alphabet $\Sigma=\{a_1,\ldots,a_k\}$:
\begin{enumerate}
\item $\emptyset,\varepsilon,a_1,\ldots,a_k$ sind regul"are Ausdr"ucke
\item Wenn $R$ r.A., dann ist $R^\ast$ und $(R)$ r.A.
\item Wenn $R_1$ und $R_2$ r.A., dann auch $R_1+R_2$ und $R_1\cdot R_2$
\end{enumerate}
Wenn $R$ ein regul"arer Ausdruck f"ur eine Sprache $L$ ist, dann ist $L$
regul"ar. \\
Wenn $L$ regul"ar ist "uber $\Sigma$, dann gibt es einen r.A. f"ur $L$ (Beweis
mit dynamischem Programmieren).

\item[Grammatik] $G=(\Sigma,V,S,P)$ mit 
\begin{itemize}
\item Endliches Alphabet $\Sigma$
\item Endliche Menge $V$ von Variabalen mit $\Sigma\cap V=\emptyset$
\item Startsymbol $S\in V$
\item Endliche Menge $P$ von Produktionen der Form $(u,v)$ mit
$u\in(\Sigma\cup V)^+)$ und $v\in(\Sigma\cup V)^\ast$
Sei $(u,v)$ eine Produktion von $G$, dann definieren wir die Worte
$w_1,w_2\in(\Sigma\cup V)^\ast$:
$$w_1 \rightarrow^\ast w_2 \Leftrightarrow \text{Es gibt } x,y\in(\Sigma\cup
V)^\ast\text{ mit } w_1=xuy\text{ und } w_2=xvy$$
Seien $r,s\in(\Sigma\cup V)^\ast$, dann definieren wir:
$$r \rightarrow s \Leftrightarrow \text{Es gibt Worte }
w_1=r,w_2,\ldots,w_k=s\text{, so da"s } w_1\rightarrow
w_2\rightarrow\ldots\rightarrow w_k$$.
$L(G)=\{w\in\Sigma^\ast|S\rightarrow^\ast w\}$ ist die \textbf{von der Grammatik erzeugte
Sprache}.
\end{itemize}
Eine Grammatik hei"st \textbf{regul"ar}, wenn alle Produktionen $P$ die Form
haben:
\begin{align}
u\rightarrow\varepsilon & \text{(f"ur }u\in V\text{) oder} \notag \\
u\rightarrow av & \text{f"ur }u,v\in V,a\in\Sigma) \notag
\end{align}
$L$ regul"ar $\Leftrightarrow$ Es gibt eine regul"are Grammatik $G$ mit
$L=L(G)$.

\item[Fragen]
%----------------------------------
\begin{itemize}
\item Zusammenhang regul"arer Ausdruck - regul"are Grammatik
\item Definition: Regul"are Sprachen "uber DFA
\item Potenzmengenkonstruktion
\item Pumping Lemma
\item "Aquivalenz-Automat
\item Algorithmus: DEA (DFA) $\rightarrow$ Reg. Ausdruck (Idee)
\item ist $L=\left\{\omega \omega | \omega \in {a,b}^\ast \right\}$ regul"ar, kontextfrei oder kontextsensitiv?
\item Wie finde ich den Minimalautomat?
\item Isomorphie von Automaten?

\item Nerode-Relation $\equiv_L$ und -automat
%----------------------------------
\begin{itemize}
\item Was ist Menge der Zust"ande?
\item Wie sieht ein Programm aus?
\item Was ist der Index $L$?
\item "Aquivalenzklassen?
\item $N_L$
\item Minimaler Automat? $x R_L y$ Beweis; Algorithmus
\item Index von $\left\{a^n b^n | n \in \mathbb{N} \right\}$?
\item Wie w"ahlt man den Index f"ur $\left\{a^n b^n |n \in \mathbb{N} \right\}$? ($\infty$, da nicht regul"ar!)
\item Beweis: Index f"ur $L=\left\{a^n b^m c^{n+m} \right\}$ ist $\infty$, da $L$ nicht reul"ar
\end{itemize}

\item Aus einem Automat einen regul"aren Ausdruck konstruieren
\item Grammatiken
\item Kontextsensitive Sprachen (warum linear platzbeschr"ankt?)
\item Sind regul"aren Sprachen in P enthalten?
\item Wie kann aus einem DFA ein regul"arer Ausdruck f"ur die von
ihm erzeugte Sprache erzeugt werden?
\item Welche Sprachen sind r.a., in P, in NP?
\end{itemize}
\end{type}

%----------------------------------
\subsection{Kontextfreie Sprachen}
%----------------------------------
Z'iel ist die Beschreibung von Programmiersprachen durch formale Grammatiken (die
einerseits ausdrucksstark und andererseits effiziente L"osungen des Compiler-Problems
erlauben).
\begin{type}
\item[Chomsky-Hierarchie] 
\begin{entry}
\item[Typ-0-Grammatiken] Alle Grammatiken ohne Einschr"ankungen: $L_0=\{L(G)|G
\text{ ist vom Typ }0\}$\\
Die Klasse der Typ-0-Grammatiken stimmt mit der Klasse der rekursiv
aufz"ahlbaren Funktionen "uberein, l"a"st sich also von einer
nichtdeterministischen Turingmaschine in polynomieller Zeit erkennen (bei der
Simulation durch eine determinstische TM simulieren wir f"ur ein wachsendes
$l$ alle m"oglichen Rechenwege hintereinander).
\item[Kontextsensitiv (Typ 1)] Produktionen der Form $u\rightarrow v$
mit $|u|\leq|v|$: $L_1=\{L(G)|G\text{ ist vom Typ 1}\}\cup\{L(G)\cup\{\varepsilon\}|G
\text{ ist vom Typ 1}\}$ \\
Die rechte Seite jeder Ableitung darf nicht k"urzer sein als die linke. Es
darf lediglich die Produktionsregel $S\rightarrow\varepsilon$ geben, wobei
jedoch $S$ niemals auf der rechten Seite stehen darf. W"orter d"urfen also
nicht verk"urzt werden! \\
Die Klasse der kontextsensitiven Sprachen stimmt mit der Klasse der von
nichtdeterministischen TM auf linearem Platz $|w|$ akzeptierten W"orter $w$
"uberein. Da es rekursiv aufz"ahlbare, aber nicht kontextsensitive Sprachen
gibt, gibt es auch rekursiv aufz"ahlbare, aber nicht kontextfreie
Sprachen. Die Klasse der Kontextsensitiven Sprachen ist noch zu allgemein, um
das WOrtproblem effizient zu l"osen, da dieses zwar rekursiv, aber dennoch
NP-hart ist (Beispiel: das Erf"ullbarkeitsproblem SAT l"a"st sich sogar mit
einer det. TM l"osen, dennoch ist bereits die Grammatik, die SAT erzeugt,
NP-vollst"andig!).
\item[Kontextfrei (Typ 2)] Produktionen der Form $u\rightarrow v$ mit $u\in V$
und $v\in(V\cup\Sigma)^\ast$: $L_2=\{L(G)|G\text{ hat Typ 2}\}$
\item[Regul"are Grammatik (Typ 3)] $L_3=\{L(G)|G\text{ hat Typ 3}\}$
\end{entry}
$L_0$ ist die Klasse aller rekursiv aufz"ahlbaren Sprachen. \\
$L_1$ ist die Klasse aller Sprachen, die von nichtdeterministischen Turingmaschinen
auf linearem Platz erkannt werden. Jede Sprache aus $L_1$ ist entscheidbar. \\
$L_3\subset L_2\subset L_1\subset L_0$. \\
Es ergeben sich folgende Beziehungen bei den Ableitungen:
\begin{center}
\begin{tabular}{|c|c c c c|}
\hline
$\rightarrow$ & DEA & NEA & RG & RA \\
\hline
DEA & $-$ & linear & linear & exp. \\
NEA & exp. & $-$ & linear & exp. \\
RG & exp. & linear  & $-$ & exp. \\
RA & exp. & linear & linear & $-$ \\
\hline
\end{tabular}
\end{center}
Regul"are Grammatiiken und nichtdeterministische endliche Automaten sind
gleich kompakte Beschreibungsformen der Klasse regul"arer Sprachen. Regul"are
Ausdr"ucke und deterministische endliche Automaten k"onnen exponentiell
l"anger, aber nicht k"urzer sein. Auch zwischen regul"aren Ausdr"ucken und
deterministischen endlichen Automaten gibt es exponentielle Blow-ups.

\item[DTAPE(s(n)) und NTAPE(S(n))] Klassen der Sprachen, die von einer
deterministischen bzw. nichtdeterministischen TM mit Platzbedarf $s(n)$
akzeptiert werden k"onnen.

\item[PSPACE und NSPACE] Vereinigung aller DTAPE($n^k$), $k\in\mathbb{N}$ und
Vereinigung aller NTAPE($n^k$), $k\in\mathbb{N}$
\item[Syntaxbaum] Sei $G=(\Sigma,V,S,P)$ kontextfreie Grammatik und $B$ geordneter Baum
mit den Eigenschaften
\begin{itemize}
\item Die Wurzel von $B$ ist mit $S$ markiert
\item Innere Knoten sind mit Variablen markiert, Bl"atter mit Buchstaben aus $\Sigma$
\item Wenn der Knoten $v$ mit der Variablen $A$ markiert ist, und wenn die Kinder
die Markierungen $v_1,\ldots,v_s$ tragenm dann ist $A\rightarrow v_1\ldots v_s$ eine
Produktion von $G$.
\end{itemize}
$B$ ist ein Syntaxbaum des Wortes $w$, das durhc Konkatenieren der Markierungen
der Bl"atter $B$ (von links nach rechts) entsteht. \\
Grammatiken, die f"ur jedes abgeleitete Wort genau einen Syntaxbaum besitzen, erlauben
relativ einfache L"osungen des Compiler/Wort-Problems:
\begin{itemize}
\item $G$ hei"st \textbf{mehrdeutig} $\Leftrightarrow$ $\exists w\in L(G)$ mit zwei
verschiedenen Syntaxb"aumen. Ansonsten hei"st $G$ \textbf{eindeutig}.
\item Sprache $L$ hei"st \textbf{eindeutig}, wenn es eine eindeutige Grammatik $G$
gibt mit $L=L(G)$. Ansonsten hei"st $L$ \textbf{inh"arent eindeutig}.
\end{itemize}
Syntaxgraphen existieren f"ur beliebige Grammatiken. Kontextfreie Grammatiken
erm"oglichen die Einschr"ankung auf Syntaxb"aume, und regul"are Grammatiken
kommen sogar mit Syntaxlisten aus (ein Hinweis, warum das Syntaxanalyseproblem
f"ur kontextfreie Grammatiken effizient l"osbar ist).

\item[Chomsky-Normalform] Eine Grammatik ist in CNF, wenn alle Produktionen die
Form $A\rightarrow BC$ oder $A\rightarrow a$ besitzen (mit $A,B,C\in V, a\in\Sigma$).\\
Wenn $L$ kontextfrei ist mit $\varepsilon\not\in L$, dann gibt es eine Grammtik $G$ in
CNF mit $L=L(G)$. Man kann sogar effizient zu einer kontextfreien Grammatik eine
Grammatik in CNF konstruieren ($\rightarrow$Algorithmus; lediglich die
Eliminierung der Kettenregeln kann hier zu Problemen f"uhren, was eine
Umfromung in Linearzeit verhindert).
\begin{entry}
\item[Kettenregeln] Ableitungen vom Typ $A\rightarrow B$. K"onnen den Sytaxbaum
sehr gro"s machen und sind deshalb verboten.
\item[Gr"o"se der Syntaxb"aume] Das Worte der L"ange $n$ in h"ochstens $2n-1$
Schritten abgeleitet werden k"onnenist die Gr"o"se der Syntaxb"aume linear.
\item[Innere Knoten] Die Syntaxb"aume haben f"ur Worte der L"ange $n$ genau
$n-1$ innere Knoten und $n$ Bl"atter, wobei jedes Blatt noch einen Vater mit
nur diesem Blatt als Kind hat).
\end{entry}

\item[Cocke-Younger-Kasami] Sei $G$ in CNF, dann kann in Zeit $O(|$Produktionen von G$|\cdot|w|^3)$
entschieden werden, ob $w\in L(G)$. (Beweis mit dynamischen Programmieren:
Bottom-up Ansatz, wobei f"ur jedes Teilwort $w_i\ldots w_j$ bestimmt wird, aus
welchem $P_{ij}$ es sich ableiten l"a"st; da alle Teilprobleme gel"ost werden
m"ussen, bis $P_{1n}$ ausgerechnet wurde, betr"agt die Laufzeit
$O(\binom{n}{2}+n)$; f"ur jedes Teilproblem ben"otigen wir wieder $n\cdot
|\text{Anzahl Produktionen}|)$). \\
Achtung: Die Laufzeit ist \textit{immer} kubisch, da die Gr"o"se der Grammatik
immer nur als linearer Faktor in die Laufzeit eingeht, w"ahrend der Exponent
entscheidend durch die Anzahl der Variablen auf der rechten Seite der
Ableitungen bestimmt wird!

\item[Pumping-Lemma f"ur kontextfreie Sprachen] Sei $L$ kontextfreie Sprache, $\exists$Pumpingkonstante
$n$ $\forall z\in L$ mit $|Z|\geq n$ $\exists$Zerlegung $z=uvwxy$ mit Eigenschaft
\begin{itemize}
\item $|vwx|\leq n$ und $|vx\geq 1$
\item $\forall i\geq 0: uv^iwx^iy\in L$
\end{itemize}
Also gilt:
\begin{enumerate}
\item $L_1,L_2$ kontexfrei $\Rightarrow$ $L_1\cup L_2$, $L_1\circ L_2$ und $L_1^\ast$
kontextfrei
\item Es gibt kontextfreie Sprachen $L_1$ und $L_2$, so da"s $L_1\cap L_2$ nicht
kontextfrei ist.
\item Es gibt eine kontextfreie Sprachen $L$, so da"s $\overline{L}$ nicht kontexfrei
ist.
\end{enumerate}
Formal folgt also aus der Regularit"at von $L$:
$$\exists N\in\mathbb{N}\forall z\in L,|z|\geq
N\exists\text{Zerlegung }z=uvwxy,|vwx|\leq N,|vx|\geq 1\forall i\geq 0: uv^i
wx^i y\in L.$$
Zum Nachweis der nicht-Regularit"at m"ussen wir also die Umkehrung zeigen:
$$\forall N\in\mathbb{N} \exists z\in L,|z|\geq N \forall\text{Zerlegung
}z=uvwxy, |vwx|\leq N, |vx|\geq 1\exists i\geq 0: uv^i wx^i y\not \in L$$

\item[Ogden's Lemma] Sei $L$ kontextfreie Sprache, dann $\exists$Pumpingkonstante
$n$, so da"s $\forall z\in L$ mit $|z|\geq n$ mit mindestens $n$ markierten Buchstaben
eine Zerlegung $z=uvwxy$ besitzt mit
\begin{itemize}
\item h"ochstens $n$ Buchstaben sind in $vwx$ markiert
\item mindestens ein Buchstabe ist in $vx$ markiert
\item $\forall i\geq 0:uv^iwx^iy\in L$
\end{itemize}
Das Pumping-Lemma folgt aus Ogden's Lemma, wenn wir alle Buchstaben von $z$
markieren. (Beweis: Baum mit $n=2^{|V|+1}$ markierten Bl"attern und also einem
Weg der L"ange mindestens $|V|+1$, der immer die Abzweigung mit den meisten
Bl"attern nimmt).\\
Beispiel einer Grammatik, die so als nicht kontextfrei bewiesen werden kann:
$$\{d^r a^x b^y c^z|r=0\text{ oder } x=y=z\}$$

\item[Greibach-Normalform] Sei $G=(\Sigma,V,S,P)$ kontextfrei und alle Produktionen
der Form $A\rightarrow a\alpha$ (f"ur $A\in V, a\in\Sigma$ und $\alpha\in V^\ast$). \\
Wenn $G$ in CNF ist, dann gibt es eine Grammatik $G^\ast=(\Sigma,V^\ast,S^\ast,P^\ast)$
in GNF mit $L(G)=L(G^\ast)$ und $|P^\ast|=O(|P|^3)$.

\item[Kellerautomaten] 	Maschinenmodell, das genau die Klasse der kontextfreien
Sprachen akzeptiert. Dabei k"onnen \textbf{deterministisch kontextfreie Sprachen}
von einem deterministischen Kellerautomaten akzeptiert werden (f"ur diese Sprachen
gibt es sehr schnelle Algorithmen, die das Compiler-Problem l"osen).

\item[Nichtdeterministischer Kellerautomat (PDA)] $A=(Q,\Sigma,\Theta,q_0,Z_0\in\Theta,\delta,F)$
mit $Z_0$ als anf"anglicher Stackinhalt und $\delta:Q\times(\Sigma\cup\{\varepsilon\})\times
\Theta\rightarrow P(Q\times\Theta^\ast)$. \\
Eine \textit{Konfiguration} von $A$ (f"ur Eingabe $w\in\Sigma^\ast$) ist $(q,w^,\alpha)$
mit $q\in Q,w'\in\Sigma^\ast$ und $\alpha\in\Theta^\ast$, wobei $w'$ ein Suffix von $w$
und $\alpha$ der Stackinhalt ist. \\
\textit{Akzeptanz durch leeren Stack:} $w=w_0\ldots w_n$, wenn eine Konfigurationsfolge
$$(q_0,w_1\ldots w_n,Z_0),\ldots,(q,\varepsilon,\varepsilon)$$ existiert. Der Keller darf
also bis auf den letzten Schritt zu keinem Zeitpunkt leer sein. \\
\textit{Akzeptanz durch akzeptierende Zust"ande:} $A$ akzeptiert $w$, wenn es eine
Konfigurationsfolge $(q_0,w_1\ldots w_n,Z_0),\ldots,(q,\varepsilon,\alpha)$ gibt mit
$\alpha\in\Theta^\ast$ und $q\in F$ - der Keller mu"s auch diesmal leer sein.\\
Wenn $G$ in GNF ist, dann gibt es einen PDA $A$ mit $L(G)=L(A)$ und $A$ akzeptiert mit
leerem Stack. \\
Wird $L$ von einem PDA $A$ (mit leerem Stack) akzeptiert, dann gibt
es eine kontextfreie Grammatik $G$ mit $L(G)=L(A)$. Die Klasse der
kontextfreien Sprachen entspricht also genau der Menge der Sprache,
die von einem PDA mit leerem Stack erkannt werden. \\
Wenn $A_1$ mit Zust"anden akzeptiert, dann gibt es einen
"aquivalenten PDA $A_2$, der mit leerem Stack akzeptiert und
umgekehrt.

\item[Deterministischer Kellerautomat (DPDA)] F"ur jedes Tripel
$(q,a,z)$ mit $q\in Q,a\in\Sigma$ und $z\in\Theta$ gilt:
$|\delta(q,a,z)|+|\delta(q.\varepsilon,z)|\leq 1$ und $a$ mit
Zust"anden akzeptiert. \\
$L$ hei"st \textbf{deterministisch kontextfrei}, wenn $L$ von einem
deterministischen Kellerautomaten erkannt wird (deterministisch
kontextfreien Sprachen$\subseteq$kontextfreien Sprachen, da:
DPA$\subseteq$DPDA). \\
Akzeptanz durch Zust"ande ist bei DPDA's wesentlich m"achtiger als
die akzeptanz durch leeren Stack:
$$L_D^{Stack}=\{L\subseteq\Sigma^\ast|\exists\text{DPDA A, A
akzeptiert L mit leerem Stack}\}$$
$$L_D^F=\{L\subseteq\Sigma^\ast|\exists\text{DPDA A, A
akzeptiert L mit akzeptierendem Zustand}\}$$
Es gilt: $L_D^{Stack}\subset L_D^F$ \\
Wenn $L$ deterministisch kontextfrei ist, dann auch $\overline{L}$.
(Konstruktion mittels $Q\times\{1,2,3\}$)\\
Es gibt det. kontexfreie Sprachen $L_1,L_2$, so da"s $L_1\cap L_2$
nicht einmal kontextfrei ist. ($L=\{a^n b^n c^n|n\geq 0\}$)\\
Die Menge der det. kontexfreien Sprachen ist unter der Vereinigung
nicht abgeschlossen (Beweis mit Vereinigung von $\{a^x b^y c^z|x\not =
y\}$) und $\{a^x b^y c^z|y\not = z\}$.\\
Die Menge der det. kontexfreien Sprachen ist eine echte Untermenge
der kontextfreien Sprachen. Insbesondere ist $^\{a^x b^y c^z|x\not = y
\text{ oder }y\not =z\}$ kontextfrei, aber nicht deterministisch
kontextfrei. \\
Au"serdem gilt, da"s
\begin{itemize}
\item Jede det. kontextfreie Sprache eindeutig ist
\item $\{ww^{reverse}|w\in\Sigma^\ast\}$ eindeutig, aber nicht det.
kontextfrei ist
\item ein stets haltender DPDA auf Eingaben der L"ange $n$ ind Zeit
$O(n)$ l"auft. Das Wortproblem ist also f"ur deterministisch kontextfreie
Sprachen in Linearzeit l"osbar.
\end{itemize}
\item[Sprachklassen und Ihre Charakterisierung] "Ubersicht:
\begin{center}
\begin{tabular}{l p{12cm}}
Sprache & Charakterisierung \\
\hline
RA: & rekursiv aufz"ahlbar, Turingmaschinen, die nur beim Akzeptieren halten
m"ussen, Comsky-0 Grammatiken \\
REK: & rekursiv, stets haltende Turingmaschinen, keine Charakterisierung durch
Grammatiken \\
KS: & kontextsensitiv, nichtdeterministische, linear platzbeschr"ankte
Turingmaschinen, Chomsky-1, kontextsensitive oder monotone Grammatiken \\
DKS: & deterministisch kontextsensitiv, deterministische, linear
platzbeschr"ankte Turingmaschinen \\
NP: & nichtdeterministische, polynomiell zeitbeschr"ankte Turingmaschinen \\
P: & deterministische, polynomiell zeitbeschr"ankte Turingmaschinen \\
KF: & kontextfrei, (nichtdeterministische) Kellerautomaten, Chomsky-2 oder
kontextfreie Grammatiken \\
EKF: & eindeutig kontextfrei, eindeutige Grammatiken \\
DKF: & deterministisch kontextfrei, deterministische Kellerautomaten,
$LR(k)$-Grammatiken f"ur beliebiges, konstantes $k$ \\
REG: & regul"ar, endliche Automaten, Chomsky-3, rechtslineare oder regul"are
Grammatiken, regul"are Ausdr"ucke
\end{tabular}
\end{center}
Diese Sprachklassen stehen in folgenden Beziehungen zueinander:
$$REG \subsetneq DKF \subseteq EKF \subsetneq KF
\begin{array}{l l l}
\subsetneq DKS & \subseteq KS & \subseteq \\
\subsetneq P & \subseteq NP & \subseteq
\end{array}
REK \subsetneq RA $$

\item[Fragen]
\begin{itemize}
\item Definition?
\item Spiel mit Odgen's Lemma
\item Beispiele: kontextfreie Sprachen?
\item Chomsky Grammatik
\item Chomsky Normalform?
\item Definition und Beweis: Greibach Normalform
\item PDA
\item Kellerautomat
\item CYK-Algorithmus (Genaue Erkl"arung, wie sieht $v_{i,j}$ aus?)
\item Warum profitiert der CYK-Alg. von dynamischer Programmierung?
\item NFA$\rightarrow$DFA in $2^{|Q|}$
\item Beweis: Blow-up beim "Ubergang NFA$\rightarrow$DFA?
\item Beispiel: Potenzmengenkonstruktion, exponentielles Blowing
\item Beweis: $a^n b^m c^{n+m}$ ist kontextfrei
\item Gibt es kontextfreie Sprachen, die $NP$-vollst"andig sind? -Nein, wegen CYK
\item Beziehungen zwischen rek. aufz. $\Leftrightarrow$ Typ 0, nicht det. TM lin. Platz $\Leftrightarrow$ Typ 1
\item Ist $a^n b^n c^m$ kontextfrei?
\item Wof"ur NFA's? (einfachere Beschreibung als DFA, weniger Zst.: NFA hat $|Q|$ und DFA $2^{|Q|}$ Zust"ande)
\item Beispiel f"ur NFA Zustandsvorteil: $\left\{ 0,1 \right\} ^\ast 1 \left\{0,1\right\}^k$ mit $k$ fest (DFA ben"otigt nur Zeit $k+1$)
\item "Aquivalenz NDFA, DFA polynomiell?
\item Wie beweisen: Sprache nichtdet. und kontextfrei?
\item Definition: p-space
\end{itemize}

\begin{itemize}
\item Beispiel: Inh"arent mehrdeutig?
\item $L_{G_1} \cap L_{G_2} = \emptyset \rightarrow$ PKP def.
\end{itemize}

\end{type}

\end{document}
