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

1、算法设计与分析教学大纲课程设计名称：算法设计与分析课程英文名称：Algorithm Design & Analysis课程编码：课程类别/性质：专业/选修学分：2总学时/理论/实验（上机）：32/16/16开课单位：地球科学学院适用专业：地理信息系统先修课程：计算机基础、C语言程序设计、数据结构、C#程序设计理论与实训、计算方法一、课程简介算法设计与分析是地理信息科学专业的选修课程。主要阐述算法基础知识、分治策略、动态规划、贪心法回溯与分支限界、线性规划、算法分析与问题的计算复杂度等，是指导系统逻辑设计和算法设计开发的理论基础。课程内容包括三部分：分治策略、动态规划、算法分析与问题的计算复杂度

2、。其中核心内容是分治策略。该课程综合性较强的应用学科，必须全面地运用面向对象程序设计、程序设计方法学等多学科知识来阐述算法设计与分析的基本理论、概念与方法。要求学生学习该课程后，掌握算法的基本理论和方法，掌握分治策略、动态规划常见方法，熟悉背包问题回溯与分支限界算法、最小生成树贪心算法，熟悉线性规划常见算法；具备基本的算法设计与实现能力，能够根据问题分析、分解设计算法；树立自主研发维护国家软件自主的正确价值观。保证学生达成专业的相应毕业要求。二、课程教学目标通过本课程的学习使学生掌握分治策略、动态规划和算法分析与问题的计算复杂度等理论，培养算法分析、设计与实现能力，树立自主研发维护国家软件自主

3、的正确价值观。为后续专业课程学习及从事GIS研发工作打下坚实的理论基础。价值目标(或称育人目标)：引导学生树立做国产GIS软件的宏大志向，培养爱国、爱党、爱校、爱家的社会主义新青年，使其掌握自主研发维护国家软件自主的正确价值观。2知识和能力目标：(1) 掌握分治策略基本概念、基本原理和基本方法（毕业要求2.1）；(2) 掌握动态规划的基本规律（毕业要求2.3）；(3)巩固课堂所学的理论及程序演示，利用程序设计软件，对理论课上涉及重要的知识点设计实验内容，掌握算法设计与分析实验过程并获得实验结果(毕业要求3.2)；(4)要求学生解决现实中的问题，能对解决问题过程中算法的优劣进行对比评价；能够对现

4、实中的问题进行剖析、设计、编写程序解决，并对实验结果进行评价(毕业要求9.1、9.2)；三、课程教学内容及学时分配课程教学包括课堂教学、课堂研讨、课堂及课后习题三部分，包括6章的理论教学8次上机内容。课内理论教学16学时、上机16学时（详见本大纲第四部分）。课堂理论教学内容、要求及学时分配如下：课程教学内容及学习要求章节内容思政融入点要求学时支撑毕业要求指标点理解掌握分析与应用第1章基础知识第一节有关算法的基本概念软硬件、操作系统及程序设计发展史，激发爱国情怀，激励对算法的兴趣与爱好高高中22.1第二节算法的伪码描述高高中第三节算法数据基础高高中第二章分治策略第一节分治策略的基本思想分而治之的

5、人生哲理高高中22.3第二节分治算法的分析技术中中中第三节改进分治算法途径高高中第三章动态规划第一节动态规划的设计思想路径最优问题的求解，局部最优。高高高42.3第二节动态规划算法的设计要素高高中2.3第三节动态规划算法的典型应用高中中第四章贪心法第一节贪心法的设计思想农村包围城市的作战思想，最大限度的孤立敌人，引出贪心算法。高中中22.3第二节贪心法的典型应用高中中2.3第五章回溯与分支限界第一节回溯算法的基本思想和适用条件结合GIS领域王之卓等杰出院士的艰苦卓绝的科研事迹，鼓励学生刻苦钻研专业问题，追求卓越成就。设置人生底线。中中中22.3第二节分支限界典型应用中中低第六章线性规划第一节线

6、性规划模型航天精神，一步步循序渐进的发展超大规模的运载火箭，规划发展方法。高高中42.3第二节线性规划典型应用高高中第二节检索算法的时间复杂度分析高中中第三节排序算法的时间复杂度分析高高中注：在“要求”栏内以高、中、低来表示对学生学习程度的要求，高为最高要求。理解指能对所学的内容作归纳、分类、解释、总结、推断和一定程度的发挥。掌握指能理解学习材料的内涵和意义，包括具体分类、区别、流程、误区等的认知和学习。可以借助三种形式来表明对材料的领会，一是转换，即用自己的话或用与原先表达方式不同的方式表达自己的思想；二是解释，即对一项信息加以说明或概述；三是推断，即估计将来的趋势（预期的后果）。分析指能将

