《算法设计与分析》课程教学大纲

1、算法设计与分析课程教学大纲一、课程基本信息课程名称（中文）算法设计与分析课程名称（英文）Algorithm Design and Analysis课程类别：专业主干课课程性质必修授课语言中文授课学期第4学期学分2课程学时及分配总学时讲课实验课外3224832适用专业网络工程教材计算机算法设计与分析，电子工业出版社，王晓东，2018授课学院计算机与软件学院先修课程面向对象程序设计，数据结构后续课程气象传感网技术课程简介课程基本定位：本课程为专业主干课程。本课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；本课程首先介绍计算复杂性的定义和算法分

2、析的基本方法，结合计算机科学及应用领域中常见的有代表性的非数值算法，介绍了几种重要的算法设计方法：分治法、动态规划、贪心法、回溯法、分支限界法以及NP完全问题。使学生在理解各种算法设计策略的同时，熟悉算法分析的方法和应用的技巧，为从事物联网工程技术工作和科学研究奠定初步基础。课程复杂工程问题：本课程中的“算法设计与分析”课程设计是在理解算法设计策略、分析方法的基础上，综合利用分治法、动态规划、贪心法、回溯法、分支限界法的算分思想，融合个性需要，给出解决实际问题的有效方法。在具体的实施过程中，按照问题内在特性进行分类，分析可采用的潜在算法集合，制定算法设计策略。同时，分析该算法是否为最优方案，是

3、否有改进的空间，通过查阅文献、小组讨论等方式，创造性地给出改进方案，并能对该改进算法进行时间、空间复杂度分析。核心学习结果：结合自主学习,掌握算法设计基本方法，理解算法内在特性，并根据这些特性能够分类众多算法。能够运用算法设计相关专业知识，分析网络工程复杂工程问题，提高问题求解能力。应用算法解决网络工程、人工智能领域中的实际问题，并能够分析算法时间、空间复杂性，判断算法的优劣，开展实验验证工作。主要教学方法：讲授、案例、实验、专题研讨。大纲更新时间2020.8注：1.课程类别：选填“通识核心课/通识拓展课/通修课/学科基础课/专业主干课/专业选修课/专业实践/素质拓展”2.课程性质：选填“选修

4、/必修”3.授课语言：选填“中文/双语/全英文或其他语种”二、课程目标序号课程子目标支撑毕业要求指标点1达成方法1.1掌握算法设计基本概念、问题求解一般方法；讲授、实验、案例。1.2掌握算法时间、空间复杂性分析方法；1.3掌握各种典型算法的内在特性，分类方法；1.4掌握对不同问题类型的算法设计策略；2.1具有理论知识应用于构建模型、算法的能力；讲授、实验、案例、专题研讨。2.2具有分析算法时间、空间复杂性的能力；2.3具有依据工程实际问题的需求合理设计算法策略并求解问题的能力；2.4能够就网络工程领域复杂工程问题的求解，在学习小组中，充分发挥组织、协调能力，与小组成员有效沟通，合作解决问题。3

5、.1拥有求真务实、切问近思等科学精神。实验、专题讨论。注：1.支撑毕业要求指标点：选填项。需要进行专业认证，有毕业要求指标点可参照的课程必填，无明确毕业要求指标点可参照的可不填。三、理论教学环节及基本要求章标题教学内容学时思政融入点1学生学习预期学习成果2教学方式3课程目标第一章算法概述3了解算法与程序的概念；理解学习算法设计的目的、算法的概念和特性；掌握算法的描述方法；掌握算法时间、空间复杂度分析的方法。讲授、案例目标1.1目标1.2第二章递归与分治策略4理解递归、分治法的概念和基本思想；掌握分析递归算法时间复杂度的计算方法；掌握用分治策略进行合并排序、快速排序，解决大整数乘法、Strass

