Mercurial > latex
changeset 69:276d1908df24
proper indentation
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Thu, 13 Dec 2012 19:36:52 +0100 |
| parents | b2b8833da000 |
| children | 4e3e078f5338 |
| files | bayesian_networks/presentation.tex planarity/presentation.tex |
| diffstat | 2 files changed, 1455 insertions(+), 1454 deletions(-) [+] |
line wrap: on
line diff
--- a/bayesian_networks/presentation.tex Tue Dec 11 21:43:57 2012 +0100 +++ b/bayesian_networks/presentation.tex Thu Dec 13 19:36:52 2012 +0100 @@ -36,15 +36,15 @@ \newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}} \newenvironment{changemargin}[2]{% - \begin{list}{}{% - \setlength{\topsep}{0pt}% - \setlength{\leftmargin}{#1}% - \setlength{\rightmargin}{#2}% - \setlength{\listparindent}{\parindent}% - \setlength{\itemindent}{\parindent}% - \setlength{\parsep}{\parskip}% - }% - \item[]}{\end{list}} + \begin{list}{}{% + \setlength{\topsep}{0pt}% + \setlength{\leftmargin}{#1}% + \setlength{\rightmargin}{#2}% + \setlength{\listparindent}{\parindent}% + \setlength{\itemindent}{\parindent}% + \setlength{\parsep}{\parskip}% + }% +\item[]}{\end{list}} \usetikzlibrary{calc} @@ -53,13 +53,13 @@ \tikzstyle{selected edge} = [edge, tumred] \tikzstyle{circular node} = [circle,thick,draw,fill=tumblue!20,minimum size=12pt,inner sep=0pt,font=\bfseries] \tikzstyle{net node} = [ellipse, draw, thick, fill=tumblue!20, - minimum width=6em, minimum height=2.5em, - node distance=10em, inner sep = 0] + minimum width=6em, minimum height=2.5em, +node distance=10em, inner sep = 0] \tikzstyle{selected net node} = [net node, fill=tumred!20] \def \netvspace {8em} \tikzstyle{net cpt} = [draw, thick, fill = tumgreen!20, - font=\scriptsize, node distance=3em, - inner sep = 2pt] + font=\scriptsize, node distance=3em, +inner sep = 2pt] \title{Bayesnetze} \subtitle{Seminar ``Kognitive Robotik''} @@ -83,7 +83,7 @@ \begin{document} \begin{frame} - \titlepage + \titlepage \end{frame} % Inhaltsverzeichnis @@ -93,768 +93,769 @@ %\end{frame} \begin{frame}[t] - \frametitle{Motivation} - Wissen ist selten \alert{sicher} oder vollständig. - - \vspace{1em} + \frametitle{Motivation} + Wissen ist selten \alert{sicher} oder vollständig. + + \vspace{1em} - \begin{example} [Medizinische Diagnose] - Software soll mögliche Ursachen für Beschwerden finden. - \begin{center} - \begin{columns}[c] - \begin{column}{.35\textwidth} - \begin{itemize} - \item Vorgeschichte - \item Symptome - \item Testergebnisse - \end{itemize} - \end{column} - \begin{column}{.10\textwidth} - \begin{figure} - \begin{tikzpicture}[auto] - \useasboundingbox (0, 0.5) rectangle (1, -0.5); - \draw[->, >=latex, line width=.35em, black!75] (0,0) -- (1,0); - \end{tikzpicture} - \end{figure} - \end{column} - \begin{column}{.35\textwidth} - \begin{itemize} - \item Diagnose - \item Therapie - \end{itemize} - \end{column} - \end{columns} - \end{center} - \end{example} - - Mögliche Unsicherheiten - \begin{itemize} - \item Vorgeschichte \alert{unvollständig}, Symptome \alert{vage} - \item Symptome und Tests lassen mehrere \alert{Alternativen} zu - \item Das Wissen ist \alert{fehlerbehaftet} - \end{itemize} + \begin{example} [Medizinische Diagnose] + Software soll mögliche Ursachen für Beschwerden finden. + \begin{center} + \begin{columns}[c] + \begin{column}{.35\textwidth} + \begin{itemize} + \item Vorgeschichte + \item Symptome + \item Testergebnisse + \end{itemize} + \end{column} + \begin{column}{.10\textwidth} + \begin{figure} + \begin{tikzpicture}[auto] + \useasboundingbox (0, 0.5) rectangle (1, -0.5); + \draw[->, >=latex, line width=.35em, black!75] (0,0) -- (1,0); + \end{tikzpicture} + \end{figure} + \end{column} + \begin{column}{.35\textwidth} + \begin{itemize} + \item Diagnose + \item Therapie + \end{itemize} + \end{column} + \end{columns} + \end{center} + \end{example} + + Mögliche Unsicherheiten + \begin{itemize} + \item Vorgeschichte \alert{unvollständig}, Symptome \alert{vage} + \item Symptome und Tests lassen mehrere \alert{Alternativen} zu + \item Das Wissen ist \alert{fehlerbehaftet} + \end{itemize} \end{frame} \begin{frame}[c] - \frametitle{Wahrscheinlichkeitstheorie} - - \begin{definition}[Wahrscheinlichkeitsraum] - Ein \alert{Wahrscheinlichkeitsraum} $P$ besteht aus einer Menge von \alert{Elementarereignissen} $\Omega$, \alert{Ereignissen} $A$ und einem \alert{Wahrscheinlichkeitsmaß} $\Pr$. - - \begin{itemize} - \item $A$ ist $\sigma$-Algebra über $\Omega$ - \item $\Pr : A \mapsto [0,1]$ - \item $P = (\Omega, A, \Pr)$ - - \vspace{1em} - - \item $\Pr[\Omega] = 1$ - \item $A \cap B = \emptyset \Rightarrow \Pr[A \cup B] = \Pr[A] + \Pr[B]$ - \end{itemize} - \end{definition} + \frametitle{Wahrscheinlichkeitstheorie} + + \begin{definition}[Wahrscheinlichkeitsraum] + Ein \alert{Wahrscheinlichkeitsraum} $P$ besteht aus einer Menge von \alert{Elementarereignissen} $\Omega$, \alert{Ereignissen} $A$ und einem \alert{Wahrscheinlichkeitsmaß} $\Pr$. + + \begin{itemize} + \item $A$ ist $\sigma$-Algebra über $\Omega$ + \item $\Pr : A \mapsto [0,1]$ + \item $P = (\Omega, A, \Pr)$ + + \vspace{1em} + + \item $\Pr[\Omega] = 1$ + \item $A \cap B = \emptyset \Rightarrow \Pr[A \cup B] = \Pr[A] + \Pr[B]$ + \end{itemize} + \end{definition} \end{frame} \begin{frame} - \frametitle{Wahrscheinlichkeitstheorie} - - \begin{definition}[Bedingte Wahrscheinlichkeit] - A und B seien Ereignisse mit $\Pr[B] > 0$. Die \alert{bedingte Wahrscheinlichkeit} von A unter der Bedingung B ist dann - $$\Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}$$ - \end{definition} - - \begin{definition}[Unabhängigkeit] - Zwei Ereignisse A und B sind \alert{unabhängig} wenn gilt - $$\Pr[A \cap B] = \Pr[A] \cdot \Pr[B] = \Pr[A \mid B] \cdot \Pr[B]$$ - \end{definition} + \frametitle{Wahrscheinlichkeitstheorie} + + \begin{definition}[Bedingte Wahrscheinlichkeit] + A und B seien Ereignisse mit $\Pr[B] > 0$. Die \alert{bedingte Wahrscheinlichkeit} von A unter der Bedingung B ist dann + $$\Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}$$ + \end{definition} + + \begin{definition}[Unabhängigkeit] + Zwei Ereignisse A und B sind \alert{unabhängig} wenn gilt + $$\Pr[A \cap B] = \Pr[A] \cdot \Pr[B] = \Pr[A \mid B] \cdot \Pr[B]$$ + \end{definition} \end{frame} \begin{frame}[c] - \frametitle{Wahrscheinlichkeitstheorie} - - \begin{theorem}[Produktsatz] - Für unabhängige Ereignisse $A_i$ gilt - - $$\Pr\left[\, \bigcap_{i=1}^n A_i \right] = - \prod_{i=1}^n \Pr \left[ A_i \left| \bigcup_{k=1}^{i-1} \right.\right]$$ - \end{theorem} - Also zum Beispiel - $$\Pr[A,B,C] = \Pr[A \mid B, C] \cdot \Pr[B \mid C] \cdot \Pr[B]$$ - und - $$\Pr[A \mid B] = \frac{\Pr[A, B]}{\Pr[B]} = \alert{\alpha} \cdot \Pr[A,B]$$ + \frametitle{Wahrscheinlichkeitstheorie} + + \begin{theorem}[Produktsatz] + Für unabhängige Ereignisse $A_i$ gilt + + $$\Pr\left[\, \bigcap_{i=1}^n A_i \right] = + \prod_{i=1}^n \Pr \left[ A_i \left| \bigcup_{k=1}^{i-1} \right.\right]$$ + \end{theorem} + Also zum Beispiel + $$\Pr[A,B,C] = \Pr[A \mid B, C] \cdot \Pr[B \mid C] \cdot \Pr[B]$$ + und + $$\Pr[A \mid B] = \frac{\Pr[A, B]}{\Pr[B]} = \alert{\alpha} \cdot \Pr[A,B]$$ \end{frame} \begin{frame}[c] - \frametitle{Wahrscheinlichkeitstheorie} - - \begin{theorem}[Satz über die totale Wahrscheinlichkeit] - Sind die Ereignisse $A_i$ paarweise disjunkt und möglich, dann gilt für ein Ereignis $B$ mit $\Pr[B] > 0$ - $$\Pr[B] = \sum_{i=1}^n \Pr[B \mid A_i] \cdot \Pr[A_i]$$ - \end{theorem} - - \begin{theorem} [Satz von Bayes] - Für zwei Ereignisse $A$ und $B$ mit $\Pr[B] > 0$ ist - $$\Pr[A \mid B] = \frac{\Pr[B \mid A] \cdot \Pr[A]}{\Pr[B]}$$ - \end{theorem} + \frametitle{Wahrscheinlichkeitstheorie} + + \begin{theorem}[Satz über die totale Wahrscheinlichkeit] + Sind die Ereignisse $A_i$ paarweise disjunkt und möglich, dann gilt für ein Ereignis $B$ mit $\Pr[B] > 0$ + $$\Pr[B] = \sum_{i=1}^n \Pr[B \mid A_i] \cdot \Pr[A_i]$$ + \end{theorem} + + \begin{theorem} [Satz von Bayes] + Für zwei Ereignisse $A$ und $B$ mit $\Pr[B] > 0$ ist + $$\Pr[A \mid B] = \frac{\Pr[B \mid A] \cdot \Pr[A]}{\Pr[B]}$$ + \end{theorem} \end{frame} \begin{frame} - \frametitle{Nachmittagsplanung} - - \begin{example}[Nachmittagsplanung] - Ich habe einen Nachmittag lang Zeit. Ich könnte \alert{Lebensmittel kaufen}, \alert{Sport machen} oder \alert{Lernen}. Ich habe genug Zeit für alle drei. Da ich ein sehr unentschlossener Mensch bin \alert{würfle} ich mittags mit einem \alert{W20}. - \end{example} - - \vspace{2em} - - \begin{center} - \begin{tikzpicture} - \node [net node] (sport) {Sport}; - \node [net cpt] [below of = sport] - {\begin{tabu}{c} - $\Pr[S]$ \\ \tabucline{-} - $0.4$ \\ - \end{tabu}}; - - \node [net node] (kaufen) [left of = sport] {Kaufen}; - \node [net cpt] [below of = kaufen] - {\begin{tabu}{c} - $\Pr[K]$ \\ \tabucline{-} - $0.5$ \\ - \end{tabu}}; - - \node [net node] (lernen) [right of = sport] {Lernen}; - \node [net cpt] [below of = lernen] - {\begin{tabu}{c} - $\Pr[L]$ \\ \tabucline{-} - $0.2$ \\ - \end{tabu}}; - \end{tikzpicture} - \end{center} + \frametitle{Nachmittagsplanung} + + \begin{example}[Nachmittagsplanung] + Ich habe einen Nachmittag lang Zeit. Ich könnte \alert{Lebensmittel kaufen}, \alert{Sport machen} oder \alert{Lernen}. Ich habe genug Zeit für alle drei. Da ich ein sehr unentschlossener Mensch bin \alert{würfle} ich mittags mit einem \alert{W20}. + \end{example} + + \vspace{2em} + + \begin{center} + \begin{tikzpicture} + \node [net node] (sport) {Sport}; + \node [net cpt] [below of = sport] + {\begin{tabu}{c} + $\Pr[S]$ \\ \tabucline{-} + $0.4$ \\ + \end{tabu}}; + + \node [net node] (kaufen) [left of = sport] {Kaufen}; + \node [net cpt] [below of = kaufen] + {\begin{tabu}{c} + $\Pr[K]$ \\ \tabucline{-} + $0.5$ \\ + \end{tabu}}; + + \node [net node] (lernen) [right of = sport] {Lernen}; + \node [net cpt] [below of = lernen] + {\begin{tabu}{c} + $\Pr[L]$ \\ \tabucline{-} + $0.2$ \\ + \end{tabu}}; + \end{tikzpicture} + \end{center} \end{frame} \begin{frame}[t] - \frametitle{Nachmittagsplanung} - - \begin{center} - \begin{tikzpicture} - \node [net node] (sport) {Sport}; - \node [net cpt] [below of = sport] - {\begin{tabu}{c} - $\Pr[S]$ \\ \tabucline{-} - $0.4$ \\ - \end{tabu}}; - - \node [net node] (kaufen) [left of = sport] {Kaufen}; - \node [net cpt] [below of = kaufen] - {\begin{tabu}{c} - $\Pr[K]$ \\ \tabucline{-} - $0.5$ \\ - \end{tabu}}; - - \node [net node] (lernen) [right of = sport] {Lernen}; - \node [net cpt] [below of = lernen] - {\begin{tabu}{c} - $\Pr[L]$ \\ \tabucline{-} - $0.2$ \\ - \end{tabu}}; - \end{tikzpicture} - \end{center} + \frametitle{Nachmittagsplanung} + + \begin{center} + \begin{tikzpicture} + \node [net node] (sport) {Sport}; + \node [net cpt] [below of = sport] + {\begin{tabu}{c} + $\Pr[S]$ \\ \tabucline{-} + $0.4$ \\ + \end{tabu}}; + + \node [net node] (kaufen) [left of = sport] {Kaufen}; + \node [net cpt] [below of = kaufen] + {\begin{tabu}{c} + $\Pr[K]$ \\ \tabucline{-} + $0.5$ \\ + \end{tabu}}; + + \node [net node] (lernen) [right of = sport] {Lernen}; + \node [net cpt] [below of = lernen] + {\begin{tabu}{c} + $\Pr[L]$ \\ \tabucline{-} + $0.2$ \\ + \end{tabu}}; + \end{tikzpicture} + \end{center} - \vspace{1em} - \only<1>{ - Wie groß ist die Wahrscheinlichkeit, - \vspace{1em} - \begin{itemize} - \item dass ich \alert{lerne}, \alert{einkaufen} gehe, aber \alert{keinen Sport} mache? - $$\Pr[K, \neg S, L] = \Pr[K] \cdot \Pr[\neg S] \cdot \Pr[L] = 0.5 \cdot 0.6 \cdot 0.2 = 0.06$$ - - \item dass ich \alert{nicht lerne}, aber \alert{Sport mache}? - $$\Pr[S, \neg L] = \sum_k \Pr[k] \cdot \Pr[S] \cdot \Pr[\neg L] = \Pr[S] \cdot \Pr[\neg L] = 0.32$$ - \end{itemize} - } - - \only<2>{ - \begin{itemize} - \item Alle möglichen Belegungen lassen sich in einer gemeinsamen Verteilung (\alert{joint distribution}) darstellen. - \item Für \alert{$n$} binäre Zufallsgrößen hat diese aber \alert{$2^n$} Einträge. - \end{itemize} - - \begin{center} - \begin{tabu}{|ccc|[1.2pt]c||ccc|[1.2pt]c|} - \hline - K & S & L & $\Pr$ & K & S & L & $\Pr$ \\ - \tabucline[1.2pt]{-} - F & F & F & 0.24 & T & F & F & 0.24 \\ - \hline - F & F & T & 0.06 & T & T & T & 0.06 \\ - \hline - F & T & F & 0.16 & T & T & T & 0.16 \\ - \hline - F & T & T & 0.04 & T & T & T & 0.04 \\ - \hline - \end{tabu} - \end{center} - } + \vspace{1em} + \only<1>{ + Wie groß ist die Wahrscheinlichkeit, + \vspace{1em} + \begin{itemize} + \item dass ich \alert{lerne}, \alert{einkaufen} gehe, aber \alert{keinen Sport} mache? + $$\Pr[K, \neg S, L] = \Pr[K] \cdot \Pr[\neg S] \cdot \Pr[L] = 0.5 \cdot 0.6 \cdot 0.2 = 0.06$$ + + \item dass ich \alert{nicht lerne}, aber \alert{Sport mache}? + $$\Pr[S, \neg L] = \sum_k \Pr[k] \cdot \Pr[S] \cdot \Pr[\neg L] = \Pr[S] \cdot \Pr[\neg L] = 0.32$$ + \end{itemize} + } + + \only<2>{ + \begin{itemize} + \item Alle möglichen Belegungen lassen sich in einer gemeinsamen Verteilung (\alert{joint distribution}) darstellen. + \item Für \alert{$n$} binäre Zufallsgrößen hat diese aber \alert{$2^n$} Einträge. + \end{itemize} + + \begin{center} + \begin{tabu}{|ccc|[1.2pt]c||ccc|[1.2pt]c|} + \hline + K & S & L & $\Pr$ & K & S & L & $\Pr$ \\ + \tabucline[1.2pt]{-} + F & F & F & 0.24 & T & F & F & 0.24 \\ + \hline + F & F & T & 0.06 & T & T & T & 0.06 \\ + \hline + F & T & F & 0.16 & T & T & T & 0.16 \\ + \hline + F & T & T & 0.04 & T & T & T & 0.04 \\ + \hline + \end{tabu} + \end{center} + } \end{frame} \begin{frame} - \frametitle{Abhängigkeiten} - - \begin{example}[Erweiterte Nachmittagsplanung] - Ich möchte das Haus nicht verlassen müssen, wenn es regnet. Deshalb halbiere ich bei \alert{Regen} die Wahrscheinlichkeit für Aktivitäten außer Haus.\\ - Wenn ich weder Sport mache noch lerne bekomme ich ein \alert{schlechtes Gewissen}. Nach meinem Würfelergebnis möchte ich wissen, wie groß die Wahrscheinlichkeit ist, am Abend schlecht gelaunt zu sein. - \end{example} - - \vspace{1em} - - Probleme: - \begin{itemize} - \item $\Pr[R, S] \neq \Pr[R] \cdot \Pr[S]$ - \item Alle Sätze brauchen \alert{Unabhängigkeit} - \end{itemize} + \frametitle{Abhängigkeiten} + + \begin{example}[Erweiterte Nachmittagsplanung] + Ich möchte das Haus nicht verlassen müssen, wenn es regnet. Deshalb halbiere ich bei \alert{Regen} die Wahrscheinlichkeit für Aktivitäten außer Haus.\\ + Wenn ich weder Sport mache noch lerne bekomme ich ein \alert{schlechtes Gewissen}. Nach meinem Würfelergebnis möchte ich wissen, wie groß die Wahrscheinlichkeit ist, am Abend schlecht gelaunt zu sein. + \end{example} + + \vspace{1em} + + Probleme: + \begin{itemize} + \item $\Pr[R, S] \neq \Pr[R] \cdot \Pr[S]$ + \item Alle Sätze brauchen \alert{Unabhängigkeit} + \end{itemize} \end{frame} \begin{frame} - \frametitle{Bayesnetze} - - Es sind immernoch Unabhängigkeiten vorhanden: - \begin{itemize} - \item \alert{Regen} beeinflusst das \alert{Lernen} nicht - \item \alert{Einkaufen} und \alert{Sport} beeinflussen sich nicht - \end{itemize} + \frametitle{Bayesnetze} + + Es sind immernoch Unabhängigkeiten vorhanden: + \begin{itemize} + \item \alert{Regen} beeinflusst das \alert{Lernen} nicht + \item \alert{Einkaufen} und \alert{Sport} beeinflussen sich nicht + \end{itemize} - \vfill + \vfill - \begin{definition}[Bedingte Unabhängigkeit] - Zwei Ereignisse A und B sind \alert{bedingt unabhängig} unter einem Ereignis C wenn gilt - - $$\Pr[A, B \mid C] = \Pr[A \mid C] \cdot \Pr[B \mid C]$$ - \end{definition} - Einkaufen und Sport sind \alert{bedingt unabhängig} unter Regen. + \begin{definition}[Bedingte Unabhängigkeit] + Zwei Ereignisse A und B sind \alert{bedingt unabhängig} unter einem Ereignis C wenn gilt + + $$\Pr[A, B \mid C] = \Pr[A \mid C] \cdot \Pr[B \mid C]$$ + \end{definition} + Einkaufen und Sport sind \alert{bedingt unabhängig} unter Regen. \end{frame} \begin{frame} - \frametitle{Bayesnetze} + \frametitle{Bayesnetze} + + \begin{tikzpicture} + \node [net node] (sport) {Sport}; + \node [net node] (kaufen) [left of = sport] {Kaufen}; + \node [net node] (lernen) [right of = sport] {Lernen}; + + \node [net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; + \node [net node] (regen) at ($0.5*(sport.center) + 0.5*(kaufen.center) + (0,\netvspace)$) {Regen}; + + \node<2,3> [selected net node] (sport) {Sport}; + \node<2> [selected net node] (kaufen) [left of = sport] {Kaufen}; + \node<3> [selected net node] (lernen) [right of = sport] {Lernen}; - \begin{tikzpicture} - \node [net node] (sport) {Sport}; - \node [net node] (kaufen) [left of = sport] {Kaufen}; - \node [net node] (lernen) [right of = sport] {Lernen}; - - \node [net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; - \node [net node] (regen) at ($0.5*(sport.center) + 0.5*(kaufen.center) + (0,\netvspace)$) {Regen}; - - \node<2,3> [selected net node] (sport) {Sport}; - \node<2> [selected net node] (kaufen) [left of = sport] {Kaufen}; - \node<3> [selected net node] (lernen) [right of = sport] {Lernen}; - - \node<3> [selected net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; - \node<2,4> [selected net node] (regen) at ($0.5*(sport.center) + 0.5*(kaufen.center) + (0,\netvspace)$) {Regen}; - \node<4> [selected net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; - - \foreach \src/\dest in {regen/kaufen, regen/sport, - sport/gewissen, lernen/gewissen} - \path [edge] (\src) -- (\dest); - - \foreach \i/\src/\dest in {2/regen/kaufen, 2/regen/sport, - 3/sport/gewissen, 3/lernen/gewissen} - \path<\i> [selected edge] (\src) -- (\dest); - - \end{tikzpicture} + \node<3> [selected net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; + \node<2,4> [selected net node] (regen) at ($0.5*(sport.center) + 0.5*(kaufen.center) + (0,\netvspace)$) {Regen}; + \node<4> [selected net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; + + \foreach \src/\dest in {regen/kaufen, regen/sport, + sport/gewissen, lernen/gewissen} + \path [edge] (\src) -- (\dest); + + \foreach \i/\src/\dest in {2/regen/kaufen, 2/regen/sport, + 3/sport/gewissen, 3/lernen/gewissen} + \path<\i> [selected edge] (\src) -- (\dest); + + \end{tikzpicture} \end{frame} \begin{frame}[t] - \frametitle{d-Separation} - - \begin{definition}[d-Separation] - Zwei Knotenmengen $X$ und $Y$ sind in einem DAG $G$ durch $Z$ \alert{d-separiert} $\langle X \mid Z \mid Y \rangle_G$ wenn es \alert{keinen} (ungerichteten) Pfad zwischen $X$ und $Y$ gibt für den gilt - \begin{enumerate} - \item Jeder Knoten an dem Kanten \alert{zusammenlaufen} ist selbst in $Z$ oder hat einen Nachfahren in $Z$ - \item Jeder \alert{andere Knoten} ist nicht in $Z$ - \end{enumerate} - \end{definition} + \frametitle{d-Separation} + + \begin{definition}[d-Separation] + Zwei Knotenmengen $X$ und $Y$ sind in einem DAG $G$ durch $Z$ \alert{d-separiert} $\langle X \mid Z \mid Y \rangle_G$ wenn es \alert{keinen} (ungerichteten) Pfad zwischen $X$ und $Y$ gibt für den gilt + \begin{enumerate} + \item Jeder Knoten an dem Kanten \alert{zusammenlaufen} ist selbst in $Z$ oder hat einen Nachfahren in $Z$ + \item Jeder \alert{andere Knoten} ist nicht in $Z$ + \end{enumerate} + \end{definition} - \vfill - - \uncover<2-5> { - \begin{center} - \begin{tikzpicture} - \tikzstyle {dag node} = [circular node, font=\normalfont, inner sep = 2pt, - node distance = 4em] - \tikzstyle {bad dag node} = [dag node, fill=tumred!20] - \tikzstyle {good dag node} = [dag node, fill=tumgreen!20] - - \def \xdist {4em} - \def \ydist {3em} + \vfill + + \uncover<2-5> { + \begin{center} + \begin{tikzpicture} + \tikzstyle {dag node} = [circular node, font=\normalfont, inner sep = 2pt, + node distance = 4em] + \tikzstyle {bad dag node} = [dag node, fill=tumred!20] + \tikzstyle {good dag node} = [dag node, fill=tumgreen!20] + + \def \xdist {4em} + \def \ydist {3em} - \useasboundingbox ($(-3*\xdist, -\ydist)$) rectangle ($(\xdist, \ydist)$); - \node [dag node] (C) at (0,0) {C}; - \node [dag node] (A) at ($(C.center) + (-\xdist, \ydist)$) {A}; - \node [dag node] (B) at ($(C.center) + (\xdist, \ydist)$) {B}; - \node [dag node] (E) at ($(C.center) + (-\xdist, -\ydist)$) {E}; - \node [dag node] (F) at ($(C.center) + (\xdist, -\ydist)$) {F}; - \node [dag node] (D) at ($(C.center) + (2 * \xdist, 0)$) {D}; - - \foreach \src/\dest in {A/C, B/C, B/D, C/F, D/F, C/E} - \path [edge] (\src) -- (\dest); - - \foreach \i/\Node in {3/A, 3/B, 4/A, 4/B, 5/A, 5/E} - \node<\i> [good dag node] at ($(\Node.center)$) {\Node}; - - \foreach \i/\Node in {4/C, 5/C} - \node<\i> [bad dag node] at ($(\Node.center)$) {\Node}; + \useasboundingbox ($(-3*\xdist, -\ydist)$) rectangle ($(\xdist, \ydist)$); + \node [dag node] (C) at (0,0) {C}; + \node [dag node] (A) at ($(C.center) + (-\xdist, \ydist)$) {A}; + \node [dag node] (B) at ($(C.center) + (\xdist, \ydist)$) {B}; + \node [dag node] (E) at ($(C.center) + (-\xdist, -\ydist)$) {E}; + \node [dag node] (F) at ($(C.center) + (\xdist, -\ydist)$) {F}; + \node [dag node] (D) at ($(C.center) + (2 * \xdist, 0)$) {D}; + + \foreach \src/\dest in {A/C, B/C, B/D, C/F, D/F, C/E} + \path [edge] (\src) -- (\dest); + + \foreach \i/\Node in {3/A, 3/B, 4/A, 4/B, 5/A, 5/E} + \node<\i> [good dag node] at ($(\Node.center)$) {\Node}; - \foreach \i/\src/\dest in {4/A/C, 4/B/C} - \path<\i> [selected edge] (\src) -- (\dest); - - \foreach \i/\Cap in {3/$\langle A \mid \emptyset \mid B \rangle$, - 4/$\neg \langle A \mid F \mid B \rangle$, - 5/$\langle A \mid C \mid E \rangle$ - } - \node<\i> at ($(C.center) + (-3*\xdist, 0)$) {\Cap}; - - \end{tikzpicture} - \end{center} - } + \foreach \i/\Node in {4/C, 5/C} + \node<\i> [bad dag node] at ($(\Node.center)$) {\Node}; + + \foreach \i/\src/\dest in {4/A/C, 4/B/C} + \path<\i> [selected edge] (\src) -- (\dest); + + \foreach \i/\Cap in {3/$\langle A \mid \emptyset \mid B \rangle$, + 4/$\neg \langle A \mid F \mid B \rangle$, + 5/$\langle A \mid C \mid E \rangle$ + } + \node<\i> at ($(C.center) + (-3*\xdist, 0)$) {\Cap}; + + \end{tikzpicture} + \end{center} + } \end{frame} \begin{frame} - \frametitle{Bayesnetze} - - \begin{theorem}[Unabhängigkeiten in Bayes-Netzen] - Zufallsvariablen $X$ und $Y$ sind in einem Bayes-Netz \alert{bedingt unabhängig} unter $E$ wenn $\langle X \mid E \mid Y \rangle$.\\ - Speziell ist \alert{jeder Knoten} bedingt unabhängig von - \begin{itemize} - \item \alert{allen nicht-Nachfahren} gegeben seine \alert{Eltern} - \item \alert{allen Knoten} gegeben seine \alert{Markov-Einbettung} - \end{itemize} - \end{theorem} - - \begin{definition}[Markov-Einbettung] - Die \alert{Markov-Einbettung} (Markov blanket) eines Knotens ist die Menge all seiner \alert{Eltern}, \alert{Kinder} und den \alert{Eltern aller Kinder}. - \end{definition} + \frametitle{Bayesnetze} + + \begin{theorem}[Unabhängigkeiten in Bayes-Netzen] + Zufallsvariablen $X$ und $Y$ sind in einem Bayes-Netz \alert{bedingt unabhängig} unter $E$ wenn $\langle X \mid E \mid Y \rangle$.\\ + Speziell ist \alert{jeder Knoten} bedingt unabhängig von + \begin{itemize} + \item \alert{allen nicht-Nachfahren} gegeben seine \alert{Eltern} + \item \alert{allen Knoten} gegeben seine \alert{Markov-Einbettung} + \end{itemize} + \end{theorem} + + \begin{definition}[Markov-Einbettung] + Die \alert{Markov-Einbettung} (Markov blanket) eines Knotens ist die Menge all seiner \alert{Eltern}, \alert{Kinder} und den \alert{Eltern aller Kinder}. + \end{definition} \end{frame} \begin{frame} - \frametitle{Bayesnetze} + \frametitle{Bayesnetze} + + \begin{tikzpicture} + \node [net node] (sport) {Sport}; + \node [net node] (kaufen) [left of = sport] {Kaufen}; + \node [net node] (lernen) [right of = sport] {Lernen}; + + \node [net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; + \node [net node] (regen) at ($0.5*(sport.center) + 0.5*(kaufen.center) + (0,\netvspace)$) {Regen}; + + \foreach \src/\dest in {regen/kaufen, regen/sport, + sport/gewissen, lernen/gewissen} + \path [edge] (\src) -- (\dest); + + \only<2> { + \node [net cpt] at ($(regen.center)-(5em,0)$) + {\begin{tabu}{c} + $\Pr[R]$ \\ \tabucline{-} + $0.1$ \\ + \end{tabu}}; - \begin{tikzpicture} - \node [net node] (sport) {Sport}; - \node [net node] (kaufen) [left of = sport] {Kaufen}; - \node [net node] (lernen) [right of = sport] {Lernen}; - - \node [net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; - \node [net node] (regen) at ($0.5*(sport.center) + 0.5*(kaufen.center) + (0,\netvspace)$) {Regen}; - - \foreach \src/\dest in {regen/kaufen, regen/sport, - sport/gewissen, lernen/gewissen} - \path [edge] (\src) -- (\dest); - - \only<2> { - \node [net cpt] at ($(regen.center)-(5em,0)$) - {\begin{tabu}{c} - $\Pr[R]$ \\ \tabucline{-} - $0.1$ \\ - \end{tabu}}; - - \node [net cpt] at ($(lernen.center)+(0,3em)$) - {\begin{tabu}{c} - $\Pr[L]$ \\ \tabucline{-} - $0.2$ \\ - \end{tabu}}; - - \node [net cpt] at ($(kaufen.center)-(0,3em)$) - {\begin{tabu}{c|c} - R & $\Pr[K]$ \\ \tabucline{-} - F & $0.5$ \\ - T & $0.25$ \\ - \end{tabu}}; - - \node [net cpt] at ($(sport.center)-(2em,3em)$) - {\begin{tabu}{c|c} - R & $\Pr[S]$ \\ \tabucline{-} - F & $0.4$ \\ - T & $0.2$ \\ - \end{tabu}}; - - \node [net cpt] at ($(gewissen.center)+(7em,1.1em)$) - {\begin{tabu}{cc|c} - S & L & $\Pr[G]$ \\ \tabucline{-} - F & F & $0.8$ \\ - F & T & $0.25$ \\ - T & F & $0.5$ \\ - T & T & $0.1$ \\ - \end{tabu}}; - } - \end{tikzpicture} + \node [net cpt] at ($(lernen.center)+(0,3em)$) + {\begin{tabu}{c} + $\Pr[L]$ \\ \tabucline{-} + $0.2$ \\ + \end{tabu}}; + + \node [net cpt] at ($(kaufen.center)-(0,3em)$) + {\begin{tabu}{c|c} + R & $\Pr[K]$ \\ \tabucline{-} + F & $0.5$ \\ + T & $0.25$ \\ + \end{tabu}}; + + \node [net cpt] at ($(sport.center)-(2em,3em)$) + {\begin{tabu}{c|c} + R & $\Pr[S]$ \\ \tabucline{-} + F & $0.4$ \\ + T & $0.2$ \\ + \end{tabu}}; + + \node [net cpt] at ($(gewissen.center)+(7em,1.1em)$) + {\begin{tabu}{cc|c} + S & L & $\Pr[G]$ \\ \tabucline{-} + F & F & $0.8$ \\ + F & T & $0.25$ \\ + T & F & $0.5$ \\ + T & T & $0.1$ \\ + \end{tabu}}; + } + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Gemeinsame Verteilung} - - \begin{theorem}[Gemeinsame Verteilung] - Für einen Eintrag $\Pr[x_1,\ldots,x_n]$ in der gemeinsamen Verteilung eines Bayesnetzes gilt - $$\Pr[x_1,\ldots,x_n] = \prod_{i=1}^n \Pr[x_i \mid \mathsf{parents}(X_i)]$$ - \end{theorem} + \frametitle{Gemeinsame Verteilung} + + \begin{theorem}[Gemeinsame Verteilung] + Für einen Eintrag $\Pr[x_1,\ldots,x_n]$ in der gemeinsamen Verteilung eines Bayesnetzes gilt + $$\Pr[x_1,\ldots,x_n] = \prod_{i=1}^n \Pr[x_i \mid \mathsf{parents}(X_i)]$$ + \end{theorem} - Was ist die Wahrscheinlichkeit, dass ich ein \alert{schlechtes Gewissen} bei \alert{schönem Wetter} habe, obwohl ich \alert{Sport gemacht} habe nachdem ich \alert{einkaufen} war? - \begin{align*} - \Pr[G, S, \neg L, K, \neg R] &= \Pr[G \mid S, \neg L, K, \neg R] \cdot \Pr[S \mid \neg L, K, \neg R] \cdot \ldots\\ - &= \Pr[G \mid S, \neg L] \cdot \Pr[S \mid \neg R] \\&\qquad \cdot Pr[\neg L] \cdot \Pr[K \mid \neg R] \cdot \Pr[\neg R]\\ - &= 0.5 \cdot 0.8 \cdot 0.4 \cdot 0.5 \cdot 0.9 = 0.072 - \end{align*} + Was ist die Wahrscheinlichkeit, dass ich ein \alert{schlechtes Gewissen} bei \alert{schönem Wetter} habe, obwohl ich \alert{Sport gemacht} habe nachdem ich \alert{einkaufen} war? + \begin{align*} + \Pr[G, S, \neg L, K, \neg R] &= \Pr[G \mid S, \neg L, K, \neg R] \cdot \Pr[S \mid \neg L, K, \neg R] \cdot \ldots\\ + &= \Pr[G \mid S, \neg L] \cdot \Pr[S \mid \neg R] \\&\qquad \cdot Pr[\neg L] \cdot \Pr[K \mid \neg R] \cdot \Pr[\neg R]\\ + &= 0.5 \cdot 0.8 \cdot 0.4 \cdot 0.5 \cdot 0.9 = 0.072 + \end{align*} \end{frame} \begin{frame}[t] - \frametitle{Konstruktion} - \begin{block}{} - Wie konstruiert man zu einer Domäne ein möglichst \alert{kompaktes}, \alert{lokal strukturiertes} und \alert{natürliches} Netz? - \end{block} - - \begin{itemize} - \item \alert{Expertenwissen} notwendig - \vfill - \item Knoten modellieren \alert{quantifizierbare} Ereignisse - \begin{itemize} - \item Unbekanntes in Verteilungen - \item Einfachheit vs. Genauigkeit - \end{itemize} - \vspace{.2em} - \item \alert{Lokale Struktur} schaffen - \begin{itemize} - \item Direkte Einflüsse - \item Kleine Einflüsse ignorieren - \end{itemize} - \vspace{.2em} - \item \alert{Kausale Reihenfolge} abbilden - \end{itemize} + \frametitle{Konstruktion} + \begin{block}{} + Wie konstruiert man zu einer Domäne ein möglichst \alert{kompaktes}, \alert{lokal strukturiertes} und \alert{natürliches} Netz? + \end{block} + + \begin{itemize} + \item \alert{Expertenwissen} notwendig + \vfill + \item Knoten modellieren \alert{quantifizierbare} Ereignisse + \begin{itemize} + \item Unbekanntes in Verteilungen + \item Einfachheit vs. Genauigkeit + \end{itemize} + \vspace{.2em} + \item \alert{Lokale Struktur} schaffen + \begin{itemize} + \item Direkte Einflüsse + \item Kleine Einflüsse ignorieren + \end{itemize} + \vspace{.2em} + \item \alert{Kausale Reihenfolge} abbilden + \end{itemize} \end{frame} \begin{frame} - \frametitle{Knotenrepräsentation} - - \begin{itemize} - \item Grundsätzlich \alert{beliebige} Verteilungen möglich - \item Abwägung zwischen \alert{effizient} und \alert{exakt} - \vspace{1em} - \item Logische Verknüpfungen - \item \alert{Kanonische} Verteilungen - \end{itemize} + \frametitle{Knotenrepräsentation} + + \begin{itemize} + \item Grundsätzlich \alert{beliebige} Verteilungen möglich + \item Abwägung zwischen \alert{effizient} und \alert{exakt} + \vspace{1em} + \item Logische Verknüpfungen + \item \alert{Kanonische} Verteilungen + \end{itemize} - \uncover<2>{ - \begin{example}[Noisy Or] - Ein Patient hat Fieber, wenn er eine Erkältung oder Grippe hat. Hat er aber eine Krankheit, könnte er auch kein Fieber haben. - $$\Pr[\neg B \mid E, \neg G] = 0.6,\quad \Pr[\neg B \mid \neg E, G] = 0.2$$ - - \begin{center} - \begin{tabu}{|cc|[1.2pt]cc||cc|[1.2pt]cc|} - \hline - E & G & $\Pr[B]$ & $\Pr[\neg B]$ & E & G & $\Pr[B]$ & $\Pr[\neg B]$ \\ - \tabucline[1.2pt]{-} - F & F & 0 & 1 & T & F & 0.4 & \alert{0.6} \\ - \hline - F & T & 0.8 & \alert{0.2} & T & T & 0.88 & 0.12 \\ - \hline - \end{tabu} - \end{center} - \end{example} - } + \uncover<2>{ + \begin{example}[Noisy Or] + Ein Patient hat Fieber, wenn er eine Erkältung oder Grippe hat. Hat er aber eine Krankheit, könnte er auch kein Fieber haben. + $$\Pr[\neg B \mid E, \neg G] = 0.6,\quad \Pr[\neg B \mid \neg E, G] = 0.2$$ + + \begin{center} + \begin{tabu}{|cc|[1.2pt]cc||cc|[1.2pt]cc|} + \hline + E & G & $\Pr[B]$ & $\Pr[\neg B]$ & E & G & $\Pr[B]$ & $\Pr[\neg B]$ \\ + \tabucline[1.2pt]{-} + F & F & 0 & 1 & T & F & 0.4 & \alert{0.6} \\ + \hline + F & T & 0.8 & \alert{0.2} & T & T & 0.88 & 0.12 \\ + \hline + \end{tabu} + \end{center} + \end{example} + } \end{frame} \begin{frame} - \frametitle{Hotdogs} - \begin{example}[Hotdog zum Mittagessen] - Im MI-Gebäude gibt es jeden Dienstag Hotdogs. Um genau 12 Uhr werfe ich einen Blick auf die \alert{Schlange} und entscheide allein anhand ihrer Länge ob ich auf mein Mittagessen \alert{verzichte}.\\ - Die Länge der Schlange ist abhängig davon, ob es in der \alert{Mensa} akzeptables Essen gibt und wieviele Studenten \alert{verschlafen} haben. - \end{example} - - \begin{itemize} - \item Der Anteil der schlafenden Studenten ist \alert{gleichverteilt}. - \item Die Länge der Schlange ist \alert{normalverteilt}. - \end{itemize} + \frametitle{Hotdogs} + \begin{example}[Hotdog zum Mittagessen] + Im MI-Gebäude gibt es jeden Dienstag Hotdogs. Um genau 12 Uhr werfe ich einen Blick auf die \alert{Schlange} und entscheide allein anhand ihrer Länge ob ich auf mein Mittagessen \alert{verzichte}.\\ + Die Länge der Schlange ist abhängig davon, ob es in der \alert{Mensa} akzeptables Essen gibt und wieviele Studenten \alert{verschlafen} haben. + \end{example} + + \begin{itemize} + \item Der Anteil der schlafenden Studenten ist \alert{gleichverteilt}. + \item Die Länge der Schlange ist \alert{normalverteilt}. + \end{itemize} \end{frame} \begin{frame} - \frametitle{Hotdogs} - - \begin{tikzpicture} - \node [net node] (schlange) {Schlange}; - \node [net node] (mensa) at ($(schlange.center) + (-4em,\netvspace)$) {Mensa}; - \node [net node] (schlafen) at ($(schlange.center) + (4em,\netvspace)$) {Schlafen}; - - \node [net node] (hotdog) at ($(schlange.center) - (0,\netvspace)$) {Hotdog}; - - \foreach \src/\dest in {mensa/schlange, schlafen/schlange, - schlange/hotdog} - \path [edge] (\src) -- (\dest); - - \node [net cpt] at ($(schlafen.center)-(-3em,2.2em)$) - {$V \sim GV(0,100)$}; - - \node [net cpt] at ($(mensa.center)-(1em,3em)$) - {\begin{tabu}{c} - $\Pr[M]$ \\ \tabucline{-} - $0.4$ \\ - \end{tabu}}; - - \node [net cpt] at ($(schlange.center)-(5em,3em)$) - {\begin{tabu}{c|c} - M & $S$ \\ \tabucline{-} - F & $S \sim N(\mu_t(v),\sigma_t)$ \\ - T & $S \sim N(\mu_f(v),\sigma_f)$ \\ - \end{tabu}}; - - \node [net cpt] at ($(hotdog.center)-(-1em,2.2em)$) - {$\Pr[h \mid S = s] = \Phi(\frac{-s + \mu}{\sigma})$}; - - \only<2> { - \def\sdiv{3.2} - \begin{axis}[label style=sloped,xlabel=Schlange,ylabel=\% schlafend, - xshift=.225\textwidth,yshift=-6em,width=0.55\textwidth, - colormap={tum}{color(0cm)=(tumblue); color(1cm)=(yellow); - color(2cm)=(tumorange); color(3cm)=(tumred)}] - \addplot3[surf,domain=0:40,domain y=0:100] - {0.6 * exp(-0.5*((x-(30-0.25*y))/\sdiv)^2 )/(2.5*\sdiv) + - 0.4 * exp(-0.5*((x-(15-0.1*y))/\sdiv)^2 )/(2.5*\sdiv)}; - \end{axis} - - \begin{axis}[ticks=none,very thick, - width=0.3\textwidth, yshift=-10em, xshift=-8.5em] - \addplot[domain=0:10,smooth] - {1/(1+ exp(-2*((-x+5)/1.3)))}; - - \end{axis} - } - \end{tikzpicture} + \frametitle{Hotdogs} + + \begin{tikzpicture} + \node [net node] (schlange) {Schlange}; + \node [net node] (mensa) at ($(schlange.center) + (-4em,\netvspace)$) {Mensa}; + \node [net node] (schlafen) at ($(schlange.center) + (4em,\netvspace)$) {Schlafen}; + + \node [net node] (hotdog) at ($(schlange.center) - (0,\netvspace)$) {Hotdog}; + + \foreach \src/\dest in {mensa/schlange, schlafen/schlange, + schlange/hotdog} + \path [edge] (\src) -- (\dest); + + \node [net cpt] at ($(schlafen.center)-(-3em,2.2em)$) + {$V \sim GV(0,100)$}; + + \node [net cpt] at ($(mensa.center)-(1em,3em)$) + {\begin{tabu}{c} + $\Pr[M]$ \\ \tabucline{-} + $0.4$ \\ + \end{tabu}}; + + \node [net cpt] at ($(schlange.center)-(5em,3em)$) + {\begin{tabu}{c|c} + M & $S$ \\ \tabucline{-} + F & $S \sim N(\mu_t(v),\sigma_t)$ \\ + T & $S \sim N(\mu_f(v),\sigma_f)$ \\ + \end{tabu}}; + + \node [net cpt] at ($(hotdog.center)-(-1em,2.2em)$) + {$\Pr[h \mid S = s] = \Phi(\frac{-s + \mu}{\sigma})$}; + + \only<2> { + \def\sdiv{3.2} + \begin{axis}[label style=sloped,xlabel=Schlange,ylabel=\% schlafend, + xshift=.225\textwidth,yshift=-6em,width=0.55\textwidth, + colormap={tum}{color(0cm)=(tumblue); color(1cm)=(yellow); + color(2cm)=(tumorange); color(3cm)=(tumred)}] + \addplot3[surf,domain=0:40,domain y=0:100] + {0.6 * exp(-0.5*((x-(30-0.25*y))/\sdiv)^2 )/(2.5*\sdiv) + + 0.4 * exp(-0.5*((x-(15-0.1*y))/\sdiv)^2 )/(2.5*\sdiv)}; + \end{axis} + + \begin{axis}[ticks=none,very thick, + width=0.3\textwidth, yshift=-10em, xshift=-8.5em] + \addplot[domain=0:10,smooth] + {1/(1+ exp(-2*((-x+5)/1.3)))}; + + \end{axis} + } + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Inferenz} - - \begin{definition}[Inferenz] - Für ein Netz mit Knotenmenge $K = \{X\} \cup E \cup Y$ soll die \alert{Wahrscheinlichkeit} ermittelt werden, dass eine \alert{Variable} $X$ einen Wert annimmt, unter der Bedingung, dass für die \alert{Evidenzvariablen} $E$ die Werte $e$ \alert{beobachtet} werden und die \alert{versteckten Variablen} $Y$ unbekannt sind. - $$\Pr[X \mid e] = \Pr[X = x \mid E_1 = e_1, \ldots, E_n = e_n] = \;?$$ - \end{definition} - - Wenn ich abends ein \alert{schlechtes Gewissen} habe, wie groß ist die Wahrscheinlichkeit, dass ich \alert{nicht gelernt} habe? - $$\Pr[\neg L \mid G] \approx 0.936$$ + \frametitle{Inferenz} + + \begin{definition}[Inferenz] + Für ein Netz mit Knotenmenge $K = \{X\} \cup E \cup Y$ soll die \alert{Wahrscheinlichkeit} ermittelt werden, dass eine \alert{Variable} $X$ einen Wert annimmt, unter der Bedingung, dass für die \alert{Evidenzvariablen} $E$ die Werte $e$ \alert{beobachtet} werden und die \alert{versteckten Variablen} $Y$ unbekannt sind. + $$\Pr[X \mid e] = \Pr[X = x \mid E_1 = e_1, \ldots, E_n = e_n] = \;?$$ + \end{definition} + + Wenn ich abends ein \alert{schlechtes Gewissen} habe, wie groß ist die Wahrscheinlichkeit, dass ich \alert{nicht gelernt} habe? + $$\Pr[\neg L \mid G] \approx 0.936$$ \end{frame} \begin{frame} - \frametitle{Inferenz durch Aufzählen} + \frametitle{Inferenz durch Aufzählen} + + \only<1>{ + \begin{example}[Bekämpfung des schlechten Gewissens] + Wenn ich ein \alert{schlechtes Gewissen} habe werde ich unglücklich. Unglück kann man bekämpfen, indem man sich mit einem \alert{Film} ablenkt oder passend zur Jahreszeit Schokolade aus dem \alert{Adventskalender} isst.\\ + Zur Vereinfachung soll der Einfluss des Regens nun \alert{nicht mehr} beachtet werden. + \end{example} + } + + \only<2>{ + \begin{center} + \begin{tikzpicture} + \node [net node] (sport) {Sport}; + \node [net node] (lernen) [right of = sport] {Lernen}; + + \node [net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; + \node [net node] (film) at ($(sport.center) - (0,2*\netvspace)$) {Film}; + \node [net node] (advent) at ($(lernen.center) - (0,2*\netvspace)$) {Advent}; + + \foreach \src/\dest in {sport/gewissen, lernen/gewissen, + gewissen/film, gewissen/advent} + \path [edge] (\src) -- (\dest); + + + \node [net cpt] at ($(lernen.center)+(6em,0)$) + {\begin{tabu}{c} + $\Pr[L]$ \\ \tabucline{-} + $0.2$ \\ + \end{tabu}}; - \only<1>{ - \begin{example}[Bekämpfung des schlechten Gewissens] - Wenn ich ein \alert{schlechtes Gewissen} habe werde ich unglücklich. Unglück kann man bekämpfen, indem man sich mit einem \alert{Film} ablenkt oder passend zur Jahreszeit Schokolade aus dem \alert{Adventskalender} isst.\\ - Zur Vereinfachung soll der Einfluss des Regens nun \alert{nicht mehr} beachtet werden. - \end{example} - } - - \only<2>{ - \begin{center} - \begin{tikzpicture} - \node [net node] (sport) {Sport}; - \node [net node] (lernen) [right of = sport] {Lernen}; - - \node [net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; - \node [net node] (film) at ($(sport.center) - (0,2*\netvspace)$) {Film}; - \node [net node] (advent) at ($(lernen.center) - (0,2*\netvspace)$) {Advent}; - - \foreach \src/\dest in {sport/gewissen, lernen/gewissen, - gewissen/film, gewissen/advent} - \path [edge] (\src) -- (\dest); - - - \node [net cpt] at ($(lernen.center)+(6em,0)$) - {\begin{tabu}{c} - $\Pr[L]$ \\ \tabucline{-} - $0.2$ \\ - \end{tabu}}; - - \node [net cpt] at ($(film.center)-(7em,0)$) - {\begin{tabu}{c|c} - G & $\Pr[M]$ \\ \tabucline{-} - F & $0.4$ \\ - T & $0.75$ \\ - \end{tabu}}; - - \node [net cpt] at ($(advent.center)+(7em,0)$) - {\begin{tabu}{c|c} - G & $\Pr[A]$ \\ \tabucline{-} - F & $0.6$ \\ - T & $0.9$ \\ - \end{tabu}}; - - \node [net cpt] at ($(sport.center)-(6em,0)$) - {\begin{tabu}{c} - $\Pr[S]$ \\ \tabucline{-} - $0.4$ \\ - \end{tabu}}; - - \node [net cpt] at ($(gewissen.center)+(7em,0)$) - {\begin{tabu}{cc|c} - S & L & $\Pr[G]$ \\ \tabucline{-} - F & F & $0.8$ \\ - F & T & $0.25$ \\ - T & F & $0.5$ \\ - T & T & $0.1$ \\ - \end{tabu}}; - \end{tikzpicture} - \end{center} - } + \node [net cpt] at ($(film.center)-(7em,0)$) + {\begin{tabu}{c|c} + G & $\Pr[M]$ \\ \tabucline{-} + F & $0.4$ \\ + T & $0.75$ \\ + \end{tabu}}; + + \node [net cpt] at ($(advent.center)+(7em,0)$) + {\begin{tabu}{c|c} + G & $\Pr[A]$ \\ \tabucline{-} + F & $0.6$ \\ + T & $0.9$ \\ + \end{tabu}}; + + \node [net cpt] at ($(sport.center)-(6em,0)$) + {\begin{tabu}{c} + $\Pr[S]$ \\ \tabucline{-} + $0.4$ \\ + \end{tabu}}; + + \node [net cpt] at ($(gewissen.center)+(7em,0)$) + {\begin{tabu}{cc|c} + S & L & $\Pr[G]$ \\ \tabucline{-} + F & F & $0.8$ \\ + F & T & $0.25$ \\ + T & F & $0.5$ \\ + T & T & $0.1$ \\ + \end{tabu}}; + \end{tikzpicture} + \end{center} + } \end{frame} \begin{frame} - \frametitle{Inferenz durch Aufzählen} - - \begin{example} - Wie groß ist die Wahrscheinlichkeit, dass ich \alert{ohne Sport} einen \alert{Film} schaue und dabei \alert{Schokolade} esse? - \end{example} - Aus dem Satz der totalen Wahrscheinlichkeit erhalten wir - $$\Pr[X \mid e] = \alpha \Pr[X, e] = \alpha \sum_y \Pr[X, e, y]$$ - also - \begin{align*} - \Pr[\neg S \mid M, A] &= \alpha \sum_g \sum_l \Pr[\neg S, M, A, g, l]\\ - &=\alpha \cdot \Pr[\neg S] \cdot \sum_l \Pr[l]\\ - &\qquad \cdot \sum_g \Pr[g \mid \neg S, l] \cdot \Pr[M \mid g] \cdot \Pr[A \mid g]\\ - &\approx 0.585 - \end{align*} + \frametitle{Inferenz durch Aufzählen} + + \begin{example} + Wie groß ist die Wahrscheinlichkeit, dass ich \alert{ohne Sport} einen \alert{Film} schaue und dabei \alert{Schokolade} esse? + \end{example} + Aus dem Satz der totalen Wahrscheinlichkeit erhalten wir + $$\Pr[X \mid e] = \alpha \Pr[X, e] = \alpha \sum_y \Pr[X, e, y]$$ + also + \begin{align*} + \Pr[\neg S \mid M, A] &= \alpha \sum_g \sum_l \Pr[\neg S, M, A, g, l]\\ + &=\alpha \cdot \Pr[\neg S] \cdot \sum_l \Pr[l]\\ + &\qquad \cdot \sum_g \Pr[g \mid \neg S, l] \cdot \Pr[M \mid g] \cdot \Pr[A \mid g]\\ + &\approx 0.585 + \end{align*} \end{frame} \begin{frame}[t] - \frametitle{Berechnungsbaum} - - \begin{tikzpicture}[grow=down] - \tikzstyle{every node} = [font=\scriptsize] - \tikzstyle{op} = [circular node] - \tikzstyle{edge from parent} = [edge] - - \tikzstyle{level 2} = [sibling distance = 14em] - \tikzstyle{level 3} = [sibling distance = 7em] - - - \node[op] {} - child { - node[op] {+} - child { - node[op] {+} - child { - node[op] {} - child { - node[op] {} - child { - node [op] {} - edge from parent - node[left] {$\Pr[A \mid g]$} - } - edge from parent - node[left] {$\Pr[M \mid g]$} - } - edge from parent - node[left] {$\Pr[g \mid \neg S, l]$} + \frametitle{Berechnungsbaum} + + \begin{tikzpicture}[grow=down] + \tikzstyle{every node} = [font=\scriptsize] + \tikzstyle{op} = [circular node] + \tikzstyle{edge from parent} = [edge] + + \tikzstyle{level 2} = [sibling distance = 14em] + \tikzstyle{level 3} = [sibling distance = 7em] + + + \node[op] {} + child { + node[op] {+} + child { + node[op] {+} + child { + node[op] {} + child { + node[op] {} + child { + node [op] {} + edge from parent + node[left] {$\Pr[A \mid g]$} + } + edge from parent + node[left] {$\Pr[M \mid g]$} + } + edge from parent + node[left] {$\Pr[g \mid \neg S, l]$} + } + child { + node[op] {} + child { + node[op] {} + child { + node [op] {} + edge from parent + node[left] {$\Pr[A \mid \neg g]$} + } + edge from parent + node[left] {$\Pr[M \mid \neg g]$} + } + edge from parent + node[right] {$\Pr[\neg g \mid \neg S, l]$} + } + edge from parent + node[above left] {$\Pr[l]$} } - child { - node[op] {} - child { - node[op] {} - child { - node [op] {} - edge from parent - node[left] {$\Pr[A \mid \neg g]$} - } - edge from parent - node[left] {$\Pr[M \mid \neg g]$} - } - edge from parent - node[right] {$\Pr[\neg g \mid \neg S, l]$} - } + child { + node[op] {+} + child { + node[op] {} + child { + node[op] {} + child { + node [op] {} + edge from parent + node[left] {$\Pr[A \mid g]$} + } + edge from parent + node[left] {$\Pr[M \mid g]$} + } + edge from parent + node[left] {$\Pr[g \mid \neg S, \neg l]$} + } + child { + node[op] {} + child { + node[op] {} + child { + node [op] {} + edge from parent + node[left] {$\Pr[A \mid \neg g]$} + } + edge from parent + node[left] {$\Pr[M \mid \neg g]$} + } + edge from parent + node[right] {$\Pr[\neg g \mid \neg S, \neg l]$} + } + edge from parent + node[above right] {$\Pr[\neg l]$} + } edge from parent - node[above left] {$\Pr[l]$} - } - child { - node[op] {+} - child { - node[op] {} - child { - node[op] {} - child { - node [op] {} - edge from parent - node[left] {$\Pr[A \mid g]$} - } - edge from parent - node[left] {$\Pr[M \mid g]$} - } - edge from parent - node[left] {$\Pr[g \mid \neg S, \neg l]$} - } - child { - node[op] {} - child { - node[op] {} - child { - node [op] {} - edge from parent - node[left] {$\Pr[A \mid \neg g]$} - } - edge from parent - node[left] {$\Pr[M \mid \neg g]$} - } - edge from parent - node[right] {$\Pr[\neg g \mid \neg S, \neg l]$} - } - edge from parent - node[above right] {$\Pr[\neg l]$} - } - edge from parent - node[left] {$\Pr[\neg S]$} - }; - \end{tikzpicture} + node[left] {$\Pr[\neg S]$} + }; + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Alternative Algorithmen} - - \begin{itemize} - \item Inferenz durch Aufzählen hat \alert{exponentielle} Laufzeit - \item Mit dynamischer Programmierung \alert{linear} auf Polytrees - \item Aber: Exakte Interferenz ist \alert{NP-vollständig} - \end{itemize} - - \vspace{3em} - Alternative: \alert{Approximative Algorithmen} - \begin{itemize} - \item Direct/Rejection Sampling - \item Likelihood weighting - \item Markov chain Monte Carlo (MCMC) - \end{itemize} + \frametitle{Alternative Algorithmen} + + \begin{itemize} + \item Inferenz durch Aufzählen hat \alert{exponentielle} Laufzeit + \item Mit dynamischer Programmierung \alert{linear} auf Polytrees + \item Aber: Exakte Interferenz ist \alert{NP-vollständig} + \end{itemize} + + \vspace{3em} + Alternative: \alert{Approximative Algorithmen} + \begin{itemize} + \item Direct/Rejection Sampling + \item Likelihood weighting + \item Markov chain Monte Carlo (MCMC) + \end{itemize} \end{frame} \begin{frame} - \frametitle{Anwendungen} - \begin{itemize} - \item Nachmittagsplanung - \vspace{.2em} - \item Krankheitsdiagnose - \vspace{.2em} - \item Kriminalitätsbekämpfung - \vspace{.2em} - \item Genanalyse - \vspace{.2em} - \item Entscheidungsfindung - \end{itemize} + \frametitle{Anwendungen} + \begin{itemize} + \item Nachmittagsplanung + \vspace{.2em} + \item Krankheitsdiagnose + \vspace{.2em} + \item Kriminalitätsbekämpfung + \vspace{.2em} + \item Genanalyse + \vspace{.2em} + \item Entscheidungsfindung + \end{itemize} \end{frame} \begin{frame} - \frametitle{Zusammenfassung} - - Bayesnetze \ldots - \begin{itemize} - \item repräsentieren \alert{mehrdimensionale Zufallsvariablen} - \item haben eine kompakte Darstellung - \item benötigen \alert{Expertenwissen} - \item modellieren \alert{Kausalitätszusammenhänge} - \item sparen Speicher - \item erlauben Interferenz - \end{itemize} -\end{frame} \end{document} + \frametitle{Zusammenfassung} + + Bayesnetze \ldots + \begin{itemize} + \item repräsentieren \alert{mehrdimensionale Zufallsvariablen} + \item haben eine kompakte Darstellung + \item benötigen \alert{Expertenwissen} + \item modellieren \alert{Kausalitätszusammenhänge} + \item sparen Speicher + \item erlauben Interferenz + \end{itemize} +\end{frame} +\end{document}
--- a/planarity/presentation.tex Tue Dec 11 21:43:57 2012 +0100 +++ b/planarity/presentation.tex Thu Dec 13 19:36:52 2012 +0100 @@ -30,15 +30,15 @@ \newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}} \newenvironment{changemargin}[2]{% - \begin{list}{}{% - \setlength{\topsep}{0pt}% - \setlength{\leftmargin}{#1}% - \setlength{\rightmargin}{#2}% - \setlength{\listparindent}{\parindent}% - \setlength{\itemindent}{\parindent}% - \setlength{\parsep}{\parskip}% - }% - \item[]}{\end{list}} + \begin{list}{}{% + \setlength{\topsep}{0pt}% + \setlength{\leftmargin}{#1}% + \setlength{\rightmargin}{#2}% + \setlength{\listparindent}{\parindent}% + \setlength{\itemindent}{\parindent}% + \setlength{\parsep}{\parskip}% + }% +\item[]}{\end{list}} \usetikzlibrary{shapes.geometric} @@ -78,7 +78,7 @@ \begin{document} \begin{frame} - \titlepage + \titlepage \end{frame} % Inhaltsverzeichnis @@ -88,860 +88,860 @@ %\end{frame} \begin{frame} - \frametitle{Grundlegendes} - \begin{itemize} - \item<1-> Graph $G$, Knotenmenge $V$, Kantenmenge $E$ - \item<1-> $G = (V, E)$ - \item<1-> $E \subseteq V^2$, $|V| = n$, $|E| = m$ - \vspace{1em} - \item<2-> \alert{einfach}: Keine Schleifen oder Mehrfachkanten - \item<2-> \alert{zusammenhängend}: Es existiert ein Pfad von jedem Knoten zu jedem Knoten - \item<2-> \alert{Baum}: Zyklenfreier zusammenhängender Graph - \item<2-> \alert{$k$-zusammenhängend}: Zusammenhängend nach Entfernen von $k-1$ Knoten - \end{itemize} + \frametitle{Grundlegendes} + \begin{itemize} + \item<1-> Graph $G$, Knotenmenge $V$, Kantenmenge $E$ + \item<1-> $G = (V, E)$ + \item<1-> $E \subseteq V^2$, $|V| = n$, $|E| = m$ + \vspace{1em} + \item<2-> \alert{einfach}: Keine Schleifen oder Mehrfachkanten + \item<2-> \alert{zusammenhängend}: Es existiert ein Pfad von jedem Knoten zu jedem Knoten + \item<2-> \alert{Baum}: Zyklenfreier zusammenhängender Graph + \item<2-> \alert{$k$-zusammenhängend}: Zusammenhängend nach Entfernen von $k-1$ Knoten + \end{itemize} \end{frame} \begin{frame} - \frametitle{Grundlegendes} - \begin{columns}[T] - \begin{column}{.5\textwidth} - \begin{itemize} - \item<2> Artikulationsknoten \\(\emph{cut vertex}) - \item<3> Block - \item<4> Pfad - \item<5> Zyklus - \item<6> Facette (\emph{face}) - \item<7> Bipartitheit - \end{itemize} - \end{column} - \begin{column}{.5\textwidth} -\begin{figure} -\begin{tikzpicture}[auto] - \useasboundingbox (-2, 0) rectangle (7,7); + \frametitle{Grundlegendes} + \begin{columns}[T] + \begin{column}{.5\textwidth} + \begin{itemize} + \item<2> Artikulationsknoten \\(\emph{cut vertex}) + \item<3> Block + \item<4> Pfad + \item<5> Zyklus + \item<6> Facette (\emph{face}) + \item<7> Bipartitheit + \end{itemize} + \end{column} + \begin{column}{.5\textwidth} + \begin{figure} + \begin{tikzpicture}[auto] + \useasboundingbox (-2, 0) rectangle (7,7); + + \foreach \pos/\name in {{(0,0)/a}, {(0,1.5)/b}, {(2,0)/c},{(2,1.5)/d}, + {(-2,2.5)/e}, + {(0,3.5)/f}, {(2,3.5)/g}, {(0,5)/h},{(2,5)/i}, + {(1,6.5)/k}} + \node[vertex] (\name) at \pos {}; - \foreach \pos/\name in {{(0,0)/a}, {(0,1.5)/b}, {(2,0)/c},{(2,1.5)/d}, - {(-2,2.5)/e}, - {(0,3.5)/f}, {(2,3.5)/g}, {(0,5)/h},{(2,5)/i}, - {(1,6.5)/k}} - \node[vertex] (\name) at \pos {}; - - \foreach \source/ \dest in {a/b, a/c, c/d, b/d, - b/e, e/f, - f/g, f/h, h/i, g/i, h/k} - \path[edge] (\source) -- (\dest); - \path[edge] (g) .. controls (3, 5.5) .. (k); - - \foreach \vertex / \fr in {e/2, - f/3, g/3, h/3, i/3, k/3, - a/4, b/4, e/4, f/4, - a/5, b/5, c/5, d/5, - a/7, d/7, e/7, g/7, h/7 - } - \path<\fr> node[selected vertex] at (\vertex) {}; - - \begin{pgfonlayer}{background} - \foreach \source / \dest / \fr in { - f/g/3, f/h/3, h/i/3, g/i/3, h/k/3, - a/b/4, b/e/4, e/f/4, - a/b/5, b/d/5, c/d/5, c/a/5 - } - \path<\fr>[selected edge] (\source) -- (\dest); - \path<3>[selected edge] (g) .. controls (3, 5.5) .. (k); + \foreach \source/ \dest in {a/b, a/c, c/d, b/d, + b/e, e/f, + f/g, f/h, h/i, g/i, h/k} + \path[edge] (\source) -- (\dest); + \path[edge] (g) .. controls (3, 5.5) .. (k); + + \foreach \vertex / \fr in {e/2, + f/3, g/3, h/3, i/3, k/3, + a/4, b/4, e/4, f/4, + a/5, b/5, c/5, d/5, + a/7, d/7, e/7, g/7, h/7 + } + \path<\fr> node[selected vertex] at (\vertex) {}; - \fill<6>[red!50] (a.center) -- (b.center) -- (d.center) -- (c.center); - \draw<6> (1, 0.75) node {f}; - \end{pgfonlayer} -\end{tikzpicture} -\end{figure} -\vspace{1em} - \end{column} - \end{columns} + \begin{pgfonlayer}{background} + \foreach \source / \dest / \fr in { + f/g/3, f/h/3, h/i/3, g/i/3, h/k/3, + a/b/4, b/e/4, e/f/4, + a/b/5, b/d/5, c/d/5, c/a/5 + } + \path<\fr>[selected edge] (\source) -- (\dest); + \path<3>[selected edge] (g) .. controls (3, 5.5) .. (k); + + \fill<6>[red!50] (a.center) -- (b.center) -- (d.center) -- (c.center); + \draw<6> (1, 0.75) node {f}; + \end{pgfonlayer} + \end{tikzpicture} + \end{figure} + \vspace{1em} + \end{column} + \end{columns} \end{frame} \begin{frame} - \frametitle{Planarität} - \begin{itemize} - \item \alert{offene Jordankurve} - \vspace{0.2em} -\begin{figure} -\begin{tikzpicture} - \draw (0,0) .. controls (1,1) and (4,0.5) .. (3,1); - - \draw (4,0) .. controls (5,1) .. (6,0.3) .. controls (7,0.5) .. (7,1); - \draw (6,0.3) .. controls (8,-0.5) and (3,0) .. (6,0.3); -\end{tikzpicture} -\end{figure} - \vspace{1em} + \frametitle{Planarität} + \begin{itemize} + \item \alert{offene Jordankurve} + \vspace{0.2em} + \begin{figure} + \begin{tikzpicture} + \draw (0,0) .. controls (1,1) and (4,0.5) .. (3,1); - \item<2-> Eine \alert{Zeichnung} ordnet in $\R^2$ jedem Knoten Koordinaten und jeder Kante eine offene Jordankurve zu - \item<2-> \alert{äquivalent}: Gleiche Reihenfolge der Kanten an Knoten - \vspace{2em} - \item<2-> \alert{planar}: Keine sich überschneidenden Kurven - \end{itemize} + \draw (4,0) .. controls (5,1) .. (6,0.3) .. controls (7,0.5) .. (7,1); + \draw (6,0.3) .. controls (8,-0.5) and (3,0) .. (6,0.3); + \end{tikzpicture} + \end{figure} + \vspace{1em} + + \item<2-> Eine \alert{Zeichnung} ordnet in $\R^2$ jedem Knoten Koordinaten und jeder Kante eine offene Jordankurve zu + \item<2-> \alert{äquivalent}: Gleiche Reihenfolge der Kanten an Knoten + \vspace{2em} + \item<2-> \alert{planar}: Keine sich überschneidenden Kurven + \end{itemize} \end{frame} \begin{frame} - \frametitle{Charakterisierung} - - \begin{theorem} - Ein Graph ist genau dann planar wenn\ldots - \begin{itemize} - \item \alert{Kuratowski} (1930): er keinen Teilgraphen enthält der eine Unterteilung von $K_5$ oder $K_{3,3}$ ist. - \item \alert{Wagner} (1937): er nicht $K_5$ oder $K_{3,3}$ als Minoren enthält. - \end{itemize} - \end{theorem} + \frametitle{Charakterisierung} + + \begin{theorem} + Ein Graph ist genau dann planar wenn\ldots + \begin{itemize} + \item \alert{Kuratowski} (1930): er keinen Teilgraphen enthält der eine Unterteilung von $K_5$ oder $K_{3,3}$ ist. + \item \alert{Wagner} (1937): er nicht $K_5$ oder $K_{3,3}$ als Minoren enthält. + \end{itemize} + \end{theorem} - \begin{figure} - \begin{tikzpicture}[auto] - \foreach \pos/ \name in {{(0,1)/a}, {(1,1)/b}, {(2,1)/c},{(0,2)/d},{(1,2)/e},{(2,2)/f}, - {(4.164,1)/g}, {(5.464,1)/h}, {(5.626,1.986)/i},{(4.814,2.75)/j},{(4,1.986)/k}} - \node[small vertex] (\name) at \pos {}; - - \foreach \source/ \dest in {a/d, a/e, a/f, - b/d, b/e, b/f, - c/d, c/e, c/f, - g/h, g/i, g/j, g/k, - h/i, h/j, h/k, - i/j, i/k, - j/k} - \path[edge] (\source) -- (\dest); - - \node at (1,0) {$K_{3,3}$}; - \node at (4.814,0) {$K_5$}; - \end{tikzpicture} - \end{figure} + \begin{figure} + \begin{tikzpicture}[auto] + \foreach \pos/ \name in {{(0,1)/a}, {(1,1)/b}, {(2,1)/c},{(0,2)/d},{(1,2)/e},{(2,2)/f}, + {(4.164,1)/g}, {(5.464,1)/h}, {(5.626,1.986)/i},{(4.814,2.75)/j},{(4,1.986)/k}} + \node[small vertex] (\name) at \pos {}; + + \foreach \source/ \dest in {a/d, a/e, a/f, + b/d, b/e, b/f, + c/d, c/e, c/f, + g/h, g/i, g/j, g/k, + h/i, h/j, h/k, + i/j, i/k, + j/k} + \path[edge] (\source) -- (\dest); + + \node at (1,0) {$K_{3,3}$}; + \node at (4.814,0) {$K_5$}; + \end{tikzpicture} + \end{figure} \end{frame} \begin{frame} - \frametitle{Vorüberlegungen} - \begin{columns}[T] - \begin{column}{.6\textwidth} - \begin{itemize} - \item<1,5> \alert{Schleifen} entfernen - \item<1,5> \alert{Parallele Kanten} entfernen - \item<2,5> \alert{Zusammenhangskomponenten} getrennt betrachten - \item<3,5> \alert{Blöcke} getrennt betrachten - \item<3,5> Knoten von \alert{Grad 1} entfernen - \item<4,5> Knoten von \alert{Grad 2} durch Kanten ersetzen - \end{itemize} - - \vspace{1.5em} - \uncover<5>{Teilgraphen sind\ldots} - \begin{itemize} - \item<5> planar wenn $|E| < 9$ oder $|V| < 5$ - \item<5> nicht planar wenn $|E| > 3|V| - 6$ - \end{itemize} - \end{column} - \begin{column}{.4\textwidth} -\begin{figure} -\begin{tikzpicture}[auto] - \useasboundingbox (-1, -1) rectangle (7,7); + \frametitle{Vorüberlegungen} + \begin{columns}[T] + \begin{column}{.6\textwidth} + \begin{itemize} + \item<1,5> \alert{Schleifen} entfernen + \item<1,5> \alert{Parallele Kanten} entfernen + \item<2,5> \alert{Zusammenhangskomponenten} getrennt betrachten + \item<3,5> \alert{Blöcke} getrennt betrachten + \item<3,5> Knoten von \alert{Grad 1} entfernen + \item<4,5> Knoten von \alert{Grad 2} durch Kanten ersetzen + \end{itemize} - \node<1>[vertex] (t) at (2,5) {}; - \node<1>[vertex] (s) at (2,2) {}; - \path<1>[edge] (t) .. controls (1,6) and (3,6) .. (t); - \path<1>[edge] (s) .. controls (1.5,3.5) .. (t); - \path<1>[edge] (s) .. controls (2.5,3.5) .. (t); + \vspace{1.5em} + \uncover<5>{Teilgraphen sind\ldots} + \begin{itemize} + \item<5> planar wenn $|E| < 9$ oder $|V| < 5$ + \item<5> nicht planar wenn $|E| > 3|V| - 6$ + \end{itemize} + \end{column} + \begin{column}{.4\textwidth} + \begin{figure} + \begin{tikzpicture}[auto] + \useasboundingbox (-1, -1) rectangle (7,7); - \foreach \pos/\name in {{(0,0)/a}, {(0,2)/b}, {(2,0)/c},{(2,2)/d}, - {(1,1)/e}} - \node<2>[vertex] (\name) at \pos {}; + \node<1>[vertex] (t) at (2,5) {}; + \node<1>[vertex] (s) at (2,2) {}; + \path<1>[edge] (t) .. controls (1,6) and (3,6) .. (t); + \path<1>[edge] (s) .. controls (1.5,3.5) .. (t); + \path<1>[edge] (s) .. controls (2.5,3.5) .. (t); + + \foreach \pos/\name in {{(0,0)/a}, {(0,2)/b}, {(2,0)/c},{(2,2)/d}, + {(1,1)/e}} + \node<2>[vertex] (\name) at \pos {}; - \foreach \pos/\name in {{(0,4)/f}, {(2,4)/g}, {(3,5)/h},{(2,6)/i}, - {(0,6)/j}} - \node<2>[vertex, fill=red!25] (\name) at \pos {}; - - \foreach \source/ \dest in {a/b, a/c, c/d, b/d, - a/e, e/d, f/g, g/h, h/i, h/j, g/i} - \path<2>[edge] (\source) -- (\dest); + \foreach \pos/\name in {{(0,4)/f}, {(2,4)/g}, {(3,5)/h},{(2,6)/i}, + {(0,6)/j}} + \node<2>[vertex, fill=red!25] (\name) at \pos {}; + + \foreach \source/ \dest in {a/b, a/c, c/d, b/d, + a/e, e/d, f/g, g/h, h/i, h/j, g/i} + \path<2>[edge] (\source) -- (\dest); + + \foreach \pos/\name in {{(0,0)/a}, {(0,1.5)/b}, {(2,0)/c},{(2,1.5)/d}} + \node<3,5>[vertex] (\name) at \pos {}; + + \foreach \pos/\name in {{(0,3.5)/f}, {(2,3.5)/g}, {(0,5)/h},{(2,5)/i}, + {(1,6.5)/k}} + \node<3,5>[vertex, fill=red!25] (\name) at \pos {}; + + \node<3,5>[vertex, fill=green!25] (e) at (-1,2.5) {}; - \foreach \pos/\name in {{(0,0)/a}, {(0,1.5)/b}, {(2,0)/c},{(2,1.5)/d}} - \node<3,5>[vertex] (\name) at \pos {}; - - \foreach \pos/\name in {{(0,3.5)/f}, {(2,3.5)/g}, {(0,5)/h},{(2,5)/i}, - {(1,6.5)/k}} - \node<3,5>[vertex, fill=red!25] (\name) at \pos {}; - - \node<3,5>[vertex, fill=green!25] (e) at (-1,2.5) {}; - - \foreach \source/ \dest in {a/b, a/c, c/d, b/d, - b/e, e/f, - f/g, f/h, h/i, g/i, h/k} - \path<3,5>[edge] (\source) -- (\dest); - \path<3,5>[edge] (g) .. controls (3, 5.5) .. (k); + \foreach \source/ \dest in {a/b, a/c, c/d, b/d, + b/e, e/f, + f/g, f/h, h/i, g/i, h/k} + \path<3,5>[edge] (\source) -- (\dest); + \path<3,5>[edge] (g) .. controls (3, 5.5) .. (k); - \foreach \pos/\name in {{(0,3)/a}, {(0,5)/b}, {(2,3)/c},{(2,5)/d}} - \node<4>[vertex] (\name) at \pos {}; - \node<4>[vertex, fill=red!25] (e) at (1, 4) {}; - - \foreach \source/ \dest in {a/b, a/c, c/d, b/d, - a/e, e/d} - \path<4>[edge] (\source) -- (\dest); -\end{tikzpicture} -\end{figure} -\vspace{1em} - \end{column} - \end{columns} + \foreach \pos/\name in {{(0,3)/a}, {(0,5)/b}, {(2,3)/c},{(2,5)/d}} + \node<4>[vertex] (\name) at \pos {}; + \node<4>[vertex, fill=red!25] (e) at (1, 4) {}; + + \foreach \source/ \dest in {a/b, a/c, c/d, b/d, + a/e, e/d} + \path<4>[edge] (\source) -- (\dest); + \end{tikzpicture} + \end{figure} + \vspace{1em} + \end{column} + \end{columns} \end{frame} \begin{frame} - \frametitle{Algorithmen} - \begin{itemize} - \item \alert{Knotenbasiert} - \begin{itemize} - \item Ein Graph bleibt planar wenn man einzelne Knoten entfernt - \item Prozess kann umgekehrt werden - \end{itemize} - \vspace{2em} - \item \alert{Kreisbasiert} - \begin{itemize} - \item Nur Graphen mit Zyklen können nicht planar sein - \item Zyklen trennen Ebene in zwei Bereiche - \item Teilgraphen sind entweder innen oder außen - \end{itemize} - \end{itemize} + \frametitle{Algorithmen} + \begin{itemize} + \item \alert{Knotenbasiert} + \begin{itemize} + \item Ein Graph bleibt planar wenn man einzelne Knoten entfernt + \item Prozess kann umgekehrt werden + \end{itemize} + \vspace{2em} + \item \alert{Kreisbasiert} + \begin{itemize} + \item Nur Graphen mit Zyklen können nicht planar sein + \item Zyklen trennen Ebene in zwei Bereiche + \item Teilgraphen sind entweder innen oder außen + \end{itemize} + \end{itemize} \end{frame} \begin{frame} - \frametitle{LR-Algorithmus} - - \begin{itemize} - \item Kreisbasiert - \item \alert{Kantenweises} betrachten des Graphen - \item Weiterentwicklung von \emph{Hopcroft und Tarjan} (1974) - \vspace{2em} - \item Original von \emph{de Fraysseix, Ossona de Mendez und -Rosenstiehl} (2006) - \item Beschrieben von \emph{Ulrik Brandes} (2009) - \end{itemize} + \frametitle{LR-Algorithmus} + + \begin{itemize} + \item Kreisbasiert + \item \alert{Kantenweises} betrachten des Graphen + \item Weiterentwicklung von \emph{Hopcroft und Tarjan} (1974) + \vspace{2em} + \item Original von \emph{de Fraysseix, Ossona de Mendez und + Rosenstiehl} (2006) + \item Beschrieben von \emph{Ulrik Brandes} (2009) + \end{itemize} \end{frame} \begin{frame} - \frametitle{Tiefensuche} + \frametitle{Tiefensuche} - \begin{columns}[T] - \begin{column}{.35\textwidth} - \begin{itemize} - \item Wurzel - \item DFS-Baum - \item Rückwärtskante - \item Orientierung - \vspace{2em} - \item<2> DFS-Index - \item<2> strikt höher/tiefer - \item<2> \alert{lowpoint}\\ $lowpt([5]) = 2$ - \end{itemize} - \end{column} - \begin{column}{.65\textwidth} -\begin{figure} -\begin{tikzpicture}[auto, scale=0.7] - \useasboundingbox (-2,0) rectangle (6,10); + \begin{columns}[T] + \begin{column}{.35\textwidth} + \begin{itemize} + \item Wurzel + \item DFS-Baum + \item Rückwärtskante + \item Orientierung + \vspace{2em} + \item<2> DFS-Index + \item<2> strikt höher/tiefer + \item<2> \alert{lowpoint}\\ $lowpt([5]) = 2$ + \end{itemize} + \end{column} + \begin{column}{.65\textwidth} + \begin{figure} + \begin{tikzpicture}[auto, scale=0.7] + \useasboundingbox (-2,0) rectangle (6,10); - \foreach \pos/\name in {{(0,0)/a},{(0,2)/b},{(-1,4)/c},{(-2,6)/d},{(0,6)/e}, - {(-1,8)/f}, {(1,8)/g}, - {(3,4)/h}, {(5,6)/i}, {(4,8)/j},{(6,8)/k}} - \node[vertex] (\name) at \pos {}; + \foreach \pos/\name in {{(0,0)/a},{(0,2)/b},{(-1,4)/c},{(-2,6)/d},{(0,6)/e}, + {(-1,8)/f}, {(1,8)/g}, + {(3,4)/h}, {(5,6)/i}, {(4,8)/j},{(6,8)/k}} + \node[vertex] (\name) at \pos {}; + + \path<1> node[selected vertex] at (a) {$r$}; + + \foreach \pos/\name in {{(0,2)/2},{(-1,4)/3},{(-2,6)/4},{(0,6)/5}, + {(-1,8)/6}, {(1,8)/7}, + {(3,4)/8}, {(5,6)/9}, {(4,8)/10},{(6,8)/11}} + \path<2> node[vertex] at \pos {$\name$}; + \path<2> node[selected vertex] at (0,0) {$1$}; - \path<1> node[selected vertex] at (a) {$r$}; - - \foreach \pos/\name in {{(0,2)/2},{(-1,4)/3},{(-2,6)/4},{(0,6)/5}, - {(-1,8)/6}, {(1,8)/7}, - {(3,4)/8}, {(5,6)/9}, {(4,8)/10},{(6,8)/11}} - \path<2> node[vertex] at \pos {$\name$}; - \path<2> node[selected vertex] at (0,0) {$1$}; - - \foreach \source/ \dest in {a/b, b/c, c/d, c/e, e/f, e/g, - b/h, h/i, i/j, i/k} - \path[tree edge] (\source) -- (\dest); - - \foreach \source/\dest/\ctrl in {{f/b/(2.5, 9.2)}, {g/c/(0.5,5)}, {d/a/(-2,2)}, - {j/b/(4.5, 3)}, {k/b/(6,3)}} - \path[back edge] (\source) .. controls \ctrl .. (\dest); -\end{tikzpicture} -\end{figure} -\vspace{1em} - \end{column} - \end{columns} + \foreach \source/ \dest in {a/b, b/c, c/d, c/e, e/f, e/g, + b/h, h/i, i/j, i/k} + \path[tree edge] (\source) -- (\dest); + + \foreach \source/\dest/\ctrl in {{f/b/(2.5, 9.2)}, {g/c/(0.5,5)}, {d/a/(-2,2)}, + {j/b/(4.5, 3)}, {k/b/(6,3)}} + \path[back edge] (\source) .. controls \ctrl .. (\dest); + \end{tikzpicture} + \end{figure} + \vspace{1em} + \end{column} + \end{columns} \end{frame} \begin{frame} - \frametitle{Beispiel} - -\begin{figure} -\begin{tikzpicture}[auto, scale=1.3] - \useasboundingbox (-4,0) rectangle (4,6); + \frametitle{Beispiel} + + \begin{figure} + \begin{tikzpicture}[auto, scale=1.3] + \useasboundingbox (-4,0) rectangle (4,6); + + \foreach \pos/\name in {{(0,1)/a},{(0,2)/b},{(1,3)/c},{(0.75,4)/d},{(-0.5,4.5)/e}, + {(-1.5,3.5)/f}, {(1.25,5.25)/g}, + {(0,5.5)/h}, {(2.5,6)/i}, {(4,5)/j},{(2.5,4.5)/k}, + {(-2,6)/l}, {(-2.5,5)/m}, {(-4,5)/n}} + \node[small vertex] (\name) at \pos {}; + + + \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g, + e/h, h/i, i/j, j/k, + h/l, l/m, m/n} + \path<1>[edge] (\source) -- (\dest); - \foreach \pos/\name in {{(0,1)/a},{(0,2)/b},{(1,3)/c},{(0.75,4)/d},{(-0.5,4.5)/e}, - {(-1.5,3.5)/f}, {(1.25,5.25)/g}, - {(0,5.5)/h}, {(2.5,6)/i}, {(4,5)/j},{(2.5,4.5)/k}, - {(-2,6)/l}, {(-2.5,5)/m}, {(-4,5)/n}} - \node[small vertex] (\name) at \pos {}; - - - \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g, - e/h, h/i, i/j, j/k, - h/l, l/m, m/n} - \path<1>[edge] (\source) -- (\dest); - - \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g, - e/h, h/i, i/j, j/k, - h/l, l/m, m/n} - \path<2->[tree edge] (\source) -- (\dest); - - \foreach \source/ \dest in {f/b, k/c, k/i, j/a, g/d, m/e, n/l, n/a} - \path<1>[edge] (\source) -- (\dest); - - \foreach \source/ \dest in {f/b, k/c, k/i, j/a, g/d, m/e, n/l, n/a} - \path<2>[back edge] (\source) -- (\dest); - - \foreach \source/ \dest in {f/b, m/e, n/a} - \path<3>[left edge] (\source) -- (\dest); - - \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l} - \path<3>[right edge] (\source) -- (\dest); - - \draw<2> (0,0) node {DFS}; - \draw<3> (0,0) node {LR-Zerlegung}; -\end{tikzpicture} -\end{figure} + \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g, + e/h, h/i, i/j, j/k, + h/l, l/m, m/n} + \path<2->[tree edge] (\source) -- (\dest); + + \foreach \source/ \dest in {f/b, k/c, k/i, j/a, g/d, m/e, n/l, n/a} + \path<1>[edge] (\source) -- (\dest); + + \foreach \source/ \dest in {f/b, k/c, k/i, j/a, g/d, m/e, n/l, n/a} + \path<2>[back edge] (\source) -- (\dest); + + \foreach \source/ \dest in {f/b, m/e, n/a} + \path<3>[left edge] (\source) -- (\dest); + + \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l} + \path<3>[right edge] (\source) -- (\dest); + + \draw<2> (0,0) node {DFS}; + \draw<3> (0,0) node {LR-Zerlegung}; + \end{tikzpicture} + \end{figure} \end{frame} \begin{frame} - \frametitle{LR-Zerlegung} - - \begin{itemize} - \item Jede Rückwärtskante erzeugt einen \alert{Zyklus} - \item LR-Zerlegung teilt Zyklen in solche im und gegen den Uhrzeigersinn - \item Quelle \alert{außen} - \item \alert{Verschachtelung} nur bei gleicher Orientierung - \end{itemize} - - \begin{center} - \begin{figure} - \begin{tikzpicture}[auto] - \useasboundingbox (-2, 0.5) rectangle (7, 5); - - \draw[edge] (0,0.5) -- (0,3); - \draw[edge] (-1.5,4) -- (0,3) node[midway, above] {}; - \draw[edge] (1.5,4) -- (0,3) node[midway, above] {}; - - \draw[left edge, rounded corners] (-1.5,4) .. controls (-0.5,1) .. (0,1); - \draw[right edge] (1.5,4) .. controls (0.5,2) .. (0,2); + \frametitle{LR-Zerlegung} + + \begin{itemize} + \item Jede Rückwärtskante erzeugt einen \alert{Zyklus} + \item LR-Zerlegung teilt Zyklen in solche im und gegen den Uhrzeigersinn + \item Quelle \alert{außen} + \item \alert{Verschachtelung} nur bei gleicher Orientierung + \end{itemize} + + \begin{center} + \begin{figure} + \begin{tikzpicture}[auto] + \useasboundingbox (-2, 0.5) rectangle (7, 5); + + \draw[edge] (0,0.5) -- (0,3); + \draw[edge] (-1.5,4) -- (0,3) node[midway, above] {}; + \draw[edge] (1.5,4) -- (0,3) node[midway, above] {}; + + \draw[left edge, rounded corners] (-1.5,4) .. controls (-0.5,1) .. (0,1); + \draw[right edge] (1.5,4) .. controls (0.5,2) .. (0,2); - \draw[edge] (4.5,0.5) -- (4.5,3); - \draw[edge] (3,4) -- (4.5,3) node[midway, above] {}; - \draw[edge] (6,4) -- (4.5,3) node[midway, above] {}; - - \draw[right edge, rounded corners] (3,4) .. controls (8.5,6) and (5.5,1) .. (4.5,1); - \draw[right edge] (6,4) .. controls (5,2) .. (4.5,2); - \end{tikzpicture} - \end{figure} - \end{center} + \draw[edge] (4.5,0.5) -- (4.5,3); + \draw[edge] (3,4) -- (4.5,3) node[midway, above] {}; + \draw[edge] (6,4) -- (4.5,3) node[midway, above] {}; + + \draw[right edge, rounded corners] (3,4) .. controls (8.5,6) and (5.5,1) .. (4.5,1); + \draw[right edge] (6,4) .. controls (5,2) .. (4.5,2); + \end{tikzpicture} + \end{figure} + \end{center} \end{frame} \begin{frame} - \frametitle{LR-Zerlegung} - - \begin{definition} - Sei $G = (V, T \uplus B)$ ein \alert{DFS-orientierter} Graph. Eine Zerlegung $B = L \uplus R$ seiner Rückwärtskanten heißt \alert{LR-Zerlegung} wenn für jeden Knoten mit ausgehenden Kanten $e_1$, $e_2$ gilt: - \begin{itemize} - \item Alle Rückwärtskanten von $e_1$ mit ihrem Ende über $lowpt(e_2)$ gehören zur einen und - \item Alle Rückwärtskanten von $e_2$ mit ihrem Ende über $lowpt(e_1)$ gehören zur anderen Klasse. - \end{itemize} - \end{definition} - - \begin{center} - \begin{figure} - \begin{tikzpicture}[auto, scale=0.5] - \useasboundingbox (-4, 2) rectangle (4, 9); - - \node[small vertex] (u) at (0,3) {}; - \node[small vertex] (v) at (0,6) {$v$}; - \node[small vertex] (w) at (-2,8) {}; - \node[small vertex] (x) at (2,8) {}; - - \path[edge] (u) -- (v); - \path[edge, ->] (v) -- (w) node[midway, below] {$e_1$}; - \path[edge, ->] (v) -- (x) node[midway, below] {$e_2$}; - \path[edge] (0,2) -- (u); - - \draw[left edge] (w) .. controls (-2, 5) .. (u); - \draw[right edge] (x) .. controls (2, 5) .. (u); - \draw[back edge] (w) .. controls (-3, 5) .. (0,2); - \draw[back edge] (x) .. controls (3, 5) .. (0,2); - \end{tikzpicture} - \end{figure} - \end{center} + \frametitle{LR-Zerlegung} + + \begin{definition} + Sei $G = (V, T \uplus B)$ ein \alert{DFS-orientierter} Graph. Eine Zerlegung $B = L \uplus R$ seiner Rückwärtskanten heißt \alert{LR-Zerlegung} wenn für jeden Knoten mit ausgehenden Kanten $e_1$, $e_2$ gilt: + \begin{itemize} + \item Alle Rückwärtskanten von $e_1$ mit ihrem Ende über $lowpt(e_2)$ gehören zur einen und + \item Alle Rückwärtskanten von $e_2$ mit ihrem Ende über $lowpt(e_1)$ gehören zur anderen Klasse. + \end{itemize} + \end{definition} + + \begin{center} + \begin{figure} + \begin{tikzpicture}[auto, scale=0.5] + \useasboundingbox (-4, 2) rectangle (4, 9); + + \node[small vertex] (u) at (0,3) {}; + \node[small vertex] (v) at (0,6) {$v$}; + \node[small vertex] (w) at (-2,8) {}; + \node[small vertex] (x) at (2,8) {}; + + \path[edge] (u) -- (v); + \path[edge, ->] (v) -- (w) node[midway, below] {$e_1$}; + \path[edge, ->] (v) -- (x) node[midway, below] {$e_2$}; + \path[edge] (0,2) -- (u); + + \draw[left edge] (w) .. controls (-2, 5) .. (u); + \draw[right edge] (x) .. controls (2, 5) .. (u); + \draw[back edge] (w) .. controls (-3, 5) .. (0,2); + \draw[back edge] (x) .. controls (3, 5) .. (0,2); + \end{tikzpicture} + \end{figure} + \end{center} \end{frame} \begin{frame} - \frametitle{LR-Zerlegung} + \frametitle{LR-Zerlegung} + + \begin{theorem} + Ein Graph ist genau dann planar, wenn er eine \alert{LR-Zerlegung} zulässt. + \end{theorem} + + \vspace{2em} - \begin{theorem} - Ein Graph ist genau dann planar, wenn er eine \alert{LR-Zerlegung} zulässt. - \end{theorem} - - \vspace{2em} - - \begin{itemize} - \item Planare Zeichnung $\rightarrow$ LR-Zerlegung intuitiv - \vspace{1em} - \item Andere Richtung: Konstruktiv - \item Probleme ergeben sich bei überlappenden Kreisen - \item Welche Kreise liegen außen, welche innen? - \item Bedingungen abhängig von Baumkanten - \end{itemize} + \begin{itemize} + \item Planare Zeichnung $\rightarrow$ LR-Zerlegung intuitiv + \vspace{1em} + \item Andere Richtung: Konstruktiv + \item Probleme ergeben sich bei überlappenden Kreisen + \item Welche Kreise liegen außen, welche innen? + \item Bedingungen abhängig von Baumkanten + \end{itemize} \end{frame} \begin{frame} - \frametitle{Verschachtelung} - - \begin{block}{Beobachtung} - Die Baumkante $e_1$ muss außerhalb von Baumkante sein $e_2$ wenn - \begin{itemize} - \item $lowpt(e_1) < lowpt(e_2)$ - \end{itemize} - oder - \begin{itemize} - \item $lowpt(e_1) = lowpt(e_2)$ und $e_2$ eine Sehne besitzt - \end{itemize} - \end{block} - \begin{center} - \begin{figure} - \begin{tikzpicture}[auto] - \useasboundingbox (-2, 0.5) rectangle (7, 5); - - \draw[edge] (0,1) -- (0,3); - \draw[edge] (-1.5,4) -- (0,3) node[midway, above] {$e_1$}; - \draw[edge] (1.5,4) -- (0,3) node[midway, above] {$e_2$}; - - \draw[back edge, rounded corners] (-1.5,4) .. controls (4,6) and (1,1) .. (0,1); - \draw[back edge] (1.5,4) .. controls (0.5,2) .. (0,2); + \frametitle{Verschachtelung} + + \begin{block}{Beobachtung} + Die Baumkante $e_1$ muss außerhalb von Baumkante sein $e_2$ wenn + \begin{itemize} + \item $lowpt(e_1) < lowpt(e_2)$ + \end{itemize} + oder + \begin{itemize} + \item $lowpt(e_1) = lowpt(e_2)$ und $e_2$ eine Sehne besitzt + \end{itemize} + \end{block} + \begin{center} + \begin{figure} + \begin{tikzpicture}[auto] + \useasboundingbox (-2, 0.5) rectangle (7, 5); + + \draw[edge] (0,1) -- (0,3); + \draw[edge] (-1.5,4) -- (0,3) node[midway, above] {$e_1$}; + \draw[edge] (1.5,4) -- (0,3) node[midway, above] {$e_2$}; + + \draw[back edge, rounded corners] (-1.5,4) .. controls (4,6) and (1,1) .. (0,1); + \draw[back edge] (1.5,4) .. controls (0.5,2) .. (0,2); - \draw[edge] (4.5,1) -- (4.5,3); - \draw[edge] (3,4) -- (4.5,3) node[midway, above] {$e_1$}; - \draw[edge] (6,4) -- (4.5,3) node[midway, above] {$e_2$}; - - \draw[back edge, rounded corners] (3,4) .. controls (8.5,6) and (5.5,1) .. (4.5,1); - \draw[back edge] (6,4) .. controls (5,2) .. (4.5,2); - \draw[back edge] (6,4) .. controls (5.5,2) .. (4.5,1); - \end{tikzpicture} - \end{figure} - \end{center} + \draw[edge] (4.5,1) -- (4.5,3); + \draw[edge] (3,4) -- (4.5,3) node[midway, above] {$e_1$}; + \draw[edge] (6,4) -- (4.5,3) node[midway, above] {$e_2$}; + + \draw[back edge, rounded corners] (3,4) .. controls (8.5,6) and (5.5,1) .. (4.5,1); + \draw[back edge] (6,4) .. controls (5,2) .. (4.5,2); + \draw[back edge] (6,4) .. controls (5.5,2) .. (4.5,1); + \end{tikzpicture} + \end{figure} + \end{center} \end{frame} \begin{frame} - \frametitle{Verschachtelung} - \begin{columns}[T] - \begin{column}{.5\textwidth} - \begin{figure} - \begin{tikzpicture}[auto, scale=0.5] - \useasboundingbox (-5, 0) rectangle (5, 8); - - \node[vertex] (u) at (0,0) {$u$}; - \node[vertex] (v) at (0,3) {$v$}; - \node[small vertex] (w) at (-4,3) {}; - \node[small vertex] (x) at (-3,6) {}; - \node[small vertex] (y) at (-1,8) {}; - \node[small vertex] (a) at (1,8) {}; - \node[small vertex] (b) at (3,6) {}; - \node[small vertex] (c) at (4,3) {}; - - \path[edge, ->] (u) -- (v); - \path[left edge] (v) -- (w) node[near end, below, black] {$e_l^L$}; - \path[left edge] (v) -- (x) node[very near end, below left, black] {$e_2^L$}; - \path[left edge] (v) -- (y) node[at end, below left, black] {$e_1^L$}; - \path[right edge] (v) -- (a) node[at end, below right, black] {$e_1^R$}; - \path[right edge] (v) -- (b) node[very near end, below right, black] {$e_2^R$}; - \path[right edge] (v) -- (c) node[near end, below, black] {$e_r^R$}; - - \end{tikzpicture} - \end{figure} - \end{column} - \begin{column}{.5\textwidth} - \begin{figure} - \begin{tikzpicture}[auto, scale=0.5] - \useasboundingbox (-5, 0) rectangle (5, 8); - - \node[vertex] (u) at (0,0) {$u$}; - \node[vertex] (v) at (0,3) {$v$}; - \node[small vertex] (w) at (-3,6) {}; - \node[small vertex] (x) at (3,6) {}; - - \path[edge, ->] (u) -- (v); - \path[left edge] (v) -- (w) node[near end, below, black] {$e^L$}; - \path[right edge] (v) -- (x) node[near end, below, black] {$e^R$}; - - \draw[edge] (w) -- (-4,7); - \draw[left edge] (-4,7) .. controls(-4, 3.5) .. (v); - \draw[left edge] (-4,7) .. controls(-3, 3.5) .. (v); - \draw[right edge] (-4,7) .. controls(-2, 7) .. (v); - - \draw[edge] (x) -- (4,7); - \draw[right edge] (4,7) .. controls(4, 3.5) .. (v); - \draw[left edge] (4,7) .. controls(2, 7) .. (v); - \end{tikzpicture} - \end{figure} - \end{column} - \end{columns} + \frametitle{Verschachtelung} + \begin{columns}[T] + \begin{column}{.5\textwidth} + \begin{figure} + \begin{tikzpicture}[auto, scale=0.5] + \useasboundingbox (-5, 0) rectangle (5, 8); + + \node[vertex] (u) at (0,0) {$u$}; + \node[vertex] (v) at (0,3) {$v$}; + \node[small vertex] (w) at (-4,3) {}; + \node[small vertex] (x) at (-3,6) {}; + \node[small vertex] (y) at (-1,8) {}; + \node[small vertex] (a) at (1,8) {}; + \node[small vertex] (b) at (3,6) {}; + \node[small vertex] (c) at (4,3) {}; + + \path[edge, ->] (u) -- (v); + \path[left edge] (v) -- (w) node[near end, below, black] {$e_l^L$}; + \path[left edge] (v) -- (x) node[very near end, below left, black] {$e_2^L$}; + \path[left edge] (v) -- (y) node[at end, below left, black] {$e_1^L$}; + \path[right edge] (v) -- (a) node[at end, below right, black] {$e_1^R$}; + \path[right edge] (v) -- (b) node[very near end, below right, black] {$e_2^R$}; + \path[right edge] (v) -- (c) node[near end, below, black] {$e_r^R$}; + + \end{tikzpicture} + \end{figure} + \end{column} + \begin{column}{.5\textwidth} + \begin{figure} + \begin{tikzpicture}[auto, scale=0.5] + \useasboundingbox (-5, 0) rectangle (5, 8); + + \node[vertex] (u) at (0,0) {$u$}; + \node[vertex] (v) at (0,3) {$v$}; + \node[small vertex] (w) at (-3,6) {}; + \node[small vertex] (x) at (3,6) {}; + + \path[edge, ->] (u) -- (v); + \path[left edge] (v) -- (w) node[near end, below, black] {$e^L$}; + \path[right edge] (v) -- (x) node[near end, below, black] {$e^R$}; + + \draw[edge] (w) -- (-4,7); + \draw[left edge] (-4,7) .. controls(-4, 3.5) .. (v); + \draw[left edge] (-4,7) .. controls(-3, 3.5) .. (v); + \draw[right edge] (-4,7) .. controls(-2, 7) .. (v); + + \draw[edge] (x) -- (4,7); + \draw[right edge] (4,7) .. controls(4, 3.5) .. (v); + \draw[left edge] (4,7) .. controls(2, 7) .. (v); + \end{tikzpicture} + \end{figure} + \end{column} + \end{columns} \end{frame} \begin{frame} - \frametitle{Verschachtelung} - - \begin{definition} - Seien \alert{$e_1^L,\ldots,e_l^L$} die linken ausgehenden Baumkanten und \alert{$e_1^R,\ldots,e_r^R$} die rechten ausgehenden Baumkanten eines Knotens $v$ und $u$ sein Elternknoten. Dann ist die \alert{LR-Ordnung} im Uhrzeigersinn - \begin{align*} - &(u, v),\\ - &L(e_l^L),e_l^L,R(e_l^L),\ldots,R(e_1^L),\\ - &L(e_1^R),\ldots,L(e_r^R),e_r^R,R(e_r^R) - \end{align*} - Dabei ist \alert{$e_1$} außerhalb von \alert{$e_2$} usw. - \end{definition} + \frametitle{Verschachtelung} - \alert{$L(e)$} bezeichnet die linken eingehenden Rückwärtskanten deren Kreise sich $e$ teilen. + \begin{definition} + Seien \alert{$e_1^L,\ldots,e_l^L$} die linken ausgehenden Baumkanten und \alert{$e_1^R,\ldots,e_r^R$} die rechten ausgehenden Baumkanten eines Knotens $v$ und $u$ sein Elternknoten. Dann ist die \alert{LR-Ordnung} im Uhrzeigersinn + \begin{align*} + &(u, v),\\ + &L(e_l^L),e_l^L,R(e_l^L),\ldots,R(e_1^L),\\ + &L(e_1^R),\ldots,L(e_r^R),e_r^R,R(e_r^R) + \end{align*} + Dabei ist \alert{$e_1$} außerhalb von \alert{$e_2$} usw. + \end{definition} + + \alert{$L(e)$} bezeichnet die linken eingehenden Rückwärtskanten deren Kreise sich $e$ teilen. \end{frame} \begin{frame} - \frametitle{Planarisierung} - - \begin{block}{Lemma} - Eine \alert{LR-Ordnung} stellt eine Planarisierung einer \alert{LR-Zerlegung} dar. - \end{block} - \vspace{2em} - - \begin{block}{Beweisidee} - Beweis durch Widerspruch - \begin{itemize} - \item \alert{Baumkanten} sind immer planar - \item Überschneidungen wenn dann nur in \alert{Rückwärtskanten} - \item Fallunterscheidung - \begin{itemize} - \item selbe Klasse - \item verschiedene Klassen - \end{itemize} - \end{itemize} - \end{block} + \frametitle{Planarisierung} + + \begin{block}{Lemma} + Eine \alert{LR-Ordnung} stellt eine Planarisierung einer \alert{LR-Zerlegung} dar. + \end{block} + \vspace{2em} + + \begin{block}{Beweisidee} + Beweis durch Widerspruch + \begin{itemize} + \item \alert{Baumkanten} sind immer planar + \item Überschneidungen wenn dann nur in \alert{Rückwärtskanten} + \item Fallunterscheidung + \begin{itemize} + \item selbe Klasse + \item verschiedene Klassen + \end{itemize} + \end{itemize} + \end{block} \end{frame} \begin{frame} - \frametitle{Algorithmus} - - \begin{itemize} - \item Testen auf Planarität entspricht Testen auf \alert{LR-Zerlegung} - \item \alert{LR-Zerlegung} stellt Randbedingungen - \vspace{2em} - \item Welche Bedingungen gibt es? - \begin{itemize} - \item Überlappende Kreise - \item Gabelungen - \end{itemize} - \item Können alle Bedingungen gleichzeitig erfüllt werden? - \end{itemize} + \frametitle{Algorithmus} + + \begin{itemize} + \item Testen auf Planarität entspricht Testen auf \alert{LR-Zerlegung} + \item \alert{LR-Zerlegung} stellt Randbedingungen + \vspace{2em} + \item Welche Bedingungen gibt es? + \begin{itemize} + \item Überlappende Kreise + \item Gabelungen + \end{itemize} + \item Können alle Bedingungen gleichzeitig erfüllt werden? + \end{itemize} \end{frame} \begin{frame} - \frametitle{Algorithmus} - - \begin{columns}[T] - \begin{column}{.33\textwidth} - \begin{figure} - \begin{tikzpicture}[auto, scale=0.5] - \useasboundingbox (-4, 0) rectangle (4, 9); - - \node[small vertex] (u) at (0,3) {}; - \node[small vertex] (v) at (0,6) {$v$}; - \node[small vertex] (w) at (-2,8) {$w_1$}; - - \path[edge] (u) -- (v); - \path[edge, ->] (v) -- (w); - \draw[edge] (0,0) -- (u); - \draw[edge] (v) -- (2, 8); - - \draw[left edge] (w) .. controls (-2, 5) .. (u); - \draw[back edge] (w) .. controls (-3, 5) .. (0,1); - - \draw[right edge] (2, 8) .. controls (2, 4) .. (0,2); - \end{tikzpicture} - \end{figure} - \end{column} - \begin{column}{.33\textwidth} - \begin{figure} - \begin{tikzpicture}[auto, scale=0.5] - \useasboundingbox (-4, 0) rectangle (4, 9); - - \node[small vertex] (u) at (0,3) {}; - \node[small vertex] (v) at (0,6) {$v$}; - \node[small vertex] (w) at (-2,8) {$w_1$}; - \node[small vertex] (x) at (2,8) {$w_2$}; - - \path[edge] (u) -- (v); - \path[edge, ->] (v) -- (w); - \path[edge, ->] (v) -- (x); - \draw[edge] (0,0) -- (u); - - \draw[left edge] (w) .. controls (-2, 5) .. (u); - \draw[right edge] (x) .. controls (2, 5) .. (u); - \draw[back edge] (w) .. controls (-3, 5) .. (-1,1); - \draw[back edge] (x) .. controls (3, 5) .. (1,1); - \end{tikzpicture} - \end{figure} - \end{column} - \begin{column}{.33\textwidth} - \begin{figure} - \begin{tikzpicture}[auto, scale=0.5] - \useasboundingbox (-4, 0) rectangle (4, 9); - - \node[small vertex] (u) at (0,3) {$v_2$}; - \node[small vertex] (v) at (0,5) {$v_1$}; - \node[small vertex] (w) at (0,7) {$x$}; - \node[small vertex] (x) at (0,9) {}; - - \path[edge] (u) -- (v); - \path[edge] (v) -- (w); - \path[edge] (w) -- (x); - \draw[edge] (0,0) -- (u); - - \draw[right edge] (x) .. controls (3, 7) .. (u); - \draw[right edge] (x) .. controls (1.5, 7) .. (v); - \draw[back edge] (w) .. controls (-2, 5) .. (0,1); - \end{tikzpicture} - \end{figure} - \end{column} - \end{columns} + \frametitle{Algorithmus} + + \begin{columns}[T] + \begin{column}{.33\textwidth} + \begin{figure} + \begin{tikzpicture}[auto, scale=0.5] + \useasboundingbox (-4, 0) rectangle (4, 9); + + \node[small vertex] (u) at (0,3) {}; + \node[small vertex] (v) at (0,6) {$v$}; + \node[small vertex] (w) at (-2,8) {$w_1$}; + + \path[edge] (u) -- (v); + \path[edge, ->] (v) -- (w); + \draw[edge] (0,0) -- (u); + \draw[edge] (v) -- (2, 8); + + \draw[left edge] (w) .. controls (-2, 5) .. (u); + \draw[back edge] (w) .. controls (-3, 5) .. (0,1); + + \draw[right edge] (2, 8) .. controls (2, 4) .. (0,2); + \end{tikzpicture} + \end{figure} + \end{column} + \begin{column}{.33\textwidth} + \begin{figure} + \begin{tikzpicture}[auto, scale=0.5] + \useasboundingbox (-4, 0) rectangle (4, 9); + + \node[small vertex] (u) at (0,3) {}; + \node[small vertex] (v) at (0,6) {$v$}; + \node[small vertex] (w) at (-2,8) {$w_1$}; + \node[small vertex] (x) at (2,8) {$w_2$}; + + \path[edge] (u) -- (v); + \path[edge, ->] (v) -- (w); + \path[edge, ->] (v) -- (x); + \draw[edge] (0,0) -- (u); + + \draw[left edge] (w) .. controls (-2, 5) .. (u); + \draw[right edge] (x) .. controls (2, 5) .. (u); + \draw[back edge] (w) .. controls (-3, 5) .. (-1,1); + \draw[back edge] (x) .. controls (3, 5) .. (1,1); + \end{tikzpicture} + \end{figure} + \end{column} + \begin{column}{.33\textwidth} + \begin{figure} + \begin{tikzpicture}[auto, scale=0.5] + \useasboundingbox (-4, 0) rectangle (4, 9); + + \node[small vertex] (u) at (0,3) {$v_2$}; + \node[small vertex] (v) at (0,5) {$v_1$}; + \node[small vertex] (w) at (0,7) {$x$}; + \node[small vertex] (x) at (0,9) {}; + + \path[edge] (u) -- (v); + \path[edge] (v) -- (w); + \path[edge] (w) -- (x); + \draw[edge] (0,0) -- (u); + + \draw[right edge] (x) .. controls (3, 7) .. (u); + \draw[right edge] (x) .. controls (1.5, 7) .. (v); + \draw[back edge] (w) .. controls (-2, 5) .. (0,1); + \end{tikzpicture} + \end{figure} + \end{column} + \end{columns} \end{frame} \begin{frame} - \frametitle{Algorithmus} - \begin{block}{Korollar} - Seien $b_1 = (u_1, v_1)$ und $b_2 = (u_2, v_2)$ \alert{zwei Rückwärtskanten} mit überlappenden Zyklen und sei $(u, v)$, $(v, w_1)$, $(v, w_2)$ ihre Gabelung. Dann gilt: - \begin{itemize} - \item $b_1$ und $b_2$ gehören zu \alert{verschiedenen} Klassen wenn $lowpt(w_2) < v_1$ und $lowpt(w_1) < v_2$ - \item $b_1$ und $b_2$ gehören zur \alert{selben} Klasse wenn es eine Kante $e' = (x, y)$ gibt, sodass $x \in C(b_1) \cap C(b_2)$ und $y \not\in C(b_1) \cap C(b_2)$ und $lowpt(y) < min\{v_1, v_2\}$ - \end{itemize} - \end{block} - - \alert{$C(b)$} bezeichnet Knoten auf dem Zyklus, der durch $b$ geschlossen wird. + \frametitle{Algorithmus} + \begin{block}{Korollar} + Seien $b_1 = (u_1, v_1)$ und $b_2 = (u_2, v_2)$ \alert{zwei Rückwärtskanten} mit überlappenden Zyklen und sei $(u, v)$, $(v, w_1)$, $(v, w_2)$ ihre Gabelung. Dann gilt: + \begin{itemize} + \item $b_1$ und $b_2$ gehören zu \alert{verschiedenen} Klassen wenn $lowpt(w_2) < v_1$ und $lowpt(w_1) < v_2$ + \item $b_1$ und $b_2$ gehören zur \alert{selben} Klasse wenn es eine Kante $e' = (x, y)$ gibt, sodass $x \in C(b_1) \cap C(b_2)$ und $y \not\in C(b_1) \cap C(b_2)$ und $lowpt(y) < min\{v_1, v_2\}$ + \end{itemize} + \end{block} + + \alert{$C(b)$} bezeichnet Knoten auf dem Zyklus, der durch $b$ geschlossen wird. \end{frame} \begin{frame} - \frametitle{Algorithmus} + \frametitle{Algorithmus} - \begin{itemize} - \item Die Bedingungen lassen sich in einem \alert{Constraint Graphen} darstellen - \item Rückwärtskanten werden Knoten - \item Abhängigkeiten werden Kanten mit Beschriftung - \end{itemize} + \begin{itemize} + \item Die Bedingungen lassen sich in einem \alert{Constraint Graphen} darstellen + \item Rückwärtskanten werden Knoten + \item Abhängigkeiten werden Kanten mit Beschriftung + \end{itemize} \end{frame} \begin{frame} - \frametitle{Constraintgraph} - -\begin{figure} -\begin{tikzpicture}[auto, scale=1.3] - \useasboundingbox (-4,1) rectangle (4,6); + \frametitle{Constraintgraph} + + \begin{figure} + \begin{tikzpicture}[auto, scale=1.3] + \useasboundingbox (-4,1) rectangle (4,6); + + \foreach \pos/\name/\ctn in {{(0,1)/a/1},{(0,2)/b/2},{(1,3)/c/3},{(0.75,4)/d/4},{(-0.5,4.5)/e/5}, + {(-1.5,3.5)/f/6}, {(1.25,5.25)/g/7}, + {(0,5.5)/h/8}, {(2.5,6)/i/9}, {(4,5)/j/10},{(2.5,4.5)/k/11}, + {(-2,6)/l/12}, {(-2.5,5)/m/13}, {(-4,5)/n/14}} + \node<1>[vertex, minimum size=15pt] (\name) at \pos {$\ctn$}; + + \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g, + e/h, h/i, i/j, j/k, + h/l, l/m, m/n} + \path<1>[tree edge] (\source) -- (\dest); + + \foreach \source/ \dest in {f/b, m/e, n/a} + \path<1>[left edge] (\source) -- (\dest); + + \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l} + \path<1>[right edge] (\source) -- (\dest); - \foreach \pos/\name/\ctn in {{(0,1)/a/1},{(0,2)/b/2},{(1,3)/c/3},{(0.75,4)/d/4},{(-0.5,4.5)/e/5}, - {(-1.5,3.5)/f/6}, {(1.25,5.25)/g/7}, - {(0,5.5)/h/8}, {(2.5,6)/i/9}, {(4,5)/j/10},{(2.5,4.5)/k/11}, - {(-2,6)/l/12}, {(-2.5,5)/m/13}, {(-4,5)/n/14}} - \node<1>[vertex, minimum size=15pt] (\name) at \pos {$\ctn$}; - - \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g, - e/h, h/i, i/j, j/k, - h/l, l/m, m/n} - \path<1>[tree edge] (\source) -- (\dest); - - \foreach \source/ \dest in {f/b, m/e, n/a} - \path<1>[left edge] (\source) -- (\dest); - - \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l} - \path<1>[right edge] (\source) -- (\dest); - - \begin{pgfonlayer}{background} - \foreach \pos/\name/\ctn in {{(0,1)/a/1},{(0,2)/b/2},{(1,3)/c/3},{(0.75,4)/d/4},{(-0.5,4.5)/e/5}, - {(-1.5,3.5)/f/6}, {(1.25,5.25)/g/7}, - {(0,5.5)/h/8}, {(2.5,6)/i/9}, {(4,5)/j/10},{(2.5,4.5)/k/11}, - {(-2,6)/l/12}, {(-2.5,5)/m/13}, {(-4,5)/n/14}} - \node<2->[vertex, minimum size=15pt, opacity=0.2] (\name) at \pos {$\ctn$}; - - \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g, - e/h, h/i, i/j, j/k, - h/l, l/m, m/n} - \path<2->[tree edge, opacity=0.35] (\source) -- (\dest); - - \foreach \source/ \dest / \name in {f/b, m/e, n/a} - \path<2->[left edge, opacity=0.35] (\source) -- (\dest) - node[midway, anchor=center] (\source\dest) {}; - - \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l} - \path<2->[right edge, opacity=0.35] (\source) -- (\dest) - node[midway, anchor=center] (\source\dest) {}; - \end{pgfonlayer} - - \foreach \source/ \dest in {f/b, m/e, n/a} - \node<2->[fill=blue,minimum size=10pt] at (\source\dest) {}; - - \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l} - \node<2->[fill=red,minimum size=10pt] at (\source\dest) {}; - - \begin{pgfonlayer}{midground} - \path<3->[edge, ultra thick] (kc.center) -- (ki.center) node[midway] {s}; - \path<4->[edge, ultra thick] (me.center) -- (nl.center) node[midway, above] {v}; - \path<5->[edge, ultra thick] (me.center) -- (kc.center) node[midway] {v}; - \path<5->[edge, ultra thick] (fb.center) -- (kc.center) node[midway] {v}; - \end{pgfonlayer} -\end{tikzpicture} -\end{figure} + \begin{pgfonlayer}{background} + \foreach \pos/\name/\ctn in {{(0,1)/a/1},{(0,2)/b/2},{(1,3)/c/3},{(0.75,4)/d/4},{(-0.5,4.5)/e/5}, + {(-1.5,3.5)/f/6}, {(1.25,5.25)/g/7}, + {(0,5.5)/h/8}, {(2.5,6)/i/9}, {(4,5)/j/10},{(2.5,4.5)/k/11}, + {(-2,6)/l/12}, {(-2.5,5)/m/13}, {(-4,5)/n/14}} + \node<2->[vertex, minimum size=15pt, opacity=0.2] (\name) at \pos {$\ctn$}; + + \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g, + e/h, h/i, i/j, j/k, + h/l, l/m, m/n} + \path<2->[tree edge, opacity=0.35] (\source) -- (\dest); + + \foreach \source/ \dest / \name in {f/b, m/e, n/a} + \path<2->[left edge, opacity=0.35] (\source) -- (\dest) + node[midway, anchor=center] (\source\dest) {}; + + \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l} + \path<2->[right edge, opacity=0.35] (\source) -- (\dest) + node[midway, anchor=center] (\source\dest) {}; + \end{pgfonlayer} + + \foreach \source/ \dest in {f/b, m/e, n/a} + \node<2->[fill=blue,minimum size=10pt] at (\source\dest) {}; + + \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l} + \node<2->[fill=red,minimum size=10pt] at (\source\dest) {}; + + \begin{pgfonlayer}{midground} + \path<3->[edge, ultra thick] (kc.center) -- (ki.center) node[midway] {s}; + \path<4->[edge, ultra thick] (me.center) -- (nl.center) node[midway, above] {v}; + \path<5->[edge, ultra thick] (me.center) -- (kc.center) node[midway] {v}; + \path<5->[edge, ultra thick] (fb.center) -- (kc.center) node[midway] {v}; + \end{pgfonlayer} + \end{tikzpicture} + \end{figure} \end{frame} \begin{frame} - \frametitle{LR-Algorithmus} - - \begin{block}{Algorithmus} - \begin{itemize} - \item Erstellen einer \alert{DFS-Orientierung} - \item Berechnen von \alert{lowpoints} - \item Erzeugen des \alert{Constraint Graphs} - \item Ist dieser Widerspruchsfrei ist der Graph planar - \end{itemize} - \end{block} - - \vspace{0.5em} - \begin{itemize} - \item Erzeugen des Constraint Graphen polynomieller Aufwand - \item Kann in $\Oh(n)$ implementiert werden indem der Graph nicht explizit erzeugt wird - \end{itemize} + \frametitle{LR-Algorithmus} + + \begin{block}{Algorithmus} + \begin{itemize} + \item Erstellen einer \alert{DFS-Orientierung} + \item Berechnen von \alert{lowpoints} + \item Erzeugen des \alert{Constraint Graphs} + \item Ist dieser Widerspruchsfrei ist der Graph planar + \end{itemize} + \end{block} + + \vspace{0.5em} + \begin{itemize} + \item Erzeugen des Constraint Graphen polynomieller Aufwand + \item Kann in $\Oh(n)$ implementiert werden indem der Graph nicht explizit erzeugt wird + \end{itemize} \end{frame} \begin{frame} - \frametitle{Q \& A} + \frametitle{Q \& A} - \begin{center} \LARGE Danke für die Aufmerksamkeit!\end{center} - \vspace{1em} - \begin{center} \LARGE Fragen?\end{center} + \begin{center} \LARGE Danke für die Aufmerksamkeit!\end{center} + \vspace{1em} + \begin{center} \LARGE Fragen?\end{center} \end{frame} \begin{frame}[plain] - \begin{center} \LARGE Backup\end{center} + \begin{center} \LARGE Backup\end{center} \end{frame} \begin{frame} - \frametitle{Knotenbasierte Algorithmen} - \begin{itemize} - \item Es existiert immer eine \alert{Kette} von Planaren Graphen - \item Einmal \alert{geschlossene Facetten} bleiben geschlossen - \item Die \alert{Reihenfolge} von Knoten um eine Facette bleibt erhalten - \end{itemize} - - \begin{figure} - \begin{tikzpicture}[auto] - \foreach \pos/\name in {{(0,0)/a}, {(-3, 1)/b}, {(3, 1)/c},{(-2, 3)/d}, - {(2,2.5)/e}} - \node[small vertex] (\name) at \pos {}; - - \foreach \source/ \dest in {a/b, a/c, c/e, b/d, - a/d, e/a} - \path[edge] (\source) -- (\dest); + \frametitle{Knotenbasierte Algorithmen} + \begin{itemize} + \item Es existiert immer eine \alert{Kette} von Planaren Graphen + \item Einmal \alert{geschlossene Facetten} bleiben geschlossen + \item Die \alert{Reihenfolge} von Knoten um eine Facette bleibt erhalten + \end{itemize} + + \begin{figure} + \begin{tikzpicture}[auto] + \foreach \pos/\name in {{(0,0)/a}, {(-3, 1)/b}, {(3, 1)/c},{(-2, 3)/d}, + {(2,2.5)/e}} + \node[small vertex] (\name) at \pos {}; - \draw[dashed] (d) -- (-2, 4); - \draw[dashed] (d) -- (-1, 2.5); - \draw[dashed] (e) -- (2.5, 3); - \draw[dashed] (e) -- (1.5, 3.5); - - \begin{pgfonlayer}{background} - \fill[red!50] (a.center) -- (b.center) -- (d.center); - \fill[red!50] (a.center) -- (c.center) -- (e.center); - \end{pgfonlayer} - \end{tikzpicture} - \end{figure} + \foreach \source/ \dest in {a/b, a/c, c/e, b/d, + a/d, e/a} + \path[edge] (\source) -- (\dest); + + \draw[dashed] (d) -- (-2, 4); + \draw[dashed] (d) -- (-1, 2.5); + \draw[dashed] (e) -- (2.5, 3); + \draw[dashed] (e) -- (1.5, 3.5); + + \begin{pgfonlayer}{background} + \fill[red!50] (a.center) -- (b.center) -- (d.center); + \fill[red!50] (a.center) -- (c.center) -- (e.center); + \end{pgfonlayer} + \end{tikzpicture} + \end{figure} \end{frame} \begin{frame} - \frametitle{Segmente} - \begin{columns}[T] - \begin{column}{.6\textwidth} - \begin{itemize} - \item Jede Kante eines Blocks ist Teil von mindestens einem Kreis - \item Kreise enthalten \alert{Segmente} - \begin{itemize} - \item Kanteninduzierte Teilgraphen - \item Mindestens zwei Aufhängungnen (\emph{attachments}) - \end{itemize} - \item \alert{Kompatible} Segmente können auf der selben Facette gezeichnet werden. - \vspace{1.5em} - \item<2> Sehne (\emph{chord}) - \item<3> Teilgraph als Segment - \end{itemize} - \end{column} - \begin{column}{.4\textwidth} -\begin{figure} -\begin{tikzpicture}[auto, scale=0.8] - \foreach \pos/\name in {{(0,0)/a}, {(0,2)/b}, {(4,0)/c},{(4,2)/d}, - {(0,4)/e}, {(4,4)/f}, - {(0,6)/g}, {(0,8)/h},{(4,6)/i},{(4,8)/k}, - {(1.5,1)/l}, {(2.5,1)/m}, {(2,2)/n}} - \node[vertex] (\name) at \pos {}; - - \foreach \source/ \dest in {a/b, a/c, c/d, - b/e, d/f, - e/g, g/h, h/k, k/i, i/f, - g/k, h/f, - l/m, m/n, n/l, a/l, m/d} - \path[edge] (\source) -- (\dest); - - \foreach \vertex / \fr in {g/2, k/2, h/2, f/2, - l/3, m/3, n/3, a/3, d/3 - } - \path<\fr> node[selected vertex] at (\vertex) {}; - - \begin{pgfonlayer}{background} - \foreach \source / \dest / \fr in {g/k/2, h/f/2, - l/m/3, m/n/3, n/l/3, a/l/3, m/d/3 - } - \path<\fr>[selected edge] (\source) -- (\dest); - \end{pgfonlayer} -\end{tikzpicture} -\end{figure} -\vspace{1em} - \end{column} - \end{columns} + \frametitle{Segmente} + \begin{columns}[T] + \begin{column}{.6\textwidth} + \begin{itemize} + \item Jede Kante eines Blocks ist Teil von mindestens einem Kreis + \item Kreise enthalten \alert{Segmente} + \begin{itemize} + \item Kanteninduzierte Teilgraphen + \item Mindestens zwei Aufhängungnen (\emph{attachments}) + \end{itemize} + \item \alert{Kompatible} Segmente können auf der selben Facette gezeichnet werden. + \vspace{1.5em} + \item<2> Sehne (\emph{chord}) + \item<3> Teilgraph als Segment + \end{itemize} + \end{column} + \begin{column}{.4\textwidth} + \begin{figure} + \begin{tikzpicture}[auto, scale=0.8] + \foreach \pos/\name in {{(0,0)/a}, {(0,2)/b}, {(4,0)/c},{(4,2)/d}, + {(0,4)/e}, {(4,4)/f}, + {(0,6)/g}, {(0,8)/h},{(4,6)/i},{(4,8)/k}, + {(1.5,1)/l}, {(2.5,1)/m}, {(2,2)/n}} + \node[vertex] (\name) at \pos {}; + + \foreach \source/ \dest in {a/b, a/c, c/d, + b/e, d/f, + e/g, g/h, h/k, k/i, i/f, + g/k, h/f, + l/m, m/n, n/l, a/l, m/d} + \path[edge] (\source) -- (\dest); + + \foreach \vertex / \fr in {g/2, k/2, h/2, f/2, + l/3, m/3, n/3, a/3, d/3 + } + \path<\fr> node[selected vertex] at (\vertex) {}; + + \begin{pgfonlayer}{background} + \foreach \source / \dest / \fr in {g/k/2, h/f/2, + l/m/3, m/n/3, n/l/3, a/l/3, m/d/3 + } + \path<\fr>[selected edge] (\source) -- (\dest); + \end{pgfonlayer} + \end{tikzpicture} + \end{figure} + \vspace{1em} + \end{column} + \end{columns} \end{frame} \begin{frame} - \frametitle{Kompatibilität} - \begin{Lemma} - Zwei Segmente sind genau dann \alert{kompatibel}, wenn ihre Aufhängungen nicht verflochten (\emph{interleaved}) sind. - \end{Lemma} - - \vspace{2em} - - \begin{theorem}<2> - Ein \alert{2-zusammenhängender} Graph mit Kreis $C$ ist planar genau dann wenn - \begin{itemize} - \item Der \alert{Verflechtungsgraph} der Segmente von C \alert{bipartit} ist - \item Für alle Segmente $P$ der Graph \alert{$P \cup C$ planar} ist - \end{itemize} - \end{theorem} + \frametitle{Kompatibilität} + \begin{Lemma} + Zwei Segmente sind genau dann \alert{kompatibel}, wenn ihre Aufhängungen nicht verflochten (\emph{interleaved}) sind. + \end{Lemma} + + \vspace{2em} + + \begin{theorem}<2> + Ein \alert{2-zusammenhängender} Graph mit Kreis $C$ ist planar genau dann wenn + \begin{itemize} + \item Der \alert{Verflechtungsgraph} der Segmente von C \alert{bipartit} ist + \item Für alle Segmente $P$ der Graph \alert{$P \cup C$ planar} ist + \end{itemize} + \end{theorem} \end{frame} \begin{frame} - \frametitle{Auslander-Parter} - \begin{block}{Algorithmus} - Rekursives Betrachten der Kreise und Teilgraphen mit drei Fällen: - \begin{itemize} - \item \textbf{Trivialer Fall} Der Graph $G$ ist ein einfacher Kreis $C$. Tritt nur am Anfang auf. - \item \textbf{Basisfall} Der Kreis $C$ enthält ein einziges Segment, das ein Pfad ist. - \item \textbf{Rekursionsfall} Ein Kreis mit mehreren Segmenten oder Subgraphen ist in $G$ enthalten. Anwendung des Theorems und rekursive Abarbeitung der Subgraphen. - \end{itemize} - \end{block} - - \vspace{0.5em} - \begin{itemize} - \item $\Oh(n)$ Rekursionen mit Verflechtungsgraphen in $\Oh(n^2)$\\ - \item Gesamtkomplexität $\Oh(n^3)$ - \end{itemize} + \frametitle{Auslander-Parter} + \begin{block}{Algorithmus} + Rekursives Betrachten der Kreise und Teilgraphen mit drei Fällen: + \begin{itemize} + \item \textbf{Trivialer Fall} Der Graph $G$ ist ein einfacher Kreis $C$. Tritt nur am Anfang auf. + \item \textbf{Basisfall} Der Kreis $C$ enthält ein einziges Segment, das ein Pfad ist. + \item \textbf{Rekursionsfall} Ein Kreis mit mehreren Segmenten oder Subgraphen ist in $G$ enthalten. Anwendung des Theorems und rekursive Abarbeitung der Subgraphen. + \end{itemize} + \end{block} + + \vspace{0.5em} + \begin{itemize} + \item $\Oh(n)$ Rekursionen mit Verflechtungsgraphen in $\Oh(n^2)$\\ + \item Gesamtkomplexität $\Oh(n^3)$ + \end{itemize} \end{frame} \end{document}