算法设计与分析课程标准

1、算法设计与分析课程标准一、课程概述算法设计是计算机科学的一门分支学科。计算机技术的发展，一方面是硬件技术的发展，另一方面是软件技术的发展，而软件技术的一个重要方向就是算法设计。算法设计既是软件设计的关键，也是培养学生成为未来软件工程师所不可或缺的一门专业知识。算法设计与分析课程将高级语言程序设计、数据结构和计算方法等内容紧密地结合在一起，全面培养学生分析问题、解决问题的能力。这门学科的重点是在培养和培训学生学会经典算法方面的知识与应用，因此它对学生的专业发展具有极其重要的意义。算法设计与分析的先修课程是高级语言程序设计、数据结构、高等数据、组合数学。二、课程目标1. 知道算法设计与分析这门学科

2、的性质、地位和独立价值。知道这门学科的研究范围、分析框架、研究方法、学科进展和未来方向。2. 理解这门学科的主要概念，尤其是算法的时间复杂度和空间复杂度。3. 初步学会运用数学的方法推导和证明算法的时间复杂度和空间复杂度。4. 掌握常用的经典算法，培养学生在软件设计时对算法设计的重视，并能够把所学的知识应用到具体的软件设计实践中去。三、教学内容和教学要求这门学科的知识与技能要求分为知道、理解、掌握、学会四个层次。这四个层次的一般涵义表述如下：知道是指对这门学科和有关知识的认知。理解是指对这门学科涉及到的概念、算法的说明和解释。掌握是指运用已理解的概念、算法解决同类的实际问题。学会是指能模仿或在

3、教师指导下独立地完成某些算法的设计、分析和调试。教学内容和要求表中的“”号表示教学知识和技能的教学要求层次。本标准中打“*”号的内容可作为自学，教师可根据实际情况确定要求或不布置要求。d 算法及算法的复杂性教学内容教学要求知道理解掌握学会1、 算法的定义2、 算法的复杂度与评价3、 解递归方程4、 算法分析举例 （二）贪婪法教学内容教学要求知道理解掌握学会1、 贪婪法的基本思想2、 背包问题3、 有限期的计算机作业调度4、 计算机网络的最短传输时间（三）递归教学内容教学要求知道理解掌握学会1、 递归调用的内部实现原理2、 递归程序的阅读3、 递归转非递归4、 递归算法设计（四）回溯法教学内容教

4、学要求知道理解掌握学会1、 回溯法的基本思想2、 子集和问题3、 皇后问题4、 哈密顿回路问题5、 图的着色问题（五）动态规划教学内容教学要求知道理解掌握学会1、 最优性原理2、 一些简单例子3、 最短路径问题4、 最优树问题5、 最优调度问题（六）分治法教学内容教学要求知道理解掌握学会1、 分治法的基本思想2、 分治法算法设计的特点3、 分治法的时间复杂度4、 分治法的应用（七）探索法教学内容教学要求知道理解掌握学会1、 探索法的基本思想2、 探索法的应用（八）分枝限界法教学内容教学要求知道理解掌握学会1、 态空间树上的检索2、 枝限界法解最优化问题3、 0/1背包问题的lc分枝-限界求解的

5、实现（九）内存分类法教学内容教学要求知道理解掌握学会1、 第k个元素2、堆分类（十）图的算法教学内容教学要求知道理解掌握学会1. 图的两种遍历2. dfs树3. 无向图的双连通分支4. 有向图的强连通分支5. 流的算法四、课程实施（一）课时安排与教学建议算法设计与分析是计算机科学技术专业的限选课。一般情况下，每周安排3课时，共54课时。函授生视具体情况而定，一般为36课时。具体课时安排如下：主要内容课时建议54课时教与学的方法建议按54课时计按36课时计算法及算法的复杂性42告知学生课程教学总体安排及基本概念；语言呈示为主贪婪法64陈述、举例、演示、讨论递归64陈述、举例、演示、演示回溯法42

6、陈述、举例、讨论动态规划64陈述、举例、演示、讨论分治法64陈述、举例、演示、讨论探索法43陈述、举例、演示分枝限界法43陈述、举例、演示内存分类法43陈述、举例、演示图的算法64陈述、举例、演示、讨论总复习22机动21（二）教学组织形式与教学方法要求1 教学班是主要的教学组织，班级授课制是目前教学的主要组织形式。有条件的话，也可以采用分组教学。或者几种组织方式灵活组合，尽量减轻学生的生理和心理疲劳。2、 注意教学方法的灵活性，培养学生发现问题、分析问题、解决问题的能力和探究意识。3、 充分发挥学生的主动性，而不是“填鸭”式的教育。一定要结合学生的实际能力进行教学。4、 评价教学方法要以实现课

7、程标准规定的教学目标为依据，好的教学方法应有助于学生对教学内容的理解，并能激发学生的学习热情。五、 教材与参考书目算法设计与分析教材要在课程标准的统一要求下，选用普通高校教材或选用公认的水平较高的教材（含教育部推荐教材）。如：原福永等 . 算法设计与分析 . 北京：机械工业出版社，1998吴中福 . 算法设计与分析 . 重庆：重庆大学出版社，2001参考书目：卢开澄 . 计算机算法导引：设计与分析北京：清华大学出版社，1996s . baase . 计算机算法：设计和分析引论 . 朱洪等译.上海：复旦大学出版社，1985bruno r . preiss数据结构与算法 . 胡广斌等译 . 北京：

8、电子工业出版社，2000六、课程评价1. 这门学科的评价依据是本课程标准规定的课程目标、教学内容和要求。2. 考试时间：120分钟。3. 考试方式、分制与分数解释采用闭卷、笔试的方式，以百分制评分，60分为及格，满分为100分。4. 建议题型比例计算题20%；算法的时间复杂度函数12%；根据给定的算法求出问题的解8小题48% 综合分析题20%。5. 样题与目标定位示例6. 计算题：（着重考查学生运用数学知识求解递归方程的能力）例：给定一个递推方程，要求求解后用o、表示。b算法的时间复杂度函数：（着重考查学生对简单算法的理解程度）例： 给定一个具体的算法，要求写出算法的时间复杂度函数。c根据给定的算法求出问题的解：（着重考查学生对经典算法的理解程度） 例：