ch5_作业题

ch5 回溯法：10. 回溯法在问题的解空间树中，按__ 深度优先___策略，从根结点出发搜索解空间树。

12．下列算法中通常以深度优先方式系统搜索问题解（D）。

D、回溯法20.下面哪种是回溯法中为避免无效搜索采取的策略（B）B.剪枝函数32、回溯法搜索状态空间树是按照（C ）的顺序。

C 深度优先遍历42．0-1背包问题的回溯算法所需的计算时间为（A）A、O（n2n）9、以深度优先方式系统搜索问题解的算法称为回溯法。

30.回溯法是一种既带有系统性又带有跳跃性的搜索算法。

33．回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。

37. 图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是m n，解空间树中每个内结点的孩子数是m。

9.请画出用回溯法解4皇后问题的解空间树和搜索空间树：解空间树：用回溯法的搜索空间树：11，请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10}，价值为{20, 30, 25}，背包容量为25时搜索空间树。

答：解空间树：搜索空间树：1不可行解价值=20价值=55价值=30价值=25价值=011 110 0 01128 1112 14 15 1310691111111123457 8 1112 14 15310694.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。

4.解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。

解空间树为：该问题的最优值为：16 最优解为：（1，1，0）。

1．某企业生产两种产品的有关资料如下表所示。

要求：从相对数和绝对数两方面来分析由于销售量和价格的变动对企业销售总额的影响。

销售额总指数及绝对增减额：I pq=p1q100=300∗12+2000∗21=45600=142.5% p1q1−p0q0=45600−32000=13600销售量总指数及由于销售量变动引起的销售额绝对增减额：I q=p0q100=300∗10+2000∗20=43000=134.375% p0q1−p0q0=43000−32000=11000价格总指数及由于价格变动引起的销售额绝对增减额：I p=p1q1p0q1=300∗12+2000∗21300∗10+2000∗20=4560043000=106.047% p1q1−p0q0=45600−43000=26002．某企业生产某产品的总成本和产量资料如下表所示。

要求：计算产量总指数以及由于产量增长而增加的总成本绝对额。

产量总指数：I q=q2014q2013p2013q201320132013=15001000∗50+28002000∗80=187=143.85%由于产量增长而增加的总成本绝对额：q2014q2013p2013q2013−p2013q2013=187−130=57（万元）3．某集团公司销售的三种商品的销售额及价格变动资料如表所示。

要求：从相对数和绝对数两方面分析公司销售总额变动的原因。

销售额总指数及绝对增减额：I pq=p1q1p0q0=150+45+510100+50+500=705650=108.46% p1q1−p0q0=705−650=55销售量总指数及由于销售量变动引起的销售额绝对增减额：I q=1p1p0p1q100=150/(1+1%)+45/(1+5%)+510/(1−2%)=711.7802 =109.505%p0q1−p0q0=711.7802−650=61.7802价格总指数及由于价格变动引起的销售额绝对增减额：I p=p1q11pp0p1q1=150+45+510150/(1+1%)+45/(1+5%)+510/(1−2%)=705711.7802 =99.05%p1q1−p0q0=705−711.7802=−6.78024．某市2013年社会商品零售额为12亿元，2014年增加为15亿元。

18.IMS网络中，I-CSCF与P-CSCF之间的接口采用（ SIP协议）
19.IMS系统中用户的第一个接入点是（ P-CSCF ）
20.IMS网络中存储所有与用户和业务相关数据的服务器是（ HSS ）
19.当IMS网络中部署了多个HSS时，找到一个合适HSS的功能实体是（ SLF ）
20.IMS网络中，S-CSCF与I-CSCF之间的接口采用（ SIP协议）
19.基于从HSS处收到的能力集来为用户指定一个S-CSCF的功能实体是（ I-CSCF ）
20.IMS网络中，MRFC与MRFP之间的接口采用（ H.248协议）
18.IMS网络中，P-CSCF与S-CSCF之间的接口协议是（ SIP协议）
19.IMS的入口点IP地址对应的网元是（ P-CSCF ）
20.从HSS下载用户信息和与业务相关数据的功能实体是（ S-CSCF ）
30.IMS网络中，不同的CSCF之间的接口采用 SIP协议协议。

