《算法分析与设计》课程教学大纲【课程编号】：14314025【英文译名】：Analysis and Design of Computer Algorithms【适用专业】：软件工程、计算机科学与技术、信息安全【学分数】：3【总学时】：48学时【实践学时】：0一、本课程教学目的和课程性质本课程是软件工程、计算机科学与技术、信息安全等专业的选修课程，也可作为其它计算机相关专业的选修课程。
课程属于专业教育课。
课程主要介绍计算机算法分析、算法设计及复杂性理论的基本概念、基本的算法分析方法和常用的算法设计方法。
通过本课程的教学，强化学生算法分析与设计的基础理论知识，使学生掌握计算机算法分析的基本方法及常见的算法设计方法（如：分治法、回溯法、贪心法、动态规划法、分枝限界法等）。
通过学习，学生能够用利用常见的算法设计方法来解决软件开发中的实际问题。
培养扎实的专业知识和基本技能和从事应用软件开发和测试的能力。
二、本课程的基本要求本课程的基本要求是让学生理解计算机算法效率分析与设计所涉及的基本概念和基础知识，掌握基本的算法分析方法和常见的算法设计方法，能熟练应用课程介绍的算法设计方法来解决软件开发中的实际问题。
通过对算法实例的分析，进一步加深学生对算法设计方法的认识和理解。
1、理解算法的基本概念和算法的效率分析方法。
2、理解分治策略的原理、效率分析，掌握分支策略在常见问题（如：二分检索、归并分类、快速排序、选择问题等）问题中的应用。
了解分治策略的变形（减治策略、变治策略）的思想和简单应用。
3、理解动态规划的原理、适用条件，了解算法的效率，掌握该算法在常见问题（如：多段图、最优二分检索树、0/1背包问题、货郎担问题、可靠性设计等）问题中的应用。
4、理解贪心方法的原理、效率分析方法，掌握在常见问题（如：背包问题、带有期限的作业排序、最小生成树、单源点最短路径等）问题中的应用。
5、理解回溯法的原理，掌握在常见问题（如：8-皇后、子集和数、图的着色、哈密顿环等）问题中的简单应用。
6、了解分支-限界方法的基本思想和简单应用。
7、了解基本的检索和周游方法的基本思想。
8、了解NP-难度和NP-完全问题基本思想和简单应用。
9、了解概率算法的基本思想及简单应用。
三、本课程与其他课程的关系该课程主要涉及算法的分析与设计，要求学生具备较好的程序设计能力，具有一定的数据结构、离散数学和数学分析基础。
前修课程：离散数学、数据结构四、课程内容（一）算法的概念与效率分析基础1、算法分析基础：算法的定义和特征，算法的时间复杂性、空间复杂性，算法运行时间估计，最优算法，递归算法的效率分析；2、算法的表示：伪代码的使用。
重点：算法的定义和特征，算法效率分析的基本方法和表示方法、递归算法的效率分析。
难点：算法时间复杂性的估计与表示、递归算法的效率分析。
（二）分治策略1、分治策略率的基本原理和效率分析；2、分治策略的典型问题应用及算法的效率分析（如：二分检索、找最大和最小元素、归并分类、快速分类、选择问题、斯特拉森矩阵乘法）；3、分治策略的变形（减治策略、变治策略）及简单应用。
重点：分治策略的基本思想及其应用。
难点：二分检索、归并分类、快速分类等问题中的算法时间复杂性的分析。
（三）贪心方法1、贪心方法的基本思想、适用条件和效率分析；2、贪心方法的典型问题的应用及算法效率分析（背包问题、带有限期的作业排序、最优归并模式、最小生成树、单源点最短路径）。
重点：贪心策略的基本思想及其适用条件。
难点：背包问题、最小生成树问题、最短路径问题的解决方法及时间复杂性的分析。
（四）动态规划1、动态规划的基本思想和适用条件，最优性原理；2、动态规划典型问题的应用及算法效率分析（如：多段图、每对结点之间的最短路径、最优二分检索树、0/1背包问题、可靠性设计、货郎担问题、流水线调度问题等）。
重点：动态规划的基本思想、适用条件及其应用。
难点：多段图、最短路径、0/1背包、可靠性设计、货郎担问题的解决方法及时间复杂性的分析。
（五）基本检索及周游方法1、图的基本检索与遍历方法简介；2、深度优先搜索及其应用；3、广度优先搜索及其应用。
重点：图的遍历的基本思想及其应用。
难点：图遍历算法的时间复杂性的分析。
（六）回溯法与分支限界法1、回溯法的基本思想及效率估计，限界函数；2、回溯法在典型问题（8-皇后问题、子集和树的问题、图的着色、哈密顿环、背包问题等）中的简单应用及算法；3、分支限界法的基本思想及简单应用。
重点：回溯法的基本思想、适用条件及其简单应用。
难点：限界函数的确定，8-皇后问题、子集和数问题、图的着色问题的解决方法及时间复杂性的分析。
*（七）概率算法1、概率算法的概念；2、随机数；3、数值概率算法。
重点、难点概率算法的概念、随机数的概念、数值概率算法。
*（八）NP-完全问题1、计算模型；2、P类与NP类；3、NP完全问题；4、NP完全问题的近似算法。
重点：NP完全问题的基本概念和计算模型。
难点：NP完全问题的近似算法。
*（九）计算复杂性引论1、计算模型：图灵机；2、k带图灵机和时间复杂性；3、离线图灵机和空间复杂性；4、带压缩和线性增速复杂性；5、类之间的关系归约；6、完全性；重点：计算模型—图灵机。
难点：各类图灵机的时空复杂性分析。
注：打“*”为选将内容。
五、教学方法建议本课程涉及了常见算法分析方法和算法设计技术，比较抽象且难懂。
建议采用案例教学并结合演示让学生理解和掌握各种算法设计方法，通过课堂讨论、课后作业和实验训练，加强学生对各种算法设计方法的掌握。
六、考核方式考核可采用开卷笔试，主要考察学生应用算法设计方法来解决具体问题的能力，再结合平时作业及课堂讨论的表现来考核，平时成绩占总成绩的30%~40%。
七、选用教材及主要参考书1、教材[1] (美) Anany Levtin著. 算法分析与设计基础，潘彦译，清华大学出版社，2004年6月2、参考资料[1] 余祥宣,崔国华，邹海明.计算机算法基础（第二版）.武汉：华中科技大学出版社 . 2000[2] [沙特] M.H. Alsuwaiyel 著，吴伟昶等译.算法设计技巧与分析 .电子工业出版社,2004算法设计与分析英文名称：The Design and Analysis of Computer Algorithms课程编号：COMP4024总学时：32（授课32）学分：2适用对象：计算机专业三年级以上学生先修课程：程序设计语言、离散数学、数据结构使用教材及参考书：[1] 王晓东,《算法设计与分析,清华大学出版社》,2003[2] 刘晓东,《计算机算法设计与分析》,西安交大讲义,1990[3] 朱洪等,《算法设计与分析》,上海科技文献出版社,1989[4] [美]萨拉.巴斯,《计算机算法：设计与分析引论》,上海科技文献出版社, 1989[5] H.Ellis,S.Sartaj,R.Sanguthevar著,冯博琴,叶茂等译,《计算机算法,机械工业出版社》,2006[6] B.Gilles,B.Paul著,邱仲潘等译,《算法基础》,清华大学出版社,2005[7] M.H.Alsuwaiyel著,《算法设计技巧与分析》,电子工业出版社,2003一、课程性质、目的和任务性质：选修课目的：计算机算法设计与分析是继数据结构之后的一门计算机专业基础课程，目的在于加强和培养学生的专业技术理论的抽象和应用能力，掌握好的算法设计和分析方法对学生提高计算机科学理论和素质的作用日显重要。
任务：本课程对计算机科学中总结抽象出的最常用的算法设计策略（分治、贪心、动态规划、回溯、分枝界限法等）、算法分析技术（算法复杂度、T（n）、S（n）等）以及算法理论进行了介绍，期望学生理解和掌握算法设计策略的思想和技巧；本课程对计算机算法的分析评价有一个较为系统规范的方法和科学评价指标，为学生分析评价选择算法奠定基础。
在今后的算法设计工作中能够灵活地运用有关知识，以人为本、物尽所能地设计出恰当合理正确高效的算法在计算机上运行。
二、课程内容简介“计算机科学的核心是算法”。
计算机算法设计与分析是一门专业基础课程，计算机算法设计与分析是继数据结构之后的一门计算机专业基础课程，目的在于加强和培养学生的专业技术理论的抽象和应用能力，掌握好的算法设计和分析方法对学生提高计算机科学理论和素质的作用日显重要。
本课程对计算机科学中总结抽象出的最常用的算法设计策略（分治、贪心、动态规划、回溯、分枝界限法等）、算法分析技术（算法复杂度、T（n）、S（n）等）以及算法理论进行了介绍，期望学生理解和掌握算法设计策略的思想和技巧；本课程对计算机算法的分析评价有一个较为系统规范的方法和科学评价指标，为学生分析评价选择算法奠定基础。
在今后的算法设计工作中能够灵活地运用有关知识，以人为本、物尽所能地设计出恰当合理正确高效的算法在计算机上运行。
实验内容:本实验是“计算机算法设计与分析”课程教学的必要环节。
本实验的目的是配合课程，通过对具体问题按照不同设计策略设计算法、编写程序上机实践、对运行结果进行分析评价，培养学生应用已学算法知识解决问题的能力。
要求学生掌握每种策略的基本设计思想和基本设计方法，对具体问题能采用适宜的策略设计出相应的算法、分析出所设计算法的性态，如能再做出一定的算法改进更好。
本实验要求用计算机高级语言编程，上机实现，最后提交实验报告。
实验基本内容和模式：对教授的分治法、贪心法、动态规划法、回溯法、分枝限界法等一些常用的典型的算法设计策略掌握其思想和具体实现方法。
对给定的问题确定适当的解题策略，编程实现解题算法，分析时间和空间复杂度，按照或改进复杂度评价自己的算法。
三、教学基本要求1．通过对经典算法设计策略的分析，让学生理解并掌握算法设计的基本策略和技术；2．通过对算法复杂度的介绍，使学生掌握算法分析评价选择的指标；3．通过对算法设计和分析的实践，锻炼培养学生运用算法理论和技术解决实际问题的能力，不仅掌握怎样做的技巧，还要明白为什么这样做的道理。
四、教学内容及要求Ⅰ算法分析部分一、概述1 算法的基本特性2 算法分析的目的3 算法的描述4 算法效率的度量要求：理解各名词、术语的含义，掌握算法相关的基本概念；了解理解算法编写的基本规范和描述方法。
二、算法复杂度的测度1 几个术语2 复杂性的渐进性态及其阶要求：理解算法复杂度的表示符号的含义，掌握算法性能的分析方法。
三、算法效率的度量１各个句子的统计２加法规则３乘法规则要求：掌握算法性能的分析统计方法，会表示和统计算法复杂度。
四、递归方程的解法１递归、递归程序2 递归方程的解要求：掌握递归算法的分析统计方法，会解递归方程。
五、存储空间复杂度的测度要求：能比照算法时间复杂度的分析统计方法处理空间复杂度。