Benutzer:Megatherium/Kram

Optimierungsproblem

Ein Optimierungsproblem besteht aus einer Menge $M$ von Lösungen und einer Zielfunktion $f:M\rightarrow \mathbb {R}$, die jeder Lösung einen Wert (Qualität; Fitness) zuordnet. Im Fall eines Maximierungsproblems ist $f(x)$ umso höher, je besser die Lösung $x$ ist. Bei einem Minimierungsproblem ist es umgekehrt, was sich durch Negieren von $f$ auf den ersten Fall zurückführen lässt. Man sucht in der Regel eine beste (optimale) Lösung in $M$, also ein $x$ mit dem höchsten bzw. niedrigsten $f(x)$.

Informatik

Man unterscheidet hier folgende Problemstellungen:

• Entscheidungsprobleme, bei denen zusätzlich ein Grenzwert $g\in \mathbb {R}$ gegeben ist, und ermittelt werden soll, ob es ein $x\in M$ gibt mit $f(x)\geq g$.
• eigentliche Optimierungsprobleme, bei denen man den Wert der besten Lösung wissen will, also $\max\{f(x)\mid x\in M\}$.
• Suchprobleme, bei denen eine optimale Lösung $o\in M$ gesucht ist, also $f(o)=\max\{f(x)\mid x\in M\}$, oder eine Lösung mit einer gegebenen Mindestqualität, d. h. ein $o$ mit $f(o)\geq g$.
• Approximationsprobleme: man will eine möglichst gute Lösung finden, ohne dass von vornherein weitere Vorgaben gemacht werden.

In der Theoretischen Informatik meint man mit Optimierungsproblem in der Regel ein eigentliches Optimierungsproblem, bei dem also nur der bestmögliche Wert und keine Lösung selbst gesucht ist. Auch betrachtet man üblicherweise den Sonderfall einer diskreten Bewertungsfunktion $f\colon M\rightarrow \mathbb {N}$, da dies meist keinen erheblichen Unterschied macht und man reelle Zahlen weniger gut handhaben kann, z. B. näherungsweise als Gleitkommazahlen.

Meistens betrachtet man in der Theoretischen Informatik aber Entscheidungsprobleme. Zu einem Optimierungsproblem lässt sich leicht ein Entscheidungsproblem erzeugen, indem man zur Problemstellung den Grenzwert $g\in \mathbb {R}$ bzw. $g\in \mathbb {N}$ hinzunimmt. Umgekehrt kann man für die meisten praktisch interessanten Probleme zeigen, dass ein Lösungsweg für das Entscheidungsproblem zu einer Lösung des entsprechenden Such- oder Optimierungsproblems modifiziert werden kann, die nicht entscheidend mehr Rechenzeit oder Speicherplatz benötigt.

Problem

$Q:=\{n^{2}|n\in \mathbb {N} ^{+}\};\;D\in \mathbb {N} ^{+}\setminus Q;\;x_{D}:=\min \,\{x\in \mathbb {N} ^{+}\;|\;{\frac {x^{2}-1}{D}}\in Q\}$

Gesucht: $D\leq 1000$, welches das größte $x_{D}$ liefert.

Registermaschine 1

Befehlssatz $I=\{H,aset,rset,rinc,j,jB,jnB,ld,st,op(1),op(2),\dotsc ,op(x),ild,ist,iop(1),\dotsc ,iop(x)\}$

endliches Alphabet $\Gamma$ mit $B\in \Gamma$

Operatoren $f_{i}:\Gamma \times \Gamma \rightarrow \Gamma ;\;\;i\in \{1,2,\dotsc ,x\}$

surjektive Adressfunktion: $g:\Gamma \rightarrow \{0,1,\dotsc ,\alpha \};\;\alpha \geq 2$

Programm $P:\mathbb {N} \rightarrow I\times \Gamma$

$a\in \Gamma ;\;p\in \mathbb {N} ;\;r\in \mathbb {N}$

Register $R:\mathbb {N} \rightarrow \Gamma$