6、en矩阵乘法问题。讲授、案例、实验、作业目标1.2目标1.3目标1.4第三章动态规划5在互动问答中融入我校近年来举办和参与的各级各类程序设计、软件设计竞赛情况，鼓励学生勇于打开创新之门，同时培养学生实事求是、踏实严谨、独立思考的科学素养。了解动态规划算法的概念与步骤；理解动态规划算法与分治法的异同；掌握动态规划算法的最优子结构性质和重叠子问题性质；掌握设计动态规划算法的步骤；掌握矩阵连乘问题、最长公共子序列问题、0/1背包问题、最优二叉搜索树问题的算法设计与分析方法。讲授、案例、实验、作业目标1.2目标1.3目标1.4第四章贪心算法4在教学中融入社会责任、工匠精神。通过给学生介绍几位我国计算机

7、算法领域著名的学者，引导学生秉承工匠精神、社会责任，用心学习基础理论，才能为将来的专业学习和工作打下坚实的基础。理解贪心算法的概念和最优子结构性质、贪心选择性质。理解贪心算法和动态规划算法的异同；掌握最优装载问题、哈夫曼编码、单源最短路径问题、最小生成树问题的算法设计与分析方法。讲授、案例、实验、作业目标1.2目标1.3目标1.4第五章回溯法2了解回溯法的思想及算法框架；掌握装载问题、0-1背包问题、图的着色问题、n-皇后问题、最大团问题的算法设计与分析方法。讲授、案例、实验、作业目标1.2目标1.3目标1.4第六章分支限界法2理解并掌握分支限界法的一般方法；掌握采用分支限界法解决单源最短路径

8、问题、装载问题、0/1背包问题、最大团问题、旅行售货员问题的求解方法。讲授、案例、作业目标1.2目标1.3目标1.4第七章随机化算法2理解随机化算法的特征和4种分类； 掌握产生伪随机数的算法；讲授、案例、专题研讨、作业目标1.2目标1.3目标1.4第八章NP完全问题2在教学中融入家国情怀、自主创新。通过课程学习，培养和鼓励学生创新意识和家国情怀，更大程度上激发青年学生的制度自信、道德自信、理论自信以及文化自信，把学生培养成爱党爱国，敢于创新的技术人才。理解NP类的基本概念，NP有关的术语，NP类的特性；理解Cook定理的证明；掌握一些典型的NP完全问题的算法。讲授、案例、专题研讨目标1.2目标

9、1.3目标1.4四、实践（实验）教学环节及基本要求编号实践（实验）项目名称教学内容学时实验类型思政融入点预期学习成果课程目标1递归与分治法利用分治法解决Strassen矩阵乘法问题2设计理解分治法的应用场合及分治法算法的递推关系式；掌握Strassen矩阵乘法问题的算法设计方法及算法时间复杂度的分析；目标2.1目标2.2目标2.3目标2.42动态规划利用动态规划解决0/1背包问题2设计结合学生所做实验结果的分析，引入我校近年来举办和参与的各级各类程序设计、软件设计竞赛情况、学生屡获佳绩的情况，鼓励学生勇于打开创新的大门，同时培养学生实事求是、踏实严谨、独立思考的科学素养。理解动态规划的应用场合

10、和填表方法；掌握0/1背包问题的算法设计方法及算法时间复杂度的分析；目标2.2目标2.3目标2.43贪心算法利用贪心算法求解单源最短路径问题2设计给学生介绍几位我国计算机算法领域著名的学者，以他们的突出成就引导学生秉承工匠精神，用心学习基础理论，将来成为具有社会责任的合格的工程师。理解贪心算法和动态规划的异同；掌握Dijkstra算法设计方法及算法时间复杂度的分析；目标2.2目标2.3目标2.44回溯法利用回溯法求解8-皇后问题2设计通过学习，培养学生爱党爱国，使他们成为敢于创新的技术人才。理解回溯法如何在解空间进行深度优先搜索；掌握回溯法时间复杂度分析。目标2.2目标2.3目标2.4注：1.

