课程大纲

课程大纲

计算机算法设计与分析

课程编码:083500M01001H-1 英文名称:The Design and Analysis of Computer Algorithm 课时:60 学分:3.00 课程属性:一级学科核心课 主讲教师:陈玉福等

教学目的要求
本课程为软件工程一级学科研究生的核心课程。本课程讲授和讨论计算机算法设计的基本思想、设计策略与技巧,算法的空间、时间复杂性分析技术。主要内容有分治策略、贪心算法、动态规划、回溯算法、分枝限界算法等经典算法和NP完全性理论、NP难问题的算法设计等。

通过本课程的学习,希望学生能掌握常用经典计算机算法的基本设计思想和策略,能够将实际问题抽象成算法问题,分析与界定问题的难度,设计求解算法;掌握算法的空间和时间复杂性分析技术;了解计算机算法与分析前沿研究领域,了解最新研究成果。

预修课程
离散数学、数据结构、程序设计语言C/C++

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

参考书
1、 现代优化计算方法 邢文训 2000 清华大学出版社

课程教师信息
陈玉福,中国科学院大学数学科学学院,教授,博士生导师。
马菲菲,中国科学院软件所,副研究员
马丙鹏,中国科学院大学,计算机科学与技术学院,副教授,硕士生导师。2009年在中国科学院计算技术研究所获工学博士学位。2009年9月至2013年3月期间任教于华中科技大学计算机科学与技术学院,2011年至2012年期间在法国卡昂诺曼底大学从事博士后研究。主要研究方向包括模式识别理论与应用、计算机视觉、人工智能和机器学习,尤其关注人体身份再识别、行人检测、行人跟踪、人脸识别和头部姿态估计等方面的研究。先后在包括IEEE
T-PAMI、IEEE
T-IP、CVPR和ICCV等本领域权威国际期刊与会议上发表学术论文50余篇,谷歌学术引用1400余次。作为第一完成人荣获2018年中国计算机学会科学技术奖自然科学二等奖,指导研究生获得ICME
2018白金最佳论文奖,ECCV
2018行人检测竞赛冠军。中国计算机学会高级会员,青年计算机科技论坛(YOCSEF)学术委员,青年工作委员会委员。
刘玉贵,男,1962.02月生,副教授。北京大学数学系,理学学士,中国科技大学计算机系,工学硕士。曾教授课程:多媒体计算机技术、分布式多媒体计算机系统、流媒体与视频服务器、数据库系统基础、计算机算法设计与分析。工作经历:1984-1997 北京玻璃研究院,从事工业自动化、管理信息系统(数据库应用)应用开发;1997- 今,中国科学院大学,教学科研。科研成果:曾获得原轻工业部科技进步三等奖,名次第二,北京市科技进步二等奖,名次第二,核心期刊、会议论文20余篇。