《算法设计》教学大纲

1、算法设计（Algorithm Design）课程代码：5241057学分：2学时：32（其中：课程教学学时：20，实验学时：12）先修课程：程序设计基础、数据结构适用专业：计算机科学与技术，软件工程教材：王晓东，计算机算法设计与分析(第四版)，电子工业出版社，2013开课学院：计算机与软件学院一、课程性质与课程目标（一）课程性质随着计算机的广泛应用，对计算机算法的研究变得日益重要。本课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；本课程首先介绍计算复杂性的定义和算法分析的基本方法，结合计算机科学及应用领域中常见的有代表性的非数值算法，介绍

2、了几种重要的算法设计方法：分治法、动态规划、贪心法、回溯法、分支限界法以及NP完全问题。使学生在掌握各种算法的同时，掌握算法分析的基本方法和技巧。（二）课程目标课程目标包括知识目标和能力目标，具体如下：课程目标1：通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术，培养学生分析算法复杂度的初步能力，能够运用算法知识解决各自学科的实际问题；课程目标2：能够运用计算思维分析问题和解决问题，培养学生的独立科研能力和理论联系实际的能力，锻炼其逻辑思维能力和想象力，并使之了解当今算法理论的发展。（三）课程目标与专业毕业要求指标点的对应关系本课程支撑专业培养计划中的毕业要求指标点5.2

3、和12.1。毕业要求指标点5.2：在计算机领域复杂工程问题的建模、模拟或解决过程中，能够使用恰当的技术、软硬件及系统资源和研发工具，提高解决复杂工程问题的能力和效率；毕业要求指标点12.1：了解计算机技术发展中取得重大突破的历史背景以及当前的热点问题，了解信息技术发展的前沿和趋势。课程目标毕业要求指标点课程目标1课程目标2毕业要求5.2毕业要求12.1二、课程内容及教学要求通过课堂讲授、课堂练习和讨论互动、课后作业和上机实验等教学手段，系统介绍计算机算法的有关概念和算法设计的基本技巧。使学生掌握计算机算法的基本概念和特性，了解计算机相关学科中算法分析与设计技巧的重要性，掌握算法时间复杂性的分析

4、方法和基本的算法设计策略，结合具体问题实例，使学生重点掌握分治法、蛮力法、回溯法、分支限界法、贪心法、动态规划法、网络流、几何计算和概率算法及近似算法等常见的算法设计策略，了解计算复杂性基本理论，具备灵活运用所学解决实际应用问题的能力。本课程基本要求是：首先了解并掌握计算复杂性的定义和算法分析的基本方法；结合计算机科学及应用领域中常见的有代表性的非数值算法，重点掌握几种重要的算法设计方法：分治法、动态规划、贪心法、回溯法、分支限界法以及NP完全问题。使学生在掌握各种算法的同时，掌握算法分析的基本方法和技巧。第1章算法概述教学内容1. 算法的定义；2. 算法设计与分析（如何设计、表示、确认和分析

5、算法）；3. 掌握使用大O记号、W记号、Q记号表示算法复杂度的估算方法。（二）教学要求1.了解算法与程序的概念；2. 理解学习算法设计的目的；3. 理解算法的概念和特性；4. 掌握算法的描述方法；5. 了解算法分析的内容；6. 掌握不同的算法时间复杂度的分析方法。（三）重点与难点1. 重点问题求解过程、系统生命周期。2. 难点算法的几种不同时间复杂度分析的估算方法。第2章递归与分治策略（一）教学内容1.递归与分治2.分治策略设计技巧（二）教学要求1.了解递归的概念；2. 理解分治法的基本思想；3. 掌握分析递归算法时间复杂度的计算方法；4. 掌握用分治策略求最大最小元问题；5. 掌握用分治策略

6、进行二分搜索；6. 掌握用分治策略进行合并排序和快速排序；7. 掌握用分治策略完成Strassen矩阵乘法。（三）重点与难点1. 重点掌握分析递归算法时间复杂度的计算方法；用分治策略进行合并排序和快速排序，用分治策略完成Strassen矩阵乘法。2. 难点掌握分析递归算法时间复杂度的计算方法；用分治策略完成Strassen矩阵乘法。第3章动态规划教学内容1. 动态规划的基本概念，算法框架；2. 动态规划算法应用。（二）教学要求1. 了解动态规划算法的概念与步骤；2. 理解动态规划算法与分治法、贪心法的异同；3. 掌握动态规划算法的基本要素最优子结构性质；重叠子问题性质；4. 掌握设计动态规划算

