算法设计与分析课程教学大纲

算法设计与分析课程教学大纲课程英文名称：AlgorithmicDesign&Analysis课程编号：0800360学分：3.0学时：32+16（实验）课程教学对象数学与计算科学学院信息与计算科学专业本科学生。课程性质及教学目的课程性质:本课程是信息与计算科学专业专业选修课。该课程包括理论教学(32学时)和课内实验(16学时)两个环节。目的和任务:通过本课程的学习，可以开阔编程思路，编写出优质程序；通过许多常见且有代表性算法的学习，使学生理解和掌握算法设计的基本方法，熟悉算法分析的基本技术，同时掌握算法分析的基本方法和技巧，培养对算法时间、空间复杂性进行正确分析能力，锻炼其逻辑思维能力和想象力，使学生具有问题抽象和建模的初步能力，并使之了解算法理论的发展；同时鼓励学生运用算法知识解决本学科的实际问题，培养学生独立科研的能力和理论联系实践的能力，为独立的设计算法和给定算法进行复杂性分析打下良好的基础，并能熟练运用一些常用算法，为学生进一步学习后续课程奠定良好的基础。对先修知识的要求离散数学，C++程序设计，数据结构课程的主要内容、基本要求和学时分配建议（总学时数:理论课32学时）知识模块知识点要求学时学习方式课外学习要求1、绪论1.1算法的基本概念C1课堂讲授1.2算法分析A1课堂讲授2、NP完全理论2.1P类问题和NP类问题B1课堂讲授2.2NP完全问题C1课堂讲授3、蛮力法3.1蛮力法的设计思想A1课堂讲授3.2查找问题中的蛮力法B1课堂讲授3.3排序问题中的蛮力法B1课堂讲授3.4组合问题中的蛮力法B1课堂讲授4、分治法4.1分治法的设计思想A1课堂讲授4.2排序问题中的分治法B1课堂讲授4.3组合问题中的分治法C1课堂讲授4.4几何问题中的分治法B1课堂讲授5、减治法5.1减治法的设计思想A1课堂讲授5.2查找问题中的减治法B1课堂讲授5.3排序问题中的减治法B1课堂讲授5.4组合问题中的减治法C1课堂讲授6、动态规划法6.1动态规划法的设计思想A1课堂讲授6.2图问题中的动态规划法A1课堂讲授6.3组合问题中的动态规划法C1课堂讲授6.4查找问题中的动态规划法B1课堂讲授7、贪心法7.1贪心算法的设计思想A1课堂讲授7.2图问题中的贪心法（1）A1课堂讲授7.3图问题中的贪心法（2）B1课堂讲授7.4组合问题中的贪心法C1课堂讲授8、回溯法8.1回溯法的设计思想A1课堂讲授8.2图问题中的回溯法（1）A1课堂讲授8.3图问题中的回溯法（2）B1课堂讲授8.4组合问题中的回溯法C1课堂讲授9、分支限界法9.1分支定界法的设计思想A1课堂讲授9.2图问题中的分支限界法(1)A1课堂讲授9.3图问题中的分支限界法(2)B1课堂讲授9.4组合问题中的分支限界法C1课堂讲授建议使用教材及参考书1、理论课教材：王红梅.算法设计与分析[M].北京：清华大学出版社，2006.72、实验课教材：王红梅.算法设计与分析[M].北京：清华大学出版社，2006.73、主要参考文献：[1]王晓东，算法设计与分析（第2版）[M]，清华大学出版社，2008.1[2]陈慧南，算法设计与分析[M]，电子工业出版设，2006.5[3]吕国英，算法设计与分析[M]，清华大学出版社，2009,1课程考核方式（宋体小三号字）以闭卷考试为主，结合平时成绩和上机实验报告评定成绩。其中平时成绩占10％(含作业和考勤)，上机实验报告占20％，期末笔试考试成绩占70％。课内实验环节及要求（16学时）序号实验项目实验内容实验目的及要求学时1求最大公约数求两个自然数m和n的最大公约数（1）复习数据结构课程的相关知识，实现课程间的平滑过渡（2）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同（3）对所设计出来的算法采用大O符号进行时间复杂性分析22串匹配问题（1）给定一个文本，在该文本中查找并定位任意给定字符串（2）实现BF算法（3）实现BF算法的改进算法：KMP算法和BM算法（4）对上述3个算法进行时间复杂性分析，并设计试验程序验证分析结果（1）深刻理解并掌握蛮力法的设计思想（2）提高应用蛮力法设计算法的技能23最近对问题（1）给出平面上n个点构成集合S，设计算法找出集合S中距离最近的点对（2）分别用蛮力法和分治法求解（3）分析算法的时间性能，设计实验程序验证分析结论（1）进一步掌握递归算法的设计思想以及递归程序的调试技巧（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中248枚硬币问题（1）在8枚外观相同的硬币中，有一枚是假币，并且已知假币和真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计减治算法来检测这枚假币（2）设计实验程序，考查用减治技术设计的算法是否高效（3）扩展算法，使之能处理n枚硬币中有1枚假币的问题（1）深刻理解并掌握减治法的设计思想（2）提高应用减治法设计算法的技能（3）理解这样一个观点：建立正确的模型对于问题的求解时非常重要的25最大子段和问题（1）给定由n个整数（可能有负整数）组成的序列，求该序列的子段和的最大值，当所有整数均为负整数时，其最大子段和为0（2）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法（3）比较不同算法的时间性能（1）深刻掌握动态规划法的设计思想并能熟练运用（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果26霍夫曼编码（1）证明霍夫曼树满足最优子结构性质（2）设计贪心算法求解霍夫曼编码（1）了解前缀编码的概念，理解数据压缩的基本方法（2）掌握最优子结构性质的证明方法（3）掌握贪心算法的设计思想并能熟练运用270/1背包问题（1）设计一个0/1背包问题，给出可能解得表示方法，构成解空间树（2）设计回溯算法完成问题求解（3）设计测试数据，统计搜索空间的结点数（1）掌握回溯法的设计思想（2）掌握解空间树的构造方法，以及在求解过程中如何存储求解路径（3）考查回溯法求解问题的有效程度28电路布线问题（1）对电路布线问题建立合理的模型，通过实验确定一个合理的限界函数（2）设计算法实现电路布线问题（1）进一步掌握分