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

算法设计与分析课程教学大纲课程英文名称Algorithmic DesignAnalysis课程编号学分:学时:

08003603.0（实验）32+16

一、课程教学对象数学与计算科学学院信息与计算科学专业本科学生

二、课程性质及教学目的课程性质本课程是信息与计算科学专业专业选修课该课程包括理论教学（学时）和课内实验（学时）两个环节3216目的和任务:通过本课程的学习，可以开阔编程思路，编写出优质程序,•通过许多常见且有代表性算法的学习，使学生理解和掌握算法设计的基本方法，熟悉算法分析的基本技术，同时掌握算法分析的基本方法和技巧，培养对算法时间、空间复杂性进行正确分析能力，锻炼其逻辑思维能力和想象力，使学生具有问题抽象和建模的初步能力，并使之了解算法理论的发展；同时鼓励学生运用算法知识解决本学科的实际问题，培养学生独立科研的能力和理论联系实践的能力，为独立的设计算法和给定算法进行复杂性分析打下良好的基础，并能熟练运用一些常用算法，为学生进一步学习后续课程奠定良好的基础

三、对先修知识的要求离散数学,程序设计，数据结构C++

四、课程的主要内容、基本要求和学时分配建议（总学时数理论课学时）32知识点要求学时学习方式课外学习要求知识模块

1、绪论L1算法的基本概念C课堂讲授

11.2算法分析A课堂讲授

12、NP完全理论

2.1P类问题和NP类问题B课堂讲授

12.2NP完全问题C课堂讲授

13、蛮力法

3.1蛮力法的设计思想A课堂讲授

13.2查找问题中的蛮力法B课堂讲授

13.3排序问题中的蛮力法B课堂讲授

13.4组合问题中的蛮力法B课堂讲授

14、分治法

4.1分治法的设计思想A课堂讲授

14.2排序问题中的分治法B课堂讲授

14.3组合问题中的分治法C课堂讲授

14.4几何问题中的分治法B课堂讲授

15、减治法

5.1减治法的设计思想A1课堂讲授

5.2查找问题中的减治法B1课堂讲授

5.3排序问题中的减治法B课堂讲授

15.4组合问题中的减治法C课堂讲授

16、动态规划法

6.1动态规划法的设计思想A课堂讲授

16.2图问题中的动态规划法A课堂讲授

16.3组合问题中的动态规划法C课堂讲授

16.4查找问题中的动态规划法B1课堂讲授

7、贪心法7」贪心算法的设计思想A课堂讲授

17.2图问题中的贪心法

（1）A1课堂讲授

7.3图问题中的贪心法

（2）B1课堂讲授

7.4组合问题中的贪心法C课堂讲授

18、回溯法

8.1回溯法的设计思想A课堂讲授

18.2图问题中的回溯法

（1）A1课堂讲授

8.3图问题中的回溯法

（2）B课堂讲授

18.4组合问题中的回溯法C1课堂讲授

9、分支限界法

9.1分支定界法的设计思想A课堂讲授

19.2图问题中的分支限界法

（1）A课堂讲授

19.3图问题中的分支限界法

（2）B课堂讲授

19.4组合问题中的分支限界法C课堂讲授1

五、建议使用教材及参考书、理论课教材王红梅.算法设计与分析北京清华大学出版社,1[M].

2006.

7、实验课教材王红梅.算法设计与分析北京清华大学出版社,2[M].

2006.

7、主要参考文献3王晓东，算法设计与分析（第版）清华大学出版社，

[1]2[M],

2008.1陈慧南，算法设计与分析电子工业出版设，吕国英，算法

[2][M],

2006.5

[3]设计与分析清华大学出版社[M],,2009,1

六、课程考核方式（宋体小三号字）以闭卷考试为主，结合平时成绩和上机实验报告评定成绩其中平时成绩占（含作业和考勤），上机实验报告占期末笔试考试成绩占10%20%,70%

七、课内实验环节及要求（学时）16实验目的及要求序号实验项目实验内容学时1求最大公约数求两个自然数m和n的最

（1）复习数据结构课程的相2大公约数关知识，实现课程间的平滑过渡2理解这样一个观点不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同3对所设计出来的算法采用大0符号进行时间复杂性分析2串匹配问题21给定一个文本，在该文1深刻理解并掌握蛮力法的本中查找并定位任意给定字设计思想符串2提高应用蛮力法设计算法2实现BF算法的技能3实现BF算法的改进算法KMP算法和BM算法4对上述3个算法进行时间复杂性分析，并设计试验程序验证分析结果3最近对问题21给出平面上n个点构成1进一步掌握递归算法的设集合S,设计算法找出集合S计思想以及递归程序的调试技中距离最近的点对巧2分别用蛮力法和分治2理解这样一个观点分治法求解与递归经常同时应用在算法设3分析算法的时间性能，计之中设计实验程序验证分析结论48枚硬币问题21在8枚外观相同的硬币1深刻理解并掌握减治法的中，有一枚是假币，并且已设计思想知假币和真币的重量不同，2提高应用减治法设计算法但不知道假币的技能与真币相比较轻还是较3理解这样一个观点建立正确的模型对于问题的求解重可以通过一架天平来任时非常重要的意比较两组硬币，设计减治算法来检测这枚假币2设计实验程序，考查用减治技术设计的算法是否高效3扩展算法，使之能处理n枚硬币中有1枚假币的问题5最大子段和问题21给定由n个整数可能1深刻掌握动态规划法的设有负整数组成的序列，求计思想并能熟练运用该序列的子段和的最大值，2理解这样一个观点同样的当所有整数均为负整数时，问题可以用不同的方法解决，一其最大子段和为0个好的算法是反复努力和重新2分别用蛮力法、分治法修正的结果和动态规划法设计最大子段和问题的算法3比较不同算法的时间性能6霍夫曼编码21证明霍夫曼树满足最1了解前缀编码的概念，理优子结构性质解数据压缩的基本方法2设计贪心算法求解霍2掌握最优子结构性质的证夫曼编码明方法3掌握贪心算法的设计思想并能熟练运用70/1背包问题21设计一个0/1背包问1掌握回溯法的设计思想题，给出可能解得表示方法，2掌握解空间树的构造方法，构成解空间树以及在求解过程中如何存储求2设计回溯算法完成问解路径题求解3考查回溯法求解问题的有3设计测试数据，统计效程度搜索空间的结点数8电路布线问题21对电路布线问题建立1进一步掌握分支限界法的合理的模型，通过实验确定设计思想，掌握限界函数的设计一个合理的限界函数技巧2设计算法实现电路布2考查分支限界法求解问题线问题的有效程度，并与回溯法进行对比3理解这样一个观点好的界限函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能在搜索早期对超出目标函数界的结点进行丢弃，减少搜索空间，从而尽快找到问题的最优解。