课程大纲

课程大纲

计算机算法设计与分析

课程编码:081203M04001H 英文名称:Algorithm design and analysis 课时:60 学分:3.00 课程属性:专业核心课 主讲教师:卜东波

教学目的要求
本课程为计算机应用学科研究生的专业核心课程。本课程讲授和讨论计算机算法前沿研究领域的主要思想和关键技术。主要内容有算法分析技术、分治法、动态规划法、贪心法、线性规划的单纯形法和对偶法、网络流、多项式归约、NP难问题、近似算法、随机算法、参数化算法和树分解、启发式方法(局部搜索)等。?通过本课程的学习,希望学生能了解计算机算法前沿研究领域,了解算法设计与分析的最新研究成果,掌握基本思想和关键技术,培养学生三个方面的能力,即将实际问题抽象成算法问题的建模能力、观察问题特性并相应设计算法的能力,以及分析算法性能的能力。?

预修课程
数据结构、计算机程序设计

大纲内容
第一章 建模、算法设计、分析完整流程 10学时 卜东波
第1节 掌握从问题出发的算法建模方法
第2节 掌握算法设计的基本思路和流程图
第3节 掌握算法的时间复杂度和空间复杂度分析的方法
第4节 理解GCD问题和TSP问题中不同算法的应用
第二章 分而治之 10学时 卜东波
第1节 掌握分而治之算法的基本思路
第2节 掌握分而治之算法的正确证明
第3节 掌握递归算法的时间复杂度分析
第4节 掌握MergerSort、CountingInversion、ClosetPair、Multipliacation、FFT等使用分而治之思路算法
第5节 掌握分而治之算法和随机化的结合,例如QuickSort、QuickSelect等
第三章 动态规划部分 10学时 卜东波
第1节 掌握动态规划算法的基本思路
第2节 掌握如何定义子问题,如何发现最优子结构的性质
第3节 掌握动态规划算法的应用实例,包括矩阵链式乘法、字符串匹配、最短路径、IntervalScheduling
第4节 理解高级动态规划的优化方法和思路
第四章 贪心算法 10学时 卜东波
第1节 掌握贪心算法的思路
第2节 掌握贪心算法中贪心规则的设计原则和方法等
第3节 掌握动态规划和贪心算法的关系
第4节 掌握BELLMAN_FORD算法和DIJKSTRA算法解决Single Source Shortest Paths问题
第5节 掌握BinomialHeap、FibinacciHeap等数据结构
第五章 线性规划及其对偶 10学时 卜东波
第1节 掌握线性规划的不同形式
第2节 掌握线性规划的建模思路和方法
第3节 掌握线性规划的单纯形法、Interior Point算法等
第4节 线性规划的Lagrangian对偶
第六章 网络流及其应用 10学时 卜东波
第1节 掌握最大流问题的Ford-Fulkerson算法和最大流最小割定理
第2节 掌握Ford-Fulkerson算法和最大流最小割定理的对偶问题角度理解
第3节 掌握最大流问题的有效算法
第4节 掌握最大流问题的扩展

教材信息
1、 算法设计 Jon Kleinberg 2021-03 人民邮电出版社

参考书

课程教师信息
卜东波 中科院计算所,生物信息学实验室,研究员 教育经历1997/09 – 2001/01,中科院计算所,博士,导师:李国杰研究员1994/09 – 1997/06,中科院计算所,硕士,导师:白硕研究员1990/09 – 1994/06,山东大学,计算机系,学士工作经历(科研与学术工作经历,按时间倒排序):2010/07-至今,中科院计算所,研究员2006/05-2008/08,加拿大滑铁卢大学计算机系,访问学者2003/07-2010/06,中科院计算所,副研究员2001/01-2003/06,中科院计算所,助理研究员