Changeset 131 for liacs/SCA2010/BDD/report.tex
- Timestamp:
- Jun 26, 2010, 3:38:22 PM (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
liacs/SCA2010/BDD/report.tex
r130 r131 40 40 gecombineerde simpele functies. In sectie~\ref{werking} zal deze techniek 41 41 uitgelegd worden, het zogenoemde \emph{smelten} (\emph{melding}) welke in 42 sectie~\ref{voorbeeld} dit toegepast zal worden in een concreet voorbeeld .42 sectie~\ref{voorbeeld} dit toegepast zal worden in een concreet voorbeelden. 43 43 44 44 \section{Samenvoegen van \emph{BDD}} … … 80 80 worden door in het slechte geval de \emph{BDD}s achter elkaar te plakken welke 81 81 dan in dit geval $B(f)B(g)$ knopen oplevert. Voorbeeld~\ref{voorbeeldPlakken} 82 is hier een geval van. In het meer algemene geval geldt $B(f) + B(g)$ 83 XXX: TODO 82 is hier een geval van. In het meer algemene geval geldt meestal $B(f) + B(g)$. 83 Deze grenzen worden in voorbeeld~\ref{voorbeeldSamenvoegen} aangescherpt. 84 85 Het smelten ligt aan de basis van de daarwerkelijke synthese. Een simpele 86 variant kan gemaakt worden met algoritme $R$. Maak eerst een reeks van 87 alle knopen $\alpha$ in $B(f)$ en $\alpha'$ in $B(g)$ met knoop $\alpha 88 \diamond \alpha'$ in rij $\alpha$ en column $\alpha'$. Vervang de bladeren 89 (\ref{bladeren}) door $\bot$ en $\top$. En voor algoritme $R$ uit op $f \diamond 90 g$. Op het eerste gezicht lijkt algoritme $R$ er ongeveer $B(f)B(g)$ over te 91 doen, maar doordat je onbereikbare knopen niet hoeft te evalueren zal je 92 uitkomen op $B(f \diamond g)$. 93 94 Deze 'truc' zorgt ervoor dat de tijd binnen de perken blijft, maar er is dan 95 nog niets gezegt over de hoeveelheid geheugen er nodig is. Omdat er nu 96 $B(f)B(g)$ knopen in geheugen gehouden moet wordt zal dit problemen opleveren 97 bij kleine en grotere algoritmen. Om deze ineffientie aan te pakken is 98 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. 99 100 84 101 85 102 \section{Voorbeelden} 86 103 \label{voorbeeld} 104 \subsection{Product groei in synthese van \emph{BDD}} 87 105 \label{voorbeeldSamenvoegen} 88 106 XXX: Ex 60 107 \subsection{Som groei in synthese van \emph{BDD}} 89 108 \label{voorbeeldPlakken} 90 109 XXX: Ex 63
Note:
See TracChangeset
for help on using the changeset viewer.