计算机算法设计与分析

课程编码：180086085405P2002H 英文名称：The Design and Analysis of Computer Algorithms 课时：60 学分：3.00 课程属性：专业核心课 主讲教师：刘玉贵

本课程讲授计算机算法设计的基本思想、设计策略与技巧，算法的时间复杂性分析技术。主要内容有分治策略、贪心算法、动态规划、回溯算法、分枝限界算法等经典算法和NP完全性理论以及解决NP难问题的概率算法、近似算法、智能搜索算法等。
通过本课程的学习，要求学生掌握常用经典计算机算法的基本设计思想和策略，能够将实际问题抽象成算法问题，分析与界定问题的难度，设计求解算法并能够熟练地在计算机上实现；掌握算法的时间复杂性分析、正确性证明、近似比分析等技术；了解计算机算法与分析的前沿研究领域和最新研究成果。

离散数学、数据结构、程序设计语言C/C＋＋

第一章 算法引论 3.0学时 刘玉贵
第1节 算法与程序
第2节 表达算法的抽象机制
第3节 描述算法
第4节 算法复杂性分析
第5节 渐进符号
第二章 分治算法 5.0学时 刘玉贵
第1节 分治策略的基本思想
第2节 排序算法
第3节 选择问题
第4节 关于矩阵乘法
第5节 快速Fourier变换
第6节 最接近点对问题
第三章 贪心算法 8.0学时 刘玉贵
第1节 贪心算法的设计思想
第2节 作业排序问题
第3节 最优生成树问题
第4节 单点源最短路径问题
第5节 Huffman编码
第四章 动态规划算法 6.0学时 刘玉贵
第1节 算法基本思想
第2节 多段图问题
第3节 0/1背包问题
第4节 流水作业调度问题
第5节 最优二叉搜索树
第五章 回溯算法 4.0学时 刘玉贵
第1节 算法的基本思想
第2节 定和子集问题和0/1背包问题
第3节 n-皇后问题和旅行商问题
第4节 图的着色问题
第5节 回溯算法的效率分析
第六章 分枝-限界算法 6.0学时 刘玉贵
第1节 算法的基本思想
第2节 0/1背包问题的分枝限界算法
第3节 电路板布线问题
第4节 优先级的确定与LC-检索
第5节 旅行商问题的分枝限界算法
第七章 NP-完全性理论 9.0学时 刘玉贵
第1节 关于问题及算法的描述
第2节 图灵机与确定性算法
第3节 P类与NP-类问题
第4节 NP-完全问题
第5节 证明新问题是NP-完全问题的方法
第6节 NP-困难问题
第八章 概率算法 4.0学时 刘玉贵
第1节 概率算法基本概念
第2节 数值概率算法
第3节 Sherwood算法
第4节 Las Vegas算法
第5节 Monte Carlo算法
第九章 近似算法 6.0学时 刘玉贵
第1节 近似算法的相关概念
第2节 集合覆盖问题的近似算法
第3节 子集和问题的近似算法
第4节 顶点覆盖问题的近似算法
第5节 货郎问题的近似算法
第6节 0/1背包问题的近似算法
第十章 启发式算法 6.0学时 刘玉贵
第1节 启发式算法基本概念
第2节 禁忌搜索算法
第3节 模拟退火算法
第4节 遗传算法(GA)
第5节 人工神经网络算法

刘玉贵，男，国科大计算机科学与技术学院，硕士生导师。研究领域：多媒体技术、信息系统。曾讲授课程：多媒体计算机技术、计算机算法设计与分析、数据库系统基础等。
分布式多媒体计算机系统
流媒体与视频服务器
文献阅读课
计算机算法设计与分析
数据库系统基础
下一代IP网络协议IPv6
文献阅读-计算机软件与理论专业 3班
移动互联网技术
分布式多媒体计算机系统
流媒体与视频服务器
文献阅读课
计算机算法设计与分析
数据库系统基础
下一代IP网络协议IPv6
文献阅读-计算机软件与理论专业 3班
移动互联网技术