Changeset 169 for liacs/SCA2010

Timestamp:

Aug 3, 2010, 11:35:14 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Aanpassingen naar aanleiding van Verbeteringen en suggesties Hendrik Jan Hoogeboom

Location:

liacs/SCA2010/BDD

Files:

• report.pdf (modified) ( previous)
• report.tex (modified) (13 diffs)

liacs/SCA2010/BDD/report.tex

@@ -24 +24 @@
   \tikz[baseline=(C.base)]\node[draw,rectangle,rounded corners,inner sep=0.5pt](C) {$#1$};\!
 }
-\newcommand*\BDD{\emph{BDD}}
-\newcommand*\BDDs{\emph{BDDs}}
+\newcommand*\BDD{\emph{BDD} }
+\newcommand*\BDDs{\emph{BDDs} }
 
 \author{Rick van der Zwet, Universiteit Leiden}
@@ -42 +42 @@
 aanleiding van het vak Seminar Combinatorial Algorithms 2010~\cite{SCA2010}. 
 \begin{figure}[htbp]
+\caption{fig:samenvoegen}
 \begin{tikzpicture}[on grid]
 \tikzstyle{true}=[]
@@ -169 +170 @@
 ontbrekende laag van knopen heeft, waardoor knopen van alle niveaus beschikbaar
 zijn. Op het moment dat de $\diamond$ ingevuld gaat worden is het ook zaak om
-de bladeren (zie vergelijking~\ref{bladeren}) te vereenvoudigen} \end{figure}
+de bladeren (zie vergelijking~\ref{bladeren}) te vereenvoudigen.} \end{figure}
 
 \section{Introductie BDD}
@@ -180 +181 @@
 \BDDs aan de basis staat van het uitdrukken van complexe systemen door
 middel van gecombineerde simpele functies. In Hoofdstuk~\ref{werking} zal deze
-techniek uitgelegd worden, het zogenoemde \emph{smelten} (\emph{melding}) dat 
-in Hoofdstuk~\ref{voorbeeld} toegepast zal worden in een concreet voorbeelden.
+techniek uitgelegd worden, het zogenoemde \emph{smelten} (\emph{melding}), dat 
+in Hoofdstuk~\ref{voorbeeld} toegepast zal worden in voorbeelden.
 
 \section{Samenvoegen van \BDD}
 \label{werking}
-De term voor het samenvoegen van \BDD structuren zullen we smelten
+De term voor het samenvoegen van \BDD structuren zullen we \emph{smelten}
 (\emph{melding}) noemen. Het werkt volgens de volgende principes.  Men neme
 twee knopen $\alpha = (v,l,h)$ en $\alpha' = (v',l',h')$. De knoop $\alpha
-\diamond \alpha'$, de ``\emph{emulsie}'' (\emph{meld}) van $\alpha$ en
-$\alpha'$, is dan als volgt gedefinieerd als $\alpha$ en $\alpha'$ niet beiden
-bladeren (\emph{sinks}) zijn:
+\diamond \alpha'$, het resultaat van de \emph{smelt} actie, de
+``\emph{emulsie}'' (\emph{meld}) van $\alpha$ en $\alpha'$, is dan als volgt
+gedefinieerd als $\alpha$ en $\alpha'$ niet beide bladeren (\emph{sinks})
+zijn:
 \begin{equation}
 \label{melt-eq}
@@ -197 +199 @@
 (v, l \diamond l', h \diamond h'), & \mathrm{als~} v = v'; \\
 (v, l \diamond \alpha', h \diamond \alpha'), & \mathrm{als~} v < v'; \\
