Changeset 169 for liacs/SCA2010/BDD/report.tex
- Timestamp:
- Aug 3, 2010, 11:35:14 PM (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
liacs/SCA2010/BDD/report.tex
r167 r169 24 24 \tikz[baseline=(C.base)]\node[draw,rectangle,rounded corners,inner sep=0.5pt](C) {$#1$};\! 25 25 } 26 \newcommand*\BDD{\emph{BDD} }27 \newcommand*\BDDs{\emph{BDDs} }26 \newcommand*\BDD{\emph{BDD} } 27 \newcommand*\BDDs{\emph{BDDs} } 28 28 29 29 \author{Rick van der Zwet, Universiteit Leiden} … … 42 42 aanleiding van het vak Seminar Combinatorial Algorithms 2010~\cite{SCA2010}. 43 43 \begin{figure}[htbp] 44 \caption{fig:samenvoegen} 44 45 \begin{tikzpicture}[on grid] 45 46 \tikzstyle{true}=[] … … 169 170 ontbrekende laag van knopen heeft, waardoor knopen van alle niveaus beschikbaar 170 171 zijn. Op het moment dat de $\diamond$ ingevuld gaat worden is het ook zaak om 171 de bladeren (zie vergelijking~\ref{bladeren}) te vereenvoudigen } \end{figure}172 de bladeren (zie vergelijking~\ref{bladeren}) te vereenvoudigen.} \end{figure} 172 173 173 174 \section{Introductie BDD} … … 180 181 \BDDs aan de basis staat van het uitdrukken van complexe systemen door 181 182 middel van gecombineerde simpele functies. In Hoofdstuk~\ref{werking} zal deze 182 techniek uitgelegd worden, het zogenoemde \emph{smelten} (\emph{melding}) dat183 in Hoofdstuk~\ref{voorbeeld} toegepast zal worden in een concreetvoorbeelden.183 techniek uitgelegd worden, het zogenoemde \emph{smelten} (\emph{melding}), dat 184 in Hoofdstuk~\ref{voorbeeld} toegepast zal worden in voorbeelden. 184 185 185 186 \section{Samenvoegen van \BDD} 186 187 \label{werking} 187 De term voor het samenvoegen van \BDD structuren zullen we smelten188 De term voor het samenvoegen van \BDD structuren zullen we \emph{smelten} 188 189 (\emph{melding}) noemen. Het werkt volgens de volgende principes. Men neme 189 190 twee knopen $\alpha = (v,l,h)$ en $\alpha' = (v',l',h')$. De knoop $\alpha 190 \diamond \alpha'$, de ``\emph{emulsie}'' (\emph{meld}) van $\alpha$ en 191 $\alpha'$, is dan als volgt gedefinieerd als $\alpha$ en $\alpha'$ niet beiden 192 bladeren (\emph{sinks}) zijn: 191 \diamond \alpha'$, het resultaat van de \emph{smelt} actie, de 192 ``\emph{emulsie}'' (\emph{meld}) van $\alpha$ en $\alpha'$, is dan als volgt 193 gedefinieerd als $\alpha$ en $\alpha'$ niet beide bladeren (\emph{sinks}) 194 zijn: 193 195 \begin{equation} 194 196 \label{melt-eq} … … 197 199 (v, l \diamond l', h \diamond h'), & \mathrm{als~} v = v'; \\ 198 200 (v, l \diamond \alpha', h \diamond \alpha'), & \mathrm{als~} v < v'; \\ 199 (v , \alpha \diamond l', \alpha \diamond h'), & \mathrm{als~} v > v'. \\201 (v', \alpha \diamond l', \alpha \diamond h'), & \mathrm{als~} v > v'. \\ 200 202 \end{array} \right. 201 203 \end{equation} 204 Als we deze recursieve formule gebruiken op de wortels van twee \BDDs $f$ en 205 $g$, vinden we een diagram dat het paar $(f,g)$ representeert. 202 206 203 207 De oplettende lezer zal zien dan als je Formule~\ref{melt-eq} toepast op de 204 208 bladeren er door samenvoegen van de bladeren ---zie bijvoorbeeld 205 voorbeeld in Hoofstuk~\ref{voorbeeldSamenvoegen}--- in plaats van de twee bladeren209 voorbeeld in Figuur~\ref{fig:samenvoegen}--- in plaats van de twee bladeren 206 210 $\top$ en $\bot$, er nu vier bladeren mogelijk zijn: 207 211 \begin{equation} … … 213 217 Om er weer een ``valide'' \BDD van te maken zullen deze bladeren vervangen 214 218 worden door het uitgerekende blad. Als bijvoorbeeld de $\diamond$ operatie 215 bedoelt is voor een \emph{EN} operatie, wordt de blad-rij in~ \ref{bladeren}219 bedoelt is voor een \emph{EN} operatie, wordt de blad-rij in~(\ref{bladeren}) 216 220 vervangen door de rij $\bot, \bot, \bot, \top$. Nu is het zaak het \BDD 217 221 te vereenvoudigen, om zo duplicaat-bladeren te snoeien (\emph{pruning}). … … 232 236 \diamond \alpha'$ in rij $\alpha$ en column $\alpha'$. (b) Vervang de bladeren 233 237 (zie Formule~\ref{bladeren}) door $\bot$ en $\top$, en (c) voer het algoritme 234 $R$\footnote{Algoritme $R$ wordt niet in deze samenvatting behandeld; de 235 vak-website~\cite{SCA2010} heeft een referentie naar algoritme $R$ 236 \url{http://www.liacs.nl/~kosters/semcom/tomb.pdf} welke behandeld wordt 237 door Tom.} op $f \diamond g$. Op het eerste gezicht lijkt algoritme $R$ er ongeveer 238 $R$\footnote{Algoritme $R$ wordt niet in deze samenvatting behandeld; zie de 239 vak-website~\cite{SCA2010} waar het algoritme $R$ behandeld wordt door Tom.} op 240 $f \diamond g$. Op het eerste gezicht lijkt algoritme $R$ er ongeveer 238 241 $B(f)B(g)$ operaties over te doen, maar doordat je onbereikbare knopen niet 239 242 hoeft te evalueren zal je uitkomen op $B(f \diamond g)$. … … 252 255 \label{voorbeeldSamenvoegen} 253 256 Het volgende voorbeeld is een uitwerking van opgave 60~\cite[p.~130]{DK2009} 254 de offi \"{e}le uitwerking is te vinden op \cite[p~.195]{DK2009}257 de offici\"{e}le uitwerking is te vinden op \cite[p.~195]{DK2009} 255 258 \\ \\ 256 259 Voorgaande aan de uitwerking is het belangrijk te weten wat een \emph{QDD} (aka 257 260 \emph{quasi-BDD}~\cite[p.~102-103]{DK2009}) is. Elke functie heeft een unieke 258 261 \emph{QDD} welke lijkt op een \BDD echter is de start-knoop altijd 259 \circled{1} en elke \circled{k} knoop bestaat for $k < n$takken naar twee262 \circled{1} en elke \circled{k} knoop heeft (voor $k < n$) takken naar twee 260 263 \squared{k+1} knopen. Wat in het kort wilt zeggen dat elk pad van de 261 264 start-knoop naar de bladeren een lengte heeft van $n$. Om dat mogelijk te maken 262 265 mogen de \emph{HOOG} en \emph{LAAG} takken van een \emph{QDD} gelijk zijn. Let 263 wel op dat reductie toegepast moet worden. 266 wel op dat reductie toegepast moet worden op tweetallen knopen waarvan de 267 \emph{HOOG} en \emph{LAAG} pointers gelijk zijn. 264 268 \\ \\ 265 269 Neem aan dat $f(x_{1},\dots,x_{n})$ en $g(x_{1},\dots,x_{n})$ de respectieve 266 270 \emph{profielen} (\emph{profiles})~\cite[p.~101]{DK2009} 267 $(b_{0},\dots,b_{n})$ ---waar $b_{k}$ met $0 \le k < n$ de knopen zijn die splitsen271 $(b_{0},\dots,b_{n})$ ---waar $b_{k}$ met $0 \le k < n$ de knopen zijn. Die splitsen 268 272 op variable $f(x_{k+1})$ en $b_{n}$ het aantal bladeren is--- en 269 273 $(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})$. 273 277 274 Om te laten zi jn dat de gesmolten $f \diamond g$ het aantal knopen278 Om te laten zien dat de gesmolten $f \diamond g$ het aantal knopen 275 279 \begin{equation} 276 280 \label{eq:knopen} … … 279 283 bevat moet gekeken worden naar het aantal \emph{beads}~\cite[p.~72]{DK2009} dat 280 284 mogelijkerwijs gemaakt kan worden van de functies $f$ en $g$. 281 Voor een will ikeurige functie $n$ met als profiel $(b_{0},\dots,b_{n})$ en282 quasi-profiel $(q_{0},\dots,q_{n})$ geldt dat $B( q_{0},\dots,q_{n}) \geq283 B( b_{0},\dots,b_{n})$. En tevens dan $(b_{0},\dots,b_{n}) \subseteq284 (q_{0},\dots,q_{n})$. Hieruit volgt dat een geen-bead zich bevindt in285 Voor een willekeurige functie $f$ met als profiel $(b_{0},\dots,b_{n})$ en 286 quasi-profiel $(q_{0},\dots,q_{n})$ geldt dat $B(b_{0},\dots,b_{n}) \leq 287 B(q_{0},\dots,q_{n})$. En tevens dan $(b_{0},\dots,b_{n}) \subseteq 288 (q_{0},\dots,q_{n})$. Hieruit volgt dat een niet-bead zich bevindt in 285 289 $(q_{0},\dots,q_{n}) - (b_{0},\dots,b_{n})$. 286 290 287 291 Elke bead van de orde $n - j$ in het geordende paar $(f,g)$ zal zich 288 292 bevinden in een van de volgende groepen; (a) de standaard-combinatie van de 289 $b_{j}b_{j}'$ geordende bea ts van $(f,g)$ of (b) de gegenereerde reeks van een290 (bead, geen-bead) of (geen-bead, bead) $b_{j}(q_{j}' - b_{j}') + (q_{j} -293 $b_{j}b_{j}'$ geordende beads van $(f,g)$ of (b) de gegenereerde reeks van een 294 (bead,niet-bead) of (niet-bead, bead) $b_{j}(q_{j}' - b_{j}') + (q_{j} - 291 295 b{j})b_{j}'$. 292 296 … … 298 302 \label{voorbeeldPlakken} 299 303 Het volgende voorbeeld is een uitwerking van opgave 63~\cite[p.~131]{DK2009} 300 de offi\"{e}le uitwerking is te vinden op \cite[p.~195]{DK2009}. 304 de offici\"{e}le uitwerking is te vinden op \cite[p.~195]{DK2009}. 305 306 De $2^{m}$-weg multiplexer $M_{m}(y_{1},\dots,y_{m};y_{m+1},\dots,y_{m+2^{m}})$ 307 geeft bij input $y_{1},\dots,y_{m}$ de waarde van variable $y_{m+k}$ waarbij $k$ 308 het getal is gerepresenteerd door $y_{1},\dots,y_{m}$, 309 zie~\cite[7.1.2-(31)]{DK2009-0}. Hiermee defineren we $\oplus$ 310 de binary operator \emph{XOR} en $n = 2m + 2^{m}$. 301 311 302 312 \begin{equation} … … 307 317 \label{eq:opgave63} 308 318 \end{equation} 309 In Vergelijking~\ref{eq:opgave63} zijn $f$ en $g$ gedefinieerd, waarbij $\oplus$310 de binary operator \emph{XOR} is en $n = 2m + 2^{m}$.311 319 312 320 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 316 324 opgemerkt worden dat zowel $f$ als $g$ $2^m$-weg 317 multiplexers ~\cite[7.1.2-(31)]{DK2009-0}zijn voor welke de profielen zijn318 $(1,2,2,\dots,2^{m-1},2^{m-1},2^m,1,1,\dots,1 .2)$ respectievelijk319 $(0,1,2,2,\dots,2^{m-1},2^{m-1},1,1,\dots,1,2 $. Dit optellen en afschatten wordt325 multiplexers zijn voor welke de profielen zijn 326 $(1,2,2,\dots,2^{m-1},2^{m-1},2^m,1,1,\dots,1,2)$ respectievelijk \\ 327 $(0,1,2,2,\dots,2^{m-1},2^{m-1},1,1,\dots,1,2)$. Dit optellen en afschatten wordt 320 328 (zie ook~\cite[p.~82]{DK2009}) $B(f) = 2^{m+2} - 1 \approx 4n$ en $B(g) = 321 329 2^{m+1} - 1 \approx 3n$. \\ 322 330 \\ 323 De bereking $B(f \land g)$ wordt aanzienlijk moeilijker. We constateren eerst 324 dat er een unieke oplossing bestaat ---de oplossing kan aan een uniek getal 325 gekoppeld worden--- 331 De bereking $B(f \land g)$ (de werking van de multiplexer) wordt aanzienlijk 332 moeilijker en zal daarom aangestipt worden. We constateren eerst dat er een 333 unieke oplossing bestaat ---de oplossing kan aan een uniek getal 334 gekoppeld worden namelijk de invoer--- 326 335 in de vorm van $x_1 \dots 327 336 x_{2m}$ als je $((x_1 \oplus x_2)(x_3 \oplus x_4) \dots (x_{2m-1} \oplus 328 337 x_{2m}))_{2} = p,((x_2 \oplus x_3) \dots (x_{2m-2} \oplus x_{2m-1})x_{2m})_{2} 329 338 = q$, waar $0 \leq p, q \le 2^m$ en $p=q$ dan en slechts als $x_1 = x_3 = \dots 330 = 2_{2m-1} = 0$. Dit zorgt dat het eerste deel ---het stuk voor de punt339 = x_{2m-1} = 0$. Dit zorgt dat het eerste deel ---het stuk voor de punt 331 340 komma--- van het profiel van $f \land g$ geschreven kan worden als $(1, 2, 4,\dots, 332 341 2^{2m-2}, 2^{2m-1} - 2^{m-1})$.
Note:
See TracChangeset
for help on using the changeset viewer.