Changeset 164 for liacs/SCA2010/BDD

Timestamp:

Jul 27, 2010, 10:04:48 AM (14 years ago)

Author:

Rick van der Zwet

Message:

First block of corrections

File:

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

liacs/SCA2010/BDD/report.tex

@@ -30 +30 @@
 \section{Inleiding}
 De hierin besproken inhoud is een samenvatting gemaakt van pagina 86--88 en de
-daarin genoemde opgave 60 en 63 uit het college boek~\cite{DK2009} na
+daarin genoemde opgave 60 en 63 uit het college boek~\cite{DK2009} naar
 aanleiding van het vak Seminar Combinatorial Algorithms 2010~\cite{SCA2010}. 
 \begin{figure}[htbp]
+\label{voorbeeldSamenvoegen}
 \begin{tikzpicture}[on grid]
 \tikzstyle{true}=[]
@@ -157 +158 @@
 \end{tikzpicture}
 \caption{Voorbeeld: twee \emph{BDD}s die samengesmolten worden door gebruik te
-maken van formule~\ref{melt-eq}. Let wel op dat dit voorbeeld geen ontbrekende
-laag van nodes heeft, waardoor nodes 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}
+maken van formule~\ref{melt-eq}. Let er wel op dat dit voorbeeld geen
+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}
 
 \section{Introductie BDD}
-Synthese van een Binary Decision Diagram \emph{BDD} is het belangrijke
-\emph{BDD} algoritme~\cite[pg 86]{DK2009}. Welke in essentie een \emph{BDD}
-functie,$f$, pakt en deze combineert met een andere \emph{BDD} functie,$g$,
-zodanig dat er een nieuwe \emph{BDD} ontstaat voor de nieuwe functie.
-Bijvoorbeeld $f \wedge g$ of $f \oplus g$.
+Synthese van een Binary Decision Diagram \emph{BDD} is een belangrijk
+\emph{BDD} algoritme~\cite[p.~86]{DK2009}. Het neemt in essentie een \emph{BDD}
+functie $f$ en combineert deze met een andere \emph{BDD} functie $g$
+zodanig dat er een nieuwe \emph{BDD} ontstaat voor een nieuwe functie,
+bijvoorbeeld $f \wedge g$ of $f \oplus g$.
 De reden dat dit zo belangrijk is komt met het feit dat het combineren van
-\emph{BDD}s aan de basis staat aan het uitdrukken van complexe systemen dmv van
-gecombineerde simpele functies. In sectie~\ref{werking} zal deze techniek
-uitgelegd worden, het zogenoemde \emph{smelten} (\emph{melding}) welke in
-sectie~\ref{voorbeeld} dit toegepast zal worden in een concreet voorbeelden.
+\emph{BDD}s 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.
 
 \section{Samenvoegen van \emph{BDD}}
 \label{werking}
-De term voor het samenvoegen \emph{BDD} structuren zullen we smelten
-(\emph{melding}) noemen. Er werkt volgens de volgende principes.  Men neme
-$\alpha = (v,l,h)"$ en $\alpha' = (v',l',h')$. De $\alpha \diamond \alpha'$, de
-"\emph{emulsie}" (\emph{meld}) van $\alpha$ en $\alpha'$, is dan als volgt
-gedefinieerd als $\alpha$ ad $\alpha'$ niet beiden bladeren (\emph{sinks}) zijn:
+De term voor het samenvoegen van \emph{BDD} structuren zullen we 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:
 \begin{equation}
 \label{melt-eq}
 \alpha \diamond \alpha' = \left\{
 \begin{array}{l l}
-(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, 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'. \\
 \end{array} \right.
 \end{equation}
 
-De oplettende lezer (voor de rest, voorbeeld figuur~\ref{voorbeeldSamenvoegen}) zal
-zien dat je door het samenvoegen van de bladeren er in plaats van de twee bladeren
+De oplettende lezer zal zien dan als je Formule~\ref{melt-eq} toepast op de
+bladeren er door samenvoegen van de bladeren ---zie bijvoorbeeld
+Figuur~\ref{voorbeeldSamenvoegen}--- in plaats van de twee bladeren
 $\top$ en $\bot$, er nu vier bladeren mogelijk zijn:
 \begin{equation}
@@ -200 +203 @@
 \end{array}
 \end{equation}
-Om er weer een 'valide' \emph{BDD} van te maken zullen deze bladeren vervangen
-worden door het uitgerekende blad. Als bijvoorbeeld de $\diamond$ operatie een
-$EN$ operatie was, wordt de blad-rij in~\ref{bladeren} vervangen door de rij
-$\bot, \bot, \bot, \top$. Nu is het zaak de \emph{BDD} te vereenvoudigen, om zo
-duplicaat bladeren te snoeien (\emph{pruning}).
-
-De kracht van deze aanpak zit hem in de zogenoemde generieke $\diamond$
+Om er weer een ``valide'' \emph{BDD} van te maken zullen deze bladeren vervangen
+worden door het uitgerekende blad. Door bijvoorbeeld voor de $\diamond$ operatie een
+\emph{EN} operatie te nemen, wordt de blad-rij in~\ref{bladeren} vervangen door de rij
+$\bot, \bot, \bot, \top$. Nu is het zaak het \emph{BDD} te vereenvoudigen, om zo
+duplicaat-bladeren te snoeien (\emph{pruning}).
+
+De kracht van deze aanpak zit hem in de generieke $\diamond$
 operatie. Het maakt niet uit welke booleaanse operatie er gebruikt wordt aan
-het eind van de rit. De gegeneerde gesmolten \emph{BDD} is geldig voor allen.
+het eind van de rit. De gegeneerde gesmolten \emph{BDD} is geldig voor alle.
 
 Kijkend naar de limieten moet geoordeeld worden kan hetzelfde altijd bereikt
@@ -304 +307 @@
 
 \begin{thebibliography}{}
-\bibitem[DK2009]{DK2009} D.E. Knuth. Fascicle 1. \texttt{Bitwise Tricks \&
-Techniques; Binary Decision Diagrams}, volume 4 of \texttt{The Art of Computer
-Programming}. Pearson Education, first edition, March 2009.
-\bibitem[DK2009-Fas0]{DK2009-0} D.E. Knuth. Fascicle 0. \texttt{Bitwise Tricks \&
-Techniques; Binary Decision Diagrams}, volume 4 of \texttt{The Art of Computer
-Programming}. Pearson Education, first edition, March 2009.
+\bibitem[DK2009]{DK2009} D.E. Knuth. Bitwise Tricks \& Techniques; Binary
+Decision Diagrams, volume 4, Fascicle 1, of The Art of Computer Programming.
+Pearson Education, first edition, 2009.
+\bibitem[DK2009-Fas0]{DK2009-0} D.E. Knuth. Bitwise Tricks \& Techniques;
+Binary Decision Diagrams, volume 4, Fascicle 0, of The Art of Computer
+Programming. Pearson Education, first edition, 2009.
 \bibitem[SCA2010]{SCA2010} Lecture Seminar Combinatorial Algorithms, 
-\url{http://www.liacs.nl/~kosters/semcom/}, dr. W.A. (Walter) Kosters, LIACS,
-Spring 2010
+\url{http://www.liacs.nl/~kosters/semcom/}, W.A. (Walter) Kosters, LIACS,
+Spring 2010.
 
 \end{thebibliography}