7、法的步骤；5. 掌握多段图问题、关键路径问题算法的设计与分析；6.掌握最长公共子序列问题的算法设计与分析；7.掌握每对结点间的最短路径问题的算法设计与分析；8.掌握0/1背包问题的算法设计与分析。（三）重点与难点1.重点掌握动态规划算法的基本要素：最优子结构性质；重叠子问题性质；掌握设计动态规划算法的步骤；掌握最长公共子序列问题的算法设计与分析；掌握最长公共子序列问题的算法设计与分析。2.难点理解并掌握动态规划算法的基本要素：最优子结构性质；重叠子问题性质；掌握0/1背包问题的算法设计与分析；掌握最长公共子序列问题的算法设计与分析。第4章贪心算法（一）教学内容1.贪心算法概念；2. 贪心算法设

8、计范例。（二）教学要求1. 了解贪心算法的概念；2. 理解贪心算法的基本要素最优子结构性质；贪心选择性质；3. 掌握最优装载问题的算法分析；4. 掌握哈夫曼编码的算法分析；5. 掌握单源最短路径的Dijkstra算法的设计与分析；6.掌握最小生成树的Prim和Kruskal算法的设计与分析。（三）重点与难点1.重点理解贪心算法的基本要素：最优子结构性质；贪心选择性质；掌握最优装载问题的算法分析；掌握单源最短路径的Dijkstra算法的设计与分析。2.难点掌握单源最短路径的Dijkstra算法的设计与分析。第5章回溯法（一）教学内容1. 回溯法的基本概念及定义；2. n皇后问题；3. 图的着色问

9、题；4. 哈密顿环问题；5. 0/1背包问题；6. 批处理作业调度。（二）教学要求1. 了解回溯法的思想及算法框架；2. 掌握装载问题、批处理作业调度问题、符号三角形问题、0-1背包问题、图的着色问题的算法设计与分析方法；3. 掌握n皇后问题、最大团问题的回溯法的算法设计与分析。（三）重点与难点1.重点掌握批处理作业调度问题、0-1背包问题、图的着色问题的算法设计与分析方法。2.难点掌握批处理作业调度问题、图的着色问题的算法设计与分析方法。第6章分支限界法（一）教学内容分支限界法的定义及算法框架；最优解的分支限界法；带时限的作业排序问题研究；0/1背包问题的分支限界解决方案。（二）教学要求1.

10、 理解并掌握分支限界法的一般方法；2. 掌握求最优解的分支限界法；3. 掌握采用分支限界法解决带时限的作业排序问题；4. 掌握采用分支限界法解决0/1背包问题。（三）重点与难点1.重点分支限界法的定义及算法框架。2.难点采用分支限界法解决带时限的作业排序问题。第7章 NP完全问题（一）教学内容1. NP完全问题的定义及基本概念；2. Cook定理和证明；3. 典型的NP完全问题。（二）教学要求1. 理解NP类的基本概念，NP有关的术语，NP类的特性；2. 理解Cook定理的证明；3. 掌握一些典型的NP完全问题的算法。（三）重点与难点1.重点NP类的基本概念，NP有关的术语，NP类的特性。2.

11、难点Cook定理的证明。三、本课程开设的实验项目编号实验项目名称学时类型要求支撑的课程目标1用分治法斯特拉森矩阵乘法2验证性必做课程目标12分治法实现大整数相乘法2验证性必做课程目标13贪心算法作业调度问题2验证性必做课程目标14动态规划算法资源分配问题2验证性必做课程目标15动态规划算法最长公共子序列问题2验证性必做课程目标16回溯法8-皇后问题2验证性必做课程目标1实验1：分治法斯特拉森矩阵乘法1. 实验目的及要求1）理解分治法的应用场合及分治法算法的递推关系式；2）掌握斯特拉森矩阵的算法及算法时间复杂度的分析；2. 实验主要内容1）设A和B是两个n*n阶矩阵，求它们的乘积矩阵C。（假设n

12、=2k）；2）自行建立两个n*n阶矩阵，然后执行7次子矩阵乘法和10次加（减）法得到7个中间矩阵；3）再使用8次子矩阵加（减）法得到最终的乘积矩阵，并分析算法时间复杂度。3. 重难点算法的设计及算法时间复杂度的分析。实验2：分治法实现大整数相乘法1. 实验目的及要求1)掌握分治算法的原理；2）掌握大整数相乘法的算法及算法时间复杂度的分析；2. 实验主要内容1）采用分治法求解两个十进制大整数的乘法，以提高乘法的效率，减少乘法次数；2）将n位的十进制整数X和Y各分为2段，每段的长为n/2位；3）利用公式：XY=AC10n+(A-B)(D-C)+AC+BD10n/2+BD完成大整数相乘；4）对上述算

