tutorium10.tex

\include{includes/common_start}
\include{includes/tutBlatt_methods}
\include{amsmath}

\tutnr{10}

\section{Informationsquellen}
\subsection{Informationsquellen}
\begin{frame}
\frametitle{look-up}
\begin{itemize}
	\item Vorlesungsfolien
	\begin{itemize}
		\item http://www.iks.kit.edu/index.php?id=tgi-ws12
	\end{itemize}
	\item Tutoriumsfolien
	\begin{itemize}
		\item tinyurl.com/tgi1213
		\item Neue Position des Download-Ordners~\\
		\includegraphics[scale=0.2]{images/download.png}
	\end{itemize}
	\item Michael Sipser, Introduction to the Theory of Computation
	\begin{itemize}
		\item Grundlage der Vorlesung
		\item Eher zum Nachschlagen empfohlen
	\end{itemize}
	\item Vorlesungs-Skript
	\begin{itemize}
		\item In Arbeit
		\item Unter Umständen sehr geringe Zeitspanne zwischen Veröffentlichung des Skripts und der Klausur
	\end{itemize}
\end{itemize}
\end{frame}

\section{Aufgaben zu P, NP}
\subsection{Aufgabe B10 A2}
\begin{frame}
	\frametitle{Aufgabe B10 A2}
	Finden Sie den Fehler im folgenden ``Beweis'' f"ur \textbf{P} $\not=$ \textbf{NP}!\\
	Betrachten Sie folgenden Algorithmus f"ur SAT:\\[4pt]
	- Durchlaufe f"ur die gegebene Formel $\phi$ alle m"oglichen Belegungen der
	Variablen mit den Wahrheitswerten\\
	- Akzeptiere $\phi$, wenn eine der durchlaufenen Belegungen $\phi$ erf"ullt\\[4pt]
	Dieser Algorithmus hat eine mit der Anzahl der Variablen exponentiell wachsende
	Laufzeit. Daher hat das Problem SAT einen exponentiellen Aufwand und kann nicht in
	\textbf{P} liegen. Weil aber SAT in \textbf{NP} liegt, mu"s also \textbf{P} $\not=$
	\textbf{NP} gelten.
\end{frame}
\subsection{Aufgabe B10 A3}
\begin{frame}
	\frametitle{Aufgabe B10 A3}
	\begin{enumerate}
		\item Zeigen Sie, dass es unter der Voraussetzung \textbf{P} $=$ \textbf{NP} m"oglich
		ist, f"ur eine aussagenlogische Formel $\phi$ in\\
		polynomieller Zeit eine erf"ullende Belegung der Variablen zu finden, falls eine
		solche Belegung existiert!
	\end{enumerate}
\end{frame}

\section{HALF-CLIQUE}
\subsection{HALF-CLIQUE}
\begin{frame}
	\frametitle{HALF-CLIQUE}
	\begin{block}{Wiederholung: CLIQUE}
		Enthält der Graph $G = (V, E)$ einen Teilmenge $V' \subseteq V$ mit $|V'| \geq n$, bei der jeder Knoten eine Kante zu jedem anderen Knoten des Teilgraphs hat?
	\end{block}
	\begin{block}{HALF-CLIQUE}
		Enthält der Graph $G = (V, E)$ eine CLIQUE mit $|V'| \geq |V|/2$?
	\end{block}
\end{frame}
\subsection{Aufgabe B10 A1}
\begin{frame}
	\frametitle{Aufgabe B10 A1}
	Gegeben ist das folgende Problem:
	\begin{tabbing}
	HALF-CLIQUE:\\
	\textit{Gegeben:} \= Ein ungerichteter Graph $G = (V,E)$\\
	\textit{Gesucht:} \> Gibt es eine Teilmenge $V' \subseteq V$\\
	\> mit	$\forall \; v,w \in V', v \not= w: (v,w) \in E$ und $|V'| \geq |V|/2$
	\end{tabbing}
	Beweisen Sie, dass HALF-CLIQUE \textbf{NP}-vollst"andig ist!\\[4pt]
	\underline{Zur Erinnerung:}\\
	Das als \textbf{NP}-vollst"andig bekannte Problem CLIQUE ist definiert durch:
	\begin{tabbing}
	CLIQUE:\\
	\textit{Gegeben:} \= Ein ungerichteter Graph $G = (V,E)$ und $k \in \mathbb{N}$\\
	\textit{Gesucht:} \> Gibt es eine Teilmenge $V' \subseteq V$\\
	\> mit	$\forall \; v,w \in V', v \not= w: (v,w) \in E$ und $|V'| \geq k$
	\end{tabbing}
\end{frame}

\section{Hamiltonkreis und TSP}
\subsection{Hamiltonkreis}
\begin{frame}
	\frametitle{Hamiltonkreis}
	\begin{block}{Kurzdefinition}
	Enthält der gegebene Graph einen Kreis, d.h. gibt es einen Pfad der durch jeden Knoten exakt einmal geht und vom Startknoten wieder zum Startknoten führt (Start- und Endknoten wird nur einmal gezählt).
	\end{block}
	\begin{block}{Formal}
	Gegeben: Ein ungerichteter Graph $G=(V,E)$.\\
	Gesucht: Besitzt $G$ einen Hamiltonkreis? (Dies ist eine Permutation $\pi$ der Knotenindizes ($v_{\pi(1)}$, $v_{\pi(2)}$,...,$v_{\pi(n)}$), sodass für $i=1,...,n-1$ gilt: $\{v_{\pi(i)},v_{\pi(i+1)}\}\in E$) und 
