《算法设计与分析》课程考试标准

《算法分析与设计》课程考试标准总学时：64学分：4一、课程性质与考试基本要求：1.课程性质：专业限选课2．考试基本要求：通过本课程中许多常见且有代表性算法的学习，使学生理解算法的定义及基本概念，熟悉算法分析的基本技术，掌握算法设计的过程和方法，能熟练运用一些常用算法解决实际问题。二、考试方法：考试，期末考试成绩（80%）+平时（20%）三、课程考试内容及要求：第一章算法概述[考核内容]：算法的概念、算法的复杂性分析。[本章重点](1)理解算法的概念；(2)掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念；(3)掌握算法复杂性的渐进性态的数学表述；第二章递归与分治策略[考核内容]：递归的概念，学会用递归方法解决实际问题；分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序。[本章重点]⑴掌握递归的概念，学会用递归方法解决实际问题。⑵熟练掌握利用分治法解决问题的基本思想。⑶对算法复杂度（时间和空间）进行分析。第三章动态规划[考核内容]：动态规划的基本要素，最长公共子序列，最大子段和，流水作业调度0-1背包问题；最优二叉搜索树。[本章重点]：⑴理解动态规划算法的概念。⑵掌握动态规划算法的基本要素。⑶掌握设计动态规划算法的步骤。⑷能够针对中等难度的问题进行动态规划建模，计算复杂度。第四章贪心算法[考核内容]：贪心算法的基本要素；哈夫曼编码；单源最短路径；最小生成树。[本章重点]：⑴理解贪心算法的概念。⑵掌握贪心算法的基本要素。⑶理解贪心算法与动态规划算法的差异。⑷会用某高级语言编写用贪心算法解决问题的程序；⑸能对算法的复杂度、可靠性进行分析。第五章回溯法[考核内容]：回溯法的算法框架、符号；n个皇后问题；图的m着色问题；旅行售货员问题；[本章重点]：⑴理解回溯法的深度优先搜索策略。⑵掌握用回溯法解题的算法框架。⑶掌握回溯算法的复杂度分析。⑷理解各种剪枝策略。⑸掌握回溯算法的程序设计。第六章分支限界法[考核内容]：分支限界法的基本思想；单源最短路径问题；装载问题；0-1背包问题；最大团问题；旅行售货员问题。[本章重点]：⑴理解分支限界法的思想。⑵掌握分支限界法的算法框架。⑶掌握分支限界法复杂度分析。⑷掌握讲授的几个问题的分支限界求解。⑸掌握分支限界法的程序设计。五、不同性质考试内容所占比重：期末考试成绩（80%）+平时（20%），其中平时成绩包括实验成绩和平时上课表现两个方面去考核。六、成绩评定方式：本课程评分采用期末考试评分法。期末考试分数*80%+平时成绩*20%共同作为总的考试成绩。统一评分标准，期末考试成绩由课程设计、平时成绩以及实验成绩共同确定。期末考试占本门课程总评分的80%，平时成绩占10%，实验及实验考核成绩占10%，按此比例计算学生该门课程最后的总评成绩。教研室主任审核：课程考试标准批准：系（院）分管领导制定：执笔教师韩芹