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

《算法设计与分析》教学大纲课程英文名AlgorithmDesignandAnalysis课程代码J0701Z35学分3总学时48理论学时32实验/实践学时16课程类别专业课课程性质任选先修课程《数据结构》《C++程序设计》适用专业信息与计算科学开课学院理学院一、课程地位与课程目标（一）课程地位本课程是信息与计算科学的专业选修课。计算机科学是一种创造性思维活动，其教育必须面向设计。算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学领域里数据结构与算法设计所研究的主要内容。（二）课程目标1.使学生掌握分治法、贪心法、动态规划、回溯法、分支限界法等常用的算法设计技术，掌握算法分析的初步能力；2.使学生掌握解决实际问题的算法设计方法，加深对数学在实际中广泛应用的理解，进一步激发学生学习数学的兴趣。二、课程目标达成的途径与方法对课程目标1，以课堂教学为主，结合课堂讨论、课外作业、课后答疑等方法达成。对课程目标2，以上机实践为主，结合小组讨论、实验报告、课外辅导等方法达成。三、课程目标与相关毕业要求的对应关系课程目标课程目标对毕业要求的支撑程度（H、M、L）毕业要求2毕业要求3毕业要求5课程目标1HMH课程目标2HHH注：1.支撑强度分别填写H、M或L（其中H表示支撑程度高、M为中等、L为低）。四、课程主要内容与基本要求第一章：算法概述理解算法的定义，理解程序与算法的区别与内在联系。掌握算法复杂性的渐近性态的数学表述。掌握用计算机语言描述算法的方法。第二章：递归与分治策略掌握递归的概念、掌握分治法的基本思想。并能运用递归、分治法设计二叉检索算法、合并排序、快速排序等算法。第三章：动态规划理解动态规划算法的概念。掌握动态规划算法的基本要素与设计动态规划算法的步骤。掌握最长公共子序列问题与0/1背包问题的动态规划算法。第四章：贪心算法理解贪心算法的概念。掌握贪心算法的基本要素。掌握背包问题、单源最短路径问题、最小花费生成树问题的算法，了解哈夫曼编码问题。第五章：回溯法掌握回溯法的算法框架。了解回溯法的解题过程。第六章：分支限界法掌握分支限界法的基本思想。掌握0/1背包问题、货郎担问题的算法。五、课程学时安排章节号教学内容学时数学生任务对应课程目标第一章算法概述21.完成第1章课后第1,3,6题；2.课后自学几个典型的NP完全问题。课程目标1,2第二章递归与分治策略181.完成第2章课后第2,3,8,13题；2.在二分搜索技术、合并排序、快速排序、线性时间选择教学内容后各安排2课时上机实践。课程目标1,2第三章动态规划81.完成第3章课后第4题及补充练习题；2.在0-1背包问题教学内容后安排2课时上机实践。课程目标1,2第四章贪心算法101.完成第4章课后第3题及补充练习题；2.在哈夫曼编码教学内容后安排2课时上机实践。课程目标1,2第五章回溯法41.完成第5章课外补充练习题；2.在0-1背包问题教学内容后安排2课时上机实践。课程目标1,2第六章分支限界法61.完成第6章课外补充练习题；2.在0-1背包问题教学内容后安排2课时上机实践。课程目标1,2六、实践环节及基本要求序号实验项目学时基本要求学生任务实验性质实验类别1二分搜索算法2掌握二分搜索算法编程在给定已排序数列中找特定元素,完成实验报告1验证性必做2合并排序2掌握合并排序与自然合并排序算法编程对给定数列进行排序，完成实验报告2验证性必做3快速排序2掌握快速排序的基本思想编程对给定数列进行排序，完成实验报告3验证性必做4选择问题2掌握选择算法的基本思想编程找出给定数列中第k小的元素，完成实验报告4验证性必做5动态规划法求解0/1背包问题2掌握动态规划的基本思想编程求解0-1背包问题，完成实验报告5验证性必做6哈夫曼编码2掌握贪婪法的基本思想编程对给定字符进行哈夫曼编码，完成实验报告6验证性必做7回溯法求解0/1背包问题2掌握回溯法的基本思想编程求解0-1背包问题，完成实验报告7验证性必做8分支限界法求解0/1背包问题2掌握分支限界法的基本思想编程求解0-1背包问题，完成实验报告8验证性必做注：1.实验性质指演示性、验证性、设计性、综合性等；2.实验类别指必做、选做等。七、考核方式及成绩评定考核内容考核方式评定标准（依据）占总成绩比例过程考核含到课率、上机实践、平时作业等平时记录、实验成绩30%期末考核闭卷试卷成绩70%考核类别考试成绩登记方式百分制八、推荐教材与主要参考书（一）推荐教材：（1）计算机算法设计与分析，王晓东，电子工业出版社，2012年2月，第4版。（2）算法设计与分析，郑宗汉，郑晓明，清华大学出版社，2017年10月，第3版。（二）主要参考书：（1）算法设计与分析基础，(美)AnanyLevitin著，清华大学出版社