Changeset 131 for liacs/SCA2010/BDD

Timestamp:

Jun 26, 2010, 3:38:22 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Explain about effienty

File:

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

liacs/SCA2010/BDD/report.tex

@@ -40 +40 @@
 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 voorbeeld.
+sectie~\ref{voorbeeld} dit toegepast zal worden in een concreet voorbeelden.
 
 \section{Samenvoegen van \emph{BDD}}
@@ -80 +80 @@
 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 $B(f) + B(g)$ 
-XXX: TODO 
+is hier een geval van. In het meer algemene geval geldt meestal $B(f) + B(g)$.
+Deze grenzen worden in voorbeeld~\ref{voorbeeldSamenvoegen} aangescherpt.
+
+Het smelten ligt aan de basis van de daarwerkelijke 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 gezegt over de hoeveelheid geheugen er 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 ineffientie aan te pakken is
+algoritme $S$ \footnote{Algoritme $S$ wordt niet in deze samenvatting gehandeld de vakwebsite~\ref{SCA2010} heeft wel een verwijzing van de samenvatting van dit algoritme} ontworpen.
+
+
 
 \section{Voorbeelden}
 \label{voorbeeld}
+\subsection{Product groei in synthese van \emph{BDD}}
 \label{voorbeeldSamenvoegen}
 XXX: Ex 60
+\subsection{Som groei in synthese van \emph{BDD}}
 \label{voorbeeldPlakken}
 XXX: Ex 63