《计算机前沿技术专题》课程教学大纲 一、课程基本信息 课程代码：16171701 课程名称：计算机前沿技术专题 英文名称：Special topics on the frontiers of computer science 课程类别：专业选修课 学 时：16 学分：1 适用对象：计算机科学与技术专业 考核方式：考查 先修课程：C语言程序设计、数据结构、算法分析与设计 二、课程简介 中文简介： 一直以来，算法在主导着计算机科学的发展。无论是前些年兴起的大数据、云计 算研究，还是近两年重新成为热点的人工智能研究，背后的问题都是复杂的算法问题。 因此将算法领域的一些最新进展和一些新的算法设计和分析技术介绍给学生是本课 程的主要目标。算法是计算机科学的核心。算法不仅应用广泛，更重要的是，算法是 更深入学习和理解计算机科学的有力手段。本课程主要讨论一些P完全问题的近似 算法和参数算法。通过一些来自各个领域的问题来介绍近似算法和参数算法设计和分 析的基本技术。通过本课程，让学生了解计算机领域前沿知识和发展趋势，建立科学 报国技术报国的理念，通过算法学习，锻炼计算机领域从业人员必备的专业技能和工 匠精神，为中华民族伟大复兴贡献自已的一份力量。 英文简介：Algorithms form the heart of computer science.The point is not simply that algorithms have many applications.The deeper issue is that the subject of algorithms is a powerful lens through which to view the field of computer science in general.This course mainly discusses approximation algorithms and parameterized algorithms for some NP complete problems.Some basic techniques of algorithm design and analysis are introduced by drawing on problems from various fields 三、课程性质与教学目的
1 《计算机前沿技术专题》课程教学大纲 一、课程基本信息 课程代码：16171701 课程名称：计算机前沿技术专题 英文名称：Special topics on the frontiers of computer science 课程类别：专业选修课 学 时：16 学 分：1 适用对象: 计算机科学与技术专业 考核方式：考查 先修课程：C 语言程序设计、数据结构、算法分析与设计 二、课程简介 中文简介： 一直以来，算法在主导着计算机科学的发展。无论是前些年兴起的大数据、云计 算研究，还是近两年重新成为热点的人工智能研究，背后的问题都是复杂的算法问题。 因此将算法领域的一些最新进展和一些新的算法设计和分析技术介绍给学生是本课 程的主要目标。算法是计算机科学的核心。算法不仅应用广泛，更重要的是，算法是 更深入学习和理解计算机科学的有力手段。本课程主要讨论一些 NP 完全问题的近似 算法和参数算法。通过一些来自各个领域的问题来介绍近似算法和参数算法设计和分 析的基本技术。通过本课程，让学生了解计算机领域前沿知识和发展趋势，建立科学 报国技术报国的理念，通过算法学习，锻炼计算机领域从业人员必备的专业技能和工 匠精神，为中华民族伟大复兴贡献自己的一份力量。 英文简介：Algorithms form the heart of computer science. The point is not simply that algorithms have many applications. The deeper issue is that the subject of algorithms is a powerful lens through which to view the field of computer science in general.This course mainly discusses approximation algorithms and parameterized algorithms for some NP complete problems. Some basic techniques of algorithm design and analysis are introduced by drawing on problems from various fields. 三、课程性质与教学目的
通过讲授一些经典P完全问题的近似算法和参数算法，让学生理解并掌握近似 算法和参数算法设计的基本技术。锻炼学生的逻辑思维能力和想象力，培养和提高学 生分析和求解复杂问题的能力，并使之了解算法研究的一些新进展。在课程学习中， 鼓励学生运用算法知识解决各自学科的实际问题，培养学生的独立科研的能力和实践 动手能力。 四、教学内容及要求 第一章优美的算法 (一)目的与要求 .掌握NP理论 2.堂握含心策略的应用 3.掌握动态规划的应用 (二)教学内容 第一节 1.主要内容」 P理论的基本知识 活动选择问题 树上的独立集问题 调度问题 2,基本概念和知识点 算法设计中贪心策略的应用 算法设计中动态规划的应用 3.问题与应用（能力要求） (三)思考与实践 课后编程实现活动选择问题的求解算法。 (四)教学方法与手段 课堂讲授，课堂讨论，编程实现。 课堂中引入改革开放前后，对于各领域动态规划的实例，一方面展示改革 开放的重大成就，另一方面也让学生体会到无论在生活中还是学习中，都需要动态规 划的态度去科学的处理事务。 第二章优美但无效的算法 (一)目的与要求 1.掌握复杂问题中动态规划的应用 2
2 通过讲授一些经典 NP 完全问题的近似算法和参数算法，让学生理解并掌握近似 算法和参数算法设计的基本技术。锻炼学生的逻辑思维能力和想象力，培养和提高学 生分析和求解复杂问题的能力，并使之了解算法研究的一些新进展。在课程学习中， 鼓励学生运用算法知识解决各自学科的实际问题，培养学生的独立科研的能力和实践 动手能力。 四、教学内容及要求 第一章 优美的算法 （一）目的与要求 1．掌握 NP 理论 2．掌握贪心策略的应用 3．掌握动态规划的应用 （二）教学内容 第一节 1．主要内容。 NP 理论的基本知识 活动选择问题 树上的独立集问题 调度问题。 2．基本概念和知识点 算法设计中贪心策略的应用 算法设计中动态规划的应用 3．问题与应用（能力要求） （三）思考与实践 课后编程实现活动选择问题的求解算法。 （四）教学方法与手段 课堂讲授，课堂讨论，编程实现。 课堂中引入改革开放前后，对于各领域动态规划的实例，一方面展示改革 开放的重大成就，另一方面也让学生体会到无论在生活中还是学习中，都需要动态规 划的态度去科学的处理事务。 第二章 优美但无效的算法 （一）目的与要求 1．掌握复杂问题中动态规划的应用
2.掌握动态规划算法的时间复杂度分析 (二)教学内容 第一节 1.主要内容 背包问题 Steiner树问题 2.基本概念和知识点 复杂问题中动态规划的应用 动态规划算法的时间复杂度分析 3.问题与应用（能力要求）》 (三)思考与实践 编程实现背包问题的求解算法 (四)教学方法与手段 课堂讲授，课堂讨论，编程实现。 在教学中引入邓小平同志的“不管白猫黑猫，抓住老鼠就是好猫”的务实 精神，深刻理解对于解决问题的方式和方法，科学的对待各种问题的解决方案。 第三章近似算法 (一)目的与要求 1.掌握相关问题的近似算法 2.掌握近似算法中近似度的分析和证明技巧 3.掌握近似算法的时间复杂度分析方法 (二)教学内容 第一节 1.主要内容 点覆盖问顾的近似算法 Steiner树问题的近似算法 2.基本概念和知识点 点覆盖问题2-近似度的证明策略 Steiner问题2-近似度的证明策略 3.问题与应用（能力要求 第二节 3
3 2．掌握动态规划算法的时间复杂度分析 （二）教学内容 第一节 1．主要内容 背包问题 Steiner 树问题 2．基本概念和知识点 复杂问题中动态规划的应用 动态规划算法的时间复杂度分析 3．问题与应用（能力要求） （三）思考与实践 编程实现背包问题的求解算法。 （四）教学方法与手段 课堂讲授，课堂讨论，编程实现。 在教学中引入邓小平同志的“不管白猫黑猫，抓住老鼠就是好猫”的务实 精神，深刻理解对于解决问题的方式和方法，科学的对待各种问题的解决方案。 第三章 近似算法 （一）目的与要求 1．掌握相关问题的近似算法 2．掌握近似算法中近似度的分析和证明技巧 3．掌握近似算法的时间复杂度分析方法 （二）教学内容 第一节 1．主要内容 点覆盖问题的近似算法 Steiner 树问题的近似算法 2．基本概念和知识点 点覆盖问题 2-近似度的证明策略 Steiner 问题 2-近似度的证明策略 3．问题与应用（能力要求） 第二节
1.主要内容 旅行商问题的近似算法 2.基本概念和知识点 满足三角不等式的旅行商问题2-近似度的证明策略 旅行商问题不可近似性的证明策略 3.问题与应用（能力要求） 第三节 1.主要内容 集合覆盖问题的近似算法 2.基本概念和知识点 集合覆盖问题近似度的证明策略 3.问题与应用（能力要求） 第四节 1.主要内容 3-SAT问题的随机化近似算法 点覆盖问题的线性规划近似算法 2。基本概念和知识点 随机化在近似算法中的应用 线性规划在近似算法中的应用 3.问题与应用（能力要求） 第五节 1.主要内容 子集合问题的近似算法 2.基本概念和知识点 具有无限接近近似度的近似算法设计 3.问题与应用（能力要求） (三)思考与实践 编程实现课堂中讲述的近似算法。 (四)教学方法与手段 课堂讲授，课堂讨论，编程实现 在课堂中通过无限近似度，引出对待工作必须持有严谨的工作态度和工 4
4 1．主要内容 旅行商问题的近似算法 2．基本概念和知识点 满足三角不等式的旅行商问题 2-近似度的证明策略 旅行商问题不可近似性的证明策略 3．问题与应用（能力要求） 第三节 1．主要内容 集合覆盖问题的近似算法 2．基本概念和知识点 集合覆盖问题近似度的证明策略 3．问题与应用（能力要求） 第四节 1．主要内容 3-SAT 问题的随机化近似算法 点覆盖问题的线性规划近似算法 2．基本概念和知识点 随机化在近似算法中的应用 线性规划在近似算法中的应用 3．问题与应用（能力要求） 第五节 1．主要内容 子集合问题的近似算法 2．基本概念和知识点 具有无限接近近似度的近似算法设计 3．问题与应用（能力要求） （三）思考与实践 编程实现课堂中讲述的近似算法。 （四）教学方法与手段 课堂讲授，课堂讨论，编程实现 在课堂中通过无限近似度，引出对待工作必须持有严谨的工作态度和工
匠精神，用科学的态度和方法来解决问题。 第四章参数算法 (一)目的与要求 1.掌握相关问题的参数算法 2.掌握参数算法设计中的核化和有界搜索树技术 3.掌握参数算法的时间复杂度分析方法 (二)教学内容 第一节 1.主要内容 点覆盖问题的核化算法 点覆盖问题的有界搜索树算法 2.基本概念和知识点 参数算法中核化技术的应用 参数算法中有界搜索树技术的应用 3.问题与应用（能力要求） (三)思考与实践 编程实现课堂中讲述的参数算法。 (四)教学方法与手段 课堂讲授 课堂讨论 编程实现 五、各教学环节学时分配 教学环节 习 教学时数 实验 其他教 学环节 女 课程内容 第一章 2 第二章 第三章 10 第四章
5 匠精神，用科学的态度和方法来解决问题。 第四章 参数算法 （一）目的与要求 1．掌握相关问题的参数算法 2．掌握参数算法设计中的核化和有界搜索树技术 3．掌握参数算法的时间复杂度分析方法 （二）教学内容 第一节 1．主要内容 点覆盖问题的核化算法 点覆盖问题的有界搜索树算法 2．基本概念和知识点 参数算法中核化技术的应用 参数算法中有界搜索树技术的应用 3．问题与应用（能力要求） （三）思考与实践 编程实现课堂中讲述的参数算法。 （四）教学方法与手段 课堂讲授 课堂讨论 编程实现 五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教 学环节 小 计 第一章 2 2 第二章 2 2 第三章 10 10 第四章 2 2
合计 16 16 六、推荐教材和教学参考资源 1.Viiay V.Vazirani.Approximation algorithms.Pearson Education,2010 2.Rolf Niedermeier.Invitation to Fixed-parameter Algorithms.Oxford university press,2006 3.相关研究论文 七、其他说明 大纲修订人：高文宇 修订日期：2020.12 大纲审定人： 审定日期： 6
6 合计 16 16 六、推荐教材和教学参考资源 1. Viiay V.Vazirani. Approximation algorithms. Pearson Education, 2010 2. Rolf Niedermeier. Invitation to Fixed-parameter Algorithms. Oxford university press, 2006 3. 相关研究论文 七、其他说明 大纲修订人：高文宇 修订日期：2020.12 大纲审定人： 审定日期：
