Changeset 165 for liacs/SCA2010/BDD

Timestamp:

Jul 27, 2010, 11:20:34 AM (14 years ago)

Author:

Rick van der Zwet

Message:

Some more corrections we are almost at the end

File:

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

liacs/SCA2010/BDD/report.tex

@@ -204 +204 @@
 \end{equation}
 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}).
+worden door het uitgerekende blad. Als bijvoorbeeld de $\diamond$ operatie
+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 \emph{BDD}
+te vereenvoudigen, om zo duplicaat-bladeren te snoeien (\emph{pruning}).
 
 De kracht van deze aanpak zit hem in de generieke $\diamond$
@@ -213 +213 @@
 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
-worden door in het slechte geval de \emph{BDD}s achter elkaar te plakken welke
-dan in dit geval $B(f)B(g)$ knopen oplevert. Voorbeeld~\ref{voorbeeldPlakken}
-is hier een geval van. In het meer algemene geval geldt meestal $B(f) + B(g)$.
-Deze grenzen worden in voorbeeld~\ref{voorbeeldSamenvoegen} aangescherpt.
+Door de \emph{BDD}s achter elkaar te plakken kan met maximaal $B(f)B(g)$ knopen
+een \emph{BDD} voor $f \diamond g$ gerealiseerd worden.
+Hoofdstuk~\ref{voorbeeldPlakken} is hier een voorbeeld van. In het meer algemene
+geval geldt meestal $B(f) + B(g)$ als bovengrens.  Deze grenzen worden in
+Hoofdstuk~\ref{voorbeeldSamenvoegen} aangescherpt.
 
 Het smelten ligt aan de basis van de daadwerkelijke synthese. Een simpele
-variant kan gemaakt worden met algoritme $R$. Maak eerst een reeks van
-alle knopen $\alpha$ in $B(f)$ en $\alpha'$ in $B(g)$ met knoop $\alpha
-\diamond \alpha'$ in rij $\alpha$ en column $\alpha'$. Vervang de bladeren
-(\ref{bladeren}) door $\bot$ en $\top$. En voor algoritme $R$ uit op $f \diamond
-g$. Op het eerste gezicht lijkt algoritme $R$ er ongeveer $B(f)B(g)$ over te
-doen, maar doordat je onbereikbare knopen niet hoeft te evalueren zal je
-uitkomen op $B(f \diamond g)$.
-
-Deze 'truc' zorgt ervoor dat de tijd binnen de perken blijft, maar er is dan
-nog niets gezegd over de hoeveelheid geheugen er nodig is. Omdat er nu
+impementatie kan gemaakt worden met algoritme $R$. (a) Maak eerst een reeks van
+alle knopen $\alpha$ in $f$ en $\alpha'$ in $g$ met knoop $\alpha
+\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
+$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)$.
+
+Deze ``truc'' zorgt ervoor dat de tijd binnen de perken blijft, maar er is dan
+nog niets gezegd over de hoeveelheid geheugen die nodig is. Omdat er nu
 $B(f)B(g)$ knopen in geheugen gehouden moet wordt zal dit problemen opleveren
-bij kleine en grotere algoritmen. Om deze efficiëntie aan te pakken is
-algoritme $S$ \footnote{Algoritme $S$ wordt niet in deze samenvatting gehandeld
-de vak-website~\cite{SCA2010} heeft een verwijzing van de samenvatting van dit
-algoritme} ontworpen.
+bij kleine en grotere bomen. Om deze effici\"{e}ntie aan te pakken is
+algoritme $S$\footnote{Algoritme $S$ wordt niet in deze samenvatting behandeld;
+het boek~\cite[p.~90-92]{DK2009} gaat hier echter uitvoerig op in.} ontworpen.
 
 
@@ -241 +243 @@
 \subsection{Product groei in synthese van \emph{BDD}}
 \label{voorbeeldSamenvoegen}
