《算法设计与分析》教学大纲（本科）.docx
算法设计与分析教学大纲课程英文名Algorithm Design and Analysis课程代码J0701Z35学分3总学时48理论学时32实验/实践学时 16课程类别专业课课程性质任选先修课程数据结构C+程序设计适用专业信息与计算科学开课学院理学院执笔人审定人制定时间2018年5月注：课程类别是指公共基础课/学科基础课/专业课；课程性质是指必修/限选/任选。一、课程地位与课程目标（-）课程地位本课程是信息与计算科学的专业选修课。计算机科学是一种创造性思维活动，其教育必须面 向设计。算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。设计一个 高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学 领域里数据结构与算法设计所研究的主要内容。（二）课程目标1.使学生掌握分治法、贪心法、动态规划、回溯法、分支限界法等常用的算法设计技术，掌 握算法分析的初步能力；2,使学生掌握解决实际问题的算法设计方法，加深对数学在实际中广泛应用的理解，进一步 激发学生学习数学的兴趣。二、课程目标达成的途径与方法对课程目标1,以课堂教学为主，结合课堂讨论、课外作业、课后答疑等方法达成。对课程目标2,以上机实践为主，结合小组讨论、实验报告、课外辅导等方法达成。三、课程目标与相关毕业要求的对应关系课程目标课程目标对毕业要求的支撑程度（H、M、L）毕业要求2毕业要求3毕业要求5课程目标1HMH课程目标2HHH注：1.支撑强度分别填写H、M或L （其中H表示支撑程度高、M为中等、L为低）。四、课程主要内容与基本要求第一章：算法概述理解算法的定义，理解程序与算法的区别与内在联系。掌握算法复杂性的渐近性态的数学表 述。掌握用计算机语言描述算法的方法。第二章：递归与分治策略掌握递归的概念、掌握分治法的基本思想。并能运用递归、分治法设计二叉检索算法、合并 排序、快速排序等算法。第三章：动态规划理解动态规划算法的概念。掌握动态规划算法的基本要素与设计动态规划算法的步骤。掌握 最长公共子序列问题与0/1背包问题的动态规划算法。第四章：贪心算法理解贪心算法的概念。掌握贪心算法的基本要素。掌握背包问题、单源最短路径问题、最小 花费生成树问题的算法，了解哈夫曼编码问题。第五章：回溯法掌握回溯法的算法框架。了解回溯法的解题过程。第六章：分支限界法掌握分支限界法的基本思想。掌握0/1背包问题、货郎担问题的算法。五、课程学时安排章节号教学内容学时数学生任务对应课程目 标给*第一早算法概述2L完成第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第五章回溯法4L完成第5章课外补充练习题；2.在0T背包问题教学内容后安省F 2课时 上机实践。课程目标 1,2第八早分支限界法6L完成第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）算法设计与分析，郑宗汉，郑晓明，清华大学出版社，2022年10月，第3版。（二）主要参考书：（1）算法设计与分析基础，（美）Anany Levitin著，清华大学出版社，2015年1月，第3 版。（2）计算机算法基础，沈孝钧，机械工业出版社，2014年1月，第1版。（3）算法设计技巧与分析，M. H. Alsuwaiyel著，吴伟昶等译，电子工业出版社，2016年8 月，第1版。
