深圳大学计算机与软件学院
《算法设计与分析》课程教学大纲
一、课程基本信息
课程编号:2315200201/2315200202
课程名称:算法设计与分析/ Design and Analysis of Algorithms
课程类别:综合选修课
适用专业:计算机专业
先修课程:高级语言程序设计、高等数学、线性代数、离散数学、数据结构
开课学期:秋季
开课院系:计算机与软件学院
总学时:54
周学时:2-1
学分:2.5
二、课程性质和任务
算法设计与分析课程是计算机类专业的专业基础课.是一门面向设计,处于计算机科学与技术学科核心地位的教育课程.通过对计算机算法系统的学习与研究,理解和掌握算法设计的主要方法,培养对算法的计算复杂性进行正确分析的能力,为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础.本课程以算法设计策略为知识单元,系统地介绍计算机算法的设计方法与分析技巧,以期为计算机学科的学生提供广泛坚实的计算机算法基础知识.
三、课程内容及要求
1.算法引论
算法定义及特征,算法设计的例子,时间复杂性,时间复杂性分析,空间复杂度分析*.
要求:了解计算机算法的定义以及特征.掌握算法设计的例子.理解时间复杂性的定义以及相关概念,掌握复杂性分析的几种类型以及分析方法.
2.递归与分治策略
递归的基本思想,递归算法的例子,分治的基本思想,多项式乘积的分治算法,Strassen矩阵乘法,合并排序*
要求:理解递归算法以及分治算法的基本思想,掌握多项式乘积的分治方法.能对递归算法以及分治算法进行分析.理解Strassen矩阵乘法的理论分析以及编程实现.掌握合并排序算法.
3.贪心算法,
贪心算法的设计思想,背包问题,单源最短路径问题,活动安排问题,最优花费树*问题.
要求:理解贪心算法的设计思想以及适用范围,掌握贪心算法典型例子如背包问题,单元最短路径问题以及活动安排问题的解决方案.
4.动态规划算法,
动态规划的思想方法,最优决策原理,多段图的最短路径问题,0 /1 背包问题,资源分配问题,矩阵连乘问题*
要求:理解动态规划算法的设计思想以及适用范围,掌握最优决策原理的概念以及分析方法.掌握动态规划算法典型例子如多段图的最短路径问题,0 /1 背包问题的解决方案.
5.回溯法
回溯法的思想方法,N后问题,回溯法解0/1背包问题,哈密顿回路问题*,回溯法的效率分析
要求:理解回溯法的设计思想以及适用范围,掌握解空间树的概念并能熟练应用于回溯法.掌握回溯算法典型例子如N后问题,0 /1 背包问题的解决方案.了解回溯法的效率分析方法.掌握N后问题能程序实现的方法.
6.分支限界法
分支限界法的基本思想,0 /1 背包问题,货郎担问题,
要求:理解分支限界法的设计思想以及适用范围,掌握分支限界法典型例子如0 /1 背包问题,货郎担问题的解决方案.
7.NP问题
NP问题基本概念,一些典型的NP完全问题,近似算法及实例
要求:了解P,NP,NPC问题的分类,概念以及关系,了解典型的NP问题的例子.
(注:带*号者为选讲内容.根据学生其他内容的掌握情况而定)
四、学时分配建议
总学时:54
讲授学时:36

下一页