Die Maschine beginnt mit $a=B;\;p=r=0$ mit der Eingabe in den Registern $R(0)$ bis $R(l-1);\;l\in \mathbb {N} ;\;x\geq l\Leftrightarrow R(x)=z$ mit $g(z)=\alpha$. Ein Arbeitsschritt besteht in der Ausführung des Befehls $P(p)$ gemäß nachfolgender Tabelle. Dies wird iterativ wiederholt, solange $P(p)_{1}\neq H$ (Der Index 1 bedeutet: das erste Element des Tupels $P(p)$). Wenn $P(p)_{1}=H$, hält die Maschine an, und die Ausgabe steht in den Registern.

Alternativ: zur Befehlsmenge werden $\{in,out\}$ zum Lesen der Eingabe bzw. Schreiben in die Ausgabe hinzugefügt, und alle Register werden mit $z$ initialisiert.

$P(p)_{1}$	Aktion
aset	$a\leftarrow P(p)_{2}$
rset	$r\leftarrow g(P(p)_{2})$
rinc	$r\leftarrow \alpha \cdot r+g(P(p)_{2})$
j	$p\leftarrow r$
jB	wenn $a=B$ dann $p\leftarrow r$
jnB	wenn $a\neq B$ dann $p\leftarrow r$
ld	$a\leftarrow R(r)$
st	$R(r)\leftarrow a$
op(i)	$a\leftarrow f_{i}(a,R(r))$
ild	$a\leftarrow R(A)$
ist	$R(A)\leftarrow a$
iop(i)	$a\leftarrow f_{i}(a,R(A))$
in	$a\leftarrow$ nächstes Eingabezeichen
out	Ausgabe $\leftarrow a$

Nach jeder Aktion wird der Befehlszähler inkrementiert ($p\leftarrow p+1$), außer nach einem Sprung, d. h. nachdem $p\leftarrow r$ ausgeführt wurde.

Für die Befehle ild, ist und iop(1) bis iop(x) wird die Adresse A wie folgt berechnet:

$A\leftarrow 0$

$j\leftarrow r$

while $g(R(j))<\alpha$ do

$A\leftarrow \alpha \cdot A+g(R(j))$

$j\leftarrow j+1$

end while

Registermaschine 2

• endliches Arbeitsalphabet $\Gamma$ mit $\gamma _{0}\in \Gamma$
• Programm $P:\mathbb {Z} \rightarrow C\times \Gamma$
• Register $R:\mathbb {Z} \rightarrow \Gamma$
• Akkumulator $a\in \Gamma$
• Befehlszähler $c\in \mathbb {Z}$
• Addressregister $p\in \mathbb {Z}$
• Operatoren $f_{i}:\Gamma \times \Gamma \rightarrow \Gamma$
• Prädikate $g_{i}:\Gamma \rightarrow \{wahr,falsch\}$
• surjektive Addressfunktion $h:\Gamma \rightarrow \{z\in \mathbb {Z} \;|\,-\lfloor |\Gamma |/2\rfloor \leq z<\lceil |\Gamma |/2\rceil \}$

Befehlscode $P(c)_{1}$	Aktion
set	$a\leftarrow P(c)_{2};\quad c\leftarrow c+1$
load	$a\leftarrow R(p+h(P(c)_{2}));\quad c\leftarrow c+1$
op(i)	$a\leftarrow f_{i}(a,R(p+h(P(c)_{2})));\quad c\leftarrow c+1$
store	$R(p+h(P(c)_{2}))\leftarrow a;\quad c\leftarrow c+1$
jmp(i)	wenn $g_{i}(a)$, dann $c\leftarrow c+h(P(c)_{2})$, sonst $c\leftarrow c+1$
offs	$p\leftarrow p+h(a);\quad c\leftarrow c+1$
halt	(keine)

Am Anfang ist $c=p=0$ und $a=\gamma _{0}$. Das Programm der Länge $l_{p}$ steht in $P(0),P(1),\dots ,P(l_{p}-1)$, und es ist $P(x)=(halt,\gamma _{0})$ für $x<0$ oder $x\geq l_{p}$. Die Eingabe der Länge $l_{e}$ steht in $R(0),R(1),\dots ,R(l_{e}-1)$, und es ist $R(x)=\gamma _{0}$ für $x<0$ oder $x\geq l_{e}$.

