\documentclass[11pt]{article} \usepackage[german]{babel} \usepackage[latin1]{inputenc} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsmath} \usepackage{color} \usepackage{multicol} \usepackage[top=1cm, left=1cm, right=1cm, bottom=1cm, a4paper]{geometry} % Platzsparende Überschriften \newcommand{\h}[1]{{\vspace{1ex}\noindent\small\textbf{#1}}\\} \newcommand{\hh}[1]{{\noindent\ \textbf{#1}}\\} \newcommand{\hhh}[1]{{\noindent\ \ \underline{#1}}} % FIXME \newcommand{\FM}[1]{{\color{red}\emph{#1}}} \begin{document} \begin{multicols}{2} \scriptsize\raggedright \setlength{\parskip}{0pt} \h{EA und Reguläre Sprachen} \hh{Reguläre Sprachen} $L \subseteq \Sigma^*$ heisst regulär, wenn: \\ $L={a},~a \in \Sigma$, $L=\epsilon$ oder $L=\O$. \\ Seien $L_1,L_2$ reg. Sprachen, dann ist L auch regulär, wenn: \\ $L=L_1 \cup L_2$ , $L=L_1 \cdot L_2$ oder $L=L_1^*$ \\ Regulärer Ausdruck genauso, nur ohne $L(\cdot)$. \\ \hh{DEA Automatenminimierung} Suchen nach Zeugen für Nichtäquivalenz: \\ \begin{enumerate} \item Betrachte alle Zustände als eine Klasse \item Betrachte Wörter der Länge 0, also $\varepsilon$. Dieser Trennt Q in $Q\backslash F$ und F. \item Betrachte alle Wörter der Länge i und alle Klassen K. Teile K in K1 und K2 gdw. $\exists q_1 , q_2 ~ \in K$ und $w \in \Sigma^i$ mit $ \delta (q_1,w) ~ \in ~ F$ und $ \delta (q_2,w) ~ \notin ~ F$. \item In Schritt (3) nichts getrennt? $\rightarrow$ Fertig! Sonst wiederhole Schritt (3) mit Wörtern der Länge i+1. \end{enumerate} \hh{DEA $\rightarrow$ RegExp} DEA $A:=/\{q_1,...,q_n\},\Sigma, \delta, q_1,F)$. \\ $L_f:=\{w ~ \in ~ \Sigma^* |$ A endet nach Abarbeitung von w in f $\}$ \\ $L_{q_i,q_j}^m:=\{w \in \Sigma^* |$ Abarbeitung von w aus $q_i$ nach $q_j$ hat nur Zwischenzustände $\{q_1,...,q_m\}$ \\ $L(A)=\bigcup_{f \in F} L_f =\bigcup_{f \in F} L_{q_1,f}^n$ \\ L(A) ist ind. definiert: \\ Falls m=0 und $q_j=q_i$: $L_{q_i,q_j}^0:=\{a \in \Sigma | \delta (q_i,a)=q_i\} \cup \{\epsilon \}$\\ Falls m=0 und $q_j \neq q_i$: $L_{q_i,q_j}^0:=\{a \in \Sigma | \delta (q_i,a)=q_j\}$\\ Sonst ($m>0$): $L_{q_i,q_j}^{m+1}:=L_{q_i,q_j}^m \cup ( L_{q_i,q_{m+1}}^m( L_{q_{m+1},q_{m+1}}^m)^* L_{q_{m+1},q_i}^m $\\ \hh{Nerode Relation zur Sprache L} $R_L:= \{(x,y) \Sigma^*× \Sigma^* : ~\forall z ~\in~ \Sigma^* : xz ~\in~ L ~ \Leftrightarrow ~ yz ~ \in ~ L \}$ \\ $R_M$ verfeinert $R_L$! \\ \textcolor{red}{Satz v. Nerode:} $Index(R_L)=\infty ~ \textcolor{red}{\rightarrow} $ L ist nicht regulär! Es gilt sogar \textcolor{red}{$\Leftrightarrow$} \hh{Pumping Lemma fuer reg. Sprachen} \hspace{3mm} L regulär $ \textcolor{red}{\rightarrow} ~$ \\ \hspace{5mm} $\exists n ~ \in ~ \mathbb{N}~:~ \forall w ~ \in ~ L~, |w|>n~ :$ \\ \hspace{5mm} $ \exists ~ u,v,x: ~ w=uvx, ~ \textcolor{blue}{|uv|< n} , ~ |v|>0, \textcolor{red}{ \forall i ~ \in ~ \mathbb{N}_0~:~ uv^ix ~ \in ~L}$ \h{Berechenbarkeit} \hh{TM} Schreibweise: $\delta (q,a) ~=~\delta (q,a,N)$ \\ Beim Graph: $Eingabe|Ausgabe, \{L,R,N\}$ \\ Endzustände kennzeichen,\textcolor{blue}{ Startzustand nicht!} \\ \hh{Def} T \textbf{akzeptiert} w \\ $\Leftrightarrow$ T akzeptiert alle $w\in L$ und kein $w \notin L$ \\ \vspace{1mm} L ist \textbf{rekursiv aufzaehlbar (= semientscheidbar)} \\ $\Leftrightarrow$ $\exists ~ T : ~$ T akzept. L \\ \vspace{1mm} L ist \textbf{rekursiv (= entscheidbar)} \\ $\Leftrightarrow$ $\exists ~ T : ~$ T akzept. L $\wedge ~ \forall w \in \Sigma^* ~:~ $ T hält \\ \vspace{1mm} Funktion $g:~ \Sigma^* \rightarrow \Gamma^*$ ist \textbf{(turing)-berechenbar} wenn g(w)=y genau dann, wenn es eine TM gibt, für die $(s)w \Rightarrow^* x(f)y$, wobei $x,y ~ \in ~ \Gamma^*$ \\ \vspace{1mm} Sprache $L\subseteq ~ \Sigma^*$ ist \textbf{entscheidbar} gdw ihre charakteristische Funktion $\chi_L$ ist berechenbar. Dabei gilt: \\ $\chi_L :~ \Sigma^* ~ \rightarrow \{0,1\} ~ mit ~ \chi_L (w) ~ = ~ \{1, ~ falls ~ w \in ~ L , ~sonst~ \textcolor{red}{0}$ \\ \vspace{1mm} Sprache $L\subseteq ~ \Sigma^*$ ist \textbf{semi-entscheidbar} gdw die Funktion $\chi^*_L$ ist berechenbar. Dabei gilt: \\ $\chi^*_L :~ \Sigma^* ~ \rightarrow \{0,1\} ~ mit ~ \chi^*_L (w) ~ = ~ \{1, ~ falls ~ w \in ~ L , ~sonst ~ \textcolor{red}{undefiniert}$ \\ \vspace{1mm} \hh{Diagonalsprache $L_d$} Sei $M_i$ die TM mit Gödelnummer $ = i$ und $w_i$ die Binärrepresentation von i. \\ $L_d:=~\{w_i~:~M_i akzeptiert w_i nicht~\}$ \\ Satz: \textbf{$L_d$ und ihr Komplement sind beide nicht entscheidbar. $L_d$ ist auch nicht semientscheidbar.} \\ \vspace{1mm} Universelle TM U akzeptiert $w$ gdw M akzeptiert w. \\ \vspace{1mm} Halteproblem $H:=\{w_iv ~ : ~ M_i $ angesetzt auf v hält $\}$ ist nicht entscheidbar. \\ Beschränktes Halteproblem (nach x Schritten) ist aber entscheidbar. \\ \hh{Postsches Korrespondenzproblem (PKP)} PKP ist semientscheidbar und nicht entscheidbar. \\ Geg: Endliche Anzahl von Wortpaaren \\ Frage: Existiert Anordnungsmoeglichkeit , so dass oben und unten gleich (nichts darf ueberstehen). \\ \hh{WHILE-Programm / LOOP Programm Aufbau} $\mathbb{N}~ main( \mathbb{N}~x_1,....,\mathbb{N}~x_k ) $ \\ \hspace{5mm} $\mathbb{N}~x_0;\mathbb{N}~x_{k+1};\mathbb{N}~x_{k+2};...$ \\ \hspace{5mm} body; \\ \hspace{5mm} $return ~ x_0;$ \\ $\}$\\ Im Body: $x_i:=x_j+c~ , ~ c \in ~ \{-1,0,1\}$, wichtig: $0-1:=0$. \\ Erlaubt: Sequenzen ";" , Unterprogrammaufrufe. \\ $while(x_j\neq 0): ~ Schleife$ \\ $loop ~ x_i:$ Schleife. Wiederhole $x_i$ mal. Relevant ist der Inhalt von $x_i$ vor der ersten Schleifenausführung. \hh{Ackermannfunktion a(x,y)} $a(0,y)=y+1$ \\ $a(x,0)=a(x-1,1)$ \\ $a(x,y)=a(x-1,a(x,y-1))$ \\ Die Ackermannfunktion ist nicht Loop-berechenbar. Sie wächst schneller als jede LOOP berechenbare Funktion. \\ Lemma: $y log_2 n$. Hier gilt fast immer $\alpha (m,n) \leq 5$, aber $\alpha (m,n) \notin O(1)$. \h{Komplexität} \hh{P} $time_M(w)~=~$ \# Rechenschritte einer TM bei Eingabe von w. \\ $TIME(f(n))~=~ \{L:~\exists ~(Mehrband-)TM ~M: ~L(M) = L ~ \wedge ~ \forall w ~ \in ~ \Sigma^*_M ~ : ~ time_M(w)~ \leq f(|w|)\}$ \\ $P:= \bigcup_{Polynom ~ p} ~ TIME(p(n))$ \\ \hh{co-NP} $co-NP=\{L^c , L~ \subseteq ~ \Sigma^* ~ , ~ L ~ \in ~ P \}$ \\ \hh{Pseudopolynomielle Algorithmen } A ist ein pseudopolynomieller Algorithmus , falls ~ $Time_A(p) ~ \in ~ P$. \\ Dabei ist n die Anzahl der Eingabebits unär kodiert ($|^n$). \\ \hh{Polynomiale Reduzierbarkeit} $A \subseteq \Sigma^* ~, B \subseteq \Gamma^*$ Sprachen. \\ $A\leq_p B$ (A ist auf B polynomial reduzierbar) $\Leftrightarrow$ \\ $\exists f~ : ~ \Sigma^* \rightarrow \Gamma^* ~ : ~ \forall w ~ \in ~ \Sigma^* ~ : ~ w ~ \in A ~ \Leftrightarrow ~ f(w) ~ \in ~ B$, \\ wobei f in polynomialer Zeit berechenbar ist. \\ \hh{Defs} A ist \textcolor{red}{NP-Hart}: $\Leftrightarrow ~ \forall L ~ \in ~ NP~ : ~ L\leq_p A$ \\ A ist \textcolor{red}{NP-vollständig} $\Leftrightarrow $ A ist NP-Hart und $A ~ \in ~ NP$. \\ \hh{Reduktionsbeweise: Schema für NPV Problem A} \begin{itemize} \item Zeige $A ~ \in ~ NP$ durch Algorithmus(-ansatz), großzügig abschaetzen. \item Zeige A ist NP-Hart, also hier $ Q \leq_p A$ \begin{itemize} \item Wähle bekanntes NPV Problem Q \item Nehme Instanz von \textcolor{red}{Q} und erzeuge daraus Instanz von A \item Zeige (begründe), dass wenn Graph G(oder ähnliches) keine Instanz von \textcolor{red}{Q} hat, so gibt es auch keine von A oder erzeuge aus Instanz von A eine Instanz von \textcolor{red}{Q}. \item Begründe, dass die Transformation polynomiell ist. \end{itemize} \end{itemize} \hh{Folgerungen} $A\leq_p B ~ \wedge ~ B \in P ~ \Rightarrow A \in P$ \\ $A\leq_p B ~ \wedge ~ A \in NPV ~ \Rightarrow B \in NP-Hart$ \\ $A\leq_p B ~ \wedge ~ B \in NPV ~ \Rightarrow A \in NP$ \\ $A\leq_p B ~ \wedge ~ A \in P ~ \Rightarrow B \neq \O ~ \wedge ~ B \neq \Sigma^*$ \\ \hh{NP-vollständige Problem} \hhh{\textcolor{red}{SAT}} \\ \textbf{Gegeben} : Formel F der Aussagen Logik mit $(\wedge, ~ \vee, ~ \neg, ~ (, ), Variablen)$ \\ \textbf{Frage} : Gibt es eine Variablenbelegung, so dass F erfüllbar ist? \\ \hhh{\textcolor{red}{3 SAT (KNF) }} \\ \textbf{Gegeben} : Formel F der Aussagen Logik mit maximal 3 Literalen pro Klausel. $(\wedge, ~ \vee, ~ \neg, ~ (, ), Variablen)$ \\ \textbf{Frage} : Gibt es eine Variablenbelegung, so dass F erfüllbar ist? \\ \hhh{\textcolor{red}{SET COVER}} \\ \textbf{Gegeben} : Grundmenge M, Teilmengen $T_i$ von $\tau ~\in ~ 2^M$, Parameter n \\ \textbf{Frage} : Gibt es Auswahl von $T_1~ \in ~ \tau,...,T_n~ \in ~ \tau$ mit $T_1 \cup ~ ... ~ \cup T_n = M$? (Mengen müssen nicht disjunkt sein)\\ \hhh{\textcolor{red}{CLIQUE}} \\ \textbf{Gegeben} : ungerichteter Graph G=(V(Knoten),E(Kanten)) und ein Parameter k \\ \textbf{Frage} : $\exists V' ~ \subseteq ~ V: ~ |V'|=k~\wedge ~ \forall u \neq v ~ \in ~ V': ~ \{u,v\} ~ \in ~ E$? \\ D.h. alle Knoten in der Clique sind mit allen Knoten in der Clique verbunden. \\ \hhh{\textcolor{red}{VERTEX COVER}} \\ \textbf{Gegeben} : ungerichteter Graph G=(V(Knoten),E(Kanten)) und ein Parameter k \\ \textbf{Frage} : $\exists V' ~ \subseteq ~ V: ~ |V'|=k~\wedge ~ \forall \{u,v\} ~ \in ~ E:~ u ~ \in ~ V' \vee v ~ \in ~ V'$ \\ D.h. alle Knoten , die mindestens ein Kantenende enthalten, von jeder Kante.\\ \hhh{\textcolor{red}{COLORING}} \\ \textbf{Gegeben} : ungerichteter Graph G=(V(Knoten),E(Kanten)) und ein Parameter k \\ \textbf{Frage} : Gibt es eine Knotenfärbung $c:V ~ \rightarrow ~ \{1,...,k\}$ mit $\forall {u,v} ~ \in ~ E : ~ c(u) \neq c(v)$?\\ Geht schon für 3-COLORING , also mit k=3. 3-COLORING ist NPV.\\ \hhh{\textcolor{red}{SUBSET SUM}} \\ \textbf{Gegeben} : n Gegenstände mit Gewicht $w_i ~ \in ~ \mathbb{N}$ und ein Parameter W \\ \textbf{Frage} : Gibt es eine Teilmenge M von $\{1,...n\}$, so dass $\sum_{i~ \in ~ M} w_i=W$ \\ \hhh{\textcolor{red}{RUCKSACK}} \\ \textbf{Gegeben} : n Gegenstände mit Gewicht $w_i ~ \in ~ \mathbb{N}$ , Profit $p_i$ und ein Parameter W \\ \textbf{Frage} : Wähle eine Teilmenge x von Gegenstände, so dass $\sum_{i ~ \in ~ x} w_i \leq W$ und $\sum_{i ~ \in ~ x} p_i \geq W$? \\ \hhh{\textcolor{red}{Partition}} \\ \textbf{Gegeben} : n Gegenstände mit Gewicht $w_i ~ \in ~ \mathbb{N}$ \\ \textbf{Frage} : Gibt es eine Teilmenge M von $\{1,...n\}$, so dass $\sum_{i~ \in ~ M} w_i=\sum_{i~ \notin ~ M} w_i$ \\ \hhh{\textcolor{red}{BIN PACKING}} \\ \textbf{Gegeben} : Plätzchendose $b ~ \in ~ \mathbb{N}$ , Plätzchen der Größe $w_1,....,w_n ~ \in ~ \mathbb{N}$ und Anzahl der Plätzchendosen k\\ \textbf{Frage} : Passen alle Plätzchen irgendwie in alle Dosen? Also\\ $\exists f:1...n ~ \rightarrow ~ 1...k ~ : ~ \forall j \in 1...k : \sum {w_i : ~ f(i)= j} \leq b$ \\ \hhh{\textcolor{red}{Integer Linear Programming (ILP)}} \\ \textbf{Gegeben} : Variablenvektor $x=(x_1,...,x_n)$, Menge von Bedingungen der Form $a\cdot ~ x\textcolor{blue}{R}b$ mit $\textcolor{blue}{R ~ \in ~ \{\leq,\geq, =\}},~ b \in \mathbb{Z}, ~ a in \mathbb{Z}^n$? \\ \textbf{Frage} : Gibt es eine Belegung für x aus $\mathbb{Z}^n$, so dass alle Bedingungen erfüllt sind? \\ \hhh{\textcolor{red}{DIRECTED HAMILTON CYCLE (DHC)}} \\ \textbf{Gegeben} : gerichteter Graph G=(V(Knoten),E(Kanten)) \\ \textbf{Frage} : Gibt es einen Hamiltonschen Kreis? D.h. jede Ecke des Graphen ist genau einmal enthalten. \\ $M:=\{G=(V,E \subseteq V \times V): \exists C \subseteq E : |C|=|V|, $C ist einfacher Kreis$\}$ \\ \hhh{\textcolor{red}{HAMILTON CYCLE (HC)}} \\ \textbf{Gegeben} : ungerichteter Graph G=(V(Knoten),E(Kanten)) \\ \textbf{Frage} : Gibt es einen Hamiltonschen Kreis? D.h. jede Ecke des Graphen ist genau einmal enthalten. \\ $M:=\{G=(V,E \subseteq V \times V): \exists C \subseteq E : |C|=|V|, $C ist einfacher Kreis$\}$ \\ \hhh{\textcolor{red}{TRAVELLING SALESMAN PROBLEM (TSP)}} \\ \textbf{Gegeben} : ungerichteter Graph G=(V(Knoten),E(Kanten)) und ein Parameter M. \\ \textbf{Frage} : Gibt es einen einfachen Kreis $C=(v_1,v_2,....,v_n,v1)$ (Reihenfolge nicht nach Nummerrierung), so dass $n=|V|$ und $\sum_{(u,v)\in C}~ d(u,v) \leq M$? \\ \hhh{\textcolor{red}{STEINER TREE }} \\ \textbf{Gegeben} : ungerichteter Graph G=(V(Knoten),E(Kanten)) mit positiven Kantengewichten $c: E ~ \rightarrow ~ \mathbb{R}^+$, $V=R (Pflichtknoten) \cup F (Steiner Knoten, nicht Pflicht)$ und ein Parameter M\\ \textbf{Frage} : Gibt es einen Baum $T \subseteq E$, der mit Kosten $\leq M$ alle Pflichtknoten verbindet? \\ \h{Chomsky Grammatiken} \hh{Übergangsrelation , L(G)} Grammatik $G=(V,\Sigma,P,S)$, $u\Rightarrow_G ~ v$ falls \\ $u=xyz ~ \in ~ (V \cup \Sigma)^*$, $v=xy'z ~ \in ~ (V \cup \Sigma)^*$ und $y \rightarrow ~ y' ~ \in ~ P$. \\ \hh{Chomsky-Hierarchie} $G=(V,\Sigma,P,S)$ $\forall ~ l \rightarrow r ~ \in ~ P$ \\ \textcolor{blue}{Typ-0} beliebig \\ \textcolor{blue}{Typ-1} $|l| \leq |r|$, zusätzlich $S \rightarrow \varepsilon$\\ \textcolor{blue}{Typ-2} Typ 1 und $l \in V$, zusätzlich $S \rightarrow \varepsilon$\\ \textcolor{blue}{Typ-3} Typ 2 und $r \in \Sigma \cup \Sigma V$, zusätzlich $S \rightarrow \varepsilon$\\ \hh{Chomsky- Normalform für ktf. Grammatiken (ohne $\epsilon$ ) } \begin{itemize} \item Elimination von zyklischen Einheitsproduktionen $A\rightarrow B \rightarrow A$ \item Elimination von nichtzyklischen Einheitsproduktionen $A\rightarrow B$ \item Elimination gemischer rechter Seiten $A \rightarrow aBc$ \item Elinination zu langer rechter Seiten von links $A \rightarrow BCD ~ \Rightarrow ~ A \rightarrow HD ~ , H \rightarrow BC$ \end{itemize} \hh{Wortproblem $w ~ \in ~ L(G)$ und CYK Algorithmus} Spezialfall $s=\varepsilon$ ist einfach. Sonst: \\ \begin{itemize} \item Forme Grammatik $G=(V,\Sigma,P,S)$ in Chomsky-Normalform um. \item Schreibe w mit viel Abstand zwischen den Buchstaben in eine Zeile \item Schreibe alle Nichtterminale, aus dem man den Buchstaben erzeugen kann unter die jeweiligen Buchstaben. \item Danach prüfe gleiche Spalte ganz oben (i) und Diagonal rechts drüber (ii) zusammen, weiter: mit (i) 1 nach unten und mit (ii) 1 Diagonal nach schräg rechts oben. \item Erzeuge umgekehrte Treppe. Falls S in der Spitze, dann $w~ \in ~ L$. \end{itemize} \hh{Pumpinglemma für kontextfreie Sprachen} \hspace{3mm} L kontextfrei $ \textcolor{red}{\rightarrow} ~$ \\ \hspace{5mm} $\exists n ~ \in ~ \mathbb{N}~:~ \textcolor{magenta}{z} ~ \in ~ L~, |\textcolor{magenta}{z}|>n~ :$ \\ \hspace{5mm} $ \exists ~ u,v,w,x,y: ~ \textcolor{magenta}{z}=uvwxy, ~ \textcolor{blue}{|vwx|\leq n} , ~ |vx|>0,$ \\ \hspace{5mm} $\textcolor{red}{ \forall i ~ \in ~ \mathbb{N}_0~:~ uv^iwx^iy ~ \in ~L}$ \hh{Nichtdet. Kellerautomaten} $K=(Q,\Sigma,\Gamma,\delta,s,\#)$, $(q,w,x) ~ \in ~ Q ~ \times ~ \Sigma^* ~ \times ~ \Gamma^*$ \\ Bei einem Übergang werden 0 oder 1 Zeichen von der Eingabe gelesen, 1 Zeichen vom Keller genommen und dieses Zeichen wird durch ein (ggf. gleiches ) Zeichen ersetzt. \\ Kellerautomat akzeptiert Wort w gdw $\exists ~ (s,w,\#) ~ \rightarrow ~ ... ~ \rightarrow ~ (q,\epsilon,\epsilon)$ mit $q ~ \in Q$ \\ L kontextfrei gdw $\exists NKellerA ~M$ mit $L(M)=L$. Geht auch mit 1Zustand NKellerA.\\ \hh{Probleme für L(G)} Leerheitsproblem $L(G)=\O$? \\ Endlichkeitsproblem $L(G)=\infty$? \\ Wortproblem $w \in L(G)$? \\ \hh{Linear beschränkte Nichtdet. Turingmaschine (NLBTM)} NTM $T=\{Q,\Sigma,\Gamma,\delta,s,F\}$ ist linear beschränkt, wenn \\ $\forall a= a_1...a_n ~ \in \Sigma^+ ~ : ~ a \Rightarrow^* \alpha (q) \beta ~ \rightarrow ~ |\alpha \beta | \leq n$ \\ \h{Überblick} \hh{Chomsky Typ und Beschreibungsmittel} \begin{tabular}{|c|c|} \hline % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... CH-Typ & Beschreibungsmittel \\ \hline 3 & rechtslin. XOR linkslin. Gramm., DEA, NEA, reg.Ausdr. \\ Det.KF & LR(k) Grammatik, DKellerA mit Endzustand \\ 2 & kontextfreie Grammatiken, (1Zustands)NKellerA \\ 1 & kontextsens. (expand.) Grammatiken $|l|\leq |r|$, NLBTM \\ 0 & Typ-0 Grammatik, NTM, DTM, (semientscheidbar) \\ \hline \end{tabular} \hh{Abschlusseigenschaften} \begin{tabular}{|c|c|c|c|c|c|} \hline % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... Typ & $\cap$ & $\cup$ & $\cdot^-$ Kompl. & $\cdot$ Konkat & $^*$ Kleen. \\ \hline 3 & ja & ja & ja & ja & ja \\ Det.KF & nein & nein & ja & nein & nein \\ 2 & nein & ja & nein & ja & ja \\ 1 & ja & ja & ja & ja & ja \\ 0 & ja & ja & nein & ja & ja \\ \hline \end{tabular} \hh{Entscheidbarkeitsprobleme} \begin{tabular}{|c|c|c|c|c|} \hline % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... Typ & Wort- & Leerheits- & Äquivalenz & Schnitt \\ \hline 3 & ja & ja & ja & ja \\ Det.KF & ja & ja & ja & nein \\ 2 & ja & ja & nein & nein \\ 1 & ja & nein & nein & nein \\ 0 & nein & nein & nein & nein \\ \hline \end{tabular} \hh{Komplexität des Wortproblems} \begin{tabular}{|c|c|} \hline % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ... CH-Typ & Komplexität des Wortproblems \\ \hline 3 & $O(n)$ \\ Det.KF & $O(n)$ \\ 2 & $O(n^3)$ \\ 1 & $|\Sigma|^{O(n)}$, NP-Hart \\ 0 & semientscheidbar \\ \hline \end{tabular} \hh{Approximationsalgorithmen} Sei L ein Optimierungsproblem und $I \in L$ eine Instanz von L. \\ OPT(I) - die Optimallösung von I. \\ A(I) - die Lösung die ein Algorithmus A zu I liefert. \\ Zu einem Minimierungsproblem L ist ein Algorithmus A ein Approximationsalgorithmus mit relativer Gütegarantie p, falls gilt \\ $A(I)/OPT(I) \leq p ~ \forall I \in L$. \\ \hh{(Fully) Polynomial Time Approximation Scheme ((F)PTAS)} Algorithmus A ist PTAS für Problem $\Pi$, falls \\ 1. Eingabe: Instanz I, Fehlerparamter $\varepsilon$ \\ 2. $f(x) \leq (1+ \varepsilon ) \cdot OPT$ \\ 3. Time ist polynomiell in $|I|$ \\ Falls Time polynomiell in $|I|$ und $1/\varepsilon$, dann ist A FPTAS. \hh{Fixpunktsatz} 1.Das Produkt zweier Wortmengen ist stetig. \\ 2. Die Vereinigung zweier Wortmengen ist stetig. \\ 3. Jede stetige Funktion ist monoton. \\ 4. Jede stetige Funktion hat Fixpunkte. \end{multicols} \end{document}