\section{`Harte' Probleme}
\subsection{Typische Problemklassen}
\inhalta{9-15}
\inhaltb{15}

\begin{frame}
Grundform einer algorithmischen Aufgabenstellung:
\begin{itemize}
\item i.d.R. nicht als Entscheidungsproblem\pause
\item sondern sondern als \Fb{funktionales Problem} (oder
Suchproblem)\pause

\Fb{ Gegeben $x$, bestimme eine ,,Lösung'' $y$, falls eine solche existiert.}
\end{itemize}\pause
$y$ ist dabei i.d.R. Resultat der Guess-Phase bei Guess-and-Check \pause\\ und kann
schnell überprüft werden\pause\\ (Bsp: Variaben-Belegung, Isomorphismus, Färbung,...)\pause

Wichtig auch: Bei nichtdeterministischen Algorithmen ist es nicht gleichgültig, ob man
\begin{itemize}
\item die Existenz einer Lösung zeigen will oder \pause
\item aber zeigen will, dass gar keine Lösung existiert
\end{itemize}

\end{frame}

\begin{frame}
\begin{definition}
Zu einem Problem $K$ aus einer Grundmenge $M$ sei co-$K:=M\setminus K$.\pause

Die Problemklasse co-NP besteht aus allen Problemen $K$, für die co-$K$ in NP liegt.
\end{definition}
\pause
Es ist noch unbekannt, ob co-NP=NP gilt (vermutlich nicht...)\pause
\begin{itemize}
\item Unbekannt ist z.B. ob co-SAT in NP liegt\pause

(Wie soll man durch Raten feststellen, dass z.B. keine erfüllende Belegung existiert?)
\pause
\item 
Bei deterministischen Entscheidungsalgorithmen kann man das Resultat einfach negieren,
d.h. co-P=P.
\end{itemize}


\end{frame}

\begin{frame}
weitere Form: \Fb{Optimierungsprobleme}\pause
\begin{itemize}
\item\Fb{ Zu Eingabe bestimme Lösung, die eine gegebene Kostenfunktion maximiert (oder minimiert)}
\end{itemize}
\pause
Bei NP-vollständigen Problemen:\pause
\begin{itemize}
\item  funktionales Problem
oder Optimierungsproblem auf Entscheidungsproblem polynomial ``reduzierbar''\pause
\item gibt es polynomialen Algorithmus für das
Entscheidungsproblem,\\
 so auch für das  funktionale oder Optimierungsproblem
\end{itemize}
\pause
Entscheidungsprobleme für Theorie ausreichend\\\pause
(aber nicht für Praxis: hier genauere Betrachtung notwendig...)
\end{frame}

\begin{frame}

Optimierungsprobleme werden spezifiziert durch:\pause
\begin{itemize}
\item die Menge der zulässigen Eingaben \pause
\item die zulässigen Lösungen $S(x)$ für zulässige Eingaben $x$\pause
\item eine  Bewertungsfunktion $v$, die Lösungen $y$ mit $v(y)$ bewertet.
\end{itemize}
\pause
Jede der drei Komponenten sollte polynomiale Komplexität haben:
\pause
\begin{itemize}
\item Zulässigkeit sollte mit
polynomialer Komplexität überprüfbar sein!\pause
 \item  $y\in S(x)$ sollte in polynomialer Komplexität entscheidbar sein.\pause
\item $v$ sei in polynomialer Komplexität berechenbar.
\end{itemize}

\pause
Optimierungsprobleme sind gegliedert in\pause
\begin{itemize}
\item Minimierungsprobleme:\pause\\  suche Lösung $y \in S(x)$ mit $v(y) = min\{v(s) \mid \in S(x)\}$. \pause
\item Maximierungsprobleme:\pause\\  suche analog Lösung mit maximalem $v$-Wert
\end{itemize}
\end{frame}
\begin{frame}
\begin{example}
{\bfseries Traveling Salesman Problem} (TSP) als Minimierungsproblem:\pause

\begin{itemize}
\item zulässige Eingaben: $n\times  n$ Entfernungsmatrix $M = (m_{i,j})$\pause\\
 (Abstände/Kosten zuje zwei
Städten $i$ und $j$, $(i, j\in\{1,\dots,n\}$)\pause
\item Erlaubt: Einträge mit Wert $\infty$\pause
\\(keine direkte Straßenverbindung zwischen Ort $i$ und Ort
$j$)\pause
\item zulässige Lösungen sind Permutationen $\pi$ auf  $\{1, 2,\ldots, n\}$\pause

(repräsentieren Rundreise durch alle Städte)\pause\\
zulässige Rundreise müssen ohne $\infty$-Einträge auskommen\pause
\item Bewertung $v$ einer zulässigen Permutation $\pi$ für $M$ \pause ist definiert als
$$v(\pi)=\sum_{k=1}^{n-1}m_{\pi(k),\pi(k+1)} + m_{\pi(n),\pi(1)}$$\pause
\item O.B.d.A. betrachte nur Permutationen $\pi$ mit $\pi(1) = 1$. 
\end{itemize}
\pause
Ziel: {\bfseries Suche $\pi$ mit minimalen Gesamtkosten $v(\pi)$}
\end{example}
\end{frame}
\begin{frame}
\begin{example}
{\bfseries MaxSAT} als Maximierungsproblem: 
\pause
\begin{itemize}
\item
Gegeben: eine {\em Menge} $F$ von
Klauseln,\pause\\
gesucht: eine Belegung, die möglichst viele Klauseln erfüllt.\pause
\item Zulässige Eingaben: syntaktisch korrekte Klauselmengen.\pause
\item Jede Belegung $\Phi$ der Variablen ist zulässige Lösung! \pause
\item Bewertung $v(\Phi)=$ Anzahl der durch $\Phi$ erfüllten Klauseln
\end{itemize}\pause

Beispiel: $$F=\{(x_1\vee x_2\vee x_3),(\neg x_2\vee x_3), \neg x_1, \neg x_2, \neg x_3\}$$
\pause mit (nicht-eindeutiger aber) optimaler Lösung 
$$\Phi: x_1\mapsto 1,  x_2\mapsto 0, x_3\mapsto 0$$
und $v(\Phi)=4$.
\end{example}
\end{frame}


\begin{frame}

Umwandlung vom Optimierungs- zum Entscheidungsproblem:\pause
\begin{itemize}
\item 
natürliche Zahl $k$ als weiterer Bestandteil der Eingabe,\pause\\
 d.h. Eingaben
sind $$\{ (x,k) \mid x \mbox{ ist zulässig, } k\in\nz\}$$\pause
\item gesucht: Gibt es  Lösung der Güte $k$ oder besser?
\end{itemize}
\pause
 Bei Minimierungsproblemen  lautet das Entscheidungsproblem also:
\pause
\begin{itemize}
\item 
 Ist zu $(x,k)$ die  Menge 
$\{  y\in S(x)\mid v(y)\leq k\}$ nichtleer?
\end{itemize}
\end{frame}

\begin{frame}
weitere Form: \Fb{Zählprobleme}\pause
\begin{itemize}
\item Zu Eingabe bestimme genaue Anzahl der Lösungen
\end{itemize}
\pause
Für NP-vollständige Probleme sind die Zählprobleme wohl schwieriger als die Entscheidungsprobleme!\pause

Andererseits beim Graphenisomorphieproblem: \pause
\begin{itemize}
\item
Aus fiktiven polynomialen Entscheidungsalgorithmus würde polynomialer Algorithmus für das Zählproblem (ohne Beweis...) \pause
\item
daher Vermutung: Graphenisomorphieproblem ist evtl. nicht NP-vollständig...
\end{itemize}
\end{frame}

\begin{frame}
Im Folgenden: Algorithmen für NP-vollständige Probleme 
\pause
\begin{itemize}
\item  insbesondere für Traveling Salesman Problem und Erfüllbarkeitsproblem als Beispiele 
\end{itemize}
\pause
Algorithmen für exakte Lösungen (für funktionales
oder Optimierungsproblem) haben (derzeit) exponentielle Laufzeit \pause

Daher folgende Möglichkeiten:\pause
\begin{itemize}
\item
Suche  nach exakten Algorithmen, die zumindest besser sind als naive Suche\pause
\item
Suche nach  polynomialen Algorithmen, die  akzeptable Näherungslösungen berechnen\pause
\item 
Benutze dabei insbesondere Zufallszahlen als Hilfsmittel
\end{itemize}

\end{frame}





\subsection{Exakte Verfahren}
\subsubsection{Dynamisches Programmieren}
\inhaltb{15}

\begin{frame}
Bekannt: {\bf Divide and Conquer}\pause
\begin{itemize}
\item \emph{Top-Down}-Verfahren\pause
\item Zerlege Problem in Teilprobleme, die getrennt gelöst werden\pause
\item Einfaches Zusammensetzen der Teillösungen\pause
\item Wichtig für Komplexität: Unabhängigkeit der Teilprobleme\pause
\item Parade-Beispiel: Quicksort\pause
\item Negativ-Beispiel: Fibonacci-Zahlen
\end{itemize}
\pause
Jetzt: {\bf Dynamisches Programmieren}\pause
\begin{itemize}
\item \emph{Bottom-Up}-Verfahren\pause
\item Löse erst triviale Probleme\pause
\item Setze Teillösungen zu größeren Lösungen zusammen\pause
\item Wichtig für Algorithmus: Speicherung der Teillösungen!\pause
\item Bereits bekannt: CYK-Algorithmus für kontextfreie Grammatiken
\end{itemize}
\end{frame}



\begin{frame} Beispiel:
{\bfseries TSP}\pause

Naiver Algorithmus: \pause
\begin{itemize}
\item  Untersuche alle Permutationen (d.h. $\Omega(n!)$ )...\pause
\item  Triviale Verbesserung: Starte immer in Stadt $1$ (d.h. $\Omega((n-1)!)$ )
\end{itemize}
\pause
Laufzeit (geschätzt, bei 1.000.000 Permutationen pro Sekunde):
\pause
$$\begin{array}{c|r}
n&\mbox{Zeit}\\\hline
10& 0.3~ s\\
11& 3.6~ s\\
12& 40~ s  \\
13& 8~ m   \\
14& 1~ h~ 43~ m  \\
15& 1~d\\
16& 15~ d \\
17& 240~ d\\
18& 11~ j \\
19&202~j  \\
20&3836~j \\
\end{array}$$
\end{frame}



\begin{frame}
Uminterpretation von {\bfseries TSP}:\pause
\begin{itemize}
\item Betrachte  {\bfseries TSP} als (kantenbewerteten) Graphen\pause
\item Knotenmenge $V=\{1,\ldots,n\}$\pause
\item Kantenmenge $E=V\times V$, Bewertung: $m_{i,j}$ für Kante $(i,j)$ 
\end{itemize}\pause
Teil-Lösungen für  {\bfseries TSP}:\pause
\begin{itemize}
\item zu Knoten $i$ und $S\subset V$ setze
$$g(i,S)=\begin{tabular}[t]{l} Gewicht des besten Weges von $i$ nach $1$,\\
 der nur über Knoten aus $S$ führt und zudem\\\pause
 jeden Knoten $j\in S$ genau einmal berührt\end{tabular}$$\pause
\item Dann ist $g(1,V\setminus\{1\})$ gesuchte Lösung des TSP\pause
\item Rekursive Beschreibung von $g$:
$$g(i,S)=\left\{\pause\begin{array}{ll} m_{i,1}& S=\emptyset\\
\pause\min_{j\in S}\left( m_{i,j} + g(j,S\setminus\{j\}\right)
&\pause S\neq \emptyset\end{array}\right.$$
\end{itemize}
\end{frame}

\begin{frame}
Beispiel:
$$M=\left[\begin{array}{ccccc}
  0 & 10 & 15 & 20\\
  5 &  0 &  9 & 10 \\
  6 & 13 &  0 & 12 \\
  8 &  8 &  9 &  0
\end{array}\right]$$
\[\includegraphics[width=.65\textwidth]{grafik/TSP-rekursiv.pdf}\]
\pause
Rekursive Implementierung $\leadsto$  `überflüssige' Auswertungen von $g$! 
\end{frame}


\begin{frame}[fragile]
`{\bfseries Dynamisches Programm}' für  {\bfseries TSP}:\pause
 \begin{itemize}
\item Bottom-Up Auswertung\pause
\item Speicherung der Funktionswerte in Tabelle
\end{itemize} 
\pause Iterativ programmiert:
\begin{programm}
\begin{semiverbatim}\bfseries
FOR i:=2 TO n DO g[i,\(\emptyset\)]=m[i,1];\pause
FOR k:=1 TO n-2 DO
    FOR S, |S|=k, 1\(\not\in\)S DO
        FOR i \(\in\)\{2,...,n\}\(\setminus\)S DO
           berechne g[i,S] nach Formel\pause
berechne g[1,\{2,...,n\}] nach Formel
\end{semiverbatim}
\end{programm}
\pause
Aufwand:
\begin{itemize}
\item Speicherplatz: \pause Tabelle mit $< n\cdot 2^n$ Einträgen\pause
\item Zeit: \pause(Größe der Tabelle) $ \cdot$ (Aufwand pro Eintrag), d.h. $n^2\cdot 2^n$
\end{itemize} 
\pause
(Hilfsmittel zum Programmieren mit (kleinen) Mengen in \verb#C++# oder \verb#Java# z.B. \verb#bitset#)
\end{frame}

% \begin{frame}[fragile]
% 
% rekursive Implementierung in \verb#C++#
% \begin{programm}
% \begin{semiverbatim}\bfseries\scriptsize
% #include <bitset>
% #include <iostream>
% #include <iomanip>
% using namespace std;
% 
% /* Achtung: V={0,1,...,n-1}
%    Modifikation: Nicht pi(1)=1 sondern pi(n)=n,
%    damit S nur aus {0,1,...,n-2}
% */
% 
% unsigned long formel(
%         unsigned int n, unsigned int m[],
%         unsigned int i, bitset<30> S)\{
%   bitset<30> S2;
%   unsigned int minimum=2000000000, m2;
%   if (S.none()) return m[i+n*(n-1)] ;
%   else \{
%      for (unsigned j=0; j<n-1; j++)\{ if (S.test(j))\{
%            S2 = S;   S2.set(j,0);
%            m2 = m[i+n*j] + formel(n,m,j,S2);
%            if (m2 < minimum) minimum = m2;
%        \}
%      \}
%      return minimum;
%   \}
% \};
% \end{semiverbatim}
% \end{programm}
% \end{frame}
% \begin{frame}[fragile]
% \begin{programm}
% \begin{semiverbatim}\bfseries\scriptsize
% 
% int main()\{
%   unsigned int n;
%   cin >> n;
%   unsigned int zpn = 1<<(n-1); 
%   unsigned int m[n*n];
%   cout << "Parameter: "<< n <<", Teilmengen: "<< zpn;
% 
%   for ( unsigned int i=0; i<n;   i++ )
%       for ( unsigned int j=0; j<n;j++)  m[i+n*j]     = 4;
%   for ( unsigned int i=0; i<n;   i++ )  m[i+n*i]     = 0;
%   for ( unsigned int i=0; i<n-1; i++ )  m[i+n*(i+1)] = 2;
%   m[n-1 + n*0] = 2;
% 
%   cout << "Resultat: "<<formel(n,m,n-1, zpn-1);
% \}
% \end{semiverbatim}
% \end{programm}
% \end{frame}
% 
% \begin{frame}[fragile]
% 
% Dynamisches Programm in \verb#C++#
% \begin{programm}
% \begin{semiverbatim}\bfseries\scriptsize
% #include <bitset>
% #include <iostream>
% #include <iomanip>
% using namespace std;
% 
% /* Achtung: V={0,1,...,n-1}
%    Modifikation: Nicht pi(1)=1 sondern pi(n)=n,
%    damit S nur aus {0,1,...,n-2}
% */
% 
% unsigned long formel(
%         unsigned int n, unsigned int m[]\Fb{, unsigned int g[]},
%         unsigned int i, bitset<30> S)\{
%   bitset<30> S2;
%   unsigned int minimum=2000000000, m2;
%   if (S.none()) return m[i+n*(n-1)] ;
%   else \{
%      for (unsigned j=0; j<n-1; j++)\{ if (S.test(j))\{
%            S2 = S;   S2.set(j,0);
%            m2 = m[i+n*j] + \Fb{g[j+n*S2.to_ulong()]};
%            if (m2 < minimum) minimum = m2;
%        \}
%      \}
%      return minimum;
%   \}
% \};
% \end{semiverbatim}
% \end{programm}
% \end{frame}
% \begin{frame}[fragile]
% \begin{programm}
% \begin{semiverbatim}\bfseries\scriptsize
% 
% int main()\{
%   unsigned int n;
%   cin >> n;
%   unsigned int zpn = 1<<(n-1); 
%   unsigned int m[n*n]\Fb{, g[n*zpn]};
%   cout << "Parameter: "<< n <<", Teilmengen: "<< zpn;
% 
%   for ( unsigned int i=0; i<n;   i++ )
%       for ( unsigned int j=0; j<n;j++)  m[i+n*j]     = 4;
%   for ( unsigned int i=0; i<n;   i++ )  m[i+n*i]     = 0;
%   for ( unsigned int i=0; i<n-1; i++ )  m[i+n*(i+1)] = 2;
%   m[n-1 + n*0] = 2;
% 
%   \Fb{for(unsigned int i=0; i<n-1;i++)
%      g[i+n*0] = formel(n,m,g,i,0);}
% 
%   \Fb{for (unsigned int k=1; k<= n-2; k++)\{
%     cout << k<< "...";
%     for (unsigned int iS=1; iS< zpn;iS+=1) \{
%        bitset<30> S(iS);
%        if (S.count()==k) \{
%          for ( unsigned int i=0; i<n-1;i++)
%            if (!S.test(i))\{
%                 g[i+n*iS]=formel(n,m,g,i,iS);
%     \} \} \} \} }
%   cout << "Resultat: "<<formel(n,m,n-1, zpn-1);
% \}
% \end{semiverbatim}
% \end{programm}
% \end{frame}

\begin{frame}[fragile]
Vergleich der Laufzeiten: \\
\pause (Intel Core  i5, 2.53GHz)%, \verb#g++ -O2#, \verb#ulimit -s unlimited#)
\pause

{\small $$\begin{array}{c|r|r|r}
&\mbox{rekursiver}&\mbox{dyn.Prog,}&\mbox{dyn.Prog,}\\
&\mbox{Algorithmus}&\mbox{Zeit}&\mbox{Speicher}\\\hline
n&(\approx (n{-}1)!~)&(\approx n^2\cdot 2^n)&(\approx n\cdot2^n)\\\hline
10& 0.01~s& <0.01~s& ?\\
11& 0.3~s& <0.01~s& ?\\
12& 4~s& <0.01~s& ?\\
13& 48~s& <0.01~s& ?\\
14& 650~s &  0.015~s & ?\\
16& ? &  0.02~s  &5~MB  \\
18& ? &  0.1~s& 12~MB\\
20& ? & 0.6~s & 43~MB\\
22& ? & 2.7~s&  180~MB\\
24& ? & 13~s& 770~MB\\
25& ? & 32~s& 1.6~GB\\
\end{array}$$
}

\pause
leichte Reduktion des Speichers auf Kosten der Zeit möglich:\pause
\begin{itemize}
\item für $g(i,S)$ nur $g(j,S')$ mit $|S'|=|S|+1$ benötigt\pause
\item ca.\ {\em halber} Speicherbedarf bei $n=24$ ...
\end{itemize}
\end{frame}



\begin{frame}
weiteres Beispiel: $0/1$-Rucksack-Problem\pause

\begin{itemize}
\item Gegeben: $n\in\nz$, $G\in\nz$, Vektoren $(v_1,...,v_n),(g_1,...,g_n)\in \nz^n$ \pause
\item Interpretation: $n$ Objekte mit\pause \begin{itemize}
\item Werten/Kosten/Gewinne \pause ($v$-Vektor)\pause
\item Gewichten \pause ($g$-Vektor)\pause
\item (Gewichts-)Kapazität $G$
\end{itemize}\pause
\item Gesucht: Wie groß kann der `Wert' $\sum_{i\in I}v_i$ einer Teilmenge $I$ von Objekten werden,\\\pause deren Gewicht $\sum_{i\in I}g_i$ nicht größer als die Schranke $G$?\pause
\item formal: bestimme 
$$\max\{ \sum_{i\in I}v_i\mid I\subseteq\{1,...,n\}\wedge\sum_{i\in I}g_i\leq G\}$$ 
\end{itemize}
\pause
Bekanntes (NP-vollständiges) Rucksack-Problem ist zugehöriges Entscheidungsproblem mit:\pause
\begin{itemize}
\item $(v_1,...,v_n)=(g_1,...,g_n)$\pause
\item Fragestellung $$G=\max\{ \sum_{i\in I}v_i\mid I\subseteq\{1,...,n\}\wedge\sum_{i\in I}g_i\leq G\}$$
\end{itemize}
\end{frame}



\begin{frame}
Formulierung von Teil-Lösungen:\pause
\begin{itemize}
\item bei $n=1$ \pause(Wert $v_1$, Gewicht $g_1$, Schranke $G$):\pause\\
Lösung trivial: \pause\begin{itemize}
\item $v_1$, falls $g_1\leq G$\pause
\item $0$, falls $g_1> G$
\end{itemize}\pause
\item bei $n>1$ Objekten teste zwei Möglichkeiten:\pause
\begin{itemize}
\item Objekt $n$ gehört zu optimaler Menge $I$:\pause\\ 
$I$ nutzt Teil-Lösung $I'\subseteq\{1,...,n-1\}$ mit Schranke $G-g_n$\pause\\
\item Objekt $n$ gehört nicht zu optimaler Menge $I$:\pause\\
$I$ ist identisch zu Teil-Lösung $I'\subseteq\{1,...,n-1\}$  mit Schranke $G$,
\typeout{ }
\typeout{ }
\typeout{ Hier noch mal genauer formulieren }
\typeout{ }
\typeout{ }
\end{itemize}
\end{itemize}\pause
Daher setze 
$$w(i,h):=\left\{\begin{tabular}{l}maximaler Lösungswert\\ für erste $i$ Objekte bei Schranke $h$
\end{tabular}\right.$$
\pause mit rekursiver Formulierung\pause
$$w(i,h)=\left\{\begin{array}{ll}
0&i=0\\
\pause w(i-1,h)&\pause i>0\wedge h< g_i\\
\pause\max\left\{\begin{array}{l} w(i{-}1,h),\\ w(i{-}1, h{-}g_i)+v_i\end{array}\right\}&\pause\mbox{sonst}
\end{array}\right.$$
\end{frame}



\begin{frame}[fragile]
Dynamisches Programm dazu:\pause
\begin{itemize}
\item verwende Tabelle für $w(i,h)$ mit $0\leq i<n$ und $0\leq h\leq G$
\end{itemize}\pause
\begin{programm}
\begin{semiverbatim}\bfseries
FOR i:=0 TO n-1 DO 
    FOR h:=0 TO G DO\pause
           berechne w[i,h] nach Formel\pause
berechne w[n,G] nach Formel
\end{semiverbatim}
\end{programm}
\pause
\begin{itemize}
\item Speicherplatz: $n\cdot(G+1)$ (optimierbar zu  $2(G+1)$ )\pause
\item 
Zeitaufwand: $n\cdot(G+1)\cdot\mbox{(Aufwand für Formelauswertung)}$

\end{itemize}
\pause
Uniformes Kostenmaß: \pause
\begin{itemize}
\item Aufwand $O(n\cdot G)$, d.h. linear in $n$\pause
\item 
Bei `beschränktem' $G$ ist $0/1$-Rucksack also {\bfseries polynomial}!
\end{itemize}
\pause
Wichtig also: betrachte auch $G$!\pause
\begin{itemize}
\item 
falls $G$ $k$ Bits hat: Aufwand $O(n\cdot 2^k)$, d.h. exponentiell in $k$\pause
\item 
vgl.\ Reduktion 3-KNF $\mapsto$ RUCKSACK (Satz \ref{RUCKSACK})\pause
\begin{itemize}
\item 
erzeugt Rucksackproblem mit $n\approx k$,\pause
 \item 
dynamisches Programm hat hier exponentielle Komplexität!
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}
Alternative Vorgehensweise:\pause
\begin{itemize}
\item Betrachte Teil-Lösungen für Kosten (und nicht für Gewichte)!\pause
\item 
definiere $g(i,v):=$ minimales Gewicht für Mengen von Objekten aus $\{1,...,i\}$, die zu den Kosten
$v$ führen\pause
\item dann wieder rekursiv $g(i,v)$ über  $g(j,v')$ mit $j<i$ definierbar\pause
\item setze dabei insbesondere $g(0,0)=0$ und $g(0,v)=\infty$ für $v>0$ \pause
\item Einzelheiten: Übung...
\end{itemize}
\end{frame}

\subsubsection{Backtracking}
\inhaltb{15}

\begin{frame}[fragile]
Backtracking:\pause
\begin{itemize}
\item Durchlauf durch (großen) Suchbaum\pause
\item Baum i.d.R. nur implizit gegeben\pause
\item wichtiges Teilziel: Ausschluss von Teilbäumen\pause
\item i.d.R. rekursive Implementierung
\end{itemize}\pause

Grundstruktur der Rekursion:\pause

\begin{programm}
\begin{semiverbatim}\bfseries
PROCEDURE \Fb{backtrack}(Lösungsansatz);\pause
  IF (Lösungsansatz == vollständige Lösung) 
    THEN gib Lösung aus\pause
    ELSE FOR (wichtige Erweiterungen des Lösungsansatzes) DO
             \Fb{backtrack}(Lösungsansatz mit Erweiterung)
         ENDFOR\pause
  ENDIF
  RETURN
ENDPROCEDURE
\end{semiverbatim}
\end{programm}\pause

Aufruf mit \verb#backtrack(leere Lösung)#
\end{frame}

\begin{frame}[fragile]
\begin{itemize}
\item Rekursion führt implizit zu Baumstruktur!\pause
\item Anzahl der Erweiterungen der Lösungsansätze klein halten!\pause
\item zur `Wichtigkeit' der Erweiterungen:\pause
\begin{itemize}
\item Jede Erweiterung, die noch zu Lösung werden könnte, ist wichtig!\pause
\item Leicht erkennbar, dass keine Lösung mehr entstehen kann: unwichtige Erweiterung\pause
\item ansonsten: vorsichtshalber als wichtige Erweiterung einstufen...
\end{itemize}\pause
\item falls keine Erweiterung wichtig $\leadsto$ Teilbaum wird ausgelassen!
\end{itemize}
\pause
Insbesondere bei CSP mit $n$ Variablen, $|D|=d$ und Ordnung $k$: \pause
\begin{itemize}
\item Erweiterung eines Lösungsansatzes = Belegung einer weiteren Variablen!\pause
\item Teste pro Variable alle $d$ möglichen Werte\pause
\item Also: $d$-ärer Suchbaum mit Tiefe $n$, Größe $d^n$\pause
\item Sobald für ein Constraint $C_j$ alle Variablen belegt sind:\\\pause
Falls $C_j$ dabei falsch wird: Werte weiterer Variablen unwichtig!
\end{itemize}

\end{frame}

\begin{frame}Grobe Abschätzung des Effektes:
\begin{itemize}
\item Constraint der Ordnung $k$ führt zur $d^k$ Teilbäumen\pause
\item Für jedes falsche Resultat: Ein Teilbaum weniger...\pause
\item Da jedes Constraint falsch werden kann (sonst trivial...):\\
\pause Statt $d^k$ Teilbäumen  i.d.R. nur $d^k-1$ \pause
\item Komplexität statt $d^n$ nur $(d^k-1)^{n/k}$
\end{itemize}\pause

heuristische Verbesserungen:\pause
\begin{itemize}
\item Sortiere Variablen nach Ordnung der Constraints:\pause
\item Erst Variablen in Constraints mit kleiner Ordnung belegen\pause
\item Bei Constraints mit gleicher minimaler Ordnung: \pause Häufigst benutzte
Variable zuerst belegen (reduziert Ordnung anderer Constraints!) 
\end{itemize}
\end{frame}





\begin{frame}[fragile]
Beispiel KNF-SAT:\pause

\begin{itemize}
\item Gegeben: Formel  $F$ in KNF mit $n$ Variablen\pause
\item Gesucht: Erfüllende Belegung $\Phi$
\end{itemize}\pause

naiver Algorithmus: Durchsuche alle möglichen Belegungen, z.B.\pause

\begin{programm}
\begin{semiverbatim}\bfseries
Gegeben \(F\) mit \(n\) Variablen\pause

FOR \(b\) := 0 TO \(power(2,n)-1\) DO\pause
    Interpretiere die Einzelbits von \(b\) als Belegung \(\Phi\).\pause
    Teste, ob \(F\) durch \(\phi\) erfüllt wird.\pause
    Wenn ja: RETURN TRUE\pause

RETURN FALSE
\end{semiverbatim}
\end{programm}\pause
Aufwand
\begin{itemize}
\item Formel nicht erfüllbar: $2^n\cdot$(Bestimmung des Wertes von $F$ bei $\phi$)\pause
\item Formel erfüllbar: schrumpft mit wachsender Zahl an Lösungen...
\end{itemize}

\end{frame}

\begin{frame}[fragile]
Backtracking-Algorithmus (einfachste Form): \pause

\begin{programm}
Gegeben: Formel $F$ mit Variablen $\{x_1,...,x_n\}$\pause

Belegung $\Phi$ ist String der Länge $n$ über $\{0,1,u\}$ (mit $0$: falsch, $1$: wahr, $u$: unbelegt)\pause
\begin{semiverbatim}\bfseries
BOOLEAN PROCEDURE backtrack(belegung \(\Phi\);\pause
  IF (\(\Phi\) enthält kein \(u\)) 
    THEN RETURN \(F(\Phi)\)
  ENDIF\pause
  IF (\(\Phi\) setzt eine Klausel in \(F\) auf \(0\) )
    THEN RETURN \(0\)
  ENDIF\pause
  wähle unbelegte Variable, Index sei \(i\)\pause
  IF  backtrack( \(\Phi[i:0]\) )
    THEN RETURN \(1\)
  ENDIF\pause
  RETURN backtrack( \(\Phi[i:1]\) )
ENDPROCEDURE\pause

main: 
  backtrack( \( u...u\) )
\end{semiverbatim}
\end{programm}
\end{frame}

\begin{frame}
Beispiel:
$F=\underbrace{(x_1\vee x_2)}_{c_1}\wedge
\underbrace{(x_1\vee\overline{x_2})}_{c_2}\wedge
\underbrace{(\overline{x_1}\vee x_3\vee x_4)}_{c_3}\wedge
\underbrace{(\overline{x_1}\vee \overline{x_3}\vee x_4}_{c_4})$
\[\includegraphics[width=.85\textwidth]{grafik/backtrack.pdf}\]

\end{frame}

\begin{frame}
Backtracking bei {\bfseries 2-KNF-SAT}:\pause
\begin{itemize}
\item Pro Klausel von 4 Wahrheitswerten nur 3 wichtig\pause
\item Formal damit statt $2^n$ nur $(\sqrt{3})^{n}$\pause
\item zudem: jede Variablen-Belegung legt Werte vieler direkt/indirekt verbundener
Variablen fest! \pause
\item Damit nur noch 2 Versuche pro `Zusammenhangskomponente'! \pause
\item Topologische Sortierung der Komponenten $\leadsto$ Polynomialer Algorithmus
(bei Modifikation des Backtracking)
\end{itemize}
\pause
Backtracking bei {\bfseries 3-KNF-SAT}:\pause
\begin{itemize}
\item 
Statt $2^n$ nur $\approx 7^{n/3}=1{,}913^n$,\pause
\item formal: bei $n=30$ nur 1/4 der Komplexität\pause
\item Hauptvorteil aber: \pause Jede Variablenbelegung macht aus manchen 
3er-Klauseln kleinere 2er-Klauseln, \pause
d.h. dieser Teil  dann wie 2-KNF-SAT behandelbar!
\end{itemize}

\end{frame}
\subsubsection{Branch and Bound}
\inhaltb{15}



\begin{frame}

\Fb{Branch and Bound}: Kombination zweier Strategien bei \Fb{Optimierungsproblemen}:
\pause
\begin{itemize}
\item Aufgabe: suche beste von allen(!) Lösungen\pause
\item wie bei Backtracking: Ausschluß von Lösungsansätzen\pause
\item zudem: bevorzugte Behandlung aussichtsreicher Lösungsansätze
\end{itemize}
\pause Dazu benötigt:\pause
\begin{itemize}
\item Optimierungsproblem mit baumartigem Lösungsalgorithmus\pause
\item einfache Bewertungsmöglichkeit $g$ der Güte eines Lösungsansatzes\pause
\item evtl. (möglichst gute) Schranke $G$ für die beste Gesamtlösung
\end{itemize}\pause
Vergleich:\pause
\begin{itemize}
\item Backtracking: Suche mit `nächster' Teil-Lösung fortgesetzt\pause
\item Branch and Bound: Suche mit `bestem' Lösungsansatz fortgesetzt\pause
\item statt Rekursionsstack wird Priority Queue verwendet
\end{itemize}
\end{frame}

\begin{frame}[fragile]
Branch-and-Bound-Algorithmus (einfachste Form): \pause
\begin{itemize}
\item Gegeben: Mimimierungsproblem\pause
\begin{itemize}
\item mit Bewertungsfunktion $v$ für Lösungen,\pause
\item mit Gütefunktion $g$ (`Bound') für Lösungsansätze
\end{itemize}\pause
\item Bedingung an $v$ und $g$:\pause\\ 
Ist Lösung $L$ Erweiterung des Ansatzes $A$, \pause dann $v(L)\geq g(A)$ 
\end{itemize}
\begin{programm}
\pause
\begin{semiverbatim}\bfseries
Ansatz         \(A\) \pause:= leerer Lösungsansatz\pause
Schranke       \(G\) := \(\infty\)\pause
Lösung         \(L\)\pause
Priority Queue \(pq\);\pause \(pq\).insert( \(A,\) \(g(A)\) )\pause

WHILE \(pq\).not_empty DO\pause
\(A\) := \(pq\).extract_min;\pause
  IF (\(A\) ist vollständige Lösung)  THEN\pause 
     IF ( \(v(A) < G\) ) THEN \(L\) := \(A\); \(G\) := \(v(A)\) ENDIF
 \pause ELSE\pause
     FORALL ( \(E\) Erweiterung von \(A\) ) DO\pause
        IF ( \(g(E) < G\) ) THEN  \(pq\).insert( \(E\), \(g(E)\) ) ENDIF
    \pause ENDFOR\pause
  ENDIF
ENDDO\pause
RETURN \(L\)
\end{semiverbatim}\end{programm}
\end{frame}

\begin{frame}
Beispiel: TSP
\begin{itemize}
\item $m_{i,j}$ Kosten/Gewicht der Kante $(ij)$\pause
\item $g$ Gewicht eines Pfades $i_1i_2 ... i_n$\pause
 $$g(i_1i_2 ... i_n)=m_{i_1,i_2}+...+m_{i_{n-1},i_n}$$
\pause
\item $v$ Gewicht einer kompletten Rundreise $i_1i_2 ...i_n$ mit $i_1=i_n$\pause
$$v(i_1i_2 ... i_n)=g(i_1 ... i_n)$$
\pause
\item bei nichtnegativen(!) Kosten $m_{i,j}$ gilt für $k\leq n$ \pause
$$v( i_1i_2 ... i_n)\geq g(i_1i_2 ... i_k)$$
\end{itemize}
\end{frame}

\begin{frame}
Betrachte TSP mit {\scriptsize $M=\left[\begin{array}{ccccc}
  - & 10 & 15 & 20\\
  5 &  - &  9 & 10 \\
  6 & 13 &  - & 12 \\
  8 &  8 &  9 &  -
\end{array}\right]$}\pause, Start mit $G=\infty$\pause

{\scriptsize$$\begin{array}{|l|}\hline
\mbox{Inhalt (Pfad,Gewicht) der Priority Queue:}\\\hline
(1,0)\\\hline
\pause\Fa{(12,10)}~~\Fa{(13,15)}~~\Fa{(14,20)}\\\hline
%
\pause(13,15)~~\Fb{(123,19)}~~\Fb{(124,20)}~~(1 4,20)\\\hline
%
\pause(123,19)~~(124,20)~~(14,20)~~\Fa{(134,27)}~~\Fa{(132,28)}\\\hline
%
\pause(124,20)~~(14,20)~~(134,27)~~(132,28)~~\Fb{(1234,31)}\\\hline
%
\pause(14,20)~~(134,27)~~(132,28)~~\Fa{(1243,29)}~~(1 234,31)\\\hline
%
\pause(134,27)~~(132,28)~~\Fb{(142,28)}~~\Fb{(143,29)}~~(1243,29)~~
(1 234,31)\\\hline
%
\pause(132,28)~~(142,28)~~(143,29)~~(1243,29)~~(1 234,31)~~
\Fa{(1342,35)})\\\hline
%
\pause(142,28)~~(143,29)~~(1243,29)~~(1234,31)~~
(1342,35)~~\Fb{(1324,38)}\\\hline
%
\pause(143,29)~~(1243,29)~~(1234,31)~~(1342,35)~~
\Fa{(1423,37)}~~(1324,38)\\\hline
%
\pause(1243,29)~~(1234,31)~~(1342,35)~~
(1423,37)~~(1324,38)~~\Fb{(1432,42)}\\\hline
%
\pause\mbox{erste Lösung gefunden: }\Fa{L=(12431)},\mbox{ neue Schranke }G=35\\
\pause(1234,31)~~(1342,35)~~(1423,37)~~(1324,38)~~(1432,42)\\\hline
\pause\mbox{ab hier: }pq\mbox{ wird nur noch geleert...}\\\hline
\end{array}$$}

\pause
Optimale Lösung ist $L=(12431)$ \pause mit Gewicht $35$
\end{frame}

\begin{frame}
Verbesserungen des Algorithmus:\pause
\begin{itemize}
\item[(1)]  Suche  besseren Startwert der Schranke $G$\pause
\begin{itemize}
\item z.B.
durch Vorab-Bestimmung einer (nicht zu schlechten) Lösung
\end{itemize}\pause
\item[(2)]  Bessere Datenstrukturen:\pause\\ 
Für TSP statt Pfad besser Paare (Knotenmenge, letzter Knoten)\pause
\begin{itemize}
\item 
z.B. statt $(1243,29)$ und $(1423,37)$ \pause nur $(~(\{2,4\},3)~,29)$ in $pq$\pause
\item 
benötigt \texttt{decreaseKey}-Operation für Priority Queues
\end{itemize}
\pause
\item[(3)]  Versuche die Unterschiede zwischen guten und schlechten Pfaden zu vergrößern...\pause\\
\begin{itemize}
\item Reduziere Gewichte der Pfade um Anteile, die allen Pfaden gemeinsam sind\pause
\item von Reduktion
profitieren insbesondere gute Lösungen
\end{itemize}
\end{itemize}

\end{frame}

\begin{frame}
Anwendung von (3) im Beispiel TSP: \pause Reduktion von  $M$ wie folgt\pause 
\begin{itemize}\item
subtrahiere von jeder Zeile in $M$ das Minimum $z_i$ der Zeile $i$,\pause\\ damit
Gewicht jeder(!) Lösung um $\sum k_i$ erniedrigt\pause
{\scriptsize $$M=\left[\begin{array}{ccccc}
  - & 10 & 15 & 20\\
  5 &  - &  9 & 10 \\
  6 & 13 &  - & 12 \\
  8 &  8 &  9 &  -
\end{array}\right] ~~~\leadsto ~~~M'=\left[\begin{array}{ccccc}
  - & 0 & 5 & 10\\
  0 &  - &  4 & 5 \\
  0 & 7 &  - & 6 \\
  0 &  0 &  1 &  -
\end{array}\right]$$}

\pause mit Minima $10,5,6,8$, \pause d.h. mit Erniedrigung um $10+5+6+8=29$\pause
\item
subtrahiere von jeder Spalte in $M'$  das Minimum $s_i$ der Spalte $i$,\pause\\ damit
Gewicht jeder(!) Lösung weiter um $\sum s_i$ erniedrigt\pause

{\scriptsize $$M'=\left[\begin{array}{ccccc}
  - & 0 & 5 & 10\\
  0 &  - &  4 & 5 \\
  0 & 7 &  - & 6 \\
  0 &  0 &  1 &  -
\end{array}\right] ~~~\leadsto ~~~M''=\left[\begin{array}{ccccc}
  - & 0 &  4 & 5\\
  0 & - &  3 & 0 \\
  0 & 7 &  - & 1 \\
  0 & 0 &  0 & -
\end{array}\right]$$}

\pause mit Erniedrigung um $0+0+1+5=6$\pause
\item Optimale Lösungen bei $M$ und $M''$ gleich,\\
aber im Gewicht verschieden\pause, sogar um $29+6=35$
\end{itemize}
\end{frame}

\begin{frame}
Betrachte TSP mit {\scriptsize$ M''=\left[\begin{array}{ccccc}
  - & 0 &  4 & 5\\
  0 & - &  3 & 0 \\
  0 & 7 &  - & 1 \\
  0 & 0 &  0 & -
\end{array}\right]$}, Start mit $G=\infty$\pause

{\scriptsize$$\begin{array}{|l|}\hline
\mbox{Inhalt (Pfad,Gewicht) der Priority Queue:}\\\hline
\pause(1,0)\\\hline
\pause\Fa{(12,0)}~~\Fa{(13,4)}~~\Fa{(14,5)}\\\hline
%
\pause\Fb{(124,0)}~~\Fb{(123,3)}~~(13,4)~~(14,5)\\\hline
%
\pause\Fa{(1243,0)}~~(123,3)~~(13,4)~~(14,5)\\\hline
%
\pause\mbox{erste Lösung gefunden: }\Fb{L=(12431)},\mbox{ neue Schranke }G=0\\
\pause(123,3)~~(13,4)~~~~(14,5)\\\hline
\pause\mbox{ab hier: }pq\mbox{ wird nur noch geleert...}\\\hline
\end{array}$$}

\pause
Optimale Lösung für $M''$ ist $L=(12431)$ mit Gewicht $0$\pause, damit wieder:

\pause Optimale Lösung für $M$ ist $L=(12431)$ mit Gewicht $35+0=35$
\end{frame}

\begin{frame}
Bestimmung guter Schrankenfunktionen:\pause
\begin{itemize}
\item Gegeben: Mimimierungsproblem $P$\pause
\begin{itemize}
\item mit Bewertungsfunktion $v$ für Lösungen,
\item benötigt: Gütefunktion $g$ (`Bound') für Lösungsansätze
\end{itemize}\pause
\item bestimme $g$ mit:\pause\\ Ist Lösung $L$ Erweiterung des Ansatzes $A$, dann $v(L)\geq g(A)$ 
\end{itemize} 
\pause

oft wird dazu {\bf Relaxation} benutzt:\pause
\begin{itemize}
\item Aufweichung der Aufgabenstellung von $P$ zu $P'$,\pause\\
 z.B. Weglassen eigentlich notwendiger Bedingungen\pause
\item $\leadsto$ Lösungsraum  von $P'$ \pause umfasst Lösungsraum von $P$\pause
\item evtl. effizienter Algorithmus für aufgeweichtes Problem $P'$ bekannt\pause
\item Gütefunktion $g'$ für $P'$ ist auch Gütefunktion $g$ für $P$...
\end{itemize}
\pause
Auch TSP-Beispiel als Relaxation interpretierbar:
\begin{itemize}
\item zyklenfreie Pfade als Lösung betrachten (statt Permutationen)\pause
\item dann: beste Lösung zu Ansatz $i_1...i_k$ \pause ist gerade  $i_1...i_k$ selbst...
\end{itemize}
\end{frame}
\subsection{Approximative Verfahren}
\subsubsection{Grundlegende Definitionen}
\inhaltb{15}


\begin{frame}
Betrachte Optimierungsprobleme\pause

Da vermutlich $P\neq NP$:\pause
\begin{itemize}
\item Dynamisches Programmieren, Backtracking, Branch-and-Bound sind i.d.R. nicht polynomial!\pause
\item als Alternative: statt `optimaler' nur `gute' Lösungen verlangen!\pause
\item suche Lösung $y \in S (x)$, so dass $v(y)$ nicht `allzu weit' von optimalen $v^*(x)=opt\{v(z)\mid z\in S(x)\}$ weg ist
\end{itemize}\pause
Anmerkung: das Finden einer zulässigen Lösung $y\in S (x)$ sollte nicht bereits $NP$-vollständig sein, \pause Beispiele:\pause
\begin{itemize}
\item Finden zulässiger Lösungen bei MaxSAT ist trivial.\pause
\item Finden zulässiger Lösungen bei TSP ist trivial, \pause\\ wenn $\infty$ in Lösungen zulässig ist\pause
\item Finden zulässiger Lösungen bei TSP ist NP-vollständig, \pause\\ wenn $\infty$ in Lösungen nicht zulässig ist \pause
(da damit die Existenz von Hamiltonkreisen getestet werden kann!)
\end{itemize}
\end{frame}

\begin{frame}
\begin{definition}
Für ein Optimierungsproblem $P$ mit zulässiger Eingabe $x$ und Lösungsmenge $S(x)$
ist die \emph{Performanz} $r(x,y)$ \pause einer Lösung $y\in S(x)$ definiert durch\pause
$$r(x,y):= \min\pause\left\{\frac{v(y)}{v^*(x)},\pause\frac{v^*(x)}{v(y)}\right\}$$
\pause wobei $v^*(x):=$ Optimum aus $\{v(z)\mid z\in S(x)\}$
\end{definition}
\pause Anmerkungen:\pause
\begin{itemize}
\item
Bei Minimierungsproblemen: $v^*(x):=\min\{v(z)\mid z\in S(x)\}$\pause
\item
Bei Maximierungsproblemen: $v^*(x):=\max\{v(z)\mid z\in S(x)\}$\pause
\item Stets $r(x,y)\leq 1$, \pause gute Approximationen haben $r(x,y)\approx 1$\pause
\item in Literatur auch Definition über Kehrwert $1/r$,\\\pause dann Performanz stets $\geq 1$ ...
\end{itemize}


\end{frame}

\begin{frame}
\begin{definition}[APX]\pause
Ein Optimierungsproblem liegt in \Fb{\bfseries APX}, \pause wenn es {\bfseries eine Zahl} $\delta\in(0,1)$ und
einen polynomialen Algorithmus gibt, \pause der bei jeder zulässigen Eingabe $x$ eine
Lösung $y\in S(x)$  liefert mit einer zugehörigen Performanz $r(x,y)\geq 1-\delta$.
\pause

Die Abkürzung {\bfseries APX} deutet an, dass das Optimierungsproblem - bis zu einem
gewissen Grad - approximierbar ist.
\end{definition}\pause
 $\delta$ darf beliebig nahe an $1$ sein, \pause d.h. schlechte Performanz erlaubt...\pause

Stärkere Einschränkung / bessere Approximationen:\pause
\begin{definition}[PTAS]
Ein Optimierungsproblem liegt in \Fb{\bfseries PTAS}, \pause wenn es {\bfseries für jede Zahl} $\delta\in(0,1)$ 
einen polynomialen Algorithmus gibt, \pause der bei jeder zulässigen Eingabe $x$ eine
Lösung $y\in S(x)$ liefert mit einer zugehörigen Performanz $r(x,y)\geq 1-\delta$.
\pause

Die Abkürzung {\bfseries PTAS} steht für \Fb{polynomial time approximation scheme}.
\end{definition}
\pause
Hier ist jede beliebig gute Performanzschranke  $\delta$ erreichbar.


\end{frame}

\begin{frame}

\begin{definition}[FPTAS]
Ein Optimierungsproblem liegt in \Fb{\bfseries FPTAS}, \pause
 wenn es einen Algorithmus
gibt, \pause
der bei jedem zulässigen $x$  und $k\in\nz$ als Eingabe \pause
 eine Lösung  $y\in S(x)$ 
liefert mit einer zugehörigen Performanz $r(x,y)\geq 1-1/k$. \pause
Die Komplexität des
Algorithmus muss polynomial in $x$  und $k$ sein.\pause


Die Abkürzung {\bfseries FPTAS} steht für \Fb{fully polynomial-time approximation scheme}.
\end{definition}
\pause
Bei FPTAS ist selbst die Abhängigkeit von der Performanzschranke noch polynomiell!\pause


Damit ergibt sich folgende Inklusionskette\pause

$$\begin{tabular}{c}
\bfseries\small
Menge exakt lösbarer Optimierungsprobleme aus $P$
\\
\pause
$\subseteq$ {\bfseries FPTAS} \pause$\subseteq$ {\bfseries PTAS} \pause$\subseteq$ {\bfseries APX} $\subseteq$ \\
\pause\bfseries\small Menge aller $NP$-Optimierungsprobleme
\end{tabular}$$

\end{frame}

\begin{frame}
Falls $P\neq NP$, sind  alle Inklusionen echt: \pause
$$\begin{tabular}{c}\bfseries\small
Menge exakt lösbarer Optimierungsprobleme aus $P$\\
$\stackrelsub{\subset}{\neq}$ {\bfseries FPTAS} 
$\stackrelsub{\subset}{\neq}$ {\bfseries PTAS}
$\stackrelsub{\subset}{\neq}$ {\bfseries APX}
$\stackrelsub{\subset}{\neq}$ \\\bfseries
\bfseries\small Menge aller $NP$-Optimierungsprobleme
\end{tabular}$$
\pause
Typische Beispiele einiger Klassen sind:\pause
\begin{itemize}
\item {\bfseries Menge exakt lösbarer Optimierungsprobleme aus $P$}:\pause\\

Maximale Flüsse in Graphen\pause\\ ($\leadsto$ Vorlesung Netzwerkalgorithmen)\pause
\item{\bfseries FPTAS}: \pause $0/1$-Rucksackproblem\pause\\
 ($\leadsto$ über dynamisches Programmieren, s.u.)\pause
\item {\bfseries APX}: \pause
 MaxSAT \pause
\begin{itemize}
\item
probabilistisches Approximationsverfahren  (analog APX)\pause\\ ($\leadsto$  Vorl.\ Approximative Algorithmen)\pause
\item  $P\neq NP \Rightarrow$  MaxSAT $\not\in$ PTAS: \pause über `PCP-Theorem' \pause \\
  (PCP: probabilistically checkable proofs) \pause \\ ($\leadsto$  Vorlesung Approximative Algorithmen)
\end{itemize} \pause 
\item {\bfseries Menge aller $NP$-Optimierungsprobleme}: \pause TSP\pause\\
(vermutlich nicht in {\bfseries APX}, s.u.)
\end{itemize}

\end{frame}

\begin{frame}
\begin{example}[zur Approximierbarkeit von TSP]

Annahme: Es gibt polynomialen Algorithmus für  TSP und $\delta\in(0, 1)$ mit
Performanz von mindestens $1-\delta$\pause
\begin{itemize}
\item
Sei $G$ beliebiger Graph mit $n$ Knoten, \pause definiere dazu TSP $x$ durch
\GLA m_{i,j}=\left\{\begin{array}{l}1,\mbox{ falls }(i,j)\mbox{ Kante in }G\\
1+\lceil\frac{n}{1-\delta}\rceil, \mbox{ sonst}
\end{array}\right.
\GLE
\item \pause
TSP-Approximation liefert zu $x$ Lösung $y$  mit Performanz
$r(x,y)=\frac{v^*(x)}{v(y)}\geq 1-\delta$\pause
\item Existiert Hamilton-Kreis in $G$, dann 
$v^*(x)=n$, \pause also $v(y)< \frac{n}{1-\delta}$, \pause d.h.
$y$ nutzt nur Kanten aus $G$ (d.h. findet Hamilton-Kreis in $G$)\pause
\item Über $v(y)$ kann also entschieden werden, ob in 
$G$ ein Hamilton-Kreis existiert ...
\end{itemize}
\pause also
 $$\mbox{\bfseries TSP}\in\mbox{\bfseries APX} \Longrightarrow P=NP$$
d.h. {\bfseries TSP} liegt vermutlich nicht in {\bfseries APX}!
\end{example}

\end{frame}

\begin{frame}
\begin{example}[$0/1$-Rucksack liegt in {\bfseries FPTAS}]\pause

Löse $0/1$-Rucksack über `minimales Gewicht für gesuchten Gewinn':\pause
\begin{itemize}
\item Gegeben: $n\in\nz$, $G\in\nz$, Vektoren $(v_1,...,v_n),(g_1,...,g_n)\in \nz^n$\pause
 \item  definiere $g(i,w):=$ minimales Gewicht für Teilmengen von Objekten aus $\{1,...,i\}$, \pause die zum Gewinn $\geq w$ führen\pause
\item formal: berechne
$$g(i,w)=\min\{ \sum_{j\in I}g_j\mid I\subseteq\{1,...,i\}\wedge\sum_{j\in I}v_j\geq w\}$$ \pause
\item Gesucht: größter Gewinn $w$ mit $g(n,w)\leq G$\pause
\item rekursive Formulierung von $g(i,w)$:\pause
$$g(i,w)=\left\{\begin{array}{ll}
0&w\leq 0\\
\infty& w> 0 \wedge i=0\\
\pause\min\left\{\begin{array}{l} g(i{-}1,w),\\ g(i{-}1, w{-}v_i)+g_i\end{array}\right\}&\pause\mbox{sonst}
\end{array}\right.$$
\end{itemize}
\end{example}
\end{frame}



\begin{frame}[fragile]
\begin{cont}{0/1-Rucksack in FPTAS}
Dynamisches Programm dazu (für exakte Lösung):\pause
\begin{itemize}
\item statt Funktion $g(i,w)$ verwende Tabelle $g[i,w]$ mit $0\leq i<n$ \\ aber nur für  $w$ mit $g[i,w]\leq G$
\end{itemize}\pause
\begin{programm}
\begin{semiverbatim}\bfseries
FOR i:=0 TO n DO 
    w:=0\pause;
    REPEAT
      w = w + 1; 
      berechne g[i,w] nach Formel\pause
    UNTIL g[i,w]\(>\) G
ENDFOR\pause
Ausgabe: w-1
\end{semiverbatim}
\end{programm}\pause
\begin{itemize}\item
Ausgabe also: größtes $W$ mit  $g[n,W]\leq G$\pause
\item $I$ sei zu $W$ gehörige optimale Teilmenge von $\{1,...,n\}$\pause
\item zur Tabellengröße: Zugriffe nur auf $g[i,w]$ mit $w\leq W+1$\pause
\item Aufwand: ${\cal O}(n\cdot W)$ (Funktionsauswerungen ignorierbar!)
\end{itemize}
\end{cont}
\end{frame}

\begin{frame}[fragile]
\begin{cont}{0/1-Rucksack in FPTAS}
jetzt approximative Lösung:\pause
\begin{itemize}\item wähle $m$ geeignet (s.u.), \pause
 setze \Fb{$v'_i:= \lfloor v_i/m\rfloor$}\pause
\item löse $(0,1)$-Rucksack für  $(v'_1,...,v'_n)$\pause\\ (aber mit unveränderten  $(g_1,...,g_n)$ und $G$)\pause
\item  $J$ sei die dabei gefundene optimale Menge, \pause 
mit  $V':=\sum_{i\in J}v'_i$\pause
\item setze  $V:=\sum_{i\in J}v_i$ \pause (d.h. neue optimale Menge, aber alte Kosten!)
\end{itemize}
\pause
Vergleiche nun  $J$ mit $I$ \pause sowie die drei Werte $W$, $V'$ und $V$:\pause
\begin{itemize}
\item Zwischen $J$ und $I$ lässt sich kein  direkter Zusammenhang finden\pause, Objekte
der Lösungen $I$ und $J$ können komplett verschieden sein!\pause
\item $J$ erfüllt $\sum_{i\in J}g_i\leq G$\pause, d.h.
$J$ ist auch (i.d.R. nicht-optimale) Lösung für das Ursprungsproblem, \pause
d.h $V\leq W$, \pause zudem  
\GLA V'=\sum_{i\in J}v'_i\pause\leq\sum_{i\in J}v_i/m\pause=V/m\leq W/m\GLE
\item \pause damit sofort:
Aufwand für die Lösung des modifizierten Problems mit $(v'_1,...,v'_n)$ ist
${\cal O}(n\cdot V')={\cal O}(n\cdot W/m)$
\end{itemize}

 
\end{cont}
\end{frame}

\begin{frame}
\begin{cont}{0/1-Rucksack in FPTAS}
Betrachte folgendes Beispielproblem:\pause
$$\Fb{ n=3, (v_1,v_2,v_3)=(3,5,6), (g_1,g_2,g_3)=(1,2,3), G=5} $$ 
\pause
Resultate beim dynamischen Programm:
{\footnotesize
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
W:& 1&2&3&4&5&6& 7&8&9& 10&11&12&...\\\hline\hline
i=1& 1&1&1&\infty\\\hline
i=2& 1&1&1&2&2&3&3&3&\infty\\\hline
i=3& 1&1&1&2&2&3&3&3&4&5&\Fb{5}&6\\\hline
\end{array}$$
}
\pause

Lösung: $W=11$ bei der Menge $I=\{2,3\}$\pause

Teste Approximation mit $m=3$, also $\Fb{(v'_1,v'_2,v'_3)=(1,1,2)}$\pause
{\footnotesize
$$\begin{array}{|c|c|c|c|c|c|}\hline
V':& 1&2&3&4&...\\\hline\hline
i=1& 1&\infty\\\hline
i=2& 1&3&\infty\\\hline
i=3& 1&3&\Fb{4}&6\\\hline
\end{array}$$
}

\pause
Lösung: $V'=3$ bei $J=\{1,3\}$, \pause
d.h. Approximation an $W$ ist $V=9$.
\end{cont}
\end{frame}

\begin{frame}[fragile]
\begin{cont}{0/1-Rucksack in FPTAS}
zur Performanz  $V/W$ der Lösung $J$ (für das Originalproblem):\pause
\begin{itemize}\item Da $J$ optimal für $(v'_1,...,v'_n)$
gilt  (1) $\sum_{i\in I}v'_i\leq V'$.\pause
\item
Setze $v_{max}:=\max\{v_1,...,v_n\}$\pause, damit sofort (2) $W\leq n\cdot v_{max}$\pause
\item o.B.d.A. stets $g_i\leq G$ \pause(sonst Objekt $i$ uninteressant...)\pause,\\
damit andererseits (3) $v_{max}\leq W$\pause
\item 
Mit Setzung $v'_i:= \lfloor v_i/m\rfloor$ ist $v'_i\geq v_i/m-1$\pause, also
\GLA V&= &\sum_{i\in J}v_i \pause\geq \sum_{i\in J}v'_i\cdot m 
 \pause=V'\cdot m\pause\stackrel{(1)}{\geq}\pause  \sum_{i\in I}v'_i\cdot m  \\
&\pause\geq&\pause
 \sum_{i\in I}(v_i/m-1)\cdot m \pause\geq
 \sum_{i\in I}(v_i - m)\pause\geq W-n\cdot m
\GLE
\item  \pause für die Performanz ergibt sich:
\GLA\frac{V}{W}\pause\geq \frac{W-nm}{W}\pause\geq 1-\frac{n\cdot m}{W}\pause\stackrel{(3)}{\geq} \pause 1-\frac{n\cdot m}{v_{max}}
\GLE
\end{itemize}
\end{cont}
\end{frame}
\begin{frame}[fragile]
\begin{cont}{0/1-Rucksack in FPTAS}
\begin{itemize}
\item
Für Ziel-Performanz $1-1/k$ \pause wähle $m$ so, dass $\frac{n\cdot m}{v_{max}}\leq 1/k$\pause, z.B. 
$$m=\frac{v_{max}}{k\cdot n}$$
\pause mit Aufwand
$${\cal O}(n\cdot W/m)\pause={\cal O}(k\cdot n^2\cdot W/v_{max})\pause\stackrel{(2)}{=}{\cal O}(k\cdot n^3)$$
\item\pause
Die Komplexität ist also polynomial in $n$ und $k$.
\end{itemize}
\end{cont}
\end{frame}

\begin{frame}
Anmerkungen:\pause
\begin{itemize}
\item Ein Problem heißt {\em stark NP-vollständig}, \pause wenn es auch noch NP-vollständig ist,
wenn alle involvierten Zahlen in unärer Schreibweise (statt binär) eingegeben werden.\pause
\item Bei unärer Notation wird die Eingabe wesentlich länger,\pause\\
 ein polynomialer Algorithmus darf länger laufen...\pause
\item Gibt man bei  $0/1$-Rucksack die Schranke $G$ unär an,\\
so gibt es eine polynomiale Lösung.\pause\\
(Bsp: bekanntes dynamisches Programm mit Laufzeit ${\cal O}(n\cdot G)$ )\pause\\
 $0/1$-Rucksack ist damit nur `schwach NP-vollständig'!\pause
\item Stark NP-vollständig sind z.B. TSP, 3-KNF-SAT, Färbbarkeit,...\pause
\item Es gilt sogar: \begin{itemize}
\item \bfseries Falls P$\neq$ NP, so liegt kein  stark NP-vollständiges Problem in FPTAS! 
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\begin{example}[TSP-Varianten]\pause
Wichtige Modifikationen des TSP sind:\pause
\begin{itemize}
\item Metrisches TSP: \pause Kosten $m_{i,j}$ der Kanten sind symmetrisch \pause und erfüllen die
Dreiecksungleichung $m_{i,j}\leq m_{i,k}+m_{k,j}$\pause
\item Euklidisches TSP: \pause Punkte liegen auf der Ebene,\pause \\ Entfernungen der Punkte
entsprechen dem Euklidischen Abstand\pause
\end{itemize}
\pause Hier gilt:\pause
\begin{itemize}
\item Metrisches TSP liegt in {\bfseries APX}, \pause wobei die Performanz $2/3$ beträgt \pause (d.h. die gefundene Route
ist 50\% maximal länger als die optimale Route)\pause (Christofides, 1976)\pause
\item Metrisches TSP liegt nicht in {\bfseries PTAS}\pause (wenn P$\neq$NP) (Arora, 1992)\pause
\item Euklidisches TSP  ist NP-vollständig\pause
\item Euklidisches TSP liegt in {\bfseries PTAS}\pause (Arora, 1996)
\end{itemize}
\end{example}  
\pause
Im folgenden: Techniken, die bei Approximationsversuchen angewendet werden \pause (i.d.R.
ohne Garantie für Performanz oder polynomiale Zeitkomplexität).
\end{frame}


\subsubsection{Greedy-Algorithmen}
\inhaltb{15}

\begin{frame}
Greedy-Verfahren: \pause
\begin{itemize}
\item Ziel: exakte/approximative Lösung von Optimierungsproblemen\pause
\item wieder: Lösung durch Erweiterung von Lösungsansätzen...\pause
\item dynamisches Programm: jeweils beste Erweiterung ($\leadsto$  Tabelle...)\pause
\item Greedy: gute, leicht findbare Erweiterung (ohne Tabelle...)\pause
\item Grundidee: \pause\Fb{\em Nimm immer das beste Stück!}
\end{itemize}
\pause
Beispiel: $0/1$-Rucksackproblem, 
$$ n=3, (v_1,v_2,v_3)=(3,5,6), (g_1,g_2,g_3)=(1,2,3), G=5 $$ 
\pause
Greedy-Heuristik hier: \\
{\em Nimm das Stück mit den höchsten Wert pro Gewichtsanteil!}
\pause

Reihenfolge für Beispiel: $$\frac{3}{1} \geq \frac{5}{2} \geq \frac{6}{3}$$
\pause also: erst Objekt 1 nehmen, \pause dann Objekt 2, \pause dann ... $G$ überschritten.\pause

Resultat: Lösung $\{1,2\}$ \pause mit Wert $3+5$ \pause (nicht optimal...) 
\end{frame}

\begin{frame}
\begin{example}[Bruchteil-Rucksackproblem]
\pause
\begin{itemize}
\item Gegeben: $n\in\nz$, $G\in\nz$, Vektoren $(v_1,...,v_n),(g_1,...,g_n)\in \nz^n$ \pause
\item Gesucht: Wie groß kann der `Wert' von Objekten werden,\\\pause deren Gewicht $\sum_{i\in I}g_i$ nicht größer als die Schranke $G$?\pause
\item Aber: \Fb{Jetzt dürfen Objekte zerteilt werden!}\pause
\item als Lösung daher jetzt ein Vektor $(a_1,...,a_n)$ \pause mit $a_i\in\qz$ \pause 
und $0\leq a_i\leq 1$ \pause
(statt einer Menge $I$) \pause
\item formal: bestimme 
$$\max\{ \sum_{i=1}^na_iv_i\pause \mid a_i\in[0,1]\pause \mbox{ mit } \sum_{i=1}^na_ig_i\leq G\}$$
\end{itemize}

\pause
Greedy-Ansatz: \pause
\begin{itemize}\item
Sortiere alle Objekte nach Wert $v_i/g_i$, \pause
d.h.
$\displaystyle\frac{v_1}{g_1}\geq \frac{v_2}{g_2}\geq... \geq\frac{v_n}{g_n} $\pause
\item dann nimm soviel von den hochwertigen Objekten, wie möglich...
\end{itemize}
\end{example}
\end{frame}

\begin{frame}[fragile]
\begin{cont}{Bruchteil-Rucksackproblem}
Algorithmische Lösung:\pause

\begin{programm}
\bfseries\em
$k :=0$\pause\\
WHILE $\displaystyle\sum_{i=1}^{k+1} g_i\leq G$ DO $k:=k+1$ ENDWHILE\pause\\
$\displaystyle b:= (G-\sum_{i=1}^{k}g_i)/g_{k+1}$\pause\\
Optimale Lösung ist 
$(a_1,a_2,...,a_n)=(\underbrace{1,1,...1}_k, b,\underbrace{0,0,...,0}_{n-k-1})$ 
\end{programm}
\pause Grundidee zu Nachweis der Optimalität der Lösung:\pause
\begin{itemize}
\item Sei $(a'_1,a'_2,...,a'_n)$ eine andere Lösung.\pause
\item Betrachte $j:=\min\{i\mid a'_i\neq a_i\}$\pause
\item Dann $\sum_{i=1}^{j} g_i < G$, also gibt es $m>j$ mit
$a'_m>0$.\pause
\item Transferiere dann Gewicht von Objekt $m$ zu Objekt $j$,\pause\\
(d.h. verkleinere $a'_m$ und vergrößere $a'_j$ soweit wie möglich)\pause
\item die entstehende Lösung wäre nicht schlechter...,\pause\\ aber `näher' an $(a_1,a_2,...,a_n)$
\end{itemize}

\end{cont}
\end{frame}

\begin{frame}
Allgemeine Form der Probleme, bei denen Greedy anwendbar ist:\pause
\begin{definition}
$E$ sei endliche Menge, \pause${\cal U}$ sei eine Menge von Teilmengen von $E$.\pause

Die Struktur $(E,{\cal U})$ heißt \Fb{Teilmengensystem}\pause, wenn
\begin{itemize}
\item $\emptyset\in {\cal U}$\pause
\item $A\subseteq B\pause\wedge B\in {\cal U} \pause\Rightarrow A\in{\cal U}$
\end{itemize}
\end{definition}
\pause
$w:E\to\qz$ sei eine Kostenfunktion, \pause\\
 gesucht wird eine in $\cal U$ maximale Menge $T$ (bzgl. $\subseteq$) \pause
mit maximalem Gesamtkosten $$w(T)=\sum_{e\in T} w(e)$$\pause
\begin{itemize}
\item Die Rolle der Gewichtsschranke $G$ übernimmt das Teilmengensystem $\cal U$\pause
\item
Dabei ist $T\in{\cal U}$ maximal in $\cal U$\pause, 
wenn kein $T'\in{\cal U}$ mit $T\subset T'$ existiert.
\end{itemize}
\end{frame}

\begin{frame}[fragile]
kanonischer Greedy-Algorithmus für Teilmengensysteme:\pause

\begin{programm}
\bfseries\em
Ordne die Elemente in $E=\{e_1,...,e_n\}$,\pause\\
\hspace*{2em} so dass $w(e_1)\geq w(e_2)\geq ...\geq w(e_n)$\pause\\
Setze $T:=\emptyset$\pause\\
FOR $k:=1$ TO n DO\pause\\
\hspace*{2em}IF $T\cup \{e_k\}\in {\cal U}$ THEN $T:=T\cup \{e_k\}$\pause\\
ENDFOR\pause\\
Ausgabe von $T$ als Lösung
\end{programm}

\pause
Charakterisierung der Probleme, die Greedy-Algorithmus optimal  löst:\pause
\begin{definition}
Ein Teilmengensystem $(E,{\cal U})$ heißt \Fb{Matroid}\pause, wenn zusätzlich die
Austauscheigenschaft gilt:\pause
\begin{itemize}
\item $A,B\in{\cal U}\pause\wedge |A|<|B|~~~ \pause\Rightarrow~~~ (\exists x\in B\setminus A)~ A\cup\{x\}\in{\cal U}$
\end{itemize}
\end{definition}
\pause
\begin{itemize}
\item  `Matroid' verallgemeinert Begriff `(lineare) Unabhängigkeit' \pause
\item  In Matroiden haben maximale Mengen gleiche Mächtigkeit!
\end{itemize}
\end{frame}

\begin{frame}
Beispiel für Matroide: \pause
\begin{itemize}
\item seien $n,k\in\nz$ gegeben, $k\leq n$\pause
\item betrachte $E=\{1,2,...,n\}$\pause
\item setze ${\cal U}=\{ A\subseteq E~~:~~ |A|\leq k\}$
\end{itemize}\pause
Maximale Menge sind hier die $k$-elementigen Mengen\pause,\\
 die Austauscheigenschaft ist
offensichtlich erfüllt.\pause

Weitere Beispiele für Matroide $(E,{\cal U})$:\pause
\begin{itemize}
\item $E$: endliche Menge von Vektoren, \pause\\ 
$\cal U$: linear unabhängige Teilmengen von $E$\pause

 (z.B.: $E$ besteht aus  Spalten einer Matrix, daher auch `Matroid')\pause

\item $E$: Kantenmenge eines endlichen Graphen $G$, \pause\\
 $\cal U$: kreisfreie Teilmengen von $E$\pause

 (auch `graphisches Matroid' genannt)\pause

Maximale Elemente von $\cal U$ sind aufspannende Wälder von $G$.
\end{itemize}
\end{frame}

\begin{frame}
Bedeutung der Austauscheigenschaft: \pause
\begin{itemize}
\item $A$ und $B$ seien maximale Elemente im Matroid $(E,{\cal U})$\pause
\item Damit $|A|=|B|$\pause
\item Falls $A\neq B$:\pause
\begin{itemize}
\item Wähle $a\in A\setminus B$.\pause
\item Zu $A\setminus \{a\}$ gibt es $b\in B\setminus A$ \pause mit $A':= A\setminus \{a\}\cup\{b\}\in {\cal U}$\pause
\item $A'\setminus B$ ist kleiner als $A\setminus B$\pause, $A'\cap B$ ist  größer als $A\cap B$ 
\end{itemize}\pause
\item
Also: Man kann $A$ durch Austausch einzelner Elemente schrittweise in $B$ umwandeln, ohne dabei $\cal U$ zu verlassen!
\end{itemize}
\pause
\begin{theorem}
Sei  $(E,{\cal U})$ ein Teilmengensystem.\pause 

Der kanonische Greedy-Algorithmus liefert beim Optimierungsproblem \pause genau dann \pause
{\bfseries für jede beliebige} Kostenfunktionen $w:E\to \qz$ \pause die optimale Lösung\pause, 
wenn $(E,{\cal U})$ ein Matroid ist.
\end{theorem}
\end{frame}

\begin{frame}
Beweis von "$\Leftarrow$": \pause
\begin{itemize} \item gegeben: $(E,{\cal U})$ Matroid, \pause $w:E\to \qz$ Gewichtsfunktion \pause
\item O.B.d.A.: bereits Ordnung $w(e_1)\geq w(e_2)...\geq w(e_n)$ vorhanden \pause
\item $T=\{e_{i_1},...,e_{i_k}\}$ sei Lösung durch Greedy-Algorithmus. \pause
\item Annahme: Greedy-Algorithmus liefert nicht die optimale Lösung. \pause
\item $T'=\{e_{j_1},...,e_{j_k}\}$ sei bessere Lösung,  \pause d.h. $w(T')> w(T)$ \pause
\item O.B.d.A.: $i_1<i_2<...<i_k$  \pause und  $j_1<j_2<...<j_k$ \pause
\item Also existiert minimales $\mu$ mit $w(e_{j_\mu})>w(e_{i_\mu})$, \pause\\ insbesondere dabei
$j_\mu<i_\mu$  \pause
\item Wende Austauscheigenschaft auf $A=\{e_{i_1},...,e_{i_{\mu-1}}\}$ und $ B=\{e_{j_1},...,e_{j_{\mu}}\}$ an: \pause

Es gibt $e_{j_\sigma}\in B\setminus A$ \pause mit $A\cup \{e_{j_\sigma}\}\in {\cal U}$ \pause
\item Mit $\sigma\leq \mu$ jedoch $w(e_{j_\sigma})\geq w(e_{j_\mu}) > w(e_{i_\mu})$, \pause d.h. Greedy-Algorithmus hätte
$e_{j_\sigma}$vor $e_{i_\mu}$  in $T$ aufnehmen müssen. \pause \widerspruch
\end{itemize}
\end{frame}

\begin{frame}
Indirekter Beweis von "$\Rightarrow$": \pause
\begin{itemize} \item Annahme: Austauscheigenschaft gilt nicht, \pause\\
 aber Greedy liefert für jedes $w$ optimale Lösung. \pause
\item Also gibt es $A,B\in{\cal U}$ mit $(\forall b\in B{\setminus} A) A\cup \{b\} \not\in{\cal U}$. \pause
\item Setze $r:=|B|$ und betrachte folgende Kostenfunktion $w$: \pause
$$w(e):=\left \{
\begin{array}{ll}
r{+}1,&e\in A\\
 \pause r,& \pause e\in B{\setminus} A\\
 \pause 0,& \pause \mbox{sonst}
\end{array}
\right.$$
\item  \pause Greedy-Algorithmus: Lösung $T$ mit  $A\subseteq T$  \pause und $T\cap(B\setminus A)=\emptyset$. \pause
\item Wegen $B\in {\cal U}$ gibt es auch eine Lösung $T'$ mit $B\subseteq T'$ \pause
\item Dann jedoch
\GLA w(T)&=& (r{+}1)\cdot |A| \pause\leq  (r{+}1)\cdot  (r{-}1)  \pause=r^2 -1\\
 \pause w(T')& \pause\geq& \pause r\cdot |B| \pause= r^2\GLE
 \pause Also $w(T)< w(T')$, d.h. Greedy versagt bei diesem $w$. \pause \widerspruch

\end{itemize}
\end{frame}

\begin{frame}
Also: \pause
\begin{itemize}
\item Teilmengensysteme erlauben die Anwendung von Greedy-Algorithmen \pause
\item Matroide führen zu optimaler Lösung  \pause
\item Oft jedoch: Austauscheigenschaft nicht vollständig erfüllt \pause\\
(z.B.: $\exists$ mehrere maximale Mengen mit untschiedlicher Mächtigkeit) \pause\\
also Greedy-Lösung nicht optimal, sondern nur approximativ \pause
\item mögliches anderes Problem: \pause\\
 nicht-additive Kostenfunktion, $w(T)\neq \sum _{e\in T} w(e)$ \pause
\item aber: Greedy liefert oft gute Heuristik! 
\end{itemize}\pause
Im Folgenden: Beispiele für `gute' Greedy-Heuristiken bei \pause
\begin{itemize}
\item Färbbarkeit
\item TSP
\end{itemize}
\end{frame}

\begin{frame}
\begin{example}[Färbbarkeit] \pause
\begin{itemize}
\item Gegeben Graph $G=(V,E)$ \pause
\item  Ziel: Färbe Knoten mit möglichst wenigen Farben, \pause\\
 d.h. suche `kleines' $k\in\nz$
und Funktion $f:V\to \{0,...,k{-}1\}$, \pause\\ so dass für Kanten $(u,v)\in E$ stets $f(u)\neq f(v)$ .
 \pause
\item Greedy-Heuristik:  \pause
\begin{itemize}
\item Sortiere $V$ nach Grad $\delta(v)$ der Knoten $v\in V$, \pause\\ 
also o.B.d.A.: $V=\{v_1,...,v_n\}$ mit $\delta(v_i)\geq \delta(v_{i+1})$. \pause
\item Wiederhole für $\mu=1,2,...,n$: \pause Setze 
\GLA f(\mu):=\min(\nz\setminus \{f(i)\mid i<\mu,  \pause(v_i,v_\mu)\in E\})\GLE
\item \pause
 Jeder Knoten erhält also, in der Reihenfolge absteigender Grade, \pause die jeweils kleinstmögliche Farbe. 
\end{itemize}\pause
\item Jeder Graph mit maximalem Grad $\Delta$  \pause wird dabei mit höchstens $\Delta+1$ Farben gefärbt!

\end{itemize}
\end{example}
\end{frame}

\begin{frame}
Aus Übung:  \pause 2-färbbare (d.h. bipartite) Graphen sind in Polynomzeit färbbar! \pause
Damit: \begin{lemma}\pause
Jeder 3-färbbare Graph mit $n$ Knoten und Grad $\Delta$  \pause kann in Polynomzeit  \pause mit 
${\cal O}(\min(\Delta,\sqrt{n}))$ Farben gefärbt werden.
\end{lemma} \pause
Beweis dazu:  \pause
\begin{itemize}
\item Ist $G$ 3-färbbar,  \pause dann ist bei jedem Knoten $v$ die Menge $N(v)$ seiner Nachbarn 2-färbbar! \pause
\item Für jeden Knoten $v\in V$ mit $\delta(v)\geq\sqrt{n}$  \pause ist  $\overline{N}(v):=N(v)\cup \{v\}$  \pause also schnell
mit 3 (neuen) Farben färbbar.  \pause\\
Danach entferne $\overline{N}(v)$ aus dem Graphen. \pause
\item Da $|N(v)|\geq \sqrt{n}$:   \pause Nach maximal $\sqrt{n}$ Iterationen kein Knoten mehr in $G$ 
mit $\delta(v)\geq\sqrt{n}$. \pause
\item Rest des Graphen dann mit $\leq\sqrt{n}$ weiteren Farben färbbar! 
\end{itemize}\pause
Bestes bekanntes Resultat (Baumann, 2004): \pause 
Färbung 3-färbbarer Graphen in Polynomzeit mit ${\cal O}(n^{3/14})$ Farben...
\end{frame}

\begin{frame}
\begin{example}[Greedy-Algorithmen für TSP]\pause
\begin{itemize}
\item Grundidee: Konstruiere sukzessive immer längere Strecken,\pause\\
 bis schließlich eine Rundreise entsteht...\pause
\item Heuristik `Nearest Neighbor':\pause
\begin{itemize}
\item Gehe vom aktuellen Tour-Ende \pause immer zur nächstliegenden neuen Stadt
\end{itemize}
\pause
\item Heuristik `Tourerweiterungen':\pause
\begin{itemize}
\item Starte mit kurzer Tour aus zwei  Städten.\pause
\item Erweitere Tour iterativ um je einen Knoten; \pause Heuristiken dabei:\pause

--- `Random Insertion': \pause Wähle neuen Knoten zufällig\pause

--- `Farthest Insertion': \pause Wähle Knoten, dessen Minimalabstand zur aktuellen Route möglichst groß
ist\pause
\item Gewählter Knoten wird an optimaler Position in die Tour eingefügt.
\end{itemize}\pause
\item `Nearest Neighbor' ist nur mäßig erfolgreich: \pause\\ Anfangs viele kurze Strecken, \pause aber am Ende kostspieliges Einsammeln übersehener, 
weit auseinanderliegender Städte\pause

(aber mit Nachverbesserungen evtl.\ brauchbar, s. lokale Suche)\pause
\item `Farthest Insertion' scheint die bessere Heuristik zu sein: \\\pause Grobstruktur der Route wird relativ schnell
festgelegt!
\end{itemize}

\end{example}
\end{frame}

\subsubsection{lokale Suche}
\inhaltb{15}

\begin{frame}
`Lokale Suche' zur Verbesserung von gefundenen Lösungen:
\begin{itemize}
\item Greedy-Algorithmus liefert Startwert für Maximumsuche...\pause
\item Ziel: analog zur Austauscheigenschaft \pause (tausche beliebig $a\in A$ gegen $b\in B\setminus A$)
 teste lokale Änderungen\pause
\item z.B.: nach Konstruktion einer Lösung \pause entferne Teile der Lösung \pause und suche eine `Zeitlang' nach Verbesserungen
\end{itemize}\pause
Grundstruktur:
\begin{programm}
\bfseries\em
Erzeuge eine Anfangslösung $L$.\pause\\
REPEAT\pause\\
\hspace*{3em}Modifiziere $L$ zufällig zu $L'$ \pause\\
\hspace*{3em}IF $L'$ ist besser als $L$ THEN $L=L'$ ENDIF \\
UNTIL längere Zeit keine Verbesserung gefunden\\
AUSGABE von $L$
\end{programm}
 \pause Prinzipieller Nachteil: \pause
\begin{itemize}
\item die gefundene Lösung ist ein `lokales Optimum'...
\item das globale Optimum kann beliebig weit entfernt sein!
\end{itemize}
\end{frame}

\begin{frame}
\begin{example}[2-Opt-Heuristik bei TSP] \pause
\begin{itemize}
\item Betrachte TSP mit symmetrischen Entfernungen $m_{i,j}=m_{j,i}$ \pause
\item Lösungen mit unendlichen Kosten seien erlaubt! \pause
\item Beginne mit beliebiger Permutation $\pi$ der Knoten  \pause(zulässig!) \pause
\item Wähle zufällig zwei  Knoten $\pi(i)$, $\pi(j)$ \pause (mit $i<j$).  \pause Falls
\GLA m_{\pi(i),\pi(i+1)}+m_{\pi(j),\pi(j+1)}  \pause> \pause m_{\pi(i),\pi(j)}+m_{\pi(i+1),\pi(j+1)}\GLE
 \pause gilt, dann gibt es eine kürzere Route / bessere Permutation: \pause
{\small\GLA
& \fbox{\includegraphics[width=0.35\linewidth]{grafik/tsp-2opt-1.pdf}}
 \Rightarrow\fbox{\includegraphics[width=0.35\linewidth]{grafik/tsp-2opt-2.pdf}}\\
&\leadsto \pause\pi(1)\pi(2)...\pi(i) \pause \pi(j)\pi(j{-}1)...\pi(i{+}2)\pi(i{+}1) \pause\pi(j{+}1)...\pi(n)\GLE}
\item \pause Animation: \href{http://www-e.uni-magdeburg.de/mertens/TSP/TSP.html}{www-e.uni-magdeburg.de/mertens/TSP/TSP.html} \pause
\item Laufzeit und Güte der Heuristik sind unbekannt!
\end{itemize}
\end{example}
\end{frame}

\begin{frame}
Weitere Heuristiken: \pause
\begin{itemize}
\item  Grundidee des \Fb{Simulated Annealing} (simulierte Abkühlung):  \pause
\begin{itemize}
\item erlaube bei der lokalen Suche auch  Zwischenlösungen,  \pause die um $c(t)$ 
schlechter sind als die aktuelle Lösung  \pause
\item aber: $c(t)$ geht mit wachsender Rechenzeit gegen $0$, etwa $$c(t)={\cal O}(1/\log t)$$
 \end{itemize}  \pause
\item Grundidee der \Fb{genetischen Algorithmen}: \pause
\begin{itemize}
\item Speichere mehrere verschiedenartige Lösungen \pause
\item Kombiniere jeweils meherere Lösungen und verwende die besseren Resultate 
\end{itemize} 
\end{itemize} 

\end{frame}
% \subsubsection{Datenreduktionstechniken}
% \begin{frame}
% metaheuristische Ideen
% \end{frame}

\subsection{Randomisierte Verfahren}

\subsubsection{Probabilistische Turingmaschinen}
\inhaltb{15}


\begin{frame}
Bisher:\\ Nichtdeterminismus als \Fb{ M\"o{}glichkeit}, eine Eingabe
zu akzeptieren.\pause 

Naheliegend auch:\\
\begin{itemize}
\item  \Fb{ Wahrscheinlichkeit} der Akzeptanz  einer Eingabe \pause 
bzw.
\item \Fb{ Wahrscheinlichkeit} der Erzeugung einer Ausgabe
\end{itemize}

\pause  Annahme hier:\pause 
\begin{itemize}
\item  jeder Befehl zufällig ausgewählt, mit \Fb{ gleicher
Wahrscheinlichkeit}\pause 
\item  die Einzel-Auswahlen seien
\Fb{unabhängig} voneinander.
\end{itemize}
\end{frame}

\begin{frame}

\begin{definition}
\begin{itemize}
\item
Eine \Fb{ probabilistische Turingmaschine} $M$ \pause  ist zunächst genauso definiert wie eine nichtdeterministische 
Turingmaschine.\pause 
\item
 Die Wahrscheinlichkeit 
$$\Fb{ Prob(K{\stackrelall{}{\longrightarrow}{M}}K')}$$
\pause  mit der bei~$M$ eine Konfiguration
$K$ in eine Konfiguration $K'$ \"u{}bergeht, \pause  wird definiert als:
\GLA
&&\Fb{ Prob(K{\stackrelall{}{\longrightarrow}{M}}K')}:=\\&&\pause 
\left\{\begin{array}{cl} 
j/i, &\pause  \mbox{falls }K\stackrelall{}{\longrightarrow}{M}K' \mbox{ mit }\\
    &\pause i:=\mbox{ Anzahl der bei $K$ ausf\"u{}hrbaren Befehle} \\
    &\pause j:=\mbox{ Anzahl dieser Befehle, bei denen aus $K$ $K'$ wird} \\
\pause   0, & \pause \mbox{sonst} \end{array}\right.
\GLE
\end{itemize}
\end{definition}
\end{frame}\begin{frame}
\begin{cont}{}
\begin{itemize}
\item
Die Wahrscheinlichkeit $$\Fb{Prob(K{\stackrelall{t}{\longrightarrow}{M}}K')}$$
\pause  mit der bei $M$ nach $t$ Schritten aus der Konfiguration
$K$ die Konfiguration $K'$ wird, \pause ergibt sich induktiv als:\pause 
\[\Fb{ Prob(K{\stackrelall{0}{\longrightarrow}{M}}K')}:=
\pause \left\{\begin{array}{ll} 1,& K=K'\\ 0,& K\neq K' \end{array}\right.\]\pause 
\[\Fb{ Prob(K{\stackrelall{t+1}{\longrightarrow}{M}}K')}:=\pause 
\sum_{\!\!\!\!\!\!K''\;{\rm Konfiguration}\!\!\!\!\!\!}\pause Prob(K{\stackrelall{t}{\longrightarrow}{M}}K'')
  \cdot Prob(K''{\stackrelall{}{\longrightarrow}{M}}K') \]
\end{itemize}
\end{cont}
\end{frame}
\begin{frame}
\begin{cont}{}
\begin{itemize}
\item
Per Definition: Nach
Erreichen einer Endkonfiguration  bleibt $M$ stehen und rechnet nicht mehr weiter.\pause 
\item
Also ist f\"u{}r 
Endkonfigurationen $K'$ sinnvoll definiert:\pause 
$$\Fb{ Prob(K{\stackrelall{*}{\longrightarrow}{M}}K')}$$
\pause  mit der bei $M$ nach beliebiger Zahl von
Schritten aus $K$ diese Endkonfiguration $K'$ wird:\pause 
\[\Fb{ Prob(K{\stackrelall{*}{\longrightarrow}{M}}K')}:= 
 \sum_{t= 0}^\infty Prob(K{\stackrelall{t}{\longrightarrow}{M}}K')\]
\end{itemize}
\end{cont}
\end{frame}\begin{frame}
\begin{cont}{}
\begin{itemize}
\item
Setze $Acc_M(y):=$ Menge aller Endkonf., die zur Ausgabe $y$ führen\pause 
\item
$I_M(x):=$ Startkonfiguration von $M$ bei Eingabe von $x$\pause 
\item
 Wahrscheinlichkeit, mit der aus  Eingabe $x$ die Ausgabe $y$ wird:\pause 
\[ \Fb{ Prob(x{\stackrelall{}{\mapsto}{M}}y)}\pause := \sum_{ K'\in Acc_M(y)}
   Prob(I_M(x){\stackrelall{*}{\longrightarrow}{M}}K')\]
\item
\pause Wahrscheinlichkeit, mit der 
bei $x$ kein Ergebnis geliefert wird:\pause 
\[\Fb{ div_M(x)}:=\pause  1-\pause \sum_y Prob(x{\stackrelall{}{\mapsto}{M}}y)\]
\end{itemize}
\end{cont}
\end{frame}

\begin{frame}

Da $M$  mit Erreichen einer Endkonfiguration endet:\pause 
$$\sum\{Prob(I_M(x){\stackrelall{*}{\longrightarrow}{M}}K')\mid 
  K'\mbox{ Endkonfiguration}\}\leq 1$$

\pause Damit f\"u{}r jedes $x$ 
$$\sum_{y}Prob(x{\stackrelall{}{\mapsto}{M}}y)\leq 1$$ 

\pause Beide Werte k\"o{}nnen echt kleiner als 1 sein, da m\"o{}glicherweise 
nicht bei jeder Berechnung eine Endkonfiguration erreicht wird!
\end{frame}
\begin{frame}


\begin{definition}\begin{itemize}
\item
Die von einer probabilistischen Turingmaschine $M$ berechnete Funktion
$f^{(p)}_M$ wird wie folgt definiert:\pause 
\[\Fb{ f^{(p)}_M(x)}\pause := \left\{\begin{array}{cl} y,&\pause    \mbox{ falls }
Prob(x{\stackrelall{}{\mapsto}{M}}y)>1/2\\[1ex]
\pause \mbox{undefiniert},& \pause 
\mbox{ falls $Prob(x{\stackrelall{}{\mapsto}{M}}y)\leq1/2$ f\"u{}r alle $y$}
 \end{array}\right.\]   
\item  \pause Die von $M$ akzeptierte Sprache $L^{(p)}_M$ wird definiert durch\pause 
\GLA\Fb{ L^{(p)}_M}:=\{x\mid f^{(p)}_M(x)=0\}\GLE
\item\pause 
Die Fehlerwahrscheinlichkeit, mit der $f^{(p)}_M$ berechnet wird, ist \pause 
\[\Fb{err_M(x)}:= \pause \left\{\begin{array}{ll} 
1-div_M(x)&\\
~~~-Prob(x{\stackrelall{}{\mapsto}{M}}f^{(p)}_M(x)),& \pause 
\mbox{ falls $f^{(p)}_M(x)$ definiert ist}\\[1ex]
\pause \mbox{undefiniert},& \pause \mbox{ sonst}\end{array}\right.\]
\end{itemize}\end{definition}
\end{frame}

\begin{frame}\begin{example}[Probabilistische Turingmaschine]\label{probTM}
Nichtdeterministische (=probabilistische) Maschine $M$:
{\small \GLA
\begin{array}[b]{@{}c@{}}\includegraphics[width=.35\textwidth]{grafik/probabTM2.pdf}\\[-4ex]
\end{array}
\pause\begin{array}[b]{c@{\,}l@{}}&\mbox{Beispiele für Konfigurationsfolgen bei $M$:}\\
\pause\mbox{(a)}&\pause s_0\Fb{0}\pause\to 0s_1\Box\pause\to s_3\Fb{0}\Box\\[.3ex]
\pause\mbox{(b)}&\pause s_0\Fb{0}\pause\to 1s_1\Box\pause\to s_3\Fb{1}\Box\\[.3ex]
\pause\mbox{(c)}&\pause s_0\Fb{0}\pause\to s_20\pause\to 0s_1\Box\pause\to s_3\Fb{0}\Box\\[.3ex]
\pause\mbox{(d)}&\pause s_0\Fb{1}\pause\to s_21\pause\to 1s_0\Box\pause\to 10s_1\Box\pause\to 1s_3\Fb{0}\Box\\[.3ex]
\pause\mbox{(e)}&\pause s_0\Fb{1}\pause\to s_21\pause\to 1s_0\Box\pause\to 11s_1\Box\pause\to 1s_3\Fb{1}\Box\\[.3ex]
\pause\mbox{(f)}&\pause s_0\Fb{1}\pause\to s_21\pause\to 1s_0\Box\pause\to 1s_2\Box\\
&\pause\mbox{~~~~~~} \to 1\Box s_0\Box\pause\to 1\Box s_2\Box\pause\to 1\Box\Box s_0\Box\pause...
\end{array}
\GLE}
\begin{itemize}
\item \pause Hier gilt $Prob(x{\stackrelall{}{\mapsto}{M}}y) = 0$, wenn $y\not\in \{0,1\}$\pause
\item $ Prob(1{\stackrelall{}{\mapsto}{M}}0) \pause= Prob(1{\stackrelall{}{\mapsto}{M}}1) \pause= \frac{1}{3}\pause+\frac{1}{3^2}\pause+\frac{1}{3^3}\pause+...\pause={\displaystyle \sum_{i=1}^\infty}(\frac{1}{3})^i\pause=\frac{1}{2}$\\
\pause also  $div_M(1)=0$, \pause zudem ist $f_M^{(p)}(1)$  nicht definiert.\pause
\\(Achtung: $M$ könnte trotzdem unendlich oft zykeln!)
\end{itemize}
\end{example}
\end{frame}


\begin{frame}
\begin{cont}{Probabilistische Turingmaschine}
\begin{itemize}
\item analog für $v=\underbrace{1...1}_{i}$ (bei $i\geq 0$):\pause
$$Prob(v{\stackrelall{}{\mapsto}{M}}0) \pause= Prob(v{\stackrelall{}{\mapsto}{M}}1) \pause=\textstyle\frac{1}{2}$$
\pause also  $div_M(v)=0$ \pause und  $f_M^{(p)}(v)$ ist  nicht definiert.\pause
\item für $\displaystyle w:=\underbrace{1...1}_{i}0$  ergibt sich jedoch:\pause
\GLA Prob(w{\stackrelall{}{\mapsto}{M}}0)=&\pause\displaystyle \sum_{j=1}^{i+1} \frac{1}{3^j}+\pause
\frac{1}{3^{i+1}}&\pause= \frac{1}{2}\cdot(1+\frac{1}{3^{i+1}})\\
\pause Prob((w{\stackrelall{}{\mapsto}{M}}1)=&\pause\displaystyle \sum_{j=1}^{i+1} \frac{1}{3^j}&\pause = \frac{1}{2}\cdot(1-\frac{1}{3^{i+1}})\GLE
\pause damit: $f^{(p)}_M(w)=0$, \pause$div_M(w)=0$ \pause und $err_M(w)= \frac{1}{2}\cdot(1-\frac{1}{3^{i+1}})$

\end{itemize}
\end{cont}
\end{frame}

\begin{frame}
\begin{cont}{Probabilistische Turingmaschine}
Betrachte z.B. Spezialfall $w=10$\pause
\begin{itemize}
\item Zunächst:
\GLA Prob((w{\stackrelall{}{\mapsto}{M}}1)&=&\frac{1}{2}\cdot(1-\frac{1}{3^{2}})\pause \approx 0.444...=:\varepsilon\\
\pause Prob(w{\stackrelall{}{\mapsto}{M}}0)&\pause =&\pause  \frac{1}{2}\cdot(1+\frac{1}{3^{2}})\pause \approx 0.555...=1-\varepsilon\GLE\pause 
\item Jetzt: Lasse $M$ $n$-fach laufen, zähle Anzahl positiver/negativer Resultate\\
\pause Dann gibt es $n{+}1$ Möglichkeiten:

\begin{tabular}{|cc||c|}\hline
Ausgabe $1$ & Ausgabe $0$ &Wahrscheinlichkeit\\\hline
\pause $n$-fach &\pause  $0$-fach&\pause  $\varepsilon^n$\\\hline
\pause $n{-}1$-fach & \pause $1$-fach &\pause  $n\cdot \varepsilon^{n-1}\cdot (1{-}\varepsilon)$\\\hline
\pause ... &&\pause ...\\\hline
\pause $1$-fach  & \pause $n{-}1$-fach& \pause $n\cdot \varepsilon^1\cdot (1{-}\varepsilon)^{n-1}$\\\hline
\pause $0$-fach  & \pause $n$-fach&\pause  $(1-\varepsilon)^n$\\\hline
\end{tabular}
\end{itemize}
\end{cont}
\end{frame}

\begin{frame}
\begin{cont}{Probabilistische Turingmaschine}
\begin{itemize}
\item Die Wahrscheinlichkeit $p(n)$, dass mehr als die Hälfte der Ausgaben $1$ sind, fällt exponentiell mit $n$:\pause 
\GLA p(n)&=&\pause \sum_{i=0}^{\lfloor n/2\rfloor}\textstyle\binom{n}{i}(1{-}\varepsilon)^i\varepsilon^{n-i}\\
&\pause \leq&\pause \sum_{i=0}^{\lfloor n/2\rfloor}{\textstyle\binom{n}{i}
(1{-}\varepsilon)^i\varepsilon^{n-i}\pause \left(\frac{1{-}\varepsilon}{\varepsilon}\right)^{n/2-i}}\pause \mbox{ da $\varepsilon<1/2$, $i\leq n/2$} \\
&\pause =&\pause (\varepsilon(1{-}\varepsilon))^{n/2}\cdot \sum_{i=0}^{\lfloor n/2\rfloor}\textstyle\binom{n}{i}
\pause \leq(\varepsilon(1{-}\varepsilon))^{n/2}\cdot2^{n}\pause  = \delta^n
\GLE
\pause mit der Setzung von $\delta=2\sqrt{\varepsilon(1{-}\varepsilon)}$ \pause (wobei insbesondere $\delta < 1$).\pause 
\item 
Um Fehler $p(n)\leq 10^{-k}$ zu erhalten, \pause  reicht also $n\geq k\cdot\frac{1}{-\log_{10}\delta}$\pause 
\item Im Beispiel: $\varepsilon= 0.444...$, \pause $\delta=0.9938...$, \pause $\frac{1}{-\log_{10}\delta}\approx 370$,\\\pause 
d.h. nach $n=3700$ Wiederholungen ist $p(n)\leq 10^{-10}$
\end{itemize}
\end{cont}
\end{frame}

\begin{frame}

\begin{definition}\pause 
Sei $M$ probabilistische Turingmaschine, bei der $f^{(p)}_M(x)$ stets existiert.\pause 
\begin{enumerate}
\item $M$ hei\ss{}t \Fb{ Random-Turingmaschine}, wenn
f\"u{}r $x\not\in L^{(p)}_M$ gilt:\pause 
$$Prob(x{\stackrelall{}{\mapsto}{M}}0) = 0$$ 
\pause ($M$ erkennt $L^{(p)}_M$ mit einseitiger 
Fehlerwahrscheinlichkeit 0.)\pause 
\item $M$ hei\ss{}t \Fb{ Monte-Carlo-Turingmaschine}, \pause wenn
ein $\varepsilon<1/2$ existiert, \pause so da\ss{} f\"u{}r alle $x$ stets gilt:\pause 
$$err_M(x){+}div_M(x)<\varepsilon$$ \pause ($M$ berechnet $f^{(p)}_M$ mit beschr\"a{}nkter
Fehlerwahrscheinlichkeit.)\pause 
\item $M$ hei\ss{}t \Fb{ Las-Vegas-Turingmaschine}, \pause  wenn
f\"u{}r alle $x$ stets gilt:\pause 
$$err_M(x)=0$$  \pause ($M$ berechnet $f^{(p)}_M$ mit 
Fehlerwahrscheinlichkeit 0.)
\end{enumerate}
\end{definition}
\end{frame}\begin{frame}
Interpretation der Definitionen: \pause 
\begin{enumerate}
\item 
Ergibt bei einer \Fb{ Random-Turingmaschine} $M$ eine Berechnung die Ausgabe 0, \pause 
so gilt \Fb{ sicher} $x\in L^{(p)}_M$.\pause 
\item Bei einer \Fb{ Monte-Carlo-Turingmaschine} $M$
wird das \Fb{ richtige Ergebnis
$f^{(p)}_M(x)$ mit signifikant h\"o{}herer 
Wahrscheinlichkeit ($>1/2$)} ausgegeben als irgendein falsches
($<\varepsilon<1/2$).\pause 

 Dabei ist $\varepsilon$ unabh\"a{}ngig(!) von $x$.\pause 
\item Eine \Fb{ Las-Vegas-Turingmaschine $M$ `l\"u{}gt' nie}, \pause 
liefert aber mit Wahrscheinlichkeit $div_M(x)<1/2$ 
\"u{}berhaupt kein Ergebnis.\pause 

Jede Las-Vegas-Maschine ist per Definition auch eine Random-Maschine.
\end{enumerate}
\pause 
 Zeitkomplexit\"a{}t über zwei Vorgehensweisen definierbar:\pause 
\begin{itemize}\item
über den Erwartungswert der Rechenzeit\pause 
\item über die Zeit, die benötigt wird, um die Ausgabe mit einer gewissen Wahrscheinlichkeit
festzulegen.
\end{itemize}
\end{frame}\begin{frame}

\begin{definition}
Sei $M$ eine probabilistische Turingmaschine. \pause 

Die
durchschnittliche (oder erwartete) Rechenzeit $\Fb{ T_M^\emptyset(x)}$ \pause von $M$ bei
einer Eingabe $x$  ist definiert als\pause 
\[\Fb{ T_M^\emptyset(x)} :=\pause 
\left\{\begin{array}{cl} \displaystyle
\sum_{t=0}^\infty t\cdot \sum_{K\,{\rm Endkonf.}}
Prob(I_M(x)\stackrelall{t}{\longrightarrow}{M}K), &\pause 
 \mbox{ falls $div_M(x)=0$}\\  \\
\pause  \infty, \mbox{ sonst} \end{array}\right.
\]
\pause F\"u{}r $\varepsilon\leq 1/2$ sei $\Fb{ T_M^\varepsilon(x)}$ \pause die Zeit, nach der
$f_M^{(p)}(x)$ mit Wahrscheinlichkeit $1{-}\varepsilon$ festliegt:\pause 
\[\Fb{ T_M^\varepsilon(x)}:= \min\{t\in\nz\mid 1{-}\varepsilon <
\sum_{\!\!\!K\in Acc_M(f_M^{(p)}(x)),\;\;t'\leq t\!\!\!}
Prob(I_M(x)\stackrelall{t'}{\longrightarrow}{M}K)\;\}\]
\end{definition}
 \end{frame}

\begin{frame}
\begin{example}[probabilistische Zeitkomplexität]
Sei $M$ wie im Beispiel \ref{probTM}\pause 
\begin{itemize}
\item Betrachte zunächst  $v=1...1$:\pause 
\GLA T_M^\emptyset(v)&=&\pause \frac{2}{3}\cdot 2 + \frac{2}{3^2}\cdot 4 +  \frac{2}{3^3}\cdot 6 + ...\\
&\pause =&\pause 4\cdot \sum_{t=1}^\infty \frac{t}{3^t}\pause \stackrel{*}{=} 4\cdot (\frac{1/3}{(1-1/3)^2})\pause = 3
\GLE
\pause Zu $(*)$: Für $p<1$ gilt $\displaystyle \sum_{i=0}^\infty \frac{i}{p^i}=\frac{p}{(1-p)^2}$\pause \\
(Beweis über $\displaystyle \sum_{i=0}^\infty \frac{1}{p^i}=\frac{1}{1-p}$ \pause und
$\displaystyle\frac{\mbox{d}}{\mbox{d}p}\frac{1}{1-p}=\frac{1}{(1-p)^2}$~~)\pause 
\item 
Für beliebige $w$ immer $T_M^\emptyset(w)\leq T_M^\emptyset(1...1)$, \pause wenn $|w|=|1...1|$.\pause 
\item
Also: Bei $M$ ist für alle $w$ die erwartete Rechenzeit $T_M^\emptyset(w)\leq 3$.
\end{itemize}
\end{example}
\end{frame}

\begin{frame}
\begin{cont}{probabilistische Zeitkomplexität}
Andererseits:\pause 
\begin{itemize}
\item $T_M^{1/2}(1...1)=\mbox{undef}$, \pause  da $f_M^{(p)}$ undefiniert ist\pause 
\item
$T_M^{1/2}(\underbrace{1...1}_i0)=2i+2$\pause 
\item
$T_M^{1/3}(\underbrace{1...1}_i0)=\mbox{undef}$, \pause da $Prob_M(1...10\mapsto 0)\leq 2/3$
\end{itemize}
\end{cont}
\pause daher:\pause 
\begin{itemize}
\item erwartete Zeit ist im Allgemeinen ungeeignetes Maß...\pause 
\item  f\"u{}r viele
Probleme gibt es probabilistische Maschinen mit
konstanter erwarteter Rechenzeit\pause 
\item 
 Ausnahme: Las-Vegas-Maschinen, hier wird die erwartete Zeit verwendet
\end{itemize}
\end{frame}

\begin{frame}
\begin{example}[Quicksort als Las-Vegas-Algorithmus]\pause 
 Gegeben Feld $a[1],...,a[n]$, \pause 
Ziel: rekursive Sortierfunktion $qs$:\pause 
\begin{itemize}
\item
$qs(i,j)$ sortiert Teilfeld $a[i]...a[j]$, \pause d.h.
Aufruf mit $qs(1,n)$\pause 
\item $qs(i,j)$ arbeitet wie folgt:\pause 
\begin{enumerate}
\item[(1)] Wähle $k$ mit $i\leq k\leq j$\pause 
\item[(2)] Modifiziere $a[i]...a[j]$ so, \pause dass $a[k]$ an eine Stelle
$m$ kommt mit \pause 
\GLA (\forall \nu, i\leq \nu\leq m) & a[\nu]\leq a[m]\\
\pause  (\forall \nu, m\leq \nu\leq j) & \pause a[m]\leq a[\nu]\GLE
\item[(3)]\pause  Falls $i< m{-1}$: Rekursiver Aufruf von $qs(i,m{-}1)$\pause 
\item[(4)] Falls $ m{+1}<j $: Rekursiver Aufruf von $qs(m{+}1,j)$
\end{enumerate}
\item \pause Übliche, deterministische Setzungen bei (1):\pause 
\begin{enumerate}
\item[(1a)] Wähle $k=i$\pause 
\item[(1b)]  Wähle $k=\lfloor \frac{i+j}{2}\rfloor$
\end{enumerate}\pause 
\item Resultat: Mittlere Laufzeit ist  ${\cal O}(n\log n)$ \pause  (gemittelt über alle möglichen Felder \pause und im Einheitskostenmaß) \pause
\item Es gibt Felder mit Worst-Case-Verhalten von ${\cal O}(n^2)$.
\end{itemize}
\end{example}
\end{frame}

\begin{frame} 
\begin{cont}{Quicksort als Las-Vegas-Algorithmus} \pause
\begin{itemize}
\item Problem: Kommen bei der Anwendung nicht alle Felder mit gleicher Wahrscheinlichkeit vor, \pause
greift die Mittelwertanalyse nicht! \pause
\item Ausweg: Probabilistischer Algorithmus mit  \pause
\begin{enumerate}
\item[(1c)] Wähle $k$ zufällig aus $\{i,...,j\}$
\end{enumerate} \pause
\item Dann gilt offensichtlich:  \pause
\begin{enumerate}
\item Der Algorithmus hält immer. \pause
\item Er liefert stets das gleiche Resultat (das sortierte Feld)
\end{enumerate} \pause
d.h.: es liegt ein Las-Vegas-Algorithmus vor. \pause
\item Durchschnittliche Laufzeit mit (1c) sofort: \pause
\GLA T_{qs}^\emptyset(n)=\underbrace{c\cdot n}_{(1c),(2)} \pause+ \frac{1}{n}
\sum_{m=1}^{n} \pause\left(~T_{qs}^\emptyset(m{-}1)+T_{qs}^\emptyset(n{-}m{-}1)\right)\GLE
 \pause wieder mit Lösung $T_{qs}^\emptyset(n) ={\cal O}(n\log n)$  \pause
\item Mittelwert ergibt sich sofort mit (1c), `Mittelwertanalyse' unnötig!
\end{itemize}
\end{cont}
\end{frame}

\begin{frame} 
\begin{cont}{Quicksort als Las-Vegas-Algorithmus}
\begin{itemize}
\item  \pause Sortierzeit bei gegebenem Feld nicht mehr konstant,  \pause sondern zufällig... \pause
\item Mittlere Laufzeit gilt jetzt bei jedem Feld! \pause
\item Achtung: Worst-Case könnte jetzt auch bei jedem Feld eintreten... \pause
\item Weitere Verbesserungen z.B.: \pause
\begin{enumerate}
\item[(1d)] Wähle drei Werte $k_1,k_2,k_3$ zufällig aus $\{i,...,j\}$, \pause\\
setze $k$:=Index des mittleren Wertes aus $\{a[k_1],a[k_2],a[k_3]\}$
\end{enumerate} \pause
Dann tritt der Worst-Case seltener ein, ist aber immer noch nicht ausgeschlossen!
\end{itemize}
\end{cont}

 \pause Analoge Vorgehensweise
ist bei vielen Algorithmen m\"oglich, die Mengen elementweise verarbeiten: \pause
\begin{itemize}
\item  Statt determinierter Auswahl eines Element wähle zufällig aus...
\end{itemize}

\end{frame}


\begin{frame} 

Vorteile der \Fb{ Randomisierung}: \pause
\begin{itemize}
\item (Komplexit\"ats-)Analyse des randomisierten Algorithmus
ist oft signifikant leichter \pause
\item keine umfangreichen
Wahrscheinlichkeitsuntersuchungen und -annahmen \"u{}ber die Menge aller
Eingaben \pause
\item
 zuf\"allige Auswahl erm\"oglicht Mittelwertuntersuchungen \pause
\item
 unbekannte Verteilung der Eingabe bei det.\ Algorithmen
erlaubt i.A. nur  Worst-Case-Analyse \pause
\item
Nach `Randomisierung' eines Algorithmus
evtl.\ erstmals Average-Case-Analyse möglich \pause
\item
 Bei randomisierten Algorithmen sind alle Eingaben gleich gut (bzw.\
gleich schlecht). \pause
\item
Der Anwender  muss sich
nicht mehr darum k\"u{}mmern, dass seine Eingaben den Mittelwertbedingungen
gen\"u{}gen.
\end{itemize}
\end{frame}



\subsubsection{Probabilistische Komplexitätsklassen}
\inhaltb{15}


\begin{frame}
\begin{definition}
Zu  $t\colon\nz\rightarrow\nz$ seien folgende
Komplexit\"a{}tsklassen definiert: \pause
\GLA
\Fb{ \tt PrTIME}(t) & =  \{L_M^{(p)}\mid&\pause M \mbox{ prob. TM }\wedge f^{(p)}_M(x)\mbox{ exist.
f\"u{}r alle $x$}\\&&\pause\wedge(\exists c)(\forall x)T^{1/2}_M(x)\leq c\cdot t(lg(x))+c \}\\
\pause\Fb{ \tt MCTIME}(t) &\pause =  \{L^{(p)}_M\mid&\pause M \mbox{ prob. TM }\wedge f^{(p)}_M(x)\mbox{ exist.
f\"u{}r alle $x$}\\&&\pause \hspace{-4ex}\wedge
(\exists \varepsilon<1/2)(\exists c)(\forall x)T^{\varepsilon}_M(x)\leq c\cdot t(lg(x))+c \}\\
\pause\Fb{ \tt RTIME}(t) &\pause =  \{L^{(p)}_M\mid&\pause M \mbox{ prob. TM }\wedge f^{(p)}_M(x)\mbox{ exist.
f\"u{}r alle $x$}\\&&\pause\wedge
(\forall x\not\in L^{(p)}_M)err_M(x)=0\\&&\pause 
\wedge(\exists c)(\forall x)T^{1/2}_M(x)\leq c\cdot t(lg(x))+c \}\\
\pause\Fb{ \tt LVTIME}(t) &\pause =  \{L^{(p)}_M\mid&\pause M \mbox{ prob. TM }\wedge f^{(p)}_M(x)\mbox{ exist.
f\"u{}r alle $x$}\\&&\pause\wedge
(\forall x)err_M(x)=0\\&&\pause
\wedge(\exists c)(\forall x)T^{\emptyset}_M(x)\leq c\cdot t(lg(x))+c \}
\GLE
\end{definition}
\end{frame}\begin{frame}
\begin{cont}{}
Ferner werden die folgenden Klassen definiert:
\[\begin{array}{lll}
{\tt PP}&\pause=\displaystyle\bigcup_{k\in\nz}{\tt PrTIME}(n^k)&\pause
\mbox{ Probabilistic Polynomial time}\\
{\tt BPP}&\pause=\displaystyle\bigcup_{k\in\nz}{\tt MCTIME}(n^k)&\pause
\mbox{ Bounded error Probabilistic}\\[-2ex]
&&\pause\mbox{ Polynomial time}\\
{\tt RP}&\pause=\displaystyle\bigcup_{k\in\nz}{\tt RTIME}(n^k)&
\pause\mbox{ Random Polynomial time}\\
{\tt ZPP}&\pause=\displaystyle\bigcup_{k\in\nz}{\tt LVTIME}(n^k)&\pause
\mbox{ Zero-error Probabilistic Polynomial time}\\
\end{array}\]
\end{cont}
\end{frame}\begin{frame}
\begin{theorem}
F\"u{}r Polynome $t\colon\nz\rightarrow\nz$ gilt:
\GLA{\tt DTIME}(t)&\stackrel{*}{\subseteq}&{\tt LVTIME}(t)\\
&\subseteq&{\tt RTIME}(t)
\left\{\begin{array}{c}\subseteq{\tt NTIME}(t)\stackrel{*}{\subseteq}\\
\stackrel{*}{\subseteq}{\tt MCTIME}(t)\subseteq \end{array}\right\}
{\tt PrTIME}(t)\\&\stackrel{*}{\subseteq}&{\tt DSPACE}(t)
\GLE
\pause(Nur bei $\stackrel{*}{\subseteq}$ wird benutzt, dass $t$ Polynom ist\\
 (genauer: es wird die `Zeitkonstruierbarkeit' von $t$ verwendet),\\
 die anderen Inklusionen gelten sogar f\"u{}r {\em alle} $t$.)\\
\pause Damit gilt:
\[{P}\subseteq{\tt ZPP}\subseteq{\tt RP}
\left\{\begin{array}{c}\subseteq{\tt NP}\subseteq\\
\subseteq{\tt BPP}\subseteq\end{array}\right\}
{\tt PP}\subseteq{PSPACE}\]
\end{theorem}

\end{frame}\begin{frame}
\Einschub{Inklusionsbeziehungen der prob. Komplexit\"a{}tsklasse}
\pause\begin{itemize}
\item Inklusionsbeziehungen zwischen ${\tt BPP}$ und ${\tt NP}$
sind unbekannt!\pause
\item ${\tt PP}$, ${\tt BPP}$, ${\tt RP}$ und ${\tt ZPP}$
sind unter  $\leq_{p}$ nach unten
abgeschlossen\\
(Beweis analog wie bei $NP$)\pause
\item Vollst\"a{}ndige Probleme nur f\"u{}r ${\tt PP}$ bekannt:
$${\tt MAJ}:=\{ \mbox{Formel }\phi\mid \mbox{\begin{tabular}[t]{l}$\phi$ ist unter mehr als der
H\"a{}lfte
aller \\Belegungen der Variablen aus $w$ wahr$\}$\end{tabular} }$$ 
\pause
${\tt MAJ}$ ist ${\tt PP}$-vollst\"a{}ndig (bzgl.\ $\leq_{p}$).
\end{itemize}
\end{frame}\begin{frame}
Unterschied zwischen ${\tt PrTIME}(t)$
und ${\tt MCTIME}(t)$ ist scheinbar gering:
\pause
$$~~~~~~~~~~(\exists c)(\forall x)T^\Fb{ 1/2}_M(x)\leq ct(lg(x))+c$$\pause und\\
$$(\exists \varepsilon{<}\frac{1}{2})~~(\exists c)(\forall x)
T^\Fb{ \varepsilon}_M(x)\leq ct(lg(x))+c$$
\pause
Jedoch: 
\begin{itemize}
\item Bei Monte-Carlo-Maschinen ist Wahrscheinlichkeit einer
nicht korrekten Ausgabe beliebig reduzierbar!
\pause
\item Sie ist leicht unter die Wahrscheinlichkeit f\"u{}r unentdeckte Hardwarefehler
zu drücken!
\end{itemize}
\end{frame}\begin{frame}\begin{theorem}
Sei $t\colon\nz\rightarrow\nz$  Polynom (bzw. zeitkonstruierbar). 
F\"u{}r jedes feste $\varepsilon$, $0<\varepsilon<\frac{1}{2}$, gilt:\pause
\GLA {\tt MCTIME}(t) 
&\pause =  \{L_M^{(p)}\mid&\pause M \mbox{ prob. TM }\wedge f^{(p)}_M(x)\mbox{ exist. 
f\"u{}r alle $x$}\\&&\pause\wedge
(\exists c)(\forall x)T^{\varepsilon}_M(x)\leq ct(lg(x))+c \}\\
&\pause  =  \{L_M^{(p)}\mid&\pause M \mbox{ prob. TM }\wedge f^{(p)}_M(x)\mbox{ exist. 
f\"u{}r alle $x$}\\&&\pause\wedge
(\forall x)err_M(x)<\varepsilon\\&&
\pause\wedge(\exists c)(\forall x)T^{\emptyset}_M(x)\leq ct(lg(x))+c \}
\GLE
\end{theorem}
\begin{itemize}
\item \pause  Für Praxis ohne Unterschied, ob Algorithmus
deterministisch / Fehlerwahrscheinlichkeit unter
$2^{-100}$ !\pause
\item `deterministische'
Ergebnisse könnten Hardware-Fehler haben...\pause
\item Kernkraftwerke gelten bei wesentlich h\"o{}heren 
Katastrophenwahrscheinlichkeiten noch als sicher!\pause
\item \Fb{\bfseries Probleme aus ${\tt BPP}$ sind also (bei moderaten Exponenten in der 
jeweiligen polynomialen Zeitschranke) mit gleichen Recht als
`praktisch berechenbar' anzusehen wie Probleme aus $P$.}
\end{itemize}

\end{frame}\begin{frame}
\Einschub{Fehlerreduktion f\"u{}r Monte-Carlo-Maschinen}


\end{frame}\begin{frame}
\begin{itemize}
\item  praktisch verwendete Monte-Carlo-Algorithmen:\\
Primzahltests von Rabin (1976) und Solovay/Strassen
(1977)\pause

$\Rightarrow$  Menge aller Primzahlen liegt in $co-{\tt RP}$\pause
\item  Adleman/Huang (1992): Menge aller Primzahlen liegt in ${\tt RP}$\pause

$\Rightarrow$   damit: Primzahlen in ${\tt ZPP}$\pause
\item  Agarwal/Kayal/Saxena (2002): Primzahlen in $P$\pause
\item Algorithmus noch (deutlich) langsamer
 als probabilistische Algorithmen\pause
\item  keine Auswirkungen auf Kryptographie zu erwarten!
\end{itemize}
\pause  
Anwendung gro\ss{}er Primzahlen z.B. bei
den `public key cryptosystems' nach dem RSA-Verfahren 
(Rivest/Shamir/Adleman, 1977).

\end{frame}

% \begin{frame}
% 
% Praktische Anwednung  probabilistischer Algorithmen:\\
% 
% Zufallszahlengeneratoren... (vgl. Simulation)
% 
% ---jeder Pseudo-Zufallszahlengenerator deterministisch \\
% $\Rightarrow$ es gibt F\"alle geben, wo er versagt
% 
% --- daher sinnvoll,
% Monte-Carlo-Algorithmen mit verschiedenen
% Generatoren mehrfach durchzuführen!
% \end{frame}



% 
% \begin{frame}
% Wie bereits erwähnt, kann man NP-(vollständige) Probleme immer dadurch lösen, dass
% man alle potenziellen ,,Lösungskandidaten" oder ,,Zusatzeingaben" y (der Länge p(n),
% für ein Polynom p) systematisch daraufhin untersucht, ob sie tatsächlich eine Lösung
% darstellen. Angenommen, die Eingabe 2: besitzt tatsächlich m 3 1 Lösungen, so
% dass dieser systematische Suchalgorithmus schließlich erfolgreich sein wird und eine
% Lösung findet. Die worst—case Komplexität ist dabei O(2"(") — m), wobei n = lm]. Ein
%  probabilistischer Algorithmus, der wiederholt zufällige Stichproblen y der Länge p(n) 1
% zieht und diese überprüft, könnte im Mittel effizienter sein, sofern m groß ist. Die Wahr-
% scheinlichkeit, bei einem einzelnen Versuch erfolgreich zu sein, ist m / 2’("). Daher ist
% der Erwartungsweit für die Anzahl der Versuche, bis man eine Lösung findet, gerade
% der Kehrwert dieser Wahrscheinlichkeit, also 2"() / m (vgl. Seite 35). Wir müssen fer-
% ner abschätzen, wie oft man solche Zufallsversuche tätigen muss, bis man bei lauter
% erfolglosen Versuchen nahezu sicher sein kann, dass keine Lösung existiert. Wir wollen
% eine sehr geringe Fehlerwahrscheinlichkeit 6 zulassen. Das Experiment wird t mal un-
% abhängig wiederholt. Dann ist ti = tm/2*’(") die erwartete Anzahl von Erfolgen. Die
% Wahrscheinlichkeit, bei t unabhängigen Wiederholungen des Zufallsexperiments jedes
% Mal keine Lösung zu finden, ist
% (1 ..... (wesen 1 — y 6 wi
% Diese Wahrscheinlichkeit soll kleiner—gleich 6 werden. Also genügt es, die Wiederho-
% lungsanzahl t größer-gleich ln(1/6)2"(") / m zu wählen. (Beispiel: für 6 = e“2 ist
% ln(1/6) = 20, also sollte die Anzahl der Versuche 20-mal so groß sein wie die erwarte-
% te Anzahl der Versuche bis zum ersten Auftreten einer Lösung).
% Die heuristischen Algorithmen, die in Kapitel 1 1 besprochen werden — sofern sie proba-
% bilistische Methoden einsetzen — lassen sich zum großen Teil so erklären, dass sie unter
% Ausnützen von Charakteristika der zu lösenden Problemstellung versuchen, die ,,Tref—
% ferwahrscheinlichkeit" (welche bei der obigen Diskussion m / 2p() beträgt) zu erhöhen
% — und damit die (mittlere) Komplexität zu reduzieren. Ein weiteres Beispiel für diesen
% Typ von Algorithmus findet sich in Abschnitt 12.5.
% 1.15 Optimierungsprobleme und Approximation
% \end{frame}
% 
% \begin{frame}
% Bei den probabilistischen Algorithmen (siehe Abschnitt 1.12), insbesondere bei de-
% nen vom Monte Carlo-Typ, also mit einer möglichen fehlerhaften Ausgabe, hat man
% sicher ein gewisses Unbehagen verspürt, selbst wenn nachgewiesen werden konnte,
% dass die Wahrscheinlichkeit für ein solches ,,Fehlverhalten“ sehr klein gehalten wer-
% den kann. Nicht zuletzt dieses Unbehagen ist wohl auch ein Grund dafür, dass wir in
% Abschnitt 1.13 die Möglichkeit betrachtet haben, probabilistische Algorithmen wieder
% vollständig zu derandomisieren, also zu deterministischen Algorithmen zu machen.
% Auch bei deterministischen Algorithmen, selbst wenn diese zuvor vollständig analysiert
% und auf Korrektheit bewiesen wurden, bleibt ein gewisser Unsicherheitsfaktor in der
% Implementierung, im verwendeten Betriebssystem, in der Hardware. Nicht viel anders
% als bei probabilistischen Algorithmen können wir also am Ende nicht 100-prozentig
% sicher sein, dass die berechneten Ergebnisse korrekt sind.
% Was wir hier vorschlagen und populär machen wollen, ist dass Algorithmen mit ei-
% nem Ergebnisveriiikationsmechanismus versehen werden sollten — sofern dies irgend-
% wie geht und effizient machbar ist. Der Benutzer soll so die überprüfbare Garantie erhal-
% ten, dass das konkret berechnete Ergebnis korrekt (in Bezug auf die aktuelle Eingabe)
% ist. Dieser Anspruch ist nicht so groß (und damit evtl. leichter realisierbar) als wenn wir
% im Vergleich dazu automatisch überprüfen oder beweisen wollten, dass der Algorithmus
% für jede potenzielle Eingabe und alle Eventualitäten korrekt arbeitet. (Tatsächlich lässt
% sich zeigen, dass dieses allgemeine Verifikationsproblern unentscheidbar ist).
% Oftmals ist der Veriiikationsprozess (für die jeweils aktuelle Eingabe) wesentlich effi-
% zienter realisierbar als das eigentliche Finden eines Ergebnisses (für diese betreffende
% Eingabe). Und genau das ist die Idealvorstellung für eine erfolgreiche Ergebnisveri-
% fikation. Zum Beispiel ist das Faktorisieren einer natürlichen Zahl eine algorithmisch
% schwierige Aufgabe (vgl. Abschnitt 9.10). Sofern aber ein (potenzieller) Faktor m einer
% Zahl n gegeben ist, so kostet es nur eine Division, um festzustellen, ob m tatsächlich ein
% Teiler von n ist. (Auch wenn n eine Primzahl sein sollte, so liefert der in Abschnitt 9.9
% besprochene Algorithmus sozusagen als Seiteneffekt einen ,,Beweis" für die Primzah-
% leigenschaft).
% \end{frame}
% 
% \begin{frame}
% Ein anderes Beispiel ist das Sortieren. Sortieren kann man mit Komplexität O(n log n)
% (siehe Kapitel 2). Um festzustellen, ob die Ergebnisfolge die sortierte Version der Ein-
% gabefolge ist, muss man überprüfen, ob die ausgegebenen Elemente tatsächlich aufstei-
% gend (oder absteigend, je nach dem) sortiert sind. Darüberhinaus muss sichergestellt
% werden, dass die (Multi-)Menge der Eingabezahlen mit der (Multi-)Menge der Ausga-
% bezahlen übereinstimmt. Genau für diese Aufgabe wurde in Abschnitt 1.12 ein (proba-
% bilistischer) Algorithmus mit O(n) Komplexität angegeben.
% Ein ähnliches Beispiel findet sich in Kapitel 9. Man kann mit Komplexität O (ns) (sogar
% mit Komplexität O(n2·87") , vgl. Abschnitt 9.1) zwei n >< n Matrizen multiplizieren.
% Verifrzieren, dass das Ergebnis richtig ist, kann man mit einem probabilistischen Algo-
% rithmus mit Komplexität O(n2), siehe Abschnitt 9.3.
% Ein weiteres Beispiel ist der erweiterte Euklidsche Algorithmus (Abschnitt 9.6). Dieser
% Algorithmus berechnet (a, b) »—> (d, az, y), wobei d = ggt(a, b) und d = cm: + by gelten
% soll. Die Korrektheit des Ergebnisses kann durch Testen auf d\ a, d\ b und d = am + by
% bestätigt werden.
% Oft ist es so, dass die Art der Programmierung bereits als ,,Seiteneffekt" eine über-
% prüfbare Datenstruktur hinterlässt, anhand der die Korrektheit des errechneten Ergeb-
% nisses nachvollzogen werden kann. Bei Algorithmen nach dem Prinzip dynamisches
% Programmieren (Kapitel 4) wird am Ende eine vollständig ausgefüllte Tabelle hinter-
% lassen, die in aller Detailliertheit ,,nachweist“, dass das Ergebnis korrekt ist (allerdings
% wird der Veriiikationsalgorithmus nicht wesentlich effizienter sein als der eigentliche
% Algorithmus).
% Es ist beispielsweise wünschenswert, dass man bei einem Entscheidungsproblem A in
% NP (siehe Abschnitt 1.14), das man ja ganz allgemein über eine polynomial entscheid-
% bare Relation R beschreiben kann und welches die Form hat
% $A = {cz | es gibt eine Zusatzeingabe y, so dass (0:,3,;) E R}$
% vom Algorithmus nicht nur die Antwort ,,ja" (es gibt eine Zusatzeingabe y mit (ar, y) E
% R) oder ,,nein" (es gibt keine) erfährt. Im Falle der Antwort ,,ja" sollte das System
% die entsprechende Zusatzeingabe y ebenso bereitstellen (und mit Hilfe der polynomial
% entscheidbaren Relation R kann so die Korrektheit der ,,ja" Antwort überprüft wer-
% den). Auch die Antwort ,,nein" sollte im Idealfall durch die Ausgabe eines ,,Beweises"
% bestätigt werden können. (Im Falle von NP—vollständigen Problemen ist die effiziente
% Verifikation der ,,nein" Ausgabe allerdings nicht möglich, da dieses implizieren würde,
% dass das betreffende Problem nicht nur in NP sondern auch in co—N P , also in N PO co-
% NP, liegt. Hieraus würde folgen NP = co—N P).
% \end{frame}
% 
% \begin{frame}
% Bei anderen Aufgabenstellungen (die nicht NP-vollständig sind) lässt sich ein Verifika-
% tionsmechanismus sowohl für den ,,ja“ als auch für den ,,nein" Fall bereitstellen. Be-
% trachten wir beispielsweise die Aufgabe, festzustellen, ob ein gegebener Graph planar
% ist. Sollte der Graph planar sein, so kann man vom Programm eine planare Einbettung
% des Graphen in die Ebene zeigen lassen. Sollte der Graph nicht planar sein, so kann
% man verlangen, dass der im Graphen versteckte K 5 oder K 3,3 gezeigt wird. (Siehe hier-
% zu jedes Buch über Graphentheorie; Stichwort: Satz von Kuratowski).
% Bei numerischen Verfahren kann sich der Verifikationsmechanimus ausschließlich
% auf die Eingrenzung des Rundungsfehlers beziehen. Synchron mit der eigentlichen
% Ausführung des numerischen Verfahrens wird bei jeder durchgeführten arithmetischen
% Rechenoperation abgeschätzt, wie groß sich hierbei der Rundungsfehler entwickeln
% könnte (im worst-case oder im average-case). Am Ende entsteht parallel mit dem ei-
% gentlichen Rechenergebnis eine Abschätzung über den mit dem Ergebnis gehafteten
% Rundungsfehler. Es kann überprüft werden, ob der Rundungsfehler im Toleranzbereich
% liegt, oder ob die Rechnung von Neuem gestartet werden sollte mit einer veränderten
% Anzahl von Iterationsschritten und/oder ob mit einer längeren Zahlendarstellung gear-
% beitet werden sollte.
% Das allgemeine Modell für einen Verifikationsmechanismus ist wie folgt. Der eigentli-
% che Algorithmus zur Lösung eines Problems oder Berechnung einer Funktion wird um
% eine Veriiikationskomponente ergänzt, die aus der Ein- und Ausgabe, sowie aus Daten,
% die während des eigentlichen Algorithmenablaufs erhoben werden, einen veriiizierba-
% ren Beweis für die Korrektheit des Ergebnisses berechneti
% :6 Algorithmus I y
%  erifikationsalg. ,,Beweis"
% \end{frame}
% 
% \begin{frame}
% Interessant ist der Pfeil vom Verifikationsalgorithmus zum eigentlichen Algorithmus. In
% manchen Situationen kann nämlich der Veriiikationsprozess so vonstatten gehen, dass
% abgesehen von der eigentlichen Berechnung az •—> y der Verifikationsalgorithmus den
% Algorithmus als Unterprogramm verwendet und einige weitere Berechnungen w' e-> y'
% einfordert. Diese Rechenergebnisse werden verwendet, um deren Konsistenz mit der
% eigentlichen Berechnung m i—> y, und damit die Korrektheit von y zu bestätigen.
% Bei den zu Beginn dieses Abschnitts aufgeführten Beispielen war es so, dass der Ve-
% rifikationsvorgang effizienter durchgeführt werden kann als der eigentliche Berech-
% nungsvorgang. Das heißt, für die entsprechenden Komplexitätsfunktionen Tcheck (n)
% und Twmpute (ri) gilt Tcheck (ri) = 0(Tc„„,p„„ (n)). Wenn nun aber der Verifikati-
% onsalgorithmus den Berechnungsalgorithmus sozusagen als Unterprogramm verwen-
% det, so wird man diese Eigenschaft nicht erfüllen können. Aber man sagt, dass ein
% Entscheidungsproblem polyriomial verüizierbar (polynomially checkable) ist, wenn
% es einen Verifikationsalgorithmus gibt, so dass für die Komplexitätsfunktionen gilt
% Tchcck (ri) = p(Tc,„„,,„„ (11)) wobei p ein Polynom ist. (Man beachte, dass Tcompute (ri)
% keine polynomial beschränkte Funktion zu sein braucht).
% Beispiel: Ein bekanntes Beispiel für ein Problem, das einen polynomialen Verif1kations—
% mechanismus zulässt, ist das Graphenisomorphieproblem (vgl. Seite 76). Die Eingabe
% besteht aus zwei Graphen G und H. Der ,,eigentliche" Algorithmus liefert lediglich die
% Antwort ,,ia" oder ,,nein", je nach dem, ob die beiden Graphen (seiner Meinung nach)
% isomorph sind oder nicht. Man beachte, dass bisher kein polynomialer Algorithmen für
% das Graphenisomorphieproblem bekannt ist. Es ist aber trotzdem auch unwahrschein-
% lich, dass das Problem NP—vollständig ist (insbesondere aufgrund des hier angegebenen
% Ergebnisses, das das Graphenisomorphieproblem von den anderen NP—vollständigen
% \ Problem unterscheidet).
% \end{frame}
% 
% \begin{frame}
% E Der hinzu kommende Verifikationsmechanismus ist nun der Folgende: Wenn der ge-
% Hjj gebene Algorithmus behauptet, die Graphen seien isomorph, so soll zum Beweis ein
% ( Isomorphismus konstruiert werden. Dies kann man mit Hilfe der so genannten Selbst-
% J reduktionsstruktur des Graphenisomorphieproblems erreichen. Und zwar kann man an
% ff einen Knoten u von G und einen Knoten 11 von H probehalber zwei identische Testgra-
% Ä phen über eine zusätzliche Kante anschließen. Diese Testgraphen können zum Beispiel
% 1 zwei Cliquen mit n -l- 1 Knoten sein, denn diese können sonst nirgends im eigentlichen
% H Graphen als Teilgraph vorkommen. Daher können die Testgraphen von einem potenziellen lsomorphismus nur aufeinander abgebildet werden und ferner muss dann u auf v
%   abgebildet werden. V
% K
% i
% \end{frame}