20.IMS网络中CSCF与HSS之间，采用（ Diameter协议）
18.IMS网络中，MGCF与IMS-MGW之间的接口采用（ H.248协议）
34.HSS/IMS/ CSCF（中文解释）。

第五章 光的衍射5.10 用波长为632.8nm 的激光束测量单缝宽度，若测得中心附近两侧第五个极小间的距离为6.3cm ，缝与屏的距离为5cm ，试求缝宽？ 解：上述装置中激光束射到单缝上可视为平行光入射，在逢后5cm 接受，这是夫琅禾费衍射.(参考教材例题5.2)单逢夫琅禾费衍射，产生极小值的条件为sin 1,2n n n θλ==±±据题意：25 3.1510sin sin 5a λθθ-⨯=≈9425632.81055100.53.1510a m mm ---⨯⨯⨯∴=⨯=⨯5.11测得一细丝的夫琅禾费零级衍射斑的宽度为1cm ，已知入射光波波长为632.8nm ，透镜焦距为50cm ，求细丝的直径？ 解 ：由sin a θλ=得：0.5sin 0.0150θ≈= 632.863280632.80.01a nm m μ===5.12折射率分别为n 1和n 2、厚度为d 、表面平行的两块玻璃片彼此对接，覆盖一定宽度的狭缝，两片各盖住缝宽的一半，单色平行光垂直入射到狭缝上.在什么条件下夫琅禾费衍射图样的中心是暗的？ 解：衍射图样的中心是在衍射角0θ= 的方向缝的上、下部相对应点在P 点的光程差为：12(n n )d ∆=-当21)2m λ∆=+（时，衍射图样中心处为暗纹.若取0m =，则12()2n n d λ-=时，P 点处为暗纹.5.13一束直径为2mm 的氦氖激光（λ=632.8nm ）自地面射向月球.已知月球离地面的距离为3.76×105km.问在月球上得到的光斑有多大？不计大气的影响.若把这样的激光束扩大到直径为2m 和5m 后在发射，月球上的光斑有多大？ 解:激光束的发射角1031.221.226328100.386210Dmradλθθ--∆=⨯⨯∆==⨯光斑半径为：145.163R L Km θ=∆⨯=；则其直径为：2R 290.272k m φ==若D=2m ，则290.272m φ=；若D=5m ，则116m φ=. 可见衍射斑的大小与衍射孔径的大小成反比. 5.14一会聚透镜，直径为3cm ，焦距f 为20cm ，问：（1）为了满足瑞利判据，两个遥远的点状物体必须有多大的角距离？（设λ=550nm ）. （2）在透镜焦平面上两个衍射图样的中心相隔多远？解: (1)由瑞利判据，当两个点状物体的角距离等于零级衍射斑的角半径时，则可分辨，则有：50 1.222.2410rad Dλθθ-===⨯(2)两衍射斑中心距离（透镜焦平面上）252010 2.2410 4.47310L f m θμ--=⋅=⨯⨯⨯=5.18由紫光在（λ=400nm ），绿光（λ=500nm ）和红光（λ=750nm ），三种波长组成的平行光垂直入射到一个光栅上，光栅常数为0.005mm ，用'1f m =的透镜把光谱会聚于焦平面上，问：第二级红线、第三级绿线和第四级紫线之间的距离为多少？解：第二级红线衍射角的正弦：2322750sin 0.3510d λθ-⨯===⨯ 第三级绿线衍射角的正弦：3333500sin 0.3510d λθ-⨯===⨯ 第四级紫线衍射角的正弦:4344400sin 0.32510d λθ-⨯===⨯ 可见第二级红线与第三级绿线在屏上重合，且与第四级紫线的距离为42(sin sin )1(0.320.30)0.0220L f m mm θθ'≈-=⨯-==5.20用波长为0.5890µm 的单色光照射一光栅，已知该光栅的缝宽0.0010a mm =，不透明部分宽度0.0025b mm =，缝数NN=105条.试求： （1）中央峰的角宽度；（2）中央峰内干涉主极大的数目； （3）第一级谱线的半角宽度. 解：（1）由22aλθθ=∆=得：0.58902 1.1781rad θ=⨯= （2）中央峰内主极大数目为：3.5d a b m a a+=== 此时中央峰内有0级到±3级干涉主极大K 2317∴=⨯+=条（3）中央峰的角宽度为：cos nd λθθ∆=其中：cos θ==代入数据得：-61.710rad θ∆=⨯5.21一块平面透射光栅，在1mm 内有500条狭缝，现对钠光谱（0.5893m λμ=）进行观察，试求：（1）当光束垂直入射到光栅上时，最多能看到几级光谱？ （2）当光束以30°角入射时，情况如何？解 ：据题意有：当光垂直入射时31210500d mm -==⨯ maxsin 3.14d d m θλλ==≈当光束以30°角入射时：(sin30sin )o d m θλ+=max (sin 30sin 90)5o o d m λ+==（取整数）5.22一块透射光栅由2N+1条缝组成，除中央一条缝的宽度为2a 外，其他2N 条缝的缝宽均为a ，相邻各缝之间的间隔d=4a.试分析此光栅在焦平面上的光强分布与各缝均为a ，间隔为d=4a 的光栅的异同.（提示：将2N+1条缝分成两部分，考虑两部分之间的相干叠加.）解：将2N+1条缝分成两部分，上半部分N 条，下半部分N 条，两部分的光程差 对于0级：sin 0 0 I 4I θ=∆==上 对于1级： sin asin I 4I 44daλλλθθ====上对于2级：2sin asin I 022d a λλλθθδπ===== 对于3级：23333sin asin I 2I d 442a λλθθλδπ===== 对于4级：缺级4da = 对于5级： 55sin I 2I 2d λθδπ===上 对于6级：6sin 3 I 0d λθδπ=== 对于7级：77sin I 2I 2d λθδπ===上 比较：相同：极大位置相同，0级光强相同. 不同：奇数级次强度减半，偶数级次强度为0.5.30在菲涅耳圆孔衍射中，若以一枚硬币作为圆盘（01cm ρ=），令0R r =，取0.5m λμ=，若要求圆盘中心有足够的亮度（圆盘挡住的部分恰好为一个半波带），则光源与观察屏的距离应为多少？解：第一个半波带被档时，屏上光振动的合振幅A 为：111122o a aA a a a =-=-=- 其中a 0是光波自由传播时，即波面没有被遮蔽时的振幅，因为102a a ≈，所以屏上的光强为： 22104a I A I ===5.32单色平行光垂直照射到直径30d cm =的圆孔上，在离圆孔 3.6r km =处的平面上产生菲涅耳衍射图样.如果要在离孔4r cm =处的屏上观察到一个相似的衍射图样，圆孔的直径应改为多少？解：当圆孔所的波带数相同时，得到相似的衍射图样.平行光入射时，2n R r ρλ→∞=，据题意：2222121201020102r d d r r r ρρλλλλ==或 222120202211301014(310) 3.610r r d d d r r λλ-===⨯⨯⨯ 24222110 1101d m d m cm --=⨯=⨯=5.33一块很大的平行平面玻璃，在其中央镀一层圆形透明薄膜，膜后500d nm =，折射率1.5n =，直径1D mm =，当可见光垂直入射时，哪一个波长的光可以在哪一个点获得光强为不镀膜时九倍？（忽略玻璃板与薄膜的损耗）. 解：设不镀膜时P 0点光振动的合振幅为：102a a =镀膜后，要求合振幅03A a =，可以写为：11103322a aA a a =+== 可以设想：所镀膜厚产生π的相位差所镀膜区域大小对P 0点是一个半波带，即第一个半波带在P 点产生的振幅是a 1，相位与第二个半波带相同.从第二个半波带到∞个的合振幅为：26144223435()() 2222222a a a a a aa a a a a a a ∞∞-+-++=-+--+--++≈- 镀膜后：22103322a aA a a =--≈-=（1） 由于镀膜使相位改变π，即波长满足以下关系式：(1)2n d λ-=2(1)500n d nm λ=-=（2）镀膜部分为第一个半波带，即：201r ρλ= 2204(0.5)500510r mm ρλ-===⨯5.36半波带片第五环半径为1.5mm ，求波带片对于波长为0.5m μ的单色光的焦距'f 和第一环半径r ，若波带与屏幕之间充以折射率为n 的介质，将发生什么变化？解：由2f n ρλ=，45 1.5,510,5mm mm n ρλ-==⨯=得：241.5900 5105f mm -==⨯⨯又因为j ρ=41,900,510j f mm mm λ-===⨯得：0.67mm ρ==若充以介质后，光波波长将变小，其焦距将变长.。

