一．概况1． 开课学院（系）和学科： 软件学院 软件工程2． 课程名称：算法设计与分析 (The Design and analysis of Algorithms)3． 课程代码：P0375014． 学时/学分：54 学时/ 3学分5． 预修课程：无6． 课程主干内容: 第1章讨论什么是算法以及算法设计的目的；第2章涉及数学归纳法，熟悉归纳法对于算法设计和分析有莫大的帮助；第3章讨论算法分析，描述了算法分析的过程，给出了算法分析所需要的工具和记法；第4章介绍数据结构，讨论数据结构的选择对于有效算法设计的影响；第5章介绍基于归纳的算法设计思想；第6章到第9章分别讨论4个领域的算法：序列和集合上的算法，关于图和树的算法，几何算法、数值和代数算法（如矩阵乘法、快速傅立叶变换等）。第10章涉及归约或约简，它是第11章的序幕，后者涉及NP完全问题和计算复杂性理论；第12章则介绍并行计算模型以及一些典型的并行算法。7． 适应专业学科： 软件工程8． 教材/教学参考书：教材UDI MANBER著，黄林鹏 等译，《算法引论：一种创造性方法》，电子工业出版社 2005教学参考书Aho等著，黄林鹏 王德俊 张仕 译，《计算机算法的设计与分析》，机械工业出版社 ，2007 年 二．课程的性质和任务 本课程讲授算法设计背后的创造性思想，通过阐述算法开发步骤来描述算法设计过程。课程将算法设计过程和定理归纳证明过程进行类比以揭示算法设计的基本思想和本质，学生通过学习可提高问题求解能力和理解算法设计的过程和思想。三．课程的教学内容和基本要求1.算法设计简介a)什么是算法？b)为何设计算法c)如何设计算法2.算法分析技术 a)算法分析记法b)算法分析技术c)递推关系求解3.数据结构和算法设计a)记录b)链表c)散列d)树图4.基于归纳的算法设计a)分治法b)动态规划c)算法正确性5.序列和集合的算法a)搜索b)排序c)顺序统计d)数据压缩e)序列比较f)概率算法6.图算法a)图的遍历b)拓扑排序c)最短路径d)图的分解e)图的匹配f)网络最大流量g)哈密尔顿回路7.几何算法a)多边形算法b)凸包算法c)最近点对d)线段交点计数8.代数和数值算法a)欧几里德算法b)多项式乘法c)距阵乘法d)快速傅里叶变换9.NP完全问题a)计算模型b)P类与NP类问题，NP完全问题，顶点覆盖问题、支配集问题、3SAT问题、3着色问题以及团（clique）问题10.并行算法a)并行计算模型b)共享存储器算法c)互连网络上的算法 d)脉动计算 四．实验（上机）内容和基本要求 五．对学生能力培养的要求通过学习本课程，学生应具备以下能力：（1）能正确理解基于归纳的算法设计的基本思想，理解算法设计、复杂性分析、正确性证明之间的潜在关系；（2）能熟练地运用所学知识设计出有效的算法以解决实际问题。（3）能对算法进行复杂性分析，并说明算法的适用性。六．其它需要说明的内容本课程教学中采用多媒体教学手段 教学环节教学时数课程内容讲课实验习题课讨论课上机课外实践其它算法设计简介4算法分析技术4数据结构和算法设计6基于归纳的算法设计8序列和集合的算法8图算法8几何算法4代数和数值算法4NP完全问题4并行算法4

(无)

平时成绩加期末考试。

• UDI MANBER著，黄林鹏 等译，《算法引论：一种创造性方法》，电子工业出版社 2005Aho等著，黄林鹏 王德俊 张仕 译，《计算机算法的设计与分析》，机械工业出版社 ，2007 年