außerdem $\{v_{\pi(n)},v_{\pi(1)}\} \in E)$.
	\end{block}
\end{frame}
\begin{frame}
	\frametitle{Beispiel}
	Gibt es in diesem Graphen einen Hamiltonkreis?
	\begin{center}
		\includegraphics[scale=0.4]{images/4_Faerben}
	\end{center}
\end{frame}
\subsection{Travelling Salesman}
\begin{frame}
	\frametitle{Travelling Salesman}
	\begin{block}{Kurzdefinition}
	Geben sie einen Kreis des gegeben vollständig verbundenen Graphen mit Kantenlängen an, sodass dessen Gesamtkantenlänge minimal ist.
	\end{block}
	\begin{block}{Formal}
	Gegeben: Ein Graph $G=(V,V \times V)$\\
	Gesucht: Ein einfacher Kreis $C=(v_1,v_2,...,v_n,v_1)$, sodass $n=|V|$ und $\sum_{(u,v)\in C} d(u,v)$ minimiert wird, wobei $d(u,v)$ die Entfernung zwischen den Knoten $u$ und $v$ ist.\\
	\end{block}
\end{frame}
\begin{frame}
	\frametitle{Beispiel}
	Wie lang ist die kürzeste Route und durch welche Kanten geht sie?
	\begin{center}		
		\includegraphics[scale=0.5]{images/Weighted_K4}
	\end{center}
\end{frame}
\subsection{Aufgabe B10 A4}
\begin{frame}
	\frametitle{Aufgabe B10 A4}
 Gegeben sind folgende Probleme: 
 \begin{tabbing}
 \textbf{Hamiltonkreisproblem:} \\
 \hspace{10pt} \= \textit{Gegeben:} \= Ein ungerichteter Baum $G=(V,E)$.\\
 \> \textit{Gesucht:} \> Besitzt $G$ einen Hamiltonkreis? (Dies ist eine Permutation $\pi$\\
 \> der Knotenindizes ($v_{\pi(1)}$,$v_{\pi(2)}$,...,$v_{\pi(n)}$), sodass für $i=1,...,n-1$ gilt:\\
 \> $\{v_{\pi(i)},v_{\pi(i+1)}\}\in E$) und außerdem $\{v_{\pi(n)},v_{\pi(1)}\} \in E)$.\\ \\
 \textbf{Travelling Salesman(TSP):}\\
 \> \textit{Gegeben:} Ein Graph $G=(V,V \times V)$\\
 \> \textit{Gesucht:} \> Ein einfacher Kreis $C=(v_1,v_2,...,v_n,v_1)$, sodass $n=|V|$\\ 
 \> und $\sum_{(u,v)\in C} d(u,v)$ minimiert wird, wobei $d(u,v)$ die Entfernung\\ 
 \>zwischen den Knoten $u$ und $v$ ist.\\
\end{tabbing}
Zeigen Sie, dass TSP NP-Vollständig ist, wobei das Hamiltonkreisproblem auch NP-Vollständig ist. Benutzen Sie für den Beweis die Reduktion Hamiltonkreisproblem$\leq_p$TSP. 
\end{frame}
\begin{frame}
	\frametitle{Aufgabe B10 A4}
Gegeben sei folgender Graph:\newline
\begin{center}
\begin{tikzpicture}
 \draw (0,0) circle (8pt);
 \draw (0,0) node {$v_0$};
 \draw (2,0) circle (8pt);
 \draw (2,0) node {$v_1$};
 \draw (2,2) circle (8pt);
 \draw (2,2) node {$v_2$};
 \draw (1,3) circle (8pt);
 \draw (1,3) node {$v_3$};
 \draw (0,2) circle (8pt);
 \draw (0,2) node {$v_4$};
 \draw (0.2,0.2) -- (1.8,1.8);
 \draw (0.2,1.8) -- (1.8,0.2);
 \draw (0.2,2.2) -- (0.8,2.8);
 \draw (1.2,2.8) -- (1.8,2.2);
 \draw (0.3,0) -- (1.7,0);
 \draw (0.3,2) -- (1.7,2);
 \draw (0,0.3) -- (0,1.7);
 \draw (2,0.3) -- (2,1.7);
\end{tikzpicture}
\end{center}
Gibt es einen Hamiltonkreis? Wandeln Sie hierzu das Problem in ein TSP um und finden Sie eine optimale Rundtour.
\end{frame}

\section{Schluss}
\subsection{Schluss}
\begin{frame}
\frametitle{Bis zum nächsten Mal!}
\begin{center}
	\includegraphics[scale=5.2]{images/287_np_complete.png}
\end{center}
\end{frame}

\include{includes/common_end}