Ch5Write out the word with the first letter given in each blank space:1.We are willing to offer you a s pecial__ discount of 5% on future order a mounting_ to STG5000 ormore.2.Your price is out of l ine_______ with the prevailing_____ market.3.As the c____________ is very keen here, your price will put us out of m________.4.If you are able to a__________ shipment from mid-December to the m__________ of October, wewill place an order for 50 metric tons.5.As the amount of this t____________ is below STG2500, we would like payment to bem_________ by D/P.6.We are pleased to inform you that we will a_________ you a special discount of 3% on any orderfor quantity of more than 200 cases, in a___________ to a 2% discount.7.I am afraid that the number of articles you r_________ is below the m__________ quantity oforder.8.Since you are in urgent need of the goods, we will try to p___________ our manufacturers toe___________ your order for delivery in August.9.U____________, we received your acceptance of our offer four days late. The price hasr__________ by 10% since August 15.10.We are e__________ a 5% rise in the price of the raw material early nest month. You wouldb__________ by ordering now.3、competition market4、advance middle5、transaction made6、allow addition7、require minimum8、persuade entertain9、unfortunately risen10、expecting benefitII. Fill in the blanks with proper prepositions:1.As regards your request ______ an 8% commission, we regret that we cannot meet your wishes aswe are dealing ______ other buyers on the basis of a 5%commission.2.We would suggest that you reconsider our terms and see your way to fall ______ line_____ otherbuyers.3.In order to meet you _____ this occasion, we are prepared to grant you a special discount of 3%_____ condition that the quantity to be ordered id not less than 1000 pieces.4.If you take the quality _____ account, you will find our price is _____ fact more favourable thanthose quoted by other suppliers.5.Since considerable business has been done _____ this price, we trust that it will also be acceptable______ you.6.While we thank you for your offer of July 9, we find it very regretable to point out that your pricesappear to be _____ the high side and that there is no possibility ____ business.7.Thank you for your letter of May 25, ____ which you ask us ____ a keener price of our raincoat.8.We regret that there is no room _____ reduction ____ our quoted price.9.We regret being unable to allow you any discount _____ our price which is very reasonable andacceptable _____ our clients in your country.10.We are sorry that we cannot meet your requirements _____ the time being because of shortage____ stock.1、for with2、into with3、on on4、into in5、at to6、on of7、in for8、for in9、in to10、for of1.If you take into account the quality of the goods, you will find that our price is reasonable.2.Owing to a very heavy demand and as we have a pile of orders to fulfill, we can accept ordersonly for shipment in October.3.If you increase the quantity of your order from 3,500 dozen to 5,000 dozen, we are prepared togrant you a discount of 4%.4. As the prices for cotton piece goods are going up in the world market, we have to adjust theprice we quoted you last month from STG13 per yard to STG14.5 per yard.5. We shall be glad to consider granting you a special discount of 5% on condition that youplace a single order amounting to STG1, 000 or over.6. We are taking your request for terms of D/P into consideration and believe that we shall be ableto inform you of our decision in a few days.7. We grant you an 8% discount as an exception with a view to promoting business between us.8. As the cost of raw materials has gone up lately, the 2% discount is the best we can offer.9. As regards your bid at USD45 per metric ton, we regret that we cannot accept, as we have donebusiness with other customers at the price of USD50 per metric ton.10. Our price is fixed on a very reasonable level. But in order to bring the transaction to a fruitfulconclusion we hope that you will let us have your reasonable counter-offer indicating the quantity required for our reference.We have received your offer of May 5 and the samples of Men's Shirts, for which we thank you.While appreciating the good quality of your products, we have to point out that your price is out of line with the current market, and very good quality of men's shirts from European manufacturers are available at prices from 8% to l0% below yours. Such being the case, we have to request you to reduce your price to USD22 per dozen.As our order is a large one, to the value of around USD60, 000, please take it into consideration and give us an early reply.Re: 2,500 Pairs Leather ShoesWe thank you for your offer of March 12 for the captioned goods and the sample you sent us.We are satisfied with the price you quoted and the quality of the shoes. But we regret that we cannot accept the terms of payment by sight irrevocable L/C as we are doing business with other suppliers on D/P terms.We believe that you will be glad to confirm the above terms by telex so that we can send you our formal order together with detailed shipping instructions.Reply to letter 4:1 Price: USD0.80 per yard2 minimum quantity: 7500 yards3 discount: a 5% discount is granted on condition that the quantity of a single order is up to 10,000 yards。