Integral

$\int _{0}^{H}\int _{P}((y(p,h)-h)^{2}+z(p,h)^{2})\,\mathrm {d} p\,\mathrm {d} h=\int _{0}^{H}\int _{P}(y(p,h)-h)^{2}\,\mathrm {d} p\,\mathrm {d} h+\int _{A}z(a)^{2}\,\mathrm {d} a$

Hash

$B:=\{0,1\}$. Gegeben: Verkettungsfunktion $f:B^{c}\times B^{r}\times B^{112}\times B^{16}\rightarrow B^{c}$, Nachricht $M\in B^{*}$, Salz $S\in B^{n}$ mit $n\leq r$, Hashlänge $e\leq c$.

$M\,\|\,0^{j}=M_{1}\,\|\,M_{2}\,\|\,\dots \,\|\,M_{k};\quad |M_{i}|=r,\,j<r$

$h_{0}=f(e,S\,\|\,0^{r-n},0,n)$

$h_{i}=f(h_{i-1},M_{i},i,g(i));\quad i=1,\dots ,k;\quad g(i)={\begin{cases}0&{\text{wenn }}i<k\\r-j&{\text{wenn }}i=k\end{cases}}$

$hash=\operatorname {trunc} (h_{k},e)$

P

Notation:

• $\mathbb {N} _{0}:=\{0,1,2,3,\dots \}$ ist die Menge der natürlichen Zahlen mit Null.
• $\Sigma =\{0,1\}$ ist das Alphabet einer formalen Sprache, das heißt jedes Wort ist eine binäre Zeichenfolge bestehend aus $0$ und $1$.
• $\Sigma ^{n}$ bezeichnet die Menge aller binären Wörter der Länge $n\in \mathbb {N} _{0}$.
• $\Sigma ^{*}=\bigcup _{n\in \mathbb {N} _{0}}\Sigma ^{n}$ bezeichnet die Menge aller endlich langen binären Wörter.

Ein Entscheidungsproblem wird als formale Sprache $S$ über dem Alphabet $\Sigma$ dargestellt, also $S\subseteq \Sigma ^{*}$. Dazu wird ein Formalismus festgelegt, um jede Probleminstanz (deren Lösung eine ja/nein-Antwort ist) als Wort in $\Sigma ^{*}$ darzustellen, und $S$ enthält genau die Wörter $x\in \Sigma ^{*}$, die eine gültige Darstelung einer Probleminstanz sind, auf die die richtige Antwort „ja“ lautet.

$L(S)$ bezeichne die Menge der Algorithmen $A:\Sigma ^{*}\to \{0,1\}$, die das Problem $S\subseteq \Sigma ^{*}$ lösen: $L(S)=\{A\;|\;\forall x\in \Sigma ^{*}:(A(x)=1\iff x\in S)\}$.

$t(A,x)$ bezeichnet die Zahl der Rechenschritte, die der Algorithmus $A$ bei Eingabe von $x\subseteq \Sigma ^{*}$ ausführt, mit der Turingmaschine als ausführendes Maschinenmodell.

Die Klasse $\mathbf {P} \in {\mathcal {P}}(\Sigma ^{*})$ ist die Menge der effizient-lösbaren Entscheidungsprobleme. Ein Entscheidungsproblem $S\subseteq \Sigma ^{*}$ ist effizient-lösbar, falls ein Algorithmus $A\in L(S)$ existiert, der nur polynomielle Zeit braucht, d. h. es existiert ein Polynom $p$, so dass $\forall n\in \mathbb {N} _{0}:\forall x\in \Sigma ^{n}:t(A,x)\leq p(n)$.

Dann ist $\mathbf {P}$ die Klasse der effizient-lösbaren Entscheidungsprobleme, das heißt

$\mathbf {P} =\{S\;|\;\exists A:\forall x:(A(x)=1\iff x\in S)\wedge t(A,x)<=p\}$