13、法进行算法时间复杂度的分析。3. 重难点算法的设计及算法时间复杂度的分析。实验3：贪心算法作业调度问题1. 实验目的及要求1) 握贪心算法的原理；2）熟悉多机调度问题的算法；3）进一步掌握贪心算法；4) 提高分析与解决问题的能力。2. 实验主要内容1）设有4个作业，每个作业的时限为(d0，d1，d2，d3)=(2，1，2，1)，收益为(p0，p1，p2，p3)=(100，10，15，27)。先用贪心算法求解该问题，并测试程序，直至正确为止；2）针对问题实例，实录运行时的输入、输出文件；3）将程序和实录的界面存盘备用。3. 重难点算法的设计及算法时间复杂度的分析。实验4：动态规划算法资源分配问题

14、1. 实验目的及要求1）掌握用动态规划方法求解实际问题的基本思路；2）掌握用动态规划方法求解实际问题的基本思路。2. 实验主要内容1）掌握用动态规划方法求解实际问题的基本思路；2）在Windows环境下用C语言实现该算法。记录实验的数据及执行结果（即最优分配方案、最优分配方案的值）、运行时间；3）记录各实例的数据及执行结果（即最优分配方案、最优分配方案的值）、运行时间。3. 重难点分析算法的时间和空间复杂度，并由此解释释相应的实验结果。实验5：动态规划算法最长公共子序列问题1. 实验目的及要求1) 进一步掌握动态规划法的原理；2）并能够按其原理编程实现求两个序列数据的最长公共子系列，以加深对其

15、的理解。2. 实验主要内容1）用动态规划法解决最长子序列问题；2）用动态规划法解决最长子序列问题；3）输出两个序列的最长公共子序列。3. 重难点分析算法的时间和空间复杂度，并由此解释释相应的实验结果。实验6：回溯法8-皇后问题1. 实验目的及要求1) 巩固和加深对回溯法的理解；2）回溯法8-皇后问题；3）能够对上述算法进行时间复杂度分析。2. 实验主要内容1）在nn格的棋盘上放置彼此不受攻击的n个皇后；2）按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子；3）理解皇后不被攻击的条件，编程模拟国际象棋规则，输入多组皇后，输出所有的解。3. 重难点分析算法的时间和空间复杂度

16、，并由此解释释相应的实验结果。注：本课程为专业课，授课对象为大二学生，实验类型主要包括验证性和设计性实验，均需要提交实验报告，实验报告主要包括实验目的、实验内容、预习内容、实验步骤、算法的时间复杂度分析以及总结。实验评价内容和评分细则参见附录1。四、学时分配及教学方法章教学形式及学时分配主要教学方法支撑的课程目标课堂教学实验上机课程实践小计第一章算法概述22讲授、案例、演示课程目标1， 2第二章递归与分治策略448讲授、案例、自学、实验课程目标1第三章动态规划448讲授、对比、自学、讨论、实验课程目标1第四章贪心算法224讲授、演示、自学、实验课程目标1第五章回溯法224讲授、自学课程目标1第

17、六章分支限界法44讲授、案例、演示、讨论、自学、实验课程目标1第七章NP完全问题22讲授、案例、演示、讨论、自学、实验课程目标1， 2合计201232注：1.课程实践学时按相关专业培养计划列入表格； 2.主要教学方法包括讲授法、讨论法、演示法、研究型教学方法（基于问题、项目、案例等教学方法）等。五、课程考核 1. 课程考核方式包括期末考试、平时作业和实验情况考核。考核形式考核要求考核权重备注平时作业及阶段测试课后完成1015个习题，主要考核学生对每节课知识点的复习、理解和掌握度，计算全部作业的平均成绩再按15%计入总成绩；可让学生查阅资料，了解本课程相关技术发展情况，自主学习并完成。15%根据

18、平时作业得分取平均值或结合平时测试情况实验完成6个实验，主要训练学生应用所学知识构建实验系统，并进行实验的能力，最后按15%计入课程总成绩。15%评分细则见附录1课程报告课程报告包括实验目的、实验内容、实验步骤以及实验分析与总结，课程报告成绩的70%计入课程总成绩。平时成绩*0.3+课程论文成绩*0.7=综合成绩70%期末采用提交课程报告的方式。六、参考书目及学习资料1.陈慧南. HYPERLINK /11055510.html 算法设计与分析：C+语言描述（第2版）.电子工业出版社.2012；2.吕国英.算法分析与设计.清华大学出版社.2006；3. HYPERLINK /writer/%E7%BD%97%E4%BC%AF%E7%89%B9%60%E5%A1%9E%E5%A5%87%E5%A8%81%E5%85%8B_1.html t _blank 罗伯特.塞奇威克， HYPERLINK /writer/%E8%8F%B2%E5%88%