`第五章综合的约束与优化综合的一个很重要的概念就是：单纯的映射是远远不够的，更重要的是设计的整体优化。

一方面设计工程师为综合规定必要的约束，例如对面积、速度、功耗的要求等，从而使优化有所依据；另一方面选择合适的综合器是优化程度的决定性因素。

同一个设计使用不同的综合器所得到的优化结果可以相差3～5倍。

第一节综合约束5-1-1 概述综合约束是对可测量的电路特性所定义的设计目标，比如面积、速度和电容等。

如果没有这些约束，Design Compiler工具将不能有效地对你的设计进行最优化。

在对设计进行优化时，Design Compiler支持两种类型的约束：●设计规则约束（Design rule constraints）●最优化约束（Optimization constraints）设计规则约束是固有的，在工艺库里定义；这些约束条件是为了保证设计的功能正确性，适用于使用工艺库的每一个设计；可以使这些约束比最优化约束更为严格。

最优化约束是外在的，由设计者自己定义；最优化约束描述设计指标，在整个dc_shell 工作期间应用于当前设计；它们必须接近于现实情况。

D esign Compiler试图同时满足设计规则约束和最优化约束，但设计规则约束必须首先被满足。

设计者可以以命令行形式交互式的指定约束或者在一个约束文件里指令约束。

图5.1显示了主要的设计规则约束和最优化约束，以及如何用dc_shell界面命令来设置这些约束。

图5.1 Major Design Compiler Constraints第二节设置设计规则约束这一节将讨论最常用的设计规则约束：•转换时间（Transition time）•扇出负载（Fanout load）•电容（Capacitance）Design Compiler给设计对象赋予属性来表示这些设计规则约束。

表5.1列出了每一个设计规则约束对应的属性名。

表5.1 设计规则属性Design Rule Constraint Attribute NameTransition time max_transitionFanout load max_fanoutCapacitance max_capacitancemin_capacitanceCell degradation cell_degradationConnection class connection_class 设计规则约束是工艺库里指定属性，你也可以明确地、随意地指定这些约束。