《计算机前沿技术专题》课程教学大纲

1、计算机前沿技术专题课程教学大纲一、课程基本信息课程代码：课程名称：计算机前沿技术专题英文名称：Special topics on the frontiers of computer science课程类别：专业选修课学 时：16学分：1适用对象: 计算机科学与技术专业考核方式：考查先修课程：C语言程序设计、数据结构、算法分析与设计二、课程简介中文简介：一直以来，算法在主导着计算机科学的发展。无论是前些年兴起的大数据、云计算研究，还是近两年重新成为热点的人工智能研究，背后的问题都是复杂的算法问题。因此将算法领域的一些最新进展和一些新的算法设计和分析技术介绍给学生是本课程的主要目标。算法是计算机科

2、学的核心。算法不仅应用广泛，更重要的是，算法是更深入学习和理解计算机科学的有力手段。本课程主要讨论一些NP完全问题的近似算法和参数算法。通过一些来自各个领域的问题来介绍近似算法和参数算法设计和分析的基本技术。通过本课程，让学生了解计算机领域前沿知识和发展趋势，建立科学报国技术报国的理念，通过算法学习，锻炼计算机领域从业人员必备的专业技能和工匠精神，为中华民族伟大复兴贡献自己的一份力量。英文简介：Algorithms form the heart of computer science. The point is not simply that algorithms have many appl

3、ications. The deeper issue is that the subject of algorithms is a powerful lens through which to view the field of computer science in course mainly discusses approximation algorithms and parameterized algorithms for some NP complete problems. Some basic techniques of algorithm design and analysis a

4、re introduced by drawing on problems from various fields.三、课程性质与教学目的通过讲授一些经典NP完全问题的近似算法和参数算法，让学生理解并掌握近似算法和参数算法设计的基本技术。锻炼学生的逻辑思维能力和想象力，培养和提高学生分析和求解复杂问题的能力，并使之了解算法研究的一些新进展。在课程学习中，鼓励学生运用算法知识解决各自学科的实际问题，培养学生的独立科研的能力和实践动手能力。四、教学内容及要求第一章 优美的算法（一） 目的与要求1 掌握NP理论2 掌握贪心策略的应用3 掌握动态规划的应用（二） 教学内容 第一节 1 主要内容。NP理论

5、的基本知识活动选择问题树上的独立集问题调度问题。2 基本概念和知识点算法设计中贪心策略的应用算法设计中动态规划的应用3 问题与应用（能力要求）（三） 思考与实践课后编程实现活动选择问题的求解算法。（四） 教学方法与手段课堂讲授，课堂讨论，编程实现。课堂中引入改革开放前后，对于各领域动态规划的实例，一方面展示改革开放的重大成就，另一方面也让学生体会到无论在生活中还是学习中，都需要动态规划的态度去科学的处理事务。第二章 优美但无效的算法（一） 目的与要求1 掌握复杂问题中动态规划的应用2 掌握动态规划算法的时间复杂度分析（二） 教学内容 第一节 1 主要内容背包问题Steiner树问题2 基本概念

6、和知识点复杂问题中动态规划的应用动态规划算法的时间复杂度分析3 问题与应用（能力要求）（三） 思考与实践编程实现背包问题的求解算法。（四） 教学方法与手段课堂讲授，课堂讨论，编程实现。在教学中引入邓小平同志的“不管白猫黑猫，抓住老鼠就是好猫”的务实精神，深刻理解对于解决问题的方式和方法，科学的对待各种问题的解决方案。第三章 近似算法（一） 目的与要求1 掌握相关问题的近似算法2 掌握近似算法中近似度的分析和证明技巧3 掌握近似算法的时间复杂度分析方法（二） 教学内容 第一节 1 主要内容点覆盖问题的近似算法Steiner树问题的近似算法2 基本概念和知识点点覆盖问题2-近似度的证明策略Stei

7、ner问题2-近似度的证明策略3 问题与应用（能力要求） 第二节1 主要内容旅行商问题的近似算法2 基本概念和知识点满足三角不等式的旅行商问题2-近似度的证明策略旅行商问题不可近似性的证明策略3 问题与应用（能力要求）第三节1 主要内容集合覆盖问题的近似算法2 基本概念和知识点集合覆盖问题近似度的证明策略3 问题与应用（能力要求）第四节1 主要内容3-SAT问题的随机化近似算法点覆盖问题的线性规划近似算法2 基本概念和知识点随机化在近似算法中的应用线性规划在近似算法中的应用3 问题与应用（能力要求）第五节1 主要内容子集合问题的近似算法2 基本概念和知识点具有无限接近近似度的近似算法设计3 问

8、题与应用（能力要求）（三） 思考与实践编程实现课堂中讲述的近似算法。（四） 教学方法与手段课堂讲授，课堂讨论，编程实现在课堂中通过无限近似度，引出对待工作必须持有严谨的工作态度和工匠精神，用科学的态度和方法来解决问题。第四章 参数算法（一） 目的与要求1 掌握相关问题的参数算法2 掌握参数算法设计中的核化和有界搜索树技术3 掌握参数算法的时间复杂度分析方法（二） 教学内容 第一节 1 主要内容点覆盖问题的核化算法点覆盖问题的有界搜索树算法2 基本概念和知识点参数算法中核化技术的应用参数算法中有界搜索树技术的应用3 问题与应用（能力要求）（三） 思考与实践编程实现课堂中讲述的参数算法。（四） 教学方法与手段课堂讲授课堂讨论编程实现五、各教学环节学时分配教学环节教学时数课程内容讲课习题课讨论课实验其他教学环节小计第一章22第二章22第三章1010第四章22合计1616六、推荐教材和教学参考资源1. Viiay V.Vazirani. Approximation algorithms. Pearson Education, 20102. Rol