11、思政融入点：至少写3条，简述该课程教学中将思政教育内容与专业教育内容有机融合的知识点（下同）。 2.学生学习预期成果：描述学生在学完本节内容后应获得的知识、能力或素养水平（下同） 3.教学方式:包括讲授、讨论、案例、演示等，但不限于所列，根据课程实际需要列举五、课程评价（一）考核内容、考核方式与课程目标对应关系课程目标考核内容课程目标在各考核方式中占比1作业课程实验课程报告目标1.1是否理解算法的基本概念，问题求解方法。2.5%2.5%目标1.2是否理解算法时间，空间复杂性、渐进进复杂性的概念和分析方法。5%7.5%目标1.3是否理解各种典型算法的特性、区别和分类方法。5%5%目标1.4是否掌

12、握针对各种具体问题的算法设计方法和时间复杂度分析方法。5%7.5%目标2.1是否具有将理论知识应用于构建模型、算法的能力。5%5%目标2.2是否具有分析算法时间、空间复杂度、判断算法优劣的能力。7.5%10%目标2.3是否具有为解决工程实际问题进行算法设计的能力。5%10%目标2.4是否能够就物联网应用领域复杂工程问题的求解，在学习小组中，充分发挥组织、协调能力，与小组成员有效沟通，合作解决问题。7.5%5%目标3.1课程实验环节是否能够反映求真务实、切问近思等科学精神。2.5%2.5%合计17.5%27.5%55%各考核方式占总成绩权重（自行赋值）100%100%100%注：1. 课程目标在

13、考核方式及占比：主要根据课程目标自行设计和制定多元化考核方式，表中所列仅为参考（红色数据可删除）。但所列考核方式必须覆盖全体学生，可根据当学期具体教学情况酌情调整。2. 各考核方式占总成绩权重：根据课程实际情况对各考核方式占总成绩的权重予以赋值。（二）考核方式评分标准1.课程作业评分标准课程目标评分标准占比90-100（优）80-89（良）70-79（中）60-69（及格）0-59（不及格）17.5%目标1.1：能够深入理解算法的概念和问题求解的方法。能够较好地理解算法的概念和问题求解的方法。能够理解算法的概念和问题求解的方法。基本理解算法的概念和问题求解的方法。不理解算法的概念和问题求解的方

14、法。目标1.2：能够深入理解算法时间，空间复杂性、渐进复杂性的概念和分析方法。较好地理解算法时间，空间复杂性、渐进复杂性的概念和分析方法。能够理解算法时间，空间复杂性、渐进复杂性的概念和分析方法。基本理解算法时间，空间复杂性、渐进复杂性的概念和分析方法。不理解算法时间，空间复杂性、渐进复杂性的概念和分析方法。目标1.3：能够深入理解各种典型算法的特性、区别和分类方法。能够较好地理解各种典型算法的特性、区别和分类方法。能够理解各种典型算法的特性、区别和分类方法。基本理解各种典型算法的特性、区别和分类方法。不理解各种典型算法的特性、区别和分类方法。目标1.4：能够深入掌握针对各种具体问题的算法设计

15、方法和时间复杂度分析方法。能够较好地掌握针对各种具体问题的算法设计方法和时间复杂度分析方法。能够掌握针对各种具体问题的算法设计方法和时间复杂度分析方法。基本掌握针对各种具体问题的算法设计方法和时间复杂度分析方法。未掌握针对各种具体问题的算法设计方法和时间复杂度分析方法。2. 课程实验评分标准课程目标评分标准占比90-100（优）80-89（良）70-79（中）60-69（及格）0-59（不及格）27.5%目标2.1：具有很强的将理论知识应用于构建模型、算法的能力。具有较强的将理论知识应用于构建模型、算法的能力。具有一般的将理论知识应用于构建模型、算法的能力。基本具有将理论知识应用于构建模型、算

