Changeset 137

Timestamp:

Jul 1, 2010, 1:06:58 AM (14 years ago)

Author:

Rick van der Zwet

Message:

Figuren werkend. Kinder bedijd

File:

• liacs/SCA2010/BDD/report.tex (modified) (3 diffs)

liacs/SCA2010/BDD/report.tex

@@ -13 +13 @@
 \usepackage{fancybox}
 \usepackage{amssymb,amsmath}
+\usepackage{subfig}
+\usepackage{tikz}
+\usetikzlibrary{scopes}
+\usetikzlibrary{positioning}
 
 \author{Rick van der Zwet, Universiteit Leiden}
@@ -28 +32 @@
 daarin genoemde opgave 60 en 63 uit het college boek~\cite{DK2009} na
 aanleiding van het vak Seminar Combinatorial Algorithms 2010~\cite{SCA2010}. 
-
+\begin{figure}[htbp]
+\begin{tikzpicture}[on grid]
+\tikzstyle{true}=[]
+\tikzstyle{false}=[dashed]
+\tikzstyle{state}=[circle, draw]
+\tikzstyle{leaf}=[rectangle, draw]
+\begin{scope}[xshift=0cm,node distance=10mm and 10mm]
+\node (1) [state]{1};
+\node (2) [state, below=of 1]{2};
+\node (3) [state, below=of 2]{3};
+\node (4) [state, below=of 3]{4};
+\node (F) [leaf, below left=of 4]{$\bot$};
+\node (T) [leaf, below right=of 4]{$\top$};
+\path[-]
+(1) edge[false] (2)
+(1) edge[true, bend left=45] (3)
+(2) edge[false, bend right=45] (F)
+(2) edge[true] (3)
+(3) edge[false] (4)
+(3) edge[true, bend left=45] (T)
+(4) edge[true] (T)
+(4) edge[false] (F)
+;
+\draw[left, inner sep=6mm]
+(1) node {$\alpha$}
+(2) node {$\beta$}
+(3) node {$\gamma$}
+(4) node {$\delta$}
+;
+\end{scope}
+
+\begin{scope}[xshift=9cm,node distance=10mm and 10mm]
+\node (1) [state]{1}; 
+\node (2-1) [state, below left=of 1]{2};
+\node (2-2) [state, below right=of 1]{2};
+\node (3) [state, below left=of 2-2]{3};
+\node (4-1) [state, below left=of 3]{4}; 
+\node (4-2) [state, below right=of 3]{4};
+\node (F) [leaf, below=of 4-1]{$\bot$};
+\node (T) [leaf, below=of 4-2]{$\top$};
+\path[-]
+(1) edge[false] (2-1)
+(1) edge[true] (2-2)
+(2-1) edge[false] (3)
+(2-1) edge[true, bend left=70] (T)
+(2-2) edge[false, bend left=45] (T)
+(2-2) edge[true] (3)
+(3) edge[false] (4-1)
+(3) edge[true] (4-2)
+(4-1) edge[false] (T)
+(4-1) edge[false] (F)
+(4-2) edge[false] (T)
+(4-2) edge[true] (F)
+;
+\draw[left, inner sep=4mm]
+(1) node {$\omega$}
+(2-1) node {$\chi$}
+(2-2) node {$\psi$}
+(3) node {$\varphi$}
+(4-1) node {$\tau$}
+(4-2) node {$\upsilon$}
+;
+\end{scope}
+
+\begin{scope}[xshift=5cm,yshift=-5cm, node distance=15mm and 20mm]
+\node (1) [state]{1}; 
+\node (2-1) [state, below left=of 1]{2};
+\node (2-2) [state, below right=of 1]{2};
+\node (3-1) [state, below left=of 2-1]{3};
+\node (3-2) [state, below left=of 2-2]{3};
+\node (3-3) [state, below right=of 2-2]{3};
+\node (4-1) [state, below left=of 3-1]{4};
+\node (4-2) [state, below=of 3-1]{4};
+\node (4-3) [state, below left=of 3-2]{4};
+\node (4-4) [state, below left=of 3-3]{4};
+\node (4-5) [state, below right=of 3-3]{4};
+\node (FT) [leaf, below right=of 4-1]{};
+\node (FF) [leaf, below right=of 4-2]{};
+\node (TT) [leaf, below=of 4-4]{};
+\node (TF) [leaf, below=of 4-5]{};
+\path[-]
+(1) edge[false] (2-1)
+(1) edge[true] (2-2)
+(2-1) edge[false] (3-1)
+(2-1) edge[true]  (3-2)
+(2-2) edge[false] (3-2)
+(2-2) edge[true]  (3-3)
+(3-1) edge[false] (4-1)
+(3-1) edge[true]  (4-2)
+(3-2) edge[false] (4-3)
+(3-2) edge[true,bend left=90]  (TT)
+(3-3) edge[false] (4-4)
+(3-3) edge[true]  (4-5)
+(4-1) edge[false] (FF)
+(4-1) edge[true]  (FT)
+(4-2) edge[false] (FT)
+(4-2) edge[true]  (FF)
+(4-3) edge[false] (FT)
+(4-3) edge[true]  (TT)
+(4-4) edge[false] (FF)
+(4-4) edge[true]  (TT)
+(4-5) edge[false] (TT)
+(4-5) edge[true]  (TF)
+;
+\draw[left, inner sep=6mm]
+(1) node {$\alpha \diamond \omega$}
+(2-1) node {$\beta \diamond \chi$}
+(2-2) node {$\gamma \diamond \psi$}
+(3-1) node {$\bot \diamond \varphi$}
+(3-2) node {$\gamma \diamond \top$}
+(3-3) node {$\gamma \diamond \varphi$}
+(4-1) node {$\bot \diamond \tau$}
+(4-2) node {$\bot \diamond \upsilon$}
+(4-3) node {$\delta \diamond \top$}
+(4-4) node {$\delta \diamond \tau$}
+(4-5) node {$\top \diamond \upsilon$}
+(FF) node {$\bot \diamond \bot$}
+(FT) node {$\bot \diamond \top$}
+(TF) node {$\top \diamond \bot$}
+(TT) node {$\top \diamond \top$}
+;
+\end{scope}
+
+\end{tikzpicture}
+\caption{Voorbeeld: twee \emph{BDD}s die samengesmolten worden}
+\end{figure}
 
 \section{Introductie BDD}
@@ -132 +261 @@
 Dan is $B(f) = 2^{m+2}-1 \approx 4n$, $B(g) = 2^{m+1}-2^{m} \approx 3n$ en $B(g
 \hat f) = 2^{m+1}+2^{m-1}-1 \approx 2n^{2}$. Om aan deze 'magische' reeksen te
-komen is het belangrijk eerst naar de profielen te kijken.
+komen is het belangrijk eerst naar de profielen te kijken van $f$ en $g$ om daarna met sommering van deze tot de antwoorden te komen.