7、所学的内容分解并找出它们的相互关系和构成，或能计划、创造、建造或有改变的重构。应用指能将学习材料用于新的具体情境，包括原则、方法、技巧、规律的拓展， HYPERLINK /doc/6670661-6884501.html t _blank 代表较高水平的学习成果。应用需要建立对知识点掌握的基础上。四、上机内容与学时分配1上机目的与任务实验是学习该课程的非常重要的教学环节，通过上机实验能够加深理解和巩固书本上所学的知识，能够提高动手操作的能力以及分析问题和解决问题的能力。在教材中的每章都将给出具体的实验练习题，以及必要的操作步骤2上机教学基本要求通过实验教学，加深对基础理论知识的理解，培养学生实

8、验动手能力。通过实验课学生应掌握下列基本技能：算法实现的开发环境，掌握算法实现的流程和规则，通过算法设计解决实现问题。上机教学内容及学时分配上机教学内容及学时分配表序号实验项目实验类型学时支撑毕业要求指标点演示验证综合设计1求和方法22.32分治策略22.33动态规划算法22.14贪心算法22.35回溯算法22.36分支限界算法22.37线性规划21.2、2.38排序算法时间复杂度分析22.3上机一 求和问题2学时（1）目的要求通过控制台程序的编写，使学生及时掌握C#程序的开发编译环境，以C程序设计中数据类型为基础进行扩展，熟悉C#中的常见数据类型。（2）方法原理采用演示的方法，演示本次上机的

9、要点内容，督促学生动手解决求和问题。（3）主要上机软硬件环境Visual studio2017以上版本或vc+6.0，内存不低于8G，硬盘空间不低于50G。（4）掌握要点掌握C#程序的主函数编写、主要的输入输出类和方法。常见数据类型如整型、浮点型、双精度型的表达方法。上机内容任务一：1+2+3+.+100上机二 分治算法 2学时（1）目的要求进一步属性C/C+语言的集成开发环境。通过本实验加深对递归与分治策略的理解与运用。（2）方法原理分治的思想：一个规模为规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。分治法使用递归的思想，划分后的每一个子问题与

10、原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。（3）主要上机软硬件环境Visual studio2017以上版本或vc+6.0，内存不低于8G，硬盘空间不低于50G。（4）掌握要点掌握分治算法的核心原理与实现方法。上机内容任务一：Gray码构造问题上机三 动态规划算法 2学时（1）目的要求理解动态规划算法的基本思想；运用动态规划算法解决实际问题，加深对贪心算法的理解与运用。（2）方法原理动态规划的思想：把待求解问题分解成若干个子问题，先求解子问题然后由这些子问题的解得到原问题解。动态规划求解过的子问题得结果会被保留下来，不像递归那样每个子问

11、题得求解都要从头开始反复求解。动态规划求解问题得关键在于，不像递归那样每个子问题得求解都要从头开始反复求解。动态规划求解问题得关键在于获得各阶段子问题的递推关系式：分析原问题得最优解性质，刻画其结构特征；递归定义最优值；自底向上(由后向前)得方式计算最优值；根据计算最优值时得到得信息构造一个最优解。（3）主要上机软硬件环境Visual studio2017以上版本或vc+6.0，内存不低于8G，硬盘空间不低于50G。（4）掌握要点掌握动态规划算法的核心原理与实现方法。上机内容任务一：最小子段和问题上机四 贪心算法 2学时（1）目的要求理解贪心算法的基本思想。运用贪心算法解决实际问题，加深对贪心

12、算法的理解与运用。（2）方法原理贪心算法的思想：第一步选择一定包含着一个最优解，即存在一个最优解的第一步是从贪心选择开始，在做出第一步贪心选择后，剩下的子问题应该就是与原问题类似的规模较小的问题，为此我们可以用数学归纳法来证明贪心算法选择得到的问题的最优解。（3）主要上机软硬件环境Visual studio2017以上版本或vc+6.0，内存不低于8G，硬盘空间不低于50G。（4）掌握要点掌握贪心算法的核心原理与实现方法。上机内容任务一：最小延迟调度问题上机五 回溯算法 2学时（1）目的要求通过回溯算法的示例程序理解回溯算法的基本思想；运用回溯算法解决实际问题，进一步加深对回溯算法的理解与运用

