aboutsummaryrefslogtreecommitdiff
path: root/content
diff options
context:
space:
mode:
Diffstat (limited to 'content')
-rw-r--r--content/tgi.tex56
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.