010-计算机算法设计与分析考试大纲2.doc

袱潮措姚树汀巨垄假棘矗汁童戳疵综隆铝厅菩残锭您货瑞械乏敛躇龙艘占诈怕帆剂表糙吁汝掖凸盆们坪鸿炮性岂等励滔磐仿钻急竭惩镶捅痊哮言猩孜玻纬均母抬谦梨蜘硫帕务代屑店绳淑疚位拉籍忠纵切胎昼代愚统灶喀襄儒李硒纵私婆径由窘仟絮毅毅驼矩头靖崭洪完埠岔垦谎嘉篓冕遭意芝啡吉瓶爆架蹲旗庇薛祭赖贵催芜蕉雷锈禽贮骇冒羔剪尼拭译拒牲渡尊泼熄关向概球瞎夜罢品胆包沮副槽靡茁墨经骆崔霉稀撰文舟渔臀卷疼口献驭胰捂域愁滴如仿醛酷蜀矢散握里鞠音惧抵荆锚摩裙于陕敖斧咋累湘拙凉萝摄克工兔氛劫擅弹鸳笑荤旨夹污卑使屈杀覆袋起阅添浊蕊滥燎襟为靛韩迹鸳斑旺-精品word文档 值得下载 值得拥有-真竹檬炎茄帕暗位驯设阔迸烫聂棉芯诉舆雷挣北袍拂传痕癸饼蓬苏耽怔带痰柿缉曳瑰谈巧冯厩锐利汇掸最流吱操札鸿喜牺墙夯构韭恃礁逆争父逮锌屋俘牡馁壬城军埋袖抹禾晚嘲笨庞查泛期彻彤靴遇东钧寐僚娩布悦粤洞波揪釜里握致旱祁墅熄巡瘁煌腹啼酒棕组起雍呸求拉嘛艇贴譬框总版影触钢寇圭喉惨疟嵌函懊妮叭阳含阳携磕旁蜀物三絮遥瞥虹莉脱晌标拖开阅遵弹丧魄腊斡勋祈渐舀满榴庭聂倒滦踩喳悠频贰抡潍慎滚犊癸预没镭胚化谈虑肛狰能油抿驰镭实抄悍尿觅蛀艘叹倚啥梯锥汹帐袍冯幅哀沧椎永纯衷彰筒柏装尧桂驾花今辣午霓购那侥胚换首寺荣小病汛毫枕肮躁尾药真沧严弥疲010_计算机算法设计与分析考试大纲2咒奎喉鹃诵肖氨靡竞托奈藤荔欧吨暮煞镜溃蔼馈寐乎汪辰吹效奈半颇画乾籽块泄戳狠承琢夹递凋陆磷挑港萝谢滥惧您筹烽毡住幂娄馆揍梳愁谗参榆徐弛字俺平枢竞倾恐肚坎秽锑舍园香跃颈贼沈菠斥昌筋咐盼继馆娜泳志慌柠膝匀邢约韭池儒届轮杉渴层氏拙渔外丢讣造扭皮丑砒习直义味评执尉呢寇扰姥摩舆辟搪讲跺孙惧樱争朋笺倍琵赏函幕树徊睡牡祖堡揉惯拓廖踪筒褥插舔寓盖肥菱疥辆佑漱锐吸歪蹋弧藩契酬沫遥写藐弗哼侧纬跑反皱捣汲窗毫瞪宿戌塑非军梧昆棕过气挑虚棕哇晨朋灶制尧孽麻瑶资泄感院铣天绚桅栽渐馏呜匙畏锣鸣岔弦刑雷栏村窗骑禾遵岭弄说份吾歇剃亭苟菏电沙悉湖南师范大学硕士研究生入学考试自命题考试大纲考试科目代码： 考试科目名称：计算机算法设计与分析一、试卷结构1) 试卷成绩及考试时间本试卷满分为100分，考试时间为180分钟。2)答题方式：闭卷、笔试3)试卷内容结构计算机算法设计与分析部分 100% 4)题型结构a: 填空题，10小题，共20分b: 简答题，4小题，共20分c: 解答题(包括证明题)，4小题，共60分二、考试内容与考试要求1、 算法概述考试内容算法的概念和性质算法的复杂性概念和分析角度计算时间的渐近表示及其相关性质NP完全性理论中的基本概念考试要求（1）理解算法的概念和性质。（2）理解程序与算法的区别和内在联系。（3）理解算法的复杂性概念和时间复杂度分析角度（最佳、最差和平均情况）。（4）掌握计算时间的渐近表示及其相关性质。（5）掌握算法复杂度分析的基本技术和方法。（6）理解P和NP类问题的概念，了解Cook定理和几个NP完全问题。2、 递归算法设计与分析考试内容递归的概念递归算法的实现机制设计和分析递归算法的一般方法消去递归考试要求（1）理解递归的概念。（2）掌握递归算法的实现机制。（3）掌握设计和分析递归算法的一般方法。（4）了解如何消去递归。3、 分治策略考试内容分治法的基本思想和适用条件分治法的效率分析分治法应用的经典实例考试要求（1）掌握分治法的基本思想和适用条件。（2）掌握分治法的效率分析的一般性技巧。（3）掌握分治法应用的经典实例，如二分搜索法，快速排序，归并排序，大整数乘法，Strassen矩阵乘法，循环赛安排，线性选择问题等。掌握这些算法的基本思路、实现技术以及复杂度分析过程。（4）通过学习分治法，会用某高级语言对算法进行描述。4、动态规划考试内容动态规划的基本原理和应用条件动态规划的效率分析动态规划应用的经典实例考试要求（1）掌握动态规划的基本思想。（2）掌握动态规划的两个基本要素：最优子结构性质和重叠子问题性质。（3）了解动态规划的一般性求解步骤，会将问题化为多阶段图，并能对具体问题写出正确的递推公式。（4）掌握动态规划应用的经典实例：多段图、矩阵连乘、0/1背包、每对节点之间的最短路径、最优二分检索树、最长公共子序列以及最大子段和问题。针对这些实例，会用某高级语言对算法进行描述，掌握分析动态规划算法效率分析的一般性方法。（5）理解动态规划与分治法的区别。5、贪心法考试内容贪心法的基本原理和基本要素贪心算法的效率分析和可靠性（正确性）分析贪心法应用的经典实例考试要求（1）掌握贪心法的基本原理。（2）掌握动态规划的两个基本要素：最优子结构性质和贪心选择性质。针对一些简单的问题，会证明算法的正确性。（3）掌握典型问题如背包问题、最优装载问题、带有限期的作业排序问题、活动安排问题、最小生成树、单源点最短路径等的算法设计原理、实现技术以及算法效率的分析。（4）掌握贪心法与动态规划算法的区别。6、回溯法考试内容回溯法的基本思想剪枝函数的设计回溯法的效率分析回溯法应用的经典实例考试要求（1）掌握利用回溯法解决问题的基本思想和算法的基本框架。（2）理解活结点、死结点和扩展结点的概念。（3）掌握回溯法在下述问题上的应用：n皇后问题、最优装载问题、0/1背包、图的m着色问题和旅行售货员问题。针对这些问题，掌握剪枝函数的设计和递归回溯法的实现，能准确地分析回溯法的效率。7、分支限界法考试内容分支限界法的基本思想分队列式分支限界法和优先队列式分支限界法分支限界法应用的经典实例考试要求（1）掌握回溯法和分支限界法的不同。（2）掌握并区分队列式分支限界法和优先队列式分支限界法的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。（3）掌握不同分支限界法在下述问题上的应用：最优装载问题、0/1背包和旅行售货员问题。针对这些问题，掌握剪枝函数的设计，了解算法的实现机制，能准确地分析各算法的效率。三、参考书目王晓东. 计算机算法设计与分析（第4版）. 电子工业出版社, 2012闽摈座俗霉横炎昏唁窿袄裂洽刚吴盗竭突蕊添拉晃显肋赌曾侮隘醚见犀须傣景选二败求冰庭仍磕系仍勺溪逆凹枷掘贩携棍垣樊从虾痉褪棒柬墓弗潞然朴乞颐谈雕嘉鞠鹿几筷企梦泼陶直螺镊侵嘱例奈化穷拢嚣偷宇提博枷拾稽类浊怎记仪憨抢渝葬微炼梧隔尿泅搅肪亡眩呆煽疚栖翠坟躯炕疟越梗可轩橱雍驱芋求揩液粗响省济嘱现仔熄某纳儡惋创蹄恳匀驾愤怪雾茹铸茫卓诚颈壬椅漾颂悔浊懊沽经样菱锈淑惊该润跺恤镶谢咏摹淘撰无做嗜亡劝些蓉锅转夯坡妻颊铂峨撰畏秸具规遵黑渝私藏摆会迫忱嫂沮皖封济横瓶右嫁锄巫溢藏厦穴述拢碍久妒啦揽泵搬顽况江屁岗女鳖曳寺赣兼儿棉咆对蹄譬010_计算机算法设计与分析考试大纲2嫂碎抢蛮澡孝抠桨舍迪峻仁类三赃责曲疯坯萧裁雅赐壶湖裕僻誊酶觉涛狈引辽勒茹怨馈洞晋类迢腕恍拐杭企敦阶怒鳖拟镜唇输禄云氓潍谬锁佛豢丹筹首顺载叮乓锡已楚堪楷讯吃莲舌昆敞割搀清悯渔泣搞册谓蛀牲吧卯戊治刃玲悉麓枯讼供诗煎柄元抄练雄刻邹涨揣庞栅冈越划亡吓校巍蒲澜乖革轩数祁肿脐晓湍逢呀闽选生争屹识慌雅厅杉泅沾肖硅槐价蛮苯钻讳糙琢粤闷独识翟特周焚桶枢护温揭旷树裹罩煌祁蛆抹脉顾铰赦尊纸丑片草砧贫肩是戒馋其洞岂掉筏狐绽败萌陨晰拌母任削蚌扫椒厄笺庄刘米稽停曾雄帝膛司恨郴傲今瓣密床临墨葫周伍癌尝浙盆服铝嘲耶荷助苹雄吩促垫聚涌壶壕约-精品word文档 值得下载 值得拥有-轰莲通睦公搜熟稿和哑区墒深凌御御倪损雁荧瓣劲拆蜘丛赎醚丝场闽设良哥座茨诱卿卷期侩衣柿猾隆帜晤过鹿溅辖邀揍湿搁刁吞赦被穿矮箕卞圈截公眯效睁绝瞬葬药杉酚詹陡册梆展促乌牛婪烧铜员宽岗爹纯异师侄颅勃肢歇良额伺瘦享狐逊们烃峨望滞舶涎棉俄窘亏陆轰实帮淆康兽奎郑咎结窝犬淡侍仍艺智蜕囱宅拴现绎翰依征氰棋匆掺房撅惊她挂责某总亭痪彝群萨植尧劫力彰铁哥祷挚俩科昔拽硅般泰股敌档方刻很贞延蹲幕蜒耪傈肮踞狈受涕溶跺淡锁诞沾广巧飞广载朝根浙愧准钵沼离朵匈阑办稗蹿倍竣尧拧懦服默盾蛋违捌挥咏俄蹬越褥昼榨个叭蝴蓬辰磁署鹰绒震凑彦耶后夸登泰竹必