diff options
Diffstat (limited to 'content')
| -rw-r--r-- | content/tgi.tex | 56 |
1 files changed, 53 insertions, 3 deletions
diff --git a/content/tgi.tex b/content/tgi.tex index d5e6d84..1b16cdd 100644 --- a/content/tgi.tex +++ b/content/tgi.tex @@ -276,11 +276,11 @@ Lösung eines Aufzählungsproblems ist $|S_\Pi(I)|$. z.B. wie viele Hamilton-Kreise gibt es? -\subsubsection*{Turing-Reduktion} +\subsection*{Turing-Reduktion} Eine \emph{Turing-Reduktion} $\propto_T$ von Relationen $R \propto_T R'$ über $\Sigma^*$ ist eine Orakel-Turing-Maschine $\mathcal{M}$ deren Orakel $R'$ realisiert und in polynomialer Zeit die $R$ realisierende Funktion berechnet. -\subsubsection*{$\NP$-Schwere} +\subsection*{$\NP$-Schwere} Ein Suchproblem $\Pi$ ist \emph{$\NP$-schwer}, wenn $\NP$-vollständige Sprache $L$ ex. s.d. $L \propto_T \Pi$. @@ -300,6 +300,14 @@ Prüfe ob $x_i, \dots, x_n \in \N_0$ ex. s.d. $\sum_{j=1}^n c_j \cdot x_j = B$ u \emph{INTEGER PROGRAMMING} ist $\NP$-schwer. +\subsection*{Raumkomplexität} + +Die Klasse der mit polynomialen Speicherplatz lösbaren Probleme ist $\mathcal{PSPACE}$. + +\spacing + +Es gilt: $\P \subseteq \NP \subseteq \mathcal{PSPACE}$ + \subsection*{Pseudopolynomiale Algorithmen} Ein Algorithmus ist \emph{pseudopolynomial}, wenn er bei Unärkodierung polynomial in Eingabelänge ist. @@ -350,6 +358,29 @@ $\mathcal{A}$ ist \emph{$\epsilon$-approximativ}, wenn: \vspace*{-2mm} \[ \forall I \in D_\Pi : \mathcal{R_A}(I) \leq 1 + \epsilon \] +\subsubsection*{Greedy-Algorithmus für KNAPSACK} + +Sei $w : M \to \N_0$ Gewichtsfunktion, $c : M \to \N_0$ Kostenfunktion und $W \in \N_0$. + +\spacing + +Definiere Gewichtsdichten $p_i := \frac{c_i}{w_i}$. + +Sortiere $p_1 \geq \dots \geq p_n$ in $\mathcal{O}(n \log n)$. + +Für $i \in \{1,\dots,n\}$ setze $x_i := \left\lfloor \frac{W}{w_i} \right\rfloor, W := W - \left\lfloor \frac{W}{w_i} \right\rfloor \cdot w_i$ + +\spacing + +Dieser Greedy-Algorithmus $\mathcal{A}$ läuft in $\mathcal{O}(n \log n)$. + +\spacing + +Für $\mathcal{A}$ gilt: $\forall I \in D_\text{KNAPSACK} : \mathcal{R_A}(I) \leq 2$ + +\vfill\null +\columnbreak + \section*{Chomsky-Hierarchie} \begin{description}[leftmargin=!,labelwidth=8mm] @@ -395,12 +426,27 @@ Eine kontextfreie Grammatik ist in \emph{Chomsky-Normalform}, wenn alle Regeln v \spacing -Jede nicht $\epsilon$ erzeugende kontextfreie Grammatik ist in Chomsky-Normalform überführbar. +Jede nicht $\epsilon$ erzeugende kontextfreie Grammatik ist in Chomsky-Normalform überführbar: + +\begin{enumerate} +\item Regeln ergeben nur Variablen oder genau ein $a \in \Sigma$. Mit Hilfsvariablen erreichbar. +\item Alle Regeln haben Länge $\leq 2$ +\item Elimination von Regeln $A \to \epsilon$ +\item Ersetzen von Kettenregeln (Kreise, DFS) +\end{enumerate} \subsubsection*{Cocke-Younger-Kasami Algorithmus} Entscheidet für kontextfreie Grammatik $G$ in Chomsky-Normalform und Wort $w \in \Sigma^*$ das Wortproblem in Zeit $\mathcal{O}(|R|\cdot |w|^3)$ wobei $|R|$ Anzahl der Regeln in $G$ ist. +\subsubsection*{Pumping-Lemma (kontextfreie Sprachen)} + +Für kontextfreie Sprachen $L$ gilt: $\exists n \in \N \forall z \in L :$ + +\spacing + +$|z| \geq n \implies \exists u,v,w,x,y \in L : z=uvwxy$ s.d. $|vx| \geq 1, |vwx| \leq n$ und $\forall i \in \N : uv^iwx^iy \in L$ + \subsubsection*{Greibach-Normalform} Eine kontextfreie Grammatik ist in \emph{Greibach-Normalform}, wenn alle Regeln von Form $A \to a\alpha$ für $A \in V, a \in \Sigma$ und $\alpha \in V^*$ sind. @@ -409,6 +455,10 @@ Eine kontextfreie Grammatik ist in \emph{Greibach-Normalform}, wenn alle Regeln Jede nicht $\epsilon$ erzeugende kontextfreie Grammatik ist in Greibach-Normalform überführbar. +\spacing + +Für jede Grammatik $G$ in Greibach-Normalform kann ein Kellerautomat (PDA) gebildet werden, der $L(G)$ mit leerem Stack aktzeptiert. + \subsubsection*{Unentscheidbare Probleme} Seien $G, G_1, G_2$ kontextfreie Grammatiken. |