ࡱ> !mLMNOPQRSTUVWXYZ[\]^_`abcdefghijkln#4d%, PNG  IHDR:%sRGB pHYsjPLTE999555333111---666$$$+++)))'''SSSOOOLLLDDD]]]YYYZZZTTTUUUzzzhhhuuudddqqqfff#"IDATxir5^A\w t64i Ԣʬgg8 =*UEfEd.t @Ёt :Ёt AMCg{x<of']7}ere}3@Gmz'zqk+:ZL~.w:齃Γtt Йuk׼]Ga 7d:_[a|f7<7$U[t nfFbmt0:O с t:@@CgN^t2Xa]aǫV[@g ?a6 g`Y*O M(^0:;3Cm?: TI1*Ƌp' fh]wOKX9Y8zai˲}n( 䣣74'/ _e`h1(X 4 'tj1aO˲'d/veb2 @g^YвK8bMH'V}dy 6_i w- ]Evڃyn9DR7#]? r7,q>ϻ)iAu ' }ҞsYӤHizsvBSNbؽaC!^kg _m]Cg[8߱=';72_:Io :q}{oCnYve3ԟ6&S;N?*Ol G_<윷*d;N(o%̙}eT`4)tFW%Ш^7 <,=|w8f /ςTHnN~io,>::aˏJT\Seq~wC~F91;fK{-EQGt<B۽Aܴ+\ڿ,,vPM@g_=ox^ؙ6tąiOSN\4Œw{e禂ߙ3.%wQѪ;zY,CW &ÂLΡvXui׉#7&I-+>y(J</*JRH'CvX } tѹ ߀ΡltYV* W3>P]D'*7v$CkheetC)yNĎ)/F'~m|hTwbgt۴b+/vQ1S̑|]NIOM?n ;I?QiU+m:n;NX~M쬦d2>_m~h*秝ؙ5uA?}3FJ't FFFY7?svU#v-;C'm<9T+K^fI˃*te_JILMV3Eif.Mi/':,̎f3RR@tVv鵬-L30skq,^763)h4s)yLw9MCVP]5s<8@T(xݳpڇNl5YM3H뜎3}qL͇:c!ݪKIּ& |W|Ǝ]3R[ۥ35kI3mRck0tj iihќdeG:3 ԅZ\J *9XM ;tKz\JkmNd6 6s)ֲ# UW)pBzf.ZvD蕣`E3ZZvD3}NzܧiR[k$t[)qfઙK)o-; m/B:g4Oz\J|B'q 9n 6sUj>:sQ u̥9,k]0NrnF)K;իf@̥4J1,2j4s)eG :: lh D\jyjّκ;t!ky֛̓8ZH3lRSktv5xnVΧݙC㛆NTszhTH'n^J295 λ V\uΪ]tύsKU3̀K-?i"KWiNN1K)?-;"Ii!jvF)Q5E"`],&^Y[˩OТTC=9YfoIY.N̥xxq @'r4$b&97yimqWǐ|\A:x4CQG'v<?ҽ4s)%?:}G[>Lf.|"z`;5s)壵;:#W&FZHOD͎_e7:+vEƉ̥4J|?{mx[=sp8T6˝䞑~FXS=yfD4;(Skӓwo͎4JN S0&̀J.BB}nZŲe+:[ܹ)kډeCkWtnkCjȨ޲vE.Mfiom+oOe߲ʁeFU3Pv(=9/u;Zf(, ğFv#],3\iQnlw\4bnmNDijNC(=S;տRZÛFt\ NMGA%*w&+P mmG'!nUlܧJPHOX[vO *Ms(K;i]{Uʹ, H3`mmgG'~>z,O3`mmF@,yY^HgM8 A)f9fwk%3:R+UDe;fskk;3:1C%g r跐ΚFɌN5yYg%/: ~4c- c 8fggk;+:+j;v _,+s찢<WS1lm.^YfFɉNu9: x̢b(c%#:drZ'c#:1y^?fOc%#:#㹙+5Kck;:h{;1M ;C#Gk[okѶYm >!XIs*>m;;1dS&b(C@gY~] DMAJv:NmVvcv\OM(y?3vcM΋ JtTkoEM i/[|q? D# ; EJt:o{f:H)aiA~B2߾M@cMEp[ /T3gt_\i$x1}@ca fqm[+yOGo~f.a >qV O,Gg֛_Ifem;ņW9,̯|љ}ff.cvx!O(Ggx}Mm'zvf.{v Rt~DY+M3Z1oJ3 Uq]Ԋdg􍝰C.Cg1Ӊ~Ǘ:]3Z 2ݲC~LF:La(Wq< (Nv}{Nfǁ)CmiTMwPtm)puk{ :Oo3;_%p.@hP^Vp E!:q/q'gQ3ۻ2~,)YNL of.f o|b(ue1:/SQo؇Af&mTM3o_H'nm/DgڢNs[#ӠJLT\j5tqN!:\cGAǗ;qKYL; [$ \r4(j)xc^1tA۲SWxjԽIMW+3.hu|-uN'}4tm齬C-tC̥V#M;-Bh)U,F7(ҦQ)+XdEDjh)XZ#tߏk92Uk:3;4̰c7r>3/djWy*f]$l)xm3c%k#]XS&B:ik%:,Yo)Xҵ%:Smt$L3l f iB(@>mi@ɦM6tҴKtBg٘;|,vL Zi̴1Am)xy1r%ud,G\mPёa5̰c2㧴%lO#Ufr|3;ioj[ttXB-0o2+ۢsDGJ[ LA+vG-: `/a5::bZa df@FiNRNZa >~.;5Tr-1]\:Gα䁤=,vwvttiNfg ^IN^*vm1 ١<<)]g0E44ʚ褉rZd *Ղz?ag8 -2*=qXdQUݟZS2 !=Gᒛ<&_4PL;D'6S&e1,s'VLAmv8=UfM:ό U):T;3oRH(iIRuS=N\K};TLg1 ٩f4̀e9`M c --튅)ADN%;B*z DǟNKME~qB NsxRG򡰥U/CII!V:2֚E$L6l߮Լ?[0k f.;oh!2f;O{H05_/rdizneG'9KWŦ`"'0;l~Zl fY7Fjt찢s6xf>_63XefI'<Ít|V7-\OUC|<:49ʎgGdz9rS"Slˇvtm7Ӈ2!yo2ЩweM<歝:aG:}䍝};wgk\bt9;ϤY/t37s0i|_O~[?)j :$6O`MAs_* Bx''Lb<裓蠓:a?u4K!~sᚣ:Bį@t֛.::Tgx9h)8z_U5]|D)XTzw @r)*MLRa6)TkZdjt.i&谚w 'Nl+#G :`:wÉN )蘝[Oo>s .@a\t.l>Ê~9$嚷S Nj)x{Kz-r9_ϗ9؍pyj)+ dX|2]D.,t@RIO?\:IAOL'rr@JC\w!f\8>0;9S+D84萛1qMk t)At.C))tHAF<l7: LCg` 2s`ѡ2W0[9S0;9)tHA@'5x/a vs`Gqo :O]t@>scs`w9#OTwNs` vtv]:wvBw LN)1t`׸_t(qL)9t+7 L)=tSCǍ9S81]DDž9S800N}s`Wѩm0N]s`wѩk.:5AF'5 ]F9Sqȁ|@U6LVk@G0;VLΣY ٱ1x` "fؙ0Ι9S27w0N9S\dl0Ν# й)t<{@.3s y`  ; LA$}s y9S:'A;yб:@RXaK:wcW.N91SimaϬu^F/Fz 1p6ˆ]yE0"inB,șdaDή #rƤÉk傈u4DYs #xXm#b` IךڕkgaD#ˆ9iJ4ZHUy8)D/HF0򗮒I ưKE`8Jgsv5Q#^Wi`yEZ@ HQxH/rcQR/ c ֞o*F"P 0 ?j8 H0֍A;tyU1AB? >Kx.dF:jd"RG{ L}_Is aQk}six~<*HdXccc=ԻBJGs`4Bq,qàjW %)kpx ܒq$埚Bq`l ŢMxe h`/ j%Jz*#?;dw1qlİ$Ȩ`zg-gX.ӥt02I*S5uT0 Xc-pfv$iixP⸠S7[4."~wSԟL -?eZ8LY;Ђv+inH Vƈ_,Xb2(=zNkf<0 _{>)#ЍwǮoh8xU`Btqtť2cOfc{gCIj;1ѣ&_ӿ#{L±"F Lo4Jd}Ѡ(?̋+.=kUŢdȍ" ٹ-F$fq&l5?P&]g ?`*$8(058&Fr-/&~U"AT'uťCuk;8m]o89Q|у"YRLߞ9H\lMLBxqْHōbƁ#,t u-{ }F5h5w&wUWz4>U5w/+}up̜quǟ9)riN) q$3w+/8!2\M3oƓLBoaCD!Ϡ RlӽvAUd̑0Ie75sUՏ#(F}=ךuYa(iG1(Ì94@g "ޱͰ+ܹzn/f6|Y~$=bmC4-"yYqّ0"q!1ly)R0Šbe\:]>9n&7"HG1z9OtϮl؏ #(cY ]"aW/@da;oH F1$ aI&aj%Ӌ?m^9,J,D2O:(au傔qcs7@⫋N8<] l4t悔bj0uك"qrqM1Q!(;g$9V1"#bQ v{)+μQn/M-E@iYd #Q JL_cHSpɗ Du=̭Y?ibmL|do]tp0"Ŏ%ۑ9R) ҆˒$(G1fekk$ez\Es|qD!>E)?w` j$4ⷩDևk12 7ujI F$0!Fprygmв~;#B-#xe #{ɯ,od*(HC+th*{AOrsAs!#2{(52CX46-ʼnK\#K cҪuR58 RCɶ1I'elO w=2"> e{{C|'OZ%qcO[NEԹ#uG1:3 ׷w x|?c6R7"0,K.ewN;#dM֠(z?2'.]ۣN^ٞ!(Lv/W vFC3h5;[ 0ƟΜM҄;}NA*}bLM39 I46g{ ~JTdlUpB=ߙ b`WM-Hq/gH@|R hL?jO(Bq$(a8goLM;!%Fa4T,xG=`?tH+mvMrqfhn&D(! 5.(M NH%(jFѿJ;jdKZ"aD[9ʜ M%<҄H܆H%>>хc:n*Zu~/*Am(6`ʻ''g| 4Ţ4#ZNH%>6p?$?:H(>ij]nӷ@TQȴa-2Moqt02[| E}/NPס+mH%JH~vx/U,,"2!ad`-1ݭ@5}/^L}e%ڕ>l kyAK/O q]a%VnvۤힺƷ}mibc unK]e 56(вrAꃀ٧\۝{z;u2Ω,!asU_2CSy%sQ㣢Vx71xĄv͔X0Z5/̻SV#M0JX|$emFJ5Yn}Pd adYː4Gr)< >Q#i zuZ}Z]q@Cw~rOxHIRI69.Uel(TdC!adl|$v=;.k}KOI/KHW.e #ߩV(E O4e #%^ q!|MeV 2tCȘryS]L]~ 3˓%$  -360?%%#ac$_7P͍nѱy~^8[Ko;K/D cs<{4Bb߽ŷ8NKqT_87B4EJ|_&n$o^ M0aG5gGr6%jrޭ'x ut#ySLӏWZe6#΄HшOdH>ib@LeI yjGˆx|c5BȺ IOH_6"-Pxh!kys0 ai0"WIq瑜Bd3k[w>eb0"%jpS^V&&41Fˠ7rq!p8s7}he #{壛BBcw3 93޽ra wsb#h`m~{ H+ohb8rB8=b';$\_,O x;RdAnټ7;L,!a -_ϦeZ0 yO5+HHaGbP8E(ușm2iڷ9J-o 0h3F71MDV~C2lac$P#S}lL}ٳpYB->*>tŕd TLc z-KH!G|x>}yo8  #ܽO s{G ǁ 2)FpюLyS(Od1"ƞ=53-KHA˛B_j)b7Ʒq=T UN<֞⨜+iƪb*zZZT~CvoYfq0;UO˯3œW6T B U~CwdYR]rӾ1z.HJ~(1H{aV~Cr۸9<"W^\؛NSҲa2IVle)>Fr U%DG!Bp S1O!9DwmH-ՐWHn7dS#o8vc zЦODG_^CG"xq1W"_ux(oHw%!-ۃ$P($2uoᯎ*r?mM+!u&pYRŨ)V:Ƨ )K ^ɹ5rɍDl AZ4DƭEmFϺ EwbZUvga_<R赀O9Chvc%-K}y52 Ⴕ/&}R3er0͏4;NRߍ ů<bZOO:RBt%)09>ɞ=%f`s6_ZAYQo &fX6>q|g9}8.8I~gvO^H3ϲxjUFAI{P5Ǒ.L8y&#$5Ÿ vo緗u@2V'S?DC(zaf3PWjO U~CZ\#'<w^xt=Ї->9w0*PbovFu9`{0&ÀlΐTpHBugۆ/]qhͮU"NEzP+!bVdJQ[:Z|`ðo ZooHe䁆hzT]g7DlH3p*سX1ں8~&0לU ,!bĎ?8#.?o8ߺx[{ũizDaM[  bP1I)mk$AS=nk+6BuYBHU[ v[GLf|s֠LB|ltx)ӿs$^PɼP1w Ef%ڄG>!i{HG7uIި#$s,!s7Q#3a< 1=zQ!cOB6p/va&5|Aȴڠ}iTd_N1XJRn}8ɇ1v븩6-Ay&bCSwW'4%UۥkPfv*ɿ|o>X@Ş8[_7AT~YmpT3F:&}7g'=2߰yA,$`sS F7owvbFΉU~N`t4zu#; :$a"W Ru!D\y #NxT,Bh؜GRyxC $mYo @ T)wƽema)NV[`T|5ZtG65R66dJ38[p%1vlE+3n~U78㭆*z'eГk!Y S]yzv,ސa_-Ԑ f{v]S #p7Dh$5H9[,Cޣ,KWFL 0:@j 1S5e$_$a~b( 1c74ǘTzYKFŲmOs]r+X4p1ZI9(+Tdy`߼ȑ+?bٰi[M_v7l;g?j|a?t$QA(?>D'Z,.F V%oMѻ4R st%H@$kTd,0J߅k4h$DXE^=ET~Ch-}&:O # oM?x,*iƒ ha:Mc0j̥oEDӽI('o~F 4bl')b1;J%9'Hf9y1E;zR67<9Ö]ղ _n!-iPKJ'i3;AN` i`QՐSD:0z^4CO=uI<(q>*:vQКd1t`$,խnLYrˆ)8j:c1z9Ϩ K@E*џUil6-_A Aqw17z玽4~nT ^d敽Qru[WN~:e>{UsvX${H1tO>J;+SW7֓/7\e>g@*p xg jg(o!>0k5uQ>p/W'Xt F uK::fADLo jr$Tt|5klXBܺ0rNͬ᪾[[ zsVe5CP 銏 Xԙ+vo]i9֮9=*`V~:ZS|YbsƁ$.uT"k~qerrwuKhŐWe}~춖ֹ-1E-/yu+Qa/צ?>:5í9>3ǡD'ՈkϡG[ 25PFmoY8§J|M/n41ZCͶ-.<#=Noutj fF#{Dy Af0g7 -CrE_J_bO71u4X'nrg ER`=_x 2|::h=]+:nH@/F% N7?U_WUQ/6ČĻnT1 A)4=Q2;;1o޹*`GZ,2Q_*%"_5ADh^!niZ"^Z Ս˛k3VQAr,6g''ls[^C~\d//&]'y }$gG!jJ1Ten;Ħ&soKH/ $H%OS$qnf;UWiD#4Iv? n/n*lF0b{H~4Ā0e]$ 1e!݌FR=~n_[v3z"%|/$0ZBN('~ 9Wu+b!c;+jwJH)$?QFџZ gbQoY%#4\. q#-LT& fr`~3ںQM 蘳FabK0t4 nkk묎^wG0KoƊY-{sa~9*e UAp3v(S7TVʛ|ĺÓ 'fd#@ zQ¹6A5_"IIjH,ԛMܲ٬B°&*H@o1vےFbܼ[XZª6oF #'|O睙q`ՇS)Wv XZs:e5#)CF—/\֬YZEY`O #g’ؙ)/eMo0ia*5-s,Q2ryW U7lPZ%+l[.V%1$ǃ*H!^ g*5H:RS!J? ,J9whͶ]*+ٽ/yx*_ /鮲3z&yWu ''D9_YnǘtLՌ=dW;t*;x)h۬D.p1B\ϕ}ܜ 5dzYW+.FrSIWjIV?_H.t?(=ŒgķH"=%\KI$.FQfe\~h9fӞ"˩?|e2G B:+hb$:ˇi(8xb$GIp*d $|q. N%/^TȪN*O#p#-. ao~,܄Nw,gz&x9Nòur"qh/Uh}|[rG䤈q}^}vFY(Kcao;ZZei~,mgTK<[%֣"%dy!Pͧ8224Sii7/g07`adad~ _BkY#1R{ur'[ s<8G08ң=ےlulI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒kaDΖ8YѲ,9FlI-˒;z*^9 Ɍzڂ3 52AQ3kDIENDB``! ّe3;anR |xcdd``^ @c112BYL%bpu0ID loy ?I\FTX@&d%L ~:pAC ;WLLJ% {:@D/!t?2?k`!slIXu{ͻy24 hAxcdd`` @c112BYL%bpu#I3H0LcBQO= P{<` `qT4Ը! h 0y{qĤ\Y\ q1(2t/B j ߑQ<`!=C7ܴN;0/ڮ @ "XJ xcdd``fed``baV d,FYzP1n:&&V! KA?H1Zz h7T obIFHeA*CL N`A $37X/\!(?71A^.0300Usi#VM8a>#I3H0L@\= ɳj#q ₆8dK F&&\A Dy.ĠO`$P`!A--&ʦ*4!F   pXJxڝQJAN%Jb ZD:m$$ҥ80ȩ\u .`a'd} N1;;GQB$25^!& {o·Z`.i jmb^Ȅ zYՃxv=,sg<_𤡈pRSw?]11SՖqQCLnbzZ+?)7Od篜Iu%! PYPQ7 ֬:˰m1 ,/8ģjDyHYR+`!Aͯ'*s  `\XJxڝQJAb]#*ҥ8TH@ʯ+,RY ~&H:=x3D ;Ч!bh+|K6;AݵMlë:, 6.ayznG"fdÛ"~.-{*be=Ijڈua\?rHF˜S(/BAȡAҊGIh-fYWļwUNy,.LsTwlQO`!@+ t6_   pXJxڝQJA}3wH%bJZDMHq!IuS+ +?!ufXJf{%0v#bi++])mx#(^jObVUz=ʮ"fd"Ν ZLeGʽD%p1EG3AşY/?-"RAO9/!z-е:k Y֍=_t< e)v17NoMW()ZuP`!C-yY^ȱoZt  XJxڝQ=KA%J$A%TRhq*$ W]j+?`寰'Li/d} .ۙcvfwP x( b｡K]O㦠vUT7z4p9 ZOvSّq_Q BLuUֳdBn=.?'g?R2rr(LGZ %֬:Ki18˕%œ՝5ў\SdM1Q`!B#깷Z*bD   pXJxڝQJAΘK#UU$h+Icce-NKm+,|&H:=x3D -y( b｡joɎ]Y& "3w1kMgm|́ ܎"fd"]>{2U]U!]QzN&֭OY^O'[?G0X9/!BΌNH+ԚzBgj^_U9煲x6NZQ)?Q`!@?/ !3Im @ "XJxcdd``fed``baV d,FYzP1n:&&V! KA?H1Zz h7T obIFHeA*CL N`A $37X/\!(?71A^.0300Usi#zVJ5Qn>#I3H3LcBQO= P{<`cqD$4Ը! h 0y{qĤ\Y\ q1(2t/B j QR`!@!_ԪqǸ  `\XJxڝQJA}3w1Hb ZD2M@ zMZ H;, "`iiad6A҅}oy,D5[Qj1Q@{C {͕Ŏq[Pwm*F*|.A'1kM y6΁ep+^C3'$qWLeO=G%p1EO%}Fzt䷬|?ɟl}nCyr_B8%kuRԍ=_l2 e qgbmt()_Qw`!B͗f`>.+g  `\XJxڝQJAb%Jb ZD/PB&e-N䰸 "`i#X Y{lӃw;sZ@ }2-^ & {o6÷Radz+-x#>$S2+os``\xPČ4*;_c˸ר z]㤦H ~U?+|G˜(/BAȡF$XVO,Eس b޽('ӼP`&ཋ"bS `!@JuVܾ {Ҕ  XJxڝQJA}3wQs x\%b KA$MZ HKmOHWXXX Ygtav[޾;KQ>tԤ( b｡ {Jd8E ^H? zZJAxz5e|cWBC3uOE~GLeWʽD%Ѓ+YO9b=ک?rHF?"8 k?JB묵'd6dȦd:fhoP|Sd?P`!@cP=K?e'  (+XJxcdd``fed``baV d,FYzP1n:&,B@?b X ㆪaM,,He` @201d++&101z @@ڈ53H&_k`H`=FV ~.jF{FPGqAC %#RpeqIj.ŠV "<bPP'f~wQcښ(4 ,  pmwlXEquation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0l Equation Equation.30,Microsoft Equation 3.0l Equation Equation.30,Microsoft Equation 3.0l Equation Equation.30,Microsoft Equation 3.0l Equation Equation.30,Microsoft Equation 3.0l Equation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0lEquation Equation.30,Microsoft Equation 3.0/ 0DTimes New Roman(0(:A 0 DTahomaew Roman(0(:A 0 " DWingdingsRoman(0(:A 0 0DArialngsRoman(0(:A 0 @DSymbolgsRoman(0(:A 0 PDGaramondRoman(0(:A 0  B.  @n?" dd@  @@`` OO E"'Q  M+R' I  ,  >  )   =6)"7,=$=6)"7,=$---- - - - - 7- 7a- 7a&-7EAc  -7> - -H5Gq4C3T9V`a0KI8[!3 7 = (- y_2C5 ; '- '2'QwyD#yD#- ;  ; :+/I6U-'-  'EUE0), ,/ +/D 6' -07]:yc&'HG'  %?+$2j*UUk .4p#3`S`S UU#k4344.493Dg7D % l9$](.e;rG: U //3**U'EH%22k.VDWXY%l7***3*Gx e"##2*U#   gkGSlX8DZ   TT#G1*  TTJTG**30#12:;  (2 Qw Z#B;0' #1Z/ 8+/KLG5`qUW x **-*'9-,,/8+3*3''T%!!!""9''&  =q =rf1%2x ;:;S';9'8Z'x& & 8xrZ::::$(""D66%&' '*hGl9e7X;B (!")$6I44&/&'v GGFC5ml&&44&;a9) :&: :;".9qR +2 +2:;aU29 )&$* '"(L;;Xx & Yf;V+22Yh'x Lw'9"((C%668D8DDDDD &&9RRIWrWTrW  Yv3>Y50O4v=>7?@>v3>0O4avz7>,PCKaz,PCKW}OO4[\0a0O4vaveRfhIx  NYvz.9qH,PCKYDGGa b$4d%, #$$2$2X1*Ft~#b$1-; V&#%$$$$$$$$2$ ّe3;anyK$$$$$$2$U! 7&MV]]/M$$$$$$2$lIXu{ͻy{N2$GWqalCWHP2$C7ܴN;0/ڮEOQ2$--&ʦ*4!FIR2$ͯ'*sIS2$+ t6_H&U2$-yY^ȱoZtKnV2$#깷Z*bDJW$2$?/ !3ImHY2$!_ԪqǸHKZ2$͗f`>.+gJ[2$JuVܾ {ҔH\2$cP=K?e'H%^ 0e0e A@A5%8c8c     ?1d0u0@Ty2 NP'p<'p@A)BCD|E? ff33f3@8g4BdBd@:A 0p pN  <4KdKdl # 0g4:d:d@:A 0pk p<4!d!dl$ 0@K ʚ;-(21ʚ;<4ddddlT# 0X0___PPT10 `___PPT9B/ 0&? %O =7Y# From AND/OR Search to AND/OR BDDs ,$ $pRina Dechter Information and Computer Science, UC-Irvine, and Radcliffe Institue of Advanced Study, Cambridge V " PbP " Pb,>bCombining Decision Diagrams eCombining AND/OR BDDsfOBDDs vs AOBDD$~OutlineBackground in Graphical models AND/OR search trees and Graphs Minimal AND/OR graphs From AND/OR graphs to AOMDDs Compilation of AOMDDs AOMDDs and earlier BDDs xZZZZ=aPj mnPropositional Satisfiability`Graphical modelsA graphical model (X,D,C): X = {X1,& Xn} variables D = {D1, & Dn} domains C = {F1,& ,Ft} functions (constraints, CPTS, cnfs)PbP      &>%7Tree-solving is easyTransforming into a Tree By Inference (thinking) Transform into a single, equivalent tree of sub-problems By Conditioning (guessing) Transform into many tree-like sub-problems. j:-9-Inference and Treewidth Conditioning and Cycle cutset(Search over the CutsetSearch over the Cutset (cont)(Inference vs. Conditioning By Inference (thinking)*q OutlineBackground in Graphical models AND/OR search trees and Graphs Minimal AND/OR graphs From AND/OR graphs to AOMDDs Compilation of AOMDDs AOMDDs and earlier BDDs ZZZZ aPj 0Classic OR Search Space 1AND/OR Search Space + : AND/OR vs. OR( AND/OR vs. OR with Constraints $$ AND/OR vs. OR with Constraints $$PDFS algorithm (#CSP example)(yBPseudo-Trees (Freuder 85, Bayardo 95, Bodlaender and Gilbert, 91)RC(>  Tasks and value of nodesV( n) is the value of the tree T(n) for the task: Consistency: v(n) is 0 if T(n) inconsistent, 1 othewise. Counting: v(n) is number of solutions in T(n) Optimization: v(n) is the optimal solution in T(n) Belief updating: v(n), probability of evidence in T(n). Partition function: v(n) is the total probability in T(n). Goal: compute the value of the root node recursively using dfs search of the AND/OR tree. AND/OR search tree and algorithms are ([Freuder & Quinn85], [Collin, Dechter & Katz91], [Bayardo & Miranker95],[Darwiche 2001], [Bacchus et. Al, 2003]) Space: O(n) Time: O(exp(m)), where m is the depth of the pseudo-tree Time: O(exp(w* log n)) BFS is time and space O(exp(w* log n) (2PPPsPP2 1) ()(Z%o )^   A 5   From AND/OR Tree   To an AND/OR Graph   dAND/OR Search Graphs$cAny two nodes that root identical subtrees/subgraphs (are unifiable) can be merged Minimal AND/OR search graph: of R relative to tree T is the closure under merge of the AND/OR search tree of R relative to T, where inconsistent subtrees are pruned. Canonicity: The minimal AND/OR graph relative to T is unique for all constraints equivalent to R. _ZZMk [># v=Context based cachingCaching is possible when context is the same context = parent-separator set in induced pseudo-graph = current variable + ancestors connected to subtree below -y /D>Caching ?Caching !<All Four Search Spacesv#Properties of minimal AND/OR graphs$$Complexity: Minimal AND/OR R relative to pseudo-tree T is O(exp(w*)) where w* is the tree-width of R along T. Minimal OR search graph is O(exp(pw*)) where pw* is path-width w* d" pw*, pw* d" w*log n Canonicity: The minimal AND/OR search graph is unique (canonical) for all equivalent formulas (Boolean or Constraints), consistent with its pseudo tree. b PdPPZP PPPP \1  #X,;JGSearching AND/OR GraphswAO(j): searches depth-first, cache i-context j = the max size of a cache table (i.e. number of variables in a context)d.J(Gt1Context-Based Caching OutlineBackground in Graphical models AND/OR search trees and Graphs Minimal AND/OR graphs From AND/OR search graphs to AOMDDs Compilation of AOMDDs AOMDDs and earlier BDDs ZZZZ=$.Pq OR Search Graphs vs OBDDs,AND/OR Search Graphs; AOBDDs(0AND/OR Search Graphs; AOBDDs(AOBDD ConventionsAOBDD ConventionsHCombining AOBDD (apply)IExample:JExample (continued)KAOBDD vs. OBDD Complexity Complexity of apply: Complexity of apply is bounded quadratically by the product of input AOBDDs restricted to each branch in the output pseudo-tree. Complexity of VE-AOBDD: is exponential in the tree-width along the pseudo-tree.8Z:,4 @AOMDDs and tree-BDDs$ 2Tree-BDDs (McMillan1994) are : AND/OR BDDS are *! Related workRelated work in Search Backjumping + learning (Freuder 1988,Dechter 1990,Bayardo and Mirankar 1996) Recursive-conditioning (Darwiche 2001) Value elimination (Bacchus et. Al. 2003) Search over tree-decompositions (Trrioux et. Al. 2002) Related to compilation schemes: Minimal AND/OR  related to tree-OBDDs (McMillan 94), d-DNNF (Darwiche et. Al. 2002) Case-factor diagrams (Mcallester, Collins, Pereira, 2005) Tutorial references: Dechter, Constraint processing, Morgan Kauffman, 2003 Dechter, Tractable Structures of Constraint Satisfaction problems, In Handbook of constraint solving, forthcoming. PP!PPPzP1PPP!    QR% 10p+ ConclusionAND/OR search should always be used. AND/OR BDDs are superior to OBDDs. A search algorithm with good and no-good learning generates an OBDD or an AND/OR Bdds. Dynamic variable ordering can be incorporated With caching, AND/OR search is similar to inference (variable-elimination) The real tradeoff should be rephrased: Time vs space rather than search vs inference, or search vs model-checking. Search methods are more sensitive to this tradeoff. zGPMP7PPPGM7t/TL/,9 `    - Q  AjBkCldmirtx{2345P( ` 33PP` 3333` ___MMM` 13` 333fpKNāvI` j@v۩ῑ΂H` Q_{>?" dd@,?n<d@ `7 `2@`7``2 n?" dd@   @@``PR    @ ` ` p>> b Z   (    <4" B    Th6d" B    <:"U_ B    T=d">& B    N<"P B    <E" B    C x  <"`x} ?B"0 # Z ?  s *"}` @ 0] }"2 A  <"` Q k ?D"0 # Z B  s *] m` C 0 m] 2 D  <X"`ik ?D"0 # 2 E  <t"`=m ?C"0 # 2 F  <"`.k ?D"0 # Z G  s *mJ` H 0m2 I  <"`k ?D"0 #  J  Bԡ"``   G0   K  6Xp0  G1  2 L  <س"` S  ?H"0 # Z M  s *: ` N 0: 2 O  <и"` -P  ?G"0 # 2 P  <T"` PP  ?G"0 # Z Q  s * P ` R 0P Z S B s *P ` T 0: P S2 U  <"` /  ?F"0 # 2 V  <ȝ"` S  ?F"0 # 2 W  <dx"` M  ?F"0 # ` X 0kZ Y  s *k Z Z  s * : S` [ 0 ` \ 06 k Z ]  s * ` ^ 0 Z _ B s *k 0 ` ` 0k 2 a  <p"` 0 p  ?E"0 # 2 b  <L"`30   ?E"0 # 2 c  <"` 0  ?E"0 # Z d B s *>k0 ` e 0W k0 2 f  <H"`0   ?E"0 # 2 g  <"`(0   ?E"0 # Z h  s *Jk0 ` i 0kJ0 2 j  <h"`j0   ?E"0 # Z k  s *6 k Z l  s *  ` m 0 Z n  s * : SZ o  s *W : SZ p  s *  Z q  s *>  Z r B s *  Z s B s *  ` t 0 Z u B s *k0 ` v 0k` w 0  ` x 0  ` y 0 > ` z 0 ` { 0 W  | 0hC"?S ,L' ,$ 0 Q OBDD f * g =(0( 2H  0޽h ?                                    '      !  "  ! # $ " ! % ' , ( & ' ) & # * " & + , # - ! , . 3 > 4 2 3 5 2 8 6 J 2 7 8 < : 9 8 ; > E ?  = > @ != D B "A = C #E I G $F E H %L K M &J L N 'O K Q (J O R )P K S *L P T +J 9 X ,9 U Y -U L Z .J U [ /V < \ 0V O ] 1J V ^ 2A b _ 3J A ` 4F f d 5c D e 6I j h 7g I i 8< W k 9W P l :J W m ;b L n <c L o =a P p >f P q ?g O r @j P s AJ b t BD a u CJ F v DW j w EV g x FW f y GJ a z HJ c {  3333___PPT10.mLR+.F7D' = @B DI' = @BA?%,( < +O%,( < +D' =%(D(' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*1 %(D' =-s6Bwipe(left)*<3<*1 D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*| %(+8+0+|  +^B  ;;e_ $5(   x  c $t ak     0d  M f = A*E + B*F$0( 2  0 "b L g = C*G +D*H$ 0( 2 Z L     #  2   <`%"`tm! ?B"0 # 2   <0*"`87 ?A"0 # Z   s *7t`  07tZ   s *!B `  0! 2   <0."`B ;  ?F"0 #    B8"`:   G0     6hB T  G1  Z   s *  `  0  2   <|D"`R ?E"0 # 2   <G"`t^! ?B"0 # Z   s *!R`  0[!RZ   s *[ `  0[ 2   <,L"`^R  ?E"0 # Z  B s * `  0B Z L c    # U ^2   <`P"`c t ! ?D"0 # 2   <S"`  7 ?C"0 # Z   s *2 7 t`  0 72 tZ   s * ! B `  0 != 2 !  <X"`1 B  ?H"0 #  "  BX["`   G0   #  6(m7   G1  Z $  s * ` % 0= 2 &  <+B#style.visibility<*{ %(D' =-s6Bwipe(left)*<3<*{ D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*z %(+8+0+z  +P  OOe E(   x  c $lx ak     0 0m2 ?  <"` k ?D"0 # 2 @  <\"`  m ?C"0 # 2 A  <"`x} ?B"0 # Z B  s *"}` C 0] }"2 D  <"` Q k ?D"0 # Z E  s *] m` F 0 m] 2 G  <"`ik ?D"0 # 2 H  <"`=m ?C"0 # 2 I  <L"`.k ?D"0 # Z J  s *mJ` K 0m2 L  <$"`k ?D"0 #  M  Bl"``   G0   N  6p0  G1  2 O  <̄"` S  ?H"0 # Z P  s *: ` Q 0: 2 R  <"` -P  ?G"0 # 2 S  <T"` PP  ?G"0 # Z T  s * P ` U 0P Z V B s *P ` W 0: P S2 X  <"` /  ?F"0 # 2 Y  <"` S  ?F"0 # 2 Z  <L"` M  ?F"0 # ` [ 0kZ \  s *k Z ]  s * : S` ^ 0 ` _ 06 k Z `  s * ` a 0 Z b B s *k 0 ` c 0k 2 d  <"` 0 p  ?E"0 # 2 e  <"`30   ?E"0 # 2 f  <4"` 0  ?E"0 # Z g B s *>k0 ` h 0W k0 2 i  < "`0   ?E"0 # 2 j  <"`(0   ?E"0 # Z k  s *Jk0 ` l 0kJ0 2 m  <"`j0   ?E"0 # Z n  s *6 k Z o  s *  ` p 0 Z q  s * : SZ r  s *W : SZ s  s *  Z t  s *>  Z u B s *  Z v B s *  ` w 0 Z x B s *k0 ` y 0