Changeset 135 for liacs/SCA2010/BDD

Timestamp:

Jun 30, 2010, 8:03:44 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Bunch of formula's added

File:

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

liacs/SCA2010/BDD/report.tex

@@ -52 +52 @@
 \alpha \diamond \alpha' = \left\{
 \begin{array}{l l}
-(v, l \diamond \l'), h \diamond h'), & \mathrm{if~} v = v'; \\
+(v, l \diamond l'), h \diamond h'), & \mathrm{if~} v = v'; \\
 (v, l \diamond \alpha'), h \diamond \alpha'), & \mathrm{if~} v < v'; \\
 (v, \alpha \diamond l'), \alpha \diamond h'), & \mathrm{if~} v > v'. \\
@@ -101 +101 @@
 
 
-
 \section{Voorbeelden}
 \label{voorbeeld}
@@ -107 +106 @@
 \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 160~\cite{DK2009}
+de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009}
 
 Neem aan dat $f(x_{1},...,x_{n})$ en $g(x_{1},...,x_{n})$ de respectieve
-\emph{profielen} (\emph{profiles})~\cite[pg 101]{DK2009} $(b_{0},...,b_{n}$ en
-$(b'_{0},...,b_{n}$ hebben. En de respectieve \emph{quasi-profielen}
+\emph{profielen} (\emph{profiles})~\cite[pg 101]{DK2009} $(b_{0},...,b_{n})$ en
+$(b'_{0},...,b_{n})$ hebben. En de respectieve \emph{quasi-profielen}
 (\emph{quasi-profiles})~\cite[pg 103]{DK2009} $(q_{0},...,q_{n})$ en
-$(q'_{0},...,q'_{n}$.  Om te laten zijn dat de smolten $f \diamond g$ het
+$(q'_{0},...,q'_{n})$.  Om te laten zijn dat de gesmolten $f \diamond g$ het
 aantal knopen van $B(f \diamond g) \leq
-\sum^{n}_{j=0}(q_{j}b'_{j}+b_{j}q'_{j}-b_{j}b'_{j})$ bevat.
+\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$.  
 
-XXX: Detail uitwerking
+Elke bead van de orde $n - j$ van het geoordende 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 (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.
 
+Dit bij elkaar optellen levert op $b_{j}b_{j}' + b_{j}(q_{j}' - b_{j}') + (q_{j} - b{j})b_{j}'$. Vereenvoudigen en de sommering is oefening voor de lezer.
 
 \subsection{Som groei in synthese van \emph{BDD}}
 \label{voorbeeldPlakken}
 Het volgende voorbeeld is een uitwerking van opgave 63~\cite[pg. 131]{DK2009}
-de offi\"{e}le uitwerking is te vinden op pagina 160~\cite{DK2009}
+de offi\"{e}le uitwerking is te vinden op pagina 195~\cite{DK2009}
 
 Laat $f(x_{1},...,x_{n}) = M_{m}(x_{1} \oplus x_{2},x_{3} \oplus
 x_{4},...,x_{2m-1} \oplus x_{2m};x_{2m+1},...,x_{n})$ en $g(x_{1},...,x_{n}) =
 M_{m}(x_{2} \oplus x_{3},...,x_{2m-2} \oplus x_{2m-1},x_{2m};\overline
-x_{2m+1},...,\overline x_{n})$ waar $n = 2m + 2^{m}$. Dan is $B(f)$ XXX:TODO,
-$B(g)$ XXX:TODO. $B(g \hat f)$
+x_{2m+1},...,\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
+\hat f) = 2^{m+1}+2^{m-1}-1 \approx 2n^{2}$. Om aan deze 'magische' reeksen te
+komen is het belangrijk eerst naar de profielen te kijken.