《编程拓展课程设计》课程教学大纲 一、课程基本信息 课程代码：16056602 课程名称：编程拓展课程设计 英文名称：Course design of programming 课程类别：专业必修课 时：32 学 分：2 适用对象：计算机科学与技术专业 考核方式：考查 先修课程：C语言程序设计 二、课程简介 中文简介：算法和编程思维无处不在，遍及计算机科学和其他邻域。本课程将算 法和编程作为一个设计过程来介绍，即从计算机应用领域提出问题开始，继而建立对 算法和程序设计技术的理解，最终形成对这些问题有效的解决方案。理解复杂算法最 好的方法通常是重构从初始的简单想法到最终解决问题的思考过程，包括错误的初始 想法和行不通的想法。因此，本课程以来自计算机科学和相关领域的问题为例来介绍 算法和程序设计的基本技术。这些技术包括贪心策略，分治策略，动态规划，随机算 法箅。酒过该课程，讲一步加强对学生专业技术能力的培养，以及树立专业报国技术 报国的信念，建立科学分析问题的态度和专业工匠精神，从专业多角度进一步体会技 术是国家强盛的基础，提升为国家服务的理念和态度。 英文简介：Algorithmic ideas and programming are pervasive,and their reach is apparent in examples both within computer science and beyond.This course is to convey this approach to algorithms and programming,as a design process that begins with problems arising across the full range of computing applications,builds on an understanding of algorithm and program design techniques,and results in the development of efficient solutions to these problems.Sophisticated algorithms are often best understood by reconstructing the sequence of ideas-including false starts and dead ends-that led from simpler initial approaches to the eventual solution.By doing this,the basic algorithm and program design techniques are introduced by drawing on problems from across many 1
1 《编程拓展课程设计》课程教学大纲 一、课程基本信息 课程代码：16056602 课程名称：编程拓展课程设计 英文名称：Course design of programming 课程类别：专业必修课 学 时：32 学 分：2 适用对象: 计算机科学与技术专业 考核方式：考查 先修课程：C 语言程序设计 二、课程简介 中文简介：算法和编程思维无处不在，遍及计算机科学和其他邻域。本课程将算 法和编程作为一个设计过程来介绍，即从计算机应用领域提出问题开始，继而建立对 算法和程序设计技术的理解, 最终形成对这些问题有效的解决方案。理解复杂算法最 好的方法通常是重构从初始的简单想法到最终解决问题的思考过程，包括错误的初始 想法和行不通的想法。因此，本课程以来自计算机科学和相关领域的问题为例来介绍 算法和程序设计的基本技术。这些技术包括贪心策略，分治策略，动态规划，随机算 法等。通过该课程，进一步加强对学生专业技术能力的培养，以及树立专业报国技术 报国的信念，建立科学分析问题的态度和专业工匠精神，从专业多角度进一步体会技 术是国家强盛的基础，提升为国家服务的理念和态度。 英文简介：Algorithmic ideas and programming are pervasive, and their reach is apparent in examples both within computer science and beyond. This course is to convey this approach to algorithms and programming, as a design process that begins with problems arising across the full range of computing applications, builds on an understanding of algorithm and program design techniques, and results in the development of efficient solutions to these problems.Sophisticated algorithms are often best understood by reconstructing the sequence of ideas—including false starts and dead ends—that led from simpler initial approaches to the eventual solution. By doing this, the basic algorithm and program design techniques are introduced by drawing on problems from across many
areas of computer science and related fields.These design techniques includes greedy algorithms,divide and conquer,dynamic programming,and randomized algorithms,etc. 三、课程性质与教学目的 本课程通过讲授一些基本的算法和程序设计技术，结合一些算法问题的编程训 练，切实提高学生的算法和程序设计能力。要求学生通过学习掌握诸如贪心、分治、 动态规别、贿机化第管法和程序设计技术，并能运用这些技术绵程求解一些较为复杂 的问题。通过课程学习锻炼学生的逻辑思维能力和编程实践能力，培养和提高学生分 析和解决一些复杂问题的能力。 四、教学内容及要求 第一章算法分析入门 (一)目的与要求 1.掌握算法分析的基本原理 (二)教学内容 第一节 1.主要内容。 算法分析的基本知识 最大子序列和问题 2.基本概念和知识点 算法分析中递推关系的复杂度分析 求解最大子序列和问题的分治策略 3.问题与应用（能力要求 (三)思考与实践 课后编程实现最大子序列和问题的求解算法。 (四)教学方法与手段 课堂讲授，课堂讨论，编程实现 在课堂中，通过讲授算法分析的基础概念和知识，传递科学分析问题的方 法和思路，利用算法的不同体现多角度的思考问题的科学发展观。 第二章算法和程序设计的基本技术 (一)目的与要求 1.掌握算法和程序设计的基本技术 2.掌握一些复杂问题的算法分析技巧 2
2 areas of computer science and related fields. These design techniques includes greedy algorithms, divide and conquer, dynamic programming, and randomized algorithms, etc. 三、课程性质与教学目的 本课程通过讲授一些基本的算法和程序设计技术，结合一些算法问题的编程训 练，切实提高学生的算法和程序设计能力。要求学生通过学习掌握诸如贪心、分治、 动态规划、随机化等算法和程序设计技术，并能运用这些技术编程求解一些较为复杂 的问题。通过课程学习锻炼学生的逻辑思维能力和编程实践能力，培养和提高学生分 析和解决一些复杂问题的能力。 四、教学内容及要求 第一章 算法分析入门 （一）目的与要求 1．掌握算法分析的基本原理 （二）教学内容 第一节 1．主要内容。 算法分析的基本知识 最大子序列和问题 2．基本概念和知识点 算法分析中递推关系的复杂度分析 求解最大子序列和问题的分治策略 3．问题与应用（能力要求） （三）思考与实践 课后编程实现最大子序列和问题的求解算法。 （四）教学方法与手段 课堂讲授，课堂讨论，编程实现。 在课堂中，通过讲授算法分析的基础概念和知识，传递科学分析问题的方 法和思路，利用算法的不同体现多角度的思考问题的科学发展观。 第二章 算法和程序设计的基本技术 （一）目的与要求 1．掌握算法和程序设计的基本技术 2．掌握一些复杂问题的算法分析技巧
(二)教学内容 第一节 1.主要内容 活动选择问题 树上的独立集问题 2.基本概念和知识点 贪心策略的应用 贪心策略的正确性证明 3.问题与应用（能力要求） 第二节 1.主要内容 主定理(Master theorem) 最近点对问题 2.基本概念和知识点 分治策略的应用 分治策略的时间复杂度分析 3.问题与应用（能力要求） 第三节 1.主要内容 整数的快速乘法问题 矩阵的快速乘法问题 2.基本概念和知识点 整数的快速乘法算法 矩阵的快速乘法算法 3.问题与应用（能力要求 第四节 1.主要内容 动态规划的基本原理 矩阵乘法顺序安排问题 2.基本概念和知识点 矩阵乘法顺序安排的动态规划算法 动态规划算法的时间复杂度分析 3
3 （二）教学内容 第一节 1．主要内容 活动选择问题 树上的独立集问题 2．基本概念和知识点 贪心策略的应用 贪心策略的正确性证明 3．问题与应用（能力要求） 第二节 1．主要内容 主定理（Master theorem） 最近点对问题 2．基本概念和知识点 分治策略的应用 分治策略的时间复杂度分析 3．问题与应用（能力要求） 第三节 1．主要内容 整数的快速乘法问题 矩阵的快速乘法问题 2．基本概念和知识点 整数的快速乘法算法 矩阵的快速乘法算法 3．问题与应用（能力要求） 第四节 1．主要内容 动态规划的基本原理 矩阵乘法顺序安排问题 2．基本概念和知识点 矩阵乘法顺序安排的动态规划算法 动态规划算法的时间复杂度分析
3.问题与应用（能力要求） 第五节 1.主要内容 最优二叉查找树问题 最短路径问题 2.基本概念和知识点 最优二叉查找树的动态规划算法 最短路径问题的动态规划算法 3.问题与应用（能力要求）》 第六节 1.主要内容 随机算法的基本原理。 跳跃表及其查找时间复杂度 素数测试的随机算法。 2.基本概念和知识点 随机算法的应用 随机算法的时间复杂度分材 3.问题与应用（能力要求） 第七节 1.主要内容 回溯算法的基本原理。 收费公路重建问题。 博弈树。 2.基本概念和知识点 回溯算法的应用 回溯算法的时间复杂度分析 3.问题与应用（能力要求） (三)思考与实践 编程实现相关问题的求解算法。 (四)教学方法与手段
4 3．问题与应用（能力要求） 第五节 1．主要内容 最优二叉查找树问题 最短路径问题 2．基本概念和知识点 最优二叉查找树的动态规划算法 最短路径问题的动态规划算法 3．问题与应用（能力要求） 第六节 1．主要内容 随机算法的基本原理。 跳跃表及其查找时间复杂度。 素数测试的随机算法。 2．基本概念和知识点 随机算法的应用 随机算法的时间复杂度分析 3．问题与应用（能力要求） 第七节 1．主要内容 回溯算法的基本原理。 收费公路重建问题。 博弈树。 2．基本概念和知识点 回溯算法的应用 回溯算法的时间复杂度分析 3．问题与应用（能力要求） （三）思考与实践 编程实现相关问题的求解算法。 （四）教学方法与手段
课堂讲授，课堂讨论，编程实现。 授课过程中，通过中美贸易摩擦，引入博奔论在政治经济等各领域的案例 分析，引导学生进一步理解国力的强盛是人民幸福生活的基础和保证。 第三章编程实践 (一)目的与要求 1.编程实现相关问题的求解 (二)教学内容 第一节 1.主要内容 Josephus问题 2.基本概念和知识点 Josephus问题 3.问题与应用（能力要求） 第二节 1.主要内容 八皇后问题 2.基本概念和知识点 八皇后问题 3.问题与应用（能力要求） 第三节 1.主要内容 二叉树中节点的最小公共祖先问题 2.基本概念和知识点 二叉树中节点的最小公共祖先问题 3.问题与应用（能力要求） 第四节 1.主要内容 几个简单问题的动态规划 2.基本概念和知识点 几个简单问题的动态规别 3.问题与应用（能力要求） 5
5 课堂讲授，课堂讨论，编程实现。 授课过程中，通过中美贸易摩擦，引入博弈论在政治经济等各领域的案例 分析，引导学生进一步理解国力的强盛是人民幸福生活的基础和保证。 第三章 编程实践 （一）目的与要求 1．编程实现相关问题的求解 （二）教学内容 第一节 1．主要内容 Josephus 问题 2．基本概念和知识点 Josephus 问题 3．问题与应用（能力要求） 第二节 1．主要内容 八皇后问题 2．基本概念和知识点 八皇后问题 3．问题与应用（能力要求） 第三节 1．主要内容 二叉树中节点的最小公共祖先问题 2．基本概念和知识点 二叉树中节点的最小公共祖先问题 3．问题与应用（能力要求） 第四节 1．主要内容 几个简单问题的动态规划 2．基本概念和知识点 几个简单问题的动态规划 3．问题与应用（能力要求）
第五节 1.主要内容 有向图的强连通分量 2.基本概念和知识点 有向图的强连通分量 3.问题与应用（能力要求） 第六节 1.主要内容 串的模式匹配 2.基本概念和知识点 串的模式匹配 3.问题与应用（能力要求） 第七节 1.主要内容 最短路径的Floyd-Warshall算法 2.基本概念和知识点 最短路径的Floyd-Warshall算法 3.问题与应用（能力要求） 第八节 1.主要内容 总结各种算法和程序设计技术 2.基本概念和知识点 各种算法和程序设计技术 3.问题与应用（能力要求） (三)思考与实践 编程实现课堂中讲述的近似算法。 (四)教学方法与手段 课堂讲授，课堂讨论，编程实现。 授课过程中，通过二叉树中公共祖先的知识点，引出各中华民族同根同源 的概念，强调民族自尊心和民族自信心的建立。 6
6 第五节 1．主要内容 有向图的强连通分量 2．基本概念和知识点 有向图的强连通分量 3．问题与应用（能力要求） 第六节 1．主要内容 串的模式匹配 2．基本概念和知识点 串的模式匹配 3．问题与应用（能力要求） 第七节 1．主要内容 最短路径的 Floyd-Warshall 算法 2．基本概念和知识点 最短路径的 Floyd-Warshall 算法 3．问题与应用（能力要求） 第八节 1．主要内容 总结各种算法和程序设计技术 2．基本概念和知识点 各种算法和程序设计技术 3．问题与应用（能力要求） （三）思考与实践 编程实现课堂中讲述的近似算法。 （四）教学方法与手段 课堂讲授，课堂讨论，编程实现。 授课过程中，通过二叉树中公共祖先的知识点，引出各中华民族同根同源 的概念，强调民族自尊心和民族自信心的建立
五、各教学环节学时分配 教学环节 讲 讨 小 教学时数 实验 其他教 课 学环节 课程内容 第一章 2 第二章 14 14 第三章 16 合计 32 六、推荐教材和教学参考资源 1.Jon Kleinberg,Eva Tardos.Algorithm design.Addison Wesley,2005 2.Jon Kleinberg,Eva Tardos..算法设计（中译本）.清华大学出版社，2010 七、其他说明 大纲修订人：高文宇 修订日期：2020.12 大纲审定人：许波 审定日期：2022年1月
7 五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教 学环节 小 计 第一章 2 2 第二章 14 14 第三章 16 16 合计 32 32 六、推荐教材和教学参考资源 1. Jon Kleinberg, Eva Tardos. Algorithm design. Addison Wesley, 2005 2. Jon Kleinberg, Eva Tardos. 算法设计（中译本）. 清华大学出版社, 2010 七、其他说明 大纲修订人：高文宇 修订日期：2020.12 大纲审定人： 许波 审定日期：2022 年 1 月