计算机算法设计与分析

课程编码：180086083500P1001H 英文名称：The Design and Analysis of Computer Algorithms 课时：60 学分：3.00 课程属性：学科核心课 主讲教师：陈玉福

本课程为软件工程一级学科研究生的核心课程。本课程讲授和讨论计算机算法设计
的基本思想、设计策略与技巧，算法的空间、时间复杂性分析技术和理论。通过本课程的学习，希望学生能掌握常用经典计算机算法的基本设计思想和策略，能够将实际问题抽象成算法问题，分析与界定问题的难度，设计求解算法；掌握算法的空间和时间复杂性分析技术；了解计算机算法与分析前沿研究领域，了解最新研究成果。

离散数学基础知识，数据结构基础知识，程序设计语言C/C++

第一章 算法引论 陈玉福
第1节 算法与程序 1.0学时
第2节 算法的抽象与描述 1.0学时
第3节 空间复杂性 1.0学时
第4节 时间复杂性 1.0学时
第5节 渐进符号 1.0学时
第二章 图与遍历算法 陈玉福
第1节 图的基本概念和性质 2.0学时
第2节 图上遍历算法 1.0学时
第3节 双连通与网络可靠性 1.0学时
第4节 对策树 1.0学时
第三章 分治算法 陈玉福
第1节 分治策略 1.0学时
第2节 排序问题 1.0学时
第3节 选择问题 1.0学时
第4节 关于矩阵乘法 1.0学时
第5节 快速傅里叶变换 1.0学时
第6节 最接近点对问题 1.0学时
第四章 贪心算法 陈玉福
第1节 贪心算法的设计思想 1.0学时
第2节 作业排序问题 1.0学时
第3节 最优生成树问题 1.0学时
第4节 单点源最短路径问题 1.0学时
第5节 Huffman 编码 1.0学时
第6节 贪心算法优性理论 1.0学时
第五章 动态规划算法 陈玉福
第1节 算法基本思想 1.0学时
第2节 多段图问题 1.0学时
第3节 0/1背包问题 1.0学时
第4节 流水线作业调度问题 1.0学时
第5节 最优二叉搜索树 1.0学时
第六章 回溯算法 陈玉福
第1节 算法的基本思想 1.0学时
第2节 子集和问题与0/1背包问题 1.0学时
第3节 n-皇后问题与旅行商问题 1.0学时
第4节 图的着色问题 1.0学时
第5节 回溯算法的效率分析 1.0学时
第七章 分枝-限界算法 陈玉福
第1节 算法的基本思想 1.0学时
第2节 0/1背包问题的分枝限界算法 1.0学时
第3节 电路板布线问题 1.0学时
第4节 优先级的确定与LC-检索 1.0学时
第5节 旅行商问题的分枝限界算法 1.0学时
第八章 NP-完全性理论 陈玉福
第1节 关于问题及算法描述 1.0学时
第2节 图灵机与确定性算法 1.0学时
第3节 P-类问题与NP-类问题 2.0学时
第4节 NP-完全问题 1.0学时
第5节 证明NP-完全问题的方法 2.0学时
第6节 NP-困难问题 1.0学时
第九章 NP-难问题的高效算法设计 陈玉福
第1节 约束传播 2.0学时
第2节 冲突分析与学习机制 2.0学时
第3节 打破对称 2.0学时
第4节 禁忌搜索 2.0学时
第5节 模拟退火算法 2.0学时
第6节 遗传算法 2.0学时
第7节 随机算法 3.0学时

陈玉福，教授，博士生导师