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

1、算法设计与分析课程教学大纲课程编号：08123070课程名称：算法设计与分析/ The Design and Analysis of Algorithms总学时/学分：40/2.5（其中理论30学时，实验10学时）适用专业：计算机科学与技术一、课程目标通过本课程学习，学生应达到如下目标：目标1：掌握算法有关的基本概念，理解典型的算法思想，分析、计算算法的复杂性。目标2：运用大整数的运算、枚举、递推、递归、动态规划、贪心算法、回溯法等算法思想解决复杂工程问题。目标3：根据算法编写程序，并测试程序。二、课程目标对毕业要求的支撑毕业要求二级指标点权重(=1)初始程度要求程度课程目标1、工程知识1-4

2、 能利用数学、自然科学和专业知识对复杂计算机工程问题解决方案的复杂性进行分析与判断。0.2 L1L4目标12、问题分析2-1能够利用数学、自然科学及计算机的基本理论知识解释与表达复杂计算机工程问题。0.6L1L3目标24、研究4-1能够基于计算机领域科学原理并采用科学方法对计算机软硬件及大数据系统，独立进行实验设计、算法设计及程序实现，并验证实验、测试算法与程序的正确性。0.2L1L3目标3本表注：以布鲁姆学习目标分类法描述学生在学完本课程后应具有的能力，目标栏内以L1(认知)、L2(理解)、L3(应用）、L4(分析)、L5(综合)、L6(创造)来表示对此项能力要求达到的程度，无要求则留空。三

3、、教学过程安排序号知识模块教学内容课时课程目标教学方法1算法简介及复杂性分析1.1算法及其描述4目标1算法简介及复杂性分析2大整数运算2.1求n!2.2超长整数的加、减、乘、除运算4目标2课堂讲授+演示+作业3常用算法思想3.1枚举：同码小数，整数对，基于s的双和数组，最小连续m个合数，佩尔方程，p进制乘法表3.2递推：双关系递推数列，方格网交通线路，猴子爬山，整数划分式的个数，猴子吃桃3.3递归：排队购票问题，找第k个最小的数问题6目标2课堂讲授+演示+作业4动态规划4.1动态规划概述4.2矩阵连乘积4.3 0-1背包问题4.4西瓜分堆4.5凸n边形的三角形划分4.6最长非降子序列(非连续)

4、6目标2课堂讲授+讨论+作业+测验5贪心算法5.1贪心算法概述5.2背包问题5.3删除数字问题5.4埃及分数问题5.5数列极差问题6目标2课堂讲授+讨论+作业+测验6回溯法6.1回溯法概述6.2 0-1背包问题6.3 N后问题6.4桥本分数式问题6.5逐位整除数问题4目标2课堂讲授+讨论+作业+测验7课内实验7.1大整数运算7.2枚举、递推、递归的应用7.3动态规划7.4贪心算法7.5回溯法10目标3学生操作教师指导实验报告四、实验或上机内容序号实验项目名称实验目的和任务实验学时实验类型开出要求1大整数运算目的：掌握大整数的加、减、乘、除运算的算法思想与技巧。任务：大整数的加、减、乘、除运算2

5、 设计型必做2枚举、递推、递归目的：枚举、递推、递归算法在复杂工程问题中的应用。任务：最小连续m个合数、双关系递推数列。2 设计型必做3动态规划目的：掌握动态规划的思想方法及其在复杂工程问题中的应用。任务：利用动态规划算法思想求解0-1背包问题、西瓜分堆问题。2 设计型必做4贪心算法目的：掌握贪心算法的思想方法及其在复杂工程问题中的应用。任务：用贪心算法求解可拆背包问题、删除数字问题。2设计型必做5回溯法目的：掌握回溯法的思想方法及其在复杂工程问题中的应用。任务：用回溯法求解0-1背包问题、N后问题。2设计型课外必做五、课程目标达成方法教学目标课时评价方法评价依据达成标准(分)目标14期末考试

6、（80%）+作业（20%）试卷+作业68目标226期末考试（70%）+作业（10%）+测验（10%）+讨论课（10%）试卷+作业+测验68目标310实验（100%）操作+实验报告68合计40六、考核标准本门课程考核包括6个部分，分别为考试、作业、实验、大作业、讨论、测验。具体要求及评分方法如下：1、考试试卷知识点要求序号知识模块考核内容试题比例目标1算法的概念及复杂性分析算法复杂性分析30%目标2大整数运算、枚举、递推、递归、动态规划、贪心算法、回溯法2.1算法概念及算法思想2.2大整数运算2.3枚举、递推、递归2.4动态规划、贪心算法、回溯法70%2、作业优秀（90-100分）良好（80-8

7、9分）中等（70-79分）及格（60-69分）不及格（<60分）按时完成，格式工整，解决90%以上的主要问题。能提出多种不同的解决方案。按时完成，解决80%以上的主要问题。只能提出一种解决方案，且比较有效。延时3 天内完成，解决70%以上的主要问题。解决方案有效性不足。延时一周内完成。解决50%以上的主要问题。有效性不足。延时一周以上完成。解决50%以下的主要问题。有抄袭（雷同）现象。3、实验优秀（90-100分）良好（80-89分）中等（70-79分）及格（60-69分）不及格（<60分）操作考核方法操作熟练，能提前完成任务操作较熟练，能按时完成任务操作基本熟练，基本按时完成任务

8、操作基本熟练，延迟1天完成任务操作生疏，延迟>1天完成任务实验报告按时完成，方案能解决90%以上的主要问题。能提出多种不同的解决方案，各种方案基于的原理并不相同，且比较有效。按时完成，方案能解决80%以上的主要问题。只能提出一种解决方案，且比较有效。延时3 天内完成，方案能解决60%以上的主要问题。能提出多种解决方案，且有效性不足。延时一周内完成。按时完成，方案能解决40%以上的主要问题。只能提出一种解决方案，且有效性不足。大于一周按时完成。方案能解决40%以下的主要问题。不能提出解决方案。有抄袭（雷同）现象。4、大作业优秀（90-100分）良好（80-89分）中等（70-79分）及格（

9、60-69分）不及格（<60分）按时完成，算法思想及程序正确。能提出多种不同的解决方案，各种方案基于的算法思想并不相同，且比有效。格式规范。按时完成，算法思想及程序正确。只能提出一种解决方案，且比较有效。格式规范延时3 天内完成，算法思想正确、程序BUG少。能提出多种解决方案，且有效性不足。格式基本规范延时一周内完成。算法思想基本正确、程序BUG较多。能提出一种解决方案，有效性不足。格式基本规范大于一周延时完成。算法思想不正确、程序BUG较多。不能提出有效解决方案。有抄袭（雷同）现象。格式不规范5、课堂讨论要求学生须事先按照讨论题目分组查阅资料，归纳总结，课堂汇报。优秀（90-100分）良好（80-89分）中等（70-79分）及格（60-69分）不及格（<60分）汇报和回答问题讲述清楚，内容符合要求，回答问题准确讲述清楚，内容符合要求，回答问题较准确讲述较清楚，内容基本符合要求，回答问题基本准确讲述基本清楚，内容基本符合要求，回答问题基本准确讲述不清楚，内容不符合要求，回答问题不准确6、测验随堂测验，老师给出题目，学生回答。具体由任课老师给出评分标准。七、教材及主要参考资料1 杨克昌、严权峰.，算法设计与