-Het volgende voorbeeld is een uitwerking van opgave 60~\cite[pg. 130]{DK2009}
-de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009}
-
-Neem aan dat $f(x_{1},dots,x_{n})$ en $g(x_{1},dots,x_{n})$ de respectieve
-\emph{profielen} (\emph{profiles})~\cite[pg 101]{DK2009} $(b_{0},dots,b_{n})$ en
-$(b'_{0},dots,b_{n})$ hebben. En de respectieve \emph{quasi-profielen}
-(\emph{quasi-profiles})~\cite[pg 103]{DK2009} $(q_{0},dots,q_{n})$ en
-$(q'_{0},dots,q'_{n})$.  Om te laten zijn dat de gesmolten $f \diamond g$ het
-aantal knopen van $B(f \diamond g) \leq
+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}
+
+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})$ en
+$(b'_{0},\dots,b_{n})$ hebben, en de respectieve \emph{quasi-profielen}
+(\emph{quasi-profiles})~\cite[p.~103]{DK2009} $(q_{0},\dots,q_{n})$ en
+$(q'_{0},\dots,q'_{n})$.  Om te laten zijn dat de gesmolten $f \diamond g$ het
+aantal knopen $B(f \diamond g) \leq
 \sum^{n}_{j=0}(q_{j}b'_{j}+b_{j}q'_{j}-b_{j}b'_{j})$ bevat moet gekeken worden
-aan het aantal \emph{beads}~\cite[pg 72]{DK2009} dat mogelijkerwijs gemaakt
-kunnen worden van de functies $f$ en $g$.  
-
-Elke bead van de orde $n - j$ van het geordende paar $(f,g)$ zal binnen de
-standaard combinatie vallen de $b_{j}b_{j}'$ geordende beats van $(f,g)$.
-vallen of is er eentje uit een meer speciaal gegenereerde reeks van een
+naar het aantal \emph{beads}~\cite[p.~72]{DK2009} dat mogelijkerwijs gemaakt
+kan worden van de functies $f$ en $g$.  
+
+Hierbij geldt dan voor een willikeurige functie $n$ met als profiel
+$(b_{0},\dots,b_{n})$ en quasi-profiel $(q_{0},\dots,q_{n})$ 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 $(q_{0},\dots,q_{n}) \setminus (b_{0},\dots,b_{n})$.
+
+Elke bead \beta 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}'$. Zie hierbij dat van een functie het $B(quasi-profiel) \geq
-B(profiel)$. En dat alle in het profiel altijd in het quasi-profiel zit. Er dus
-de geen-bead kan beschrijven als de rest van de quasi-profiel minus profiel.
+b{j})b_{j}'$. 
 
 Dit bij elkaar optellen levert op $b_{j}b_{j}' + b_{j}(q_{j}' - b_{j}') +
@@ -271 +277 @@
 de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009}
 
-Laat $f(x_{1},dots,x_{n}) = M_{m}(x_{1} \oplus x_{2},x_{3} \oplus
-x_{4},dots,x_{2m-1} \oplus x_{2m};x_{2m+1},dots,x_{n})$ en $g(x_{1},dots,x_{n}) =
-M_{m}(x_{2} \oplus x_{3},dots,x_{2m-2} \oplus x_{2m-1},x_{2m};\overline
-x_{2m+1},dots,\overline x_{n})$ waar $n = 2m + 2^{m}$. 
+Laat $f(x_{1},\dots,x_{n}) = M_{m}(x_{1} \oplus x_{2},x_{3} \oplus
+x_{4},\dots,x_{2m-1} \oplus x_{2m};x_{2m+1},\dots,x_{n})$ en $g(x_{1},\dots,x_{n}) =
+M_{m}(x_{2} \oplus x_{3},\dots,x_{2m-2} \oplus x_{2m-1},x_{2m};\overline
+x_{2m+1},\dots,\overline x_{n})$ waar $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
@@ -283 +289 @@
 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
+$(0,1,2,2,\dots,2^{m-1},2^{m-1},1,1,\dots,1,2$. Dit optellen en afschatten wordt
 (zie ook~\cite[pg 82]{DK2009}) $B(f) = 2^{m+2} - 1 \approx 4n$ en $B(g) =
 2^{m+1} - 1 \approx 3n$ \\