16、法的能力。不具将理论知识应用于构建模型、算法的能力。目标2.2：具有很强的分析算法时间、空间复杂度、判断算法优劣的能力。具有较强的分析算法时间、空间复杂度、判断算法优劣的能力。具有一般的分析算法时间、空间复杂度、判断算法优劣的能力。基本具有分析算法时间、空间复杂度、判断算法优劣的能力。不具有分析算法时间、空间复杂度、判断算法优劣的能力。目标2.3：具有很强的为解决工程实际问题进行算法设计的能力。具有较强的为解决工程实际问题进行算法设计的能力。具有一般的为解决工程实际问题进行算法设计的能力。基本具有为解决工程实际问题进行算法设计的能力。不具有为解决工程实际问题进行算法设计的能力。目标2.4：具有

17、良好的沟通能力，能够在小组中发挥积极作用，带领小组成员很好地分析并解决问题。有较好的沟通能力，与小组成员良好合作，共同分析问题、解决问题。具有较好的沟通能力，能够协助小组成员解决问题。有一定的沟通与协作能力，在小组其他成员帮助下，基本能够解决问题。不能进行有效沟通、未能解决问题。目标3.1：实验报告格式规范，文字严谨，内容正确，条理性好，无抄袭痕迹，图文并茂；能正确问答所提的问题。实验报告格式规范，文字严谨，内容比较正确，条理性好，无抄袭痕迹，图文并茂；能比较正确问答所提的问题。实验报告格式比较规范，文字比较严谨，内容正确，条理性好，无抄袭痕迹，图文并茂；能比较正确问答所提的问题。实验报告格式

18、基本规范，文字严谨，内容基本正确，条理性好，无抄袭痕迹，图文并茂；能基本正确问答所提的问题。实验报告有明显的抄袭痕迹，不能正确问答所提的问题。3. 期末考试评分标准（笔试类评分标准可在大纲中按以下格式予以说明，也可在通过“试卷分析表”予以说明）课程目标评分标准占比90-100（优）80-89（良）70-79（中）60-69（及格）0-59（不及格）55%目标1.1：能够深入理解算法的概念和问题求解的方法。能够较好地理解算法的概念和问题求解的方法。能够理解算法的概念和问题求解的方法。基本理解算法的概念和问题求解的方法。不理解算法的概念和问题求解的方法。目标1.2：能够深入理解算法时间，空间复杂性

19、、渐进复杂性的概念和分析方法。较好地理解算法时间，空间复杂性、渐进复杂性的概念和分析方法。能够理解算法时间，空间复杂性、渐进复杂性的概念和分析方法。基本理解算法时间，空间复杂性、渐进复杂性的概念和分析方法。不理解算法时间，空间复杂性、渐进复杂性的概念和分析方法。目标1.3：能够深入理解各种典型算法的特性、区别和分类方法。能够较好地理解各种典型算法的特性、区别和分类方法。能够理解各种典型算法的特性、区别和分类方法。基本理解各种典型算法的特性、区别和分类方法。不理解各种典型算法的特性、区别和分类方法。目标1.4：能够深入掌握针对各种具体问题的算法设计方法和时间复杂度分析方法。能够较好地掌握针对各种

20、具体问题的算法设计方法和时间复杂度分析方法。能够掌握针对各种具体问题的算法设计方法和时间复杂度分析方法。基本掌握针对各种具体问题的算法设计方法和时间复杂度分析方法。未掌握针对各种具体问题的算法设计方法和时间复杂度分析方法。目标2.1：具有很强的将理论知识应用于构建模型、算法的能力。具有较强的将理论知识应用于构建模型、算法的能力。具有一般的将理论知识应用于构建模型、算法的能力。基本具有将理论知识应用于构建模型、算法的能力。不具将理论知识应用于构建模型、算法的能力。目标2.2：具有很强的分析算法时间、空间复杂度、判断算法优劣的能力。具有较强的分析算法时间、空间复杂度、判断算法优劣的能力。具有一般的分析算法时间、空间复杂度、判断算法优劣的能力。基本具有分析算法时间、空间复杂度、判断算法优劣的能力。不具有分析算法时间、空间复杂度、判断算法优劣的能力。目标2.3：具有很强的为解决工程实际问题进行算法设计的能力。具有较强的为解决工程实际问题进行算法设计的能力。具有