算法分析与设计课程教学大纲.docx

算法分析与设计教学大纲课程性质专业限选课课程编号xx882040课程名称算法分析与设计适用专业计算机科学与技术，软件工程，物联网工程，网络工程先修课程C语言程序设计、C+程序设计、数据结构总学时48其中理论36学时，实验12学时学分数3一、课程简介算法分析与设计是一门理论性与实践性兼顾的课程，是面向设计，且处于计算 机科学与技术学科核心地位的教育课程。本课程系统介绍了软件设计中常用的算法设计 与分析方法，通过对算法设计策略的系统学习与研究，理解和掌握算法设计的主要方法, 锻炼学生独立分析问题和解决问题的能力，为开发高效的软件系统及相关领域的研究工 作奠定坚实的基础。课程是“编译原理”和“软件工程”等专业核心课程的基础课，为 学习专业课程及提高软件设计水平打下良好的基础。二、课程教学目标通过本课程的学习，学生应实现如下目标：1、知识目标：了解：算法的概念，程序与算法的区别；递归、分治策略的基本原理和效率分析动 态规划算法的概念；贪心算法的基本思想、适用条件；理解回溯法的基本思想及效率估 计，限界函数；分支限界法的基本思想及效率估计。掌握：算法时间复杂性的估计与表示；递归、分治的概念，设计有效算法的分治策 略；动态规划算法的基本要素、设计动态规划算法的步骤以及典型问题的应用与分析。 贪心算法的设计策略、基本思想、适用条件，贪心算法的典型问题的解决方法与分析； 回溯法在典型问题的应用及分析及解决方法；分支限界法的算法框架及在典型问题的应 用。2、能力目标：(1)对C+程序设计有进一步的认识和了解，提高程序调试能力；(2)掌握算法设计的基本策略，到达融会贯通之效；三、课程教学基本要求本课程的基本要求是让学生理解计算机算法效率分析与设计所涉及的基本概念和 基础知识，掌握基本的算法分析方法和常见的算法设计方法，能熟练应用课程介绍的算 法设计方法来解决软件开发中的实际问题。通过对算法实例的分析，进一步加深学生对 算法设计方法的认识和理解。四、课程教学模块（或教学内容）与学时分配序号教学模块知识点学时1工程一概述理解：算法的概念、算法的时间复杂性和空间复杂性掌握：求解问题的基本步骤掌握：算法运行时间的估计42工程二递归 与分治策略掌握：递归的概念，掌握设计有效算法的分治 策略理解：分治策略的基本原理和效率分析，掌握 设计有效算法的分治策略103工程三动态规划理解：动态规划算法的概念掌握动态规划算法的基本要素、掌握设计动态 规划算法的步骤以及典型问题的应用与分析104工程四贪心算法理解：贪心算法的基本思想、适用条件掌握：贪心算法的设计策略，掌握贪心算法典型问题的应用与分析85工程五回溯法理解：回溯法的基本思想及效率估计，限界函数掌握：回溯法在典型问题的应用及分析106工程六分支 限界法理解：分支限界法的基本思想及效率估计 掌握：分支限界法的算法框架，分支限界法在 典型问题的应用47工程七概率 算法理解：分概率法的基本思想及效率估计 掌握：概率法在典型问题的应用2序 号实验工程名称内容摘要实验 学时实验类型开出要求1C/C+环境及递 归算法熟悉C/C+语言的集成开发 环境，加深对递归过程的理 解2设计性必做2分治算法熟悉二分搜索算法和快速排 序算法，初步掌握分治算法2设计性必做3动态规划算法熟悉最长公共子序列问题的 算法，掌握动态规划算法。2设计性必做4动态规划算法熟悉最长最大字段和问题的 算法，进一步掌握动态规划 算法。2设计性选做5贪心算法熟悉多机调度问题的算法，初步掌握贪心算法2设计性必做6贪心算法掌握背包问题的算法。进一 步掌握贪心算法2设计性必做7回溯算法掌握装载问题的回溯算法， 初步掌握回溯算法2设计性选做8回溯算法掌握0-1背包问题的回溯算 法，进一步掌握回溯算法2设计性必做9分支限界法掌握旅行商售货员问题的分 支限界算法，区分分支限界 算法与回溯算法的区别，加 深对分支限界法的理解。2验证性选做10概率算法掌握拉斯维加斯算法，加深 对概率算法的理解2验证性选做五、教学方法与策略1、讲授法：介绍算法设计策略的基本思想，然后从解决计算机科学与应用中出现 的实际问题入手，由简到繁地描述几个经典的精巧算法，同时对每个算法所需要的时间 和空间进行分析。2、实验课：学生在上课过程中完成6个设计性实验，在课后自行安排时间完成4 个试验，通过各个实践性环节的训练，学生基本能够掌握算法设计的主要方法。培养学 生严谨的科学态度、科学的思维方法以及技术创新能力。六、学生学习成效考核方式七、选用教材考核环节构成（均为100分制）评分依据占总成绩 的比重上课出勤、实验上课缺席一次扣2分，缺课达1/3取消资格。40%期末考试成绩期末考试卷面成绩为准60%教材：王晓东.计算机算法分析与设计（第4版）.北京：电子工业出版社，2012.八、主要参考书：1石志国，刘冀伟，姚亦飞 编著.算法分析与设计（C+描述）.北京：清华大学出版社, 2010.