算法概论
课程编码：180090125601M3001Y
英文名称：Introduction to Computer Algorithms
课时：40
学分：2.00
课程属性：专业课
主讲教师：薛健
教学目的要求
本课程是面向信息技术领域工程管理专业和计算机应用技术专业硕士研究生的信息技术理论基础类课程，主要介绍计算机算法设计与分析领域的一般性理论和数学方法，采用理论与实践相结合的方式，为选课学生将来从事信息技术领域的实际工程管理工作建立良好的算法理论概念模型，培养学生使用计算机和相应的数学工具分析和解决实际问题的能力。
通过本课程的学习，要求学生：掌握算法复杂度分析的基本理论和方法，能够分析各类算法的时间和空间复杂度；掌握算法设计的几类通用方法，能够根据具体问题及时间复杂度要求设计相应的算法。
预修课程
数据结构
大纲内容
第一章 概述及算法分析基础 4.0学时 薛健
第1节 算法概述
第2节 背景知识
第3节 数据抽象方法及基本数据结构
第4节 算法复杂度分析基础
第二章 递归和分治法 4.0学时 薛健
第1节 递归和数学归纳法
第2节 分治法
第三章 排序算法 6.0学时 薛健
第1节 简单排序算法
第2节 用分治法设计排序算法
第3节 其他排序算法
第4节 排序算法比较
第四章 选择和检索 6.0学时 薛健
第1节 选择算法
第2节 动态集合和搜索
第五章 高级设计与分析技术 6.0学时 薛健
第1节 动态规划
第2节 贪心方法
第3节 字符串匹配算法
第六章 图算法 8.0学时 薛健
第1节 基本概念
第2节 图的表示和数据结构
第3节 图的搜索与遍历
第4节 最小生成树问题
第5节 单源最短路径问题
第七章 并行算法 3.0学时 薛健
第1节 基本概念和并行模型
第2节 简单PRAM算法与写冲突处理
第3节 归并排序的并行算法设计
第八章 NP-完全问题简介 3.0学时 薛健
第1节 基本概念
第2节 P问题和NP问题
第3节 NP-完全问题
教材信息
1、
计算机算法——设计与分析导论
Sara Baase
2001年7月
高等教育出版社
参考书
1、
算法导论@计算机程序设计艺术第一卷基本算法@计算机科学与技术学科研究生教材：计算机算法基础
Thomas H. Cormen@Donald E. Knuth@沈孝钧
2006年9月@2002年9月@2014年1月
机械工业出版社@国防工业出版社@机械工业出版社
课程教师信息
薛健，男，1979年6月生，博士，现为中国科学院大学工程科学学院教授，研究方向为计算机图形学、科学计算可视化。长期从事涉及海量数据的图像处理和科学计算可视化方面的研究工作，承担国家自然科学基金等相关科研项目多项，在面向大规模数据的分布式并行处理技术方面有一定的研究基础。