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

PAGEPAGE1算法设计与分析课程设计教学大纲课程编码：090151145周/学分：2周/4学分一、大纲使用说明本大纲根据信息与计算科学专业2017—2020版教学计划制订（一）适用专业信息与计算科学专业（二）课程设计性质必修课（三）主要先修课程和后续课程1．先修课程：C语言程序设计2．后续课程：大数据算法二、课程设计目的及基本要求本课程设计是信息与计算科学专业的重要实践性课程，隶属于《算法设计与分析》课程的一个重要部分，是课程结束后进行的一次全面的综合练习。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据结构和清晰高效的算法，这正是计算机科学领域数据结构与算法设计所研究的主要内容。算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。通过对计算机算法系统的学习与研究，掌握算法设计的主要方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础，对每一位从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者都是非常重要和必不可少的。设计目的如下：1．加深对常用算法以及计算复杂性的基本概念、基本原理和方法的理解。2.加强对分治法、动态规划、贪心法、回溯法、分支限界法设计策略的理解和实际运用能力的培养，能理论与实际相结合。3.能运用已有的算法分析的方法较准确地对算法进行分析，具有一定的分析能力；增强学生的科学实验素质。要求学生具有理论联系实际和实事求是的科学作风、严肃认真的工作态度。4.能运用已有的算法设计技术来设计实际问题的有效算法，具有较强的设计能力和一定的创新能力。注重创新实践、突出个性发展，努力培养面向软件行业的高素质应用型人才。为了使学生从课程设计中尽可能取得比较大的收获，对课程设计题目分成二类，一类为基础训练题目，学生从中学习到程序设计的常用算法。另一类为综合题目，学生从这两类型题目中各选择部分完成。基本要求：要求学生做好预习，掌握设计过程中涉及到的算法，按设计流程编程，上机调试通过，验证结果并进行分析、完成论文。三、课程设计内容及安排算法设计与分析是使学生掌握五种基本算法设计思想在求解实际问题中的应用，以及培养书写规范文档的技巧,学习基本的算法设计与复杂性分析技术。接受基本实验技能的训练，提高学生的动手能力和分析、解决问题的能力。具体的教学内容如下：1.掌握分治算法的基本设计思想逐步学会采用分治策略解决大规模问题的能力，具有正确处理合并与递归的能力。掌握数据结构在分治算法实现中的应用。2.掌握动态规划法的基本设计思想学会分析动态规划算法中最优子结构性质，了解动态规划的基本要素，掌握动态变化状态的结构特征，注意递归方程的实现。区分分治算法与动态规划算法的异同。3．掌握贪心算法的思想学会分析贪心算法的使用条件以及最优结构性质分析。掌握贪心算法解决问题的结果分析，算法的效率分析。了解贪心算法在智能算法以及启发式算法中的作用。4．掌握回溯算法的思想学会分析约束条件以及限界函数，掌握剪枝原则以及减少搜索空间的方法，并且理解深度优先的搜索策略，当前最好解的更新。5．掌握分支限界算法的思想 学会分析约束条件以及限界函数，掌握剪枝原则以及减少搜索空间的方法，并且理解宽度优先的搜索策略。区分深度优先与宽度优先在搜索上的异同整个课程设计分为以下几个阶段进行:开题,算法设计,算法实现,算法评价与验收。1．开题:题目可来自教师指定的参考题目,也可自由选题,特别是鼓励有创新性的题目或是在已知题目的基础上进行创新。2．算法设计:从问题需求出发，对问题的目标函数以及动态规程进行分析，确定基本算法的思路。在确定采用何种算法的基础上，对算法的难点进行分析，形成设计方案，考虑算法的简单性和正确性。3．算法实现:根据初步的算法设计方案,对算法进行编程实现。4．算法评价与验收:根据算法分析方法对算法进行评价。5．书写设计论文:完成文档整理,按照软件工程的要求完成设计论文。6、答辩与验收:通过答辩的形式对程序的功能进行评价与验收。四、指导方式由指导教师召开课程设计动员会，指定课程设计的题目和内容，讲解要求。学生在规定的时间内，完成题目。最后由指导教师进行验收及评定。五、课程设计考核方法及成绩评定1．考核方式：考查（学生上机操作演示，教师检查、提问，评定上机及论文成绩）。2．评分办法：（1）从五个方面考核课程设计完成的成绩:论文，算法设计方案,算法实现情况及工作量,回答教师所提出的问题，课程设计过程中的工作态度等综合打分。①论文占20%②算法设计方案占30%③算法实现情况及工作量占20%④回答教师所提出的问题占20%⑤课程设计过程中的工作态度（考勤）占10%（2）课程设计的选题新颖或算法实现了改进或创新，应予以适当加分。（4）成绩评定实行优秀、良好、中等、及格和不及格五个等级的成绩。六、课程设计教材及主要参考资料《计算机算法设计与分析》（第4版），王晓东编著，电子工业出版社，2012《算法设计与分析基础》（第3版），(美)AnanyLevitin著，潘彦译，清华大学出版社2015.《算