-(v, \alpha \diamond l', \alpha \diamond h'), & \mathrm{als~} v > v'. \\
+(v', \alpha \diamond l', \alpha \diamond h'), & \mathrm{als~} v > v'. \\
 \end{array} \right.
 \end{equation}
+Als we deze recursieve formule gebruiken op de wortels van twee \BDDs $f$ en
+$g$, vinden we een diagram dat het paar $(f,g)$ representeert.
 
 De oplettende lezer zal zien dan als je Formule~\ref{melt-eq} toepast op de
 bladeren er door samenvoegen van de bladeren ---zie bijvoorbeeld
-voorbeeld in Hoofstuk~\ref{voorbeeldSamenvoegen}--- in plaats van de twee bladeren
+voorbeeld in Figuur~\ref{fig:samenvoegen}--- in plaats van de twee bladeren
 $\top$ en $\bot$, er nu vier bladeren mogelijk zijn:
 \begin{equation}
@@ -213 +217 @@
 Om er weer een ``valide'' \BDD van te maken zullen deze bladeren vervangen
 worden door het uitgerekende blad. Als bijvoorbeeld de $\diamond$ operatie
-bedoelt is voor een \emph{EN} operatie, wordt de blad-rij in~\ref{bladeren}
+bedoelt is voor een \emph{EN} operatie, wordt de blad-rij in~(\ref{bladeren})
 vervangen door de rij $\bot, \bot, \bot, \top$. Nu is het zaak het \BDD
 te vereenvoudigen, om zo duplicaat-bladeren te snoeien (\emph{pruning}).
@@ -232 +236 @@
 \diamond \alpha'$ in rij $\alpha$ en column $\alpha'$. (b) Vervang de bladeren
 (zie Formule~\ref{bladeren}) door $\bot$ en $\top$, en (c) voer het algoritme
-$R$\footnote{Algoritme $R$ wordt niet in deze samenvatting behandeld; de
-vak-website~\cite{SCA2010} heeft een referentie naar algoritme $R$ 
-\url{http://www.liacs.nl/~kosters/semcom/tomb.pdf} welke behandeld wordt
-door Tom.} op $f \diamond g$. Op het eerste gezicht lijkt algoritme $R$ er ongeveer
+$R$\footnote{Algoritme $R$ wordt niet in deze samenvatting behandeld; zie de
+vak-website~\cite{SCA2010} waar het algoritme $R$ behandeld wordt door Tom.} op
+$f \diamond g$. Op het eerste gezicht lijkt algoritme $R$ er ongeveer
 $B(f)B(g)$ operaties over te doen, maar doordat je onbereikbare knopen niet
 hoeft te evalueren zal je uitkomen op $B(f \diamond g)$.
@@ -252 +255 @@
 \label{voorbeeldSamenvoegen}
 Het volgende voorbeeld is een uitwerking van opgave 60~\cite[p.~130]{DK2009}
-de offi\"{e}le uitwerking is te vinden op \cite[p~.195]{DK2009}
+de offici\"{e}le uitwerking is te vinden op \cite[p.~195]{DK2009}
 \\ \\
 Voorgaande aan de uitwerking is het belangrijk te weten wat een \emph{QDD} (aka
 \emph{quasi-BDD}~\cite[p.~102-103]{DK2009}) is. Elke functie heeft een unieke
 \emph{QDD} welke lijkt op een \BDD echter is de start-knoop altijd
-\circled{1} en elke \circled{k} knoop bestaat for $k < n$ takken naar twee
+\circled{1} en elke \circled{k} knoop heeft (voor $k < n$) takken naar twee
 \squared{k+1} knopen. Wat in het kort wilt zeggen dat elk pad van de
 start-knoop naar de bladeren een lengte heeft van $n$. Om dat mogelijk te maken
 mogen de \emph{HOOG} en \emph{LAAG} takken van een \emph{QDD} gelijk zijn. Let
-wel op dat reductie toegepast moet worden. 
+wel op dat reductie toegepast moet worden op tweetallen knopen waarvan de
+\emph{HOOG} en \emph{LAAG} pointers gelijk zijn. 
 \\ \\
 Neem aan dat $f(x_{1},\dots,x_{n})$ en $g(x_{1},\dots,x_{n})$ de respectieve
 \emph{profielen} (\emph{profiles})~\cite[p.~101]{DK2009}
-$(b_{0},\dots,b_{n})$ ---waar $b_{k}$ met $0 \le k < n$ de knopen zijn die splitsen
+$(b_{0},\dots,b_{n})$ ---waar $b_{k}$ met $0 \le k < n$ de knopen zijn. Die splitsen
 op variable $f(x_{k+1})$ en $b_{n}$ het aantal bladeren is--- en
 $(b'_{0},\dots,b_{n})$ hebben, en de respectieve \emph{quasi-profielen}
@@ -272 +276 @@
 de \emph{QDD} van $f$ is--- en $(q'_{0},\dots,q'_{n})$.  
 
-Om te laten zijn dat de gesmolten $f \diamond g$ het aantal knopen
+Om te laten zien dat de gesmolten $f \diamond g$ het aantal knopen
 \begin{equation}
 \label{eq:knopen}
@@ -279 +283 @@
 bevat moet gekeken worden naar het aantal \emph{beads}~\cite[p.~72]{DK2009} dat
 mogelijkerwijs gemaakt kan worden van de functies $f$ en $g$.  
-Voor een willikeurige functie $n$ met als profiel $(b_{0},\dots,b_{n})$ en
-quasi-profiel $(q_{0},\dots,q_{n})$ geldt dat $B(q_{0},\dots,q_{n}) \geq
-B(b_{0},\dots,b_{n})$. En tevens dan $(b_{0},\dots,b_{n}) \subseteq
-(q_{0},\dots,q_{n})$. Hieruit volgt dat een geen-bead zich bevindt in
+Voor een willekeurige functie $f$ met als profiel $(b_{0},\dots,b_{n})$ en
+quasi-profiel $(q_{0},\dots,q_{n})$ geldt dat $B(b_{0},\dots,b_{n}) \leq
+B(q_{0},\dots,q_{n})$. En tevens dan $(b_{0},\dots,b_{n}) \subseteq
+(q_{0},\dots,q_{n})$. Hieruit volgt dat een niet-bead zich bevindt in
 $(q_{0},\dots,q_{n}) - (b_{0},\dots,b_{n})$.
 
 Elke bead van de orde $n - j$ in het geordende paar $(f,g)$ zal zich
 bevinden in een van de volgende groepen; (a) de standaard-combinatie van de
-$b_{j}b_{j}'$ geordende beats van $(f,g)$ of (b) de gegenereerde reeks van een
-(bead,geen-bead) of (geen-bead, bead) $b_{j}(q_{j}' - b_{j}') + (q_{j} -
+$b_{j}b_{j}'$ geordende beads van $(f,g)$ of (b) de gegenereerde reeks van een
+(bead,niet-bead) of (niet-bead, bead) $b_{j}(q_{j}' - b_{j}') + (q_{j} -
 b{j})b_{j}'$. 
 
@@ -298 +302 @@
 \label{voorbeeldPlakken}
 Het volgende voorbeeld is een uitwerking van opgave 63~\cite[p.~131]{DK2009}
-de offi\"{e}le uitwerking is te vinden op \cite[p.~195]{DK2009}.
+de offici\"{e}le uitwerking is te vinden op \cite[p.~195]{DK2009}.
+
+De $2^{m}$-weg multiplexer $M_{m}(y_{1},\dots,y_{m};y_{m+1},\dots,y_{m+2^{m}})$
+geeft bij input $y_{1},\dots,y_{m}$ de waarde van variable $y_{m+k}$ waarbij $k$
+het getal is gerepresenteerd door $y_{1},\dots,y_{m}$,
+zie~\cite[7.1.2-(31)]{DK2009-0}. Hiermee defineren we $\oplus$
+de binary operator \emph{XOR} en $n = 2m + 2^{m}$.
 
 \begin{equation}
@@ -307 +317 @@
 \label{eq:opgave63}
 \end{equation}
-In Vergelijking~\ref{eq:opgave63} zijn $f$ en $g$ gedefinieerd, waarbij $\oplus$
-de binary operator \emph{XOR} is en $n = 2m + 2^{m}$.
 
 Dan is $B(f) = 2^{m+2}-1 \approx 4n$, $B(g) = 2^{m+1}-2^{m} \approx 3n$ en $B(g
@@ -315 +323 @@
 daarna met sommering van deze tot de antwoorden te komen. Als eerste moet
 opgemerkt worden dat zowel $f$ als $g$ $2^m$-weg
-multiplexers~\cite[7.1.2-(31)]{DK2009-0} zijn voor welke de profielen zijn
-$(1,2,2,\dots,2^{m-1},2^{m-1},2^m,1,1,\dots,1.2)$ respectievelijk
-$(0,1,2,2,\dots,2^{m-1},2^{m-1},1,1,\dots,1,2$. Dit optellen en afschatten wordt
+multiplexers zijn voor welke de profielen zijn
+$(1,2,2,\dots,2^{m-1},2^{m-1},2^m,1,1,\dots,1,2)$ respectievelijk \\
+$(0,1,2,2,\dots,2^{m-1},2^{m-1},1,1,\dots,1,2)$. Dit optellen en afschatten wordt
 (zie ook~\cite[p.~82]{DK2009}) $B(f) = 2^{m+2} - 1 \approx 4n$ en $B(g) =
 2^{m+1} - 1 \approx 3n$. \\
 \\
-De bereking $B(f \land g)$ wordt aanzienlijk moeilijker. We constateren eerst
-dat er een unieke oplossing bestaat ---de oplossing kan aan een uniek getal
-gekoppeld worden---
+De bereking $B(f \land g)$ (de werking van de multiplexer) wordt aanzienlijk
+moeilijker en zal daarom aangestipt worden. We constateren eerst dat er een
+unieke oplossing bestaat ---de oplossing kan aan een uniek getal
+gekoppeld worden namelijk de invoer---
 in de vorm van $x_1 \dots
 x_{2m}$ als je $((x_1 \oplus x_2)(x_3 \oplus x_4) \dots (x_{2m-1} \oplus
 x_{2m}))_{2} = p,((x_2 \oplus x_3) \dots (x_{2m-2} \oplus x_{2m-1})x_{2m})_{2}
 = q$, waar $0 \leq p, q \le 2^m$ en $p=q$ dan en slechts als $x_1 = x_3 = \dots
-= 2_{2m-1} = 0$.  Dit zorgt dat  het eerste deel ---het stuk voor de punt
+= x_{2m-1} = 0$.  Dit zorgt dat  het eerste deel ---het stuk voor de punt
 komma--- van het profiel van $f \land g$ geschreven kan worden als $(1, 2, 4,\dots,
 2^{2m-2}, 2^{2m-1} - 2^{m-1})$.