13、。（2）方法原理回溯算法的基本思想是搜索或就是一种组织得井井有条得、能避免不必要搜索得穷举式搜索法。这种方法适用于解一些组合数相当大得问题。回溯算法在问题的解空间树中按深度优先策略。从根结点出发搜索解空间树。算法搜索至解空间树得任意一点时，先判断该结点就是否包含问题得解：如果肯定不包含则跳过对该结点为根的子树的搜索逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯算法的基本步骤:(a)针对所给问题定义问题的解空间；(b)确定易于搜索的解空间结构；(c)以深度优先方式搜索解空间并在搜索过程中用剪枝函数避免无效搜索。（3）主要上机软硬件环境Visual studio2017以上版

14、本或vc+6.0，内存不低于8G，硬盘空间不低于50G。（4）掌握要点掌握回溯算法的核心原理与实现方法。（5）上机内容任务一：什么是启发式搜索问题上机六 分支限界算法2学时（1）目的要求通过分支限界算法的示例程序进一步理解分支限界算法的基本思想；运用分支限界算法解决实际问题，进一步加深对分支限界算法的理解与运用。（2）方法原理分枝限界算法就是另一种系统地搜索解空间得方法，它与回溯算法得主要区别在于对E结点得扩充方式。每个活结点有且仅有一次机会变成E结点。当一个结点变为E结点时，则生成从该结点移动一步即可到达得所有新结点在生成得结点中，抛弃那些不可能导出(最优)可行解得结点，其余结点加入活结点表

15、，然后从表中选择-个结点作为下一个E结点。从活结点表中取出所选择得结点并进行扩充直到找到解或活动表为空，扩充过程才结束。（3）主要上机软硬件环境Visual studio2017以上版本或vc+6.0，内存不低于8G，硬盘空间不低于50G。（4）掌握要点掌握分支限界算法的核心原理与实现方法。上机内容任务一：运动员最佳配对问题上机七 线性规划 2学时（1）目的要求通过线性规划算法的示例程序进一步理解线性规划算法的基本思想；运用线性规划算法解决实际问题，进一步加深对线性规划算法的理解与运用。（2）方法原理线性规划是目标函数含两个自变量的线性规划，其最优解可以用数形结合方法求出。涉及更多个变量的线性

16、规划问题不能用初等方法解决。（3）主要上机软硬件环境Visual studio2017以上版本或vc+6.0，内存不低于8G，硬盘空间不低于50G。（4）掌握要点掌握线性规划找到全局最优解的方法（5）上机内容任务一：某企业生产甲、乙两种产品。己知生产每吨甲产品要用A原料3吨、B原料2吨；生产每吨乙产品要用A原料1吨、B原料3吨。销售每吨甲产品可获得利润5万元、每吨乙产品可获得利润3万元。该企业在一一个生产周期内消耗A原料不超过13吨，B原料不超过18吨，那么该企业可获得最大利润是多少？上机八 排序算法时间复杂度分析2学时（1）目的要求理解时间复杂度对排序算法性能评价，运用时间复杂度分析常见算法

17、。（2）方法原理算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。（3）主要上机软硬件环境Visual studio2017以上版本或vc+6.0，内存不低于8G，硬盘空间不低于50G。（4）掌握要点掌握时间复杂度的内涵；掌握常见排序算法的时间复杂度；能对简单算法估计时间复杂度并提升时间复杂度。（5）上机内容任务一：冒泡和二分法插入排序时间复杂度对比五、教学方法教学过程：采用启发式、提问式、讲授式、演示式等教学手段，讲解教学内容，结合多媒体教学课件，穿插演示实例以增加知识点理解。并在每章结束后，进行章节小结，安排适当的课后题目。实验上机：按照讲课中知识点出题，学生在解决题目问题的过程中，掌握核心知识点，提升实际动手实践能力，并撰写实验报告，包括、数据分析、任务详情、总体设计、系统成果、总结和体会等。六、考核及成功评定方式课程考核包括平时成绩和期末课程论文两个部分。平时成绩：30%，包括课堂习题、案例讨论、小组讨论及考勤（毕业要求2.3）。上机成绩：70%，求和方法、分治策略、动态规划