附件1：
《算法设计与分析》课程教学大纲
课程中文名称：算法设计与分析
课程英文名称： The Design and Analysis of Algorithm
课程编号：033082C1 学分：3
总学时：48 实验学时：8 开课学期：4
适用专业：软件工程专业 先修课程：数据结构、C++
后续课程：程序语言课程设计、各专业方向模块课 开课单位：软件学院
一、课程性质和教学目标（需明确各教学环节对人才培养目标的贡献，即专业人才培养目标中的知识、能力和素质）
课程性质：本课程是软件工程专业掌握程序设计技能的一门专业基础课。通过介绍算法的复杂性的分析方法和常用的算法设计技术及相应的经典算法，使得学生掌握算法设计的基本方法，以及学会如何评价算法的好坏，旨在帮助学生完成从“会编程序”到“编好程序”的角色转变，提高学生实际求解问题的能力。通过这门课程的学习帮助学生培养良好的软件工程习惯和软件思维方法。
教学目标：本课程从算法复杂性分析的基本方法和原理入手，以讲授算法设计的基本方法和原理，算法优化的基本方法和技巧为主，通过典型的问题及相应的求解算法及算法复杂性分析，开阔学生在算法设计与分析中的思路，活跃学生的思想，锻炼学生解决问题的动手能力。
（对应毕业要求：1.3、2.5、3.8） 具体要求如下：
（1）能够应用数学知识进行计算机算法的设计与实现。（对应毕业要求：1.3） （2）能够分析复杂计算机工程问题，利用经验理论知识进行抽象化，建立合理模型，并能快速的解决问题。（对应毕业要求：2.5）
（3）能对特定需求进行算法设计和程序实现，并能测试验证算法与程序的正确性和复杂性。（对应毕业要求：3.8）
3
上机学时：0
二、课程教学内容及学时分配（含实践、自学、作业、讨论等的内容及要求）
较为系统的掌握算法设计的基本方法和算法分析的基本技术，熟悉常用的计算机算法，
能够运用所学的基本方法求解一些实际应用的问题。 1. 算法问题求解基础（2学时）：
主要内容：算法的基本概念、算法设计与分析的基本方法、递归与归纳定义及一般方法，递归的基本概念；解决实际问题：汉诺塔、斐波那契数列
要求：了解算法和算法复杂度的基本概念；掌握时间复杂度的估算方法。 作业：1-1、1-3、1-11 2. 算法分析基础（2学时）：
主要内容：算法的定量分析（时间复杂度、空间复杂度），了解程序运行运算来确定时间复杂度的评价，掌握事前分析中的程序步分析算法、渐近表示法、递推法、了解分摊分析；解决实际问题：汉诺塔
要求：了解算法复杂度的基本概念；掌握时间复杂度的估算方法 作业：2-8、2-11、2-17 3. 分治法（6学时）：
主要内容：基本概念，介绍分治思想求解问题时的分-治-合的思想一般方法，与一般的递归相比，分治往往会带来更高效的算法。介绍如二分检索，归并排序，快速排序，选择问题，斯特拉森矩阵乘法等应用分治的典型例子。
要求：掌握递归的概念，学会用递归方法解决实际问题；熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。 作业：5-9、5-11、5-12 实验一：分治法 4. 贪心法（6学时）：
主要内容：主要介绍贪心算法局部最优到全局最优的贪心性质。基本概念以及解决问题的思路以及贪心算法经典示例例如：哈夫曼编码、单源最短路径、最小生成树和背包问题等，并介绍拟阵理论。
要求：掌握利用贪心算法解决问题的基本思想，会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。 作业：6-1、6-3、6-8、6-10 实验二：贪心法
3
5. 动态规划（6学时）：
主要内容：介绍动态规划的基本概念和解决问题的步骤，以及动态规划算法在提高递归算法效率时的应用条件：最优子结构和重复子问题。经典的动态规划算法使用示例如：多源最短路径、最长公共子序列、背包问题、矩阵链乘法、最优二分检索树、流水线调度问题等。 要求：熟练掌握利用动态规划方法解决问题的基本思想，学会如何将问题化为多阶段图的方法，并能对具体问题写出正确的递推公式。 作业：7-1、7-9、7-15 实验三：贪心法 6. 回溯法（6学时）：
主要内容：介绍了回溯法的基本概念和解决问题的步骤，理解回溯法系统搜索解空间的思想和算法平均效率高的原因，掌握两种回溯法范型实现。学会利用问溯法求解诸如：n-皇后问题，子集和数问题，图的着色，哈米尔顿环，背包问题、批处理作业调度等。 要求：掌握利用回溯法解决问题的基本思想，会用回溯法解决：n个皇后问题，图的m着色问题，子集和数问题等。 作业：8-1、8-7、8-9、8-10 实验四：回溯法 7. 分支限界法（4学时）：
主要内容：介绍了分支限界法的基本概念和分枝界限法利于求解最优化问题的本质原因，掌握分枝界限法广度优先队列周游的技巧。并学会使用分支限界法解决问题：带时限的作业排序、背包问题，旅行商问题、批处理问题等。
要求：掌握利用分支限界法解决问题的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。 作业：9-2、9-8
8. 介绍NP-难度问题和NP-完全问题的基本概念，若干NP-难度问题的证明，理解多项式
规约的重要意义了解最基本的NPC问题SAT问题，并了解如何证明团集、顶点覆盖和独立集问题都是NPC问题（自学）。 三、教学方法
课程教学以课堂多媒体教学为主，利用精品资源共享课网络教学资源实现课下学习互动，开设实验、布置作业等共同实施。
3
本课程安排四次实验：
1、分治法：掌握合并排序的基本思想，学会利用分治法解决实际问题，并学会分析算法的时间复杂度。
2、贪心法 ：掌握贪心算法的基本思想，学会用贪心法分析和解决实际问题，对单机作业调度问题贪心法的求解思想和设计方法。
3、动态规划算法：掌握动态规划算法的基本思想，对具有实际意义的多段图问题进行设计和实现，并求解算法的复杂度。
4、回溯法：掌握回溯算法的基本思想，通过n皇后问题求解熟悉回溯法，并且使用蒙特卡洛方法分析算法的复杂度。 四、教材及参考书
（一）使用教材
《算法设计与分析—C++语言描述》，王幸民 , 郝晓丽，人民邮电出版社，2016 （二）参考书目
1、《算法设计与分析》，王晓东编著，清华大学出版社，2010。
2、《Fundamentals of Computer Algorithms》，E.Horowitz and S.Sahni，Computer Science Press，1978.
3、《The Design and Analysis of Computer Algorithms》,A.V.Aho, J.E.Hoperoft,and J.D.Ullman，Addison-Wesley Publicatting Company,1978.
4、《Introduction to Algorithms》(third edition),T.H.Cormen,C.E.Leiserson，R.L.Rivest and C.Stein， the MIT Press,2001中文名《算法导论(第二版)》(影印版)，高等教育出版社
5、《计算机算法基础》（第三版），余祥宣，崔国华，邹海明，华中科技大学，2003.
五、考核及成绩评定方式
平时成绩（50分） 实验 （40分） 结课考试成绩（50分） 试题 考核方式：闭卷考试
撰稿人： 审核：
修订日期：2018.09
1.3、2.5、3.8 评价环节 网上互动学习（10分） 1.3、2.5、3.8 评估毕业要求 3
《算法分析与设计》教学大纲2018 - 图文
