算法设计与分析 教学大纲

ADDINCNKISM.UserStyle课程编码课程类别专业必修课课程名称算法设计与分析英文名称AlgorithmDesignandAnalysis学分3建议修读学期4总学时数48讲授学时32实验学时16实践实训学时网络学时先修课程C语言程序设计、数据结构考核方式考试适用专业计算机科学与技术、软件工程大纲执笔人大纲审核人一、课程目标《算法分析与设计》课程是计算机科学与技术专业的核心学位课程，同时也是软件工程专业的专业必修课。课程内容覆盖计算模型、分治法、动态规划、贪心算法、回溯法和分支限界等。通过本课程的学习，达成以下课程目标：1．知识目标：掌握算法基本概念，深入理解复杂度分析，熟悉多种递归与分治、动态规划、贪心算法、回溯法、分支限界法等算法设计方法；（支撑毕业要求1）2．能力目标：能针对特定问题选择算法策略，构建算法框架并实现，具备性能分析与优化能力；（支撑毕业要求2、3）3．职业素养：具备职业素养和团队协作意识，具有设计、编写、优化算法的能力。（支撑毕业要求8、9）毕业要求工程知识问题分析设计与解决方案研究使用现代工具工程与社会环境与可持续发展职业规范个人和团队沟通项目管理终身学习课程关联度MHHLL二、课程目标与毕业要求的对应关系毕业要求指标点课程目标毕业要求1指标1-3 能够运用专业知识对工程问题建立数学模型并解决计算问题；课程目标1毕业要求2指标2-2 能够基于相关科学原理和数学模型方法正确表达复杂软件工程问题；课程目标2毕业要求3指标3-2 能够针对特定需求，完成软件算法流程、单元模块（组件、部件）的设计、开发和测试，并能在设计、开发和测试等全周期中体现工程思维；课程目标2毕业要求8指标8-3 理解工程师对公众的安全、健康和福祉，以及环境保护的社会责任，能够在工程实践中自觉履行责任。课程目标3毕业要求9指标9-3 能够了解团队成员想法，具备在多学科背景下的团队中的协调、协作、组织和管理能力，并能够在项目实施过程中运用以上能力；课程目标3三、教学内容和重难点第一章算法分析基础（支撑课程目标1、3）（一）教学要求理解算法的概念掌握算法在最佳、最差和平均情况下的复杂度分析掌握算法复杂度渐进性态的数学表达式（二）教学内容1.1算法与程序1.2算法复杂度分析概念1.3算法复杂度的渐进性态1.4O,Ω,θ1.5数学基础1.6非递归算法的算法复杂度分析（三）本章重难点教学重点：算法的定义和复杂度教学难点：复杂度的计算第二章分治法（支撑课程目标1、2、3）（一）教学要求理解递归的概念掌握设计有效算法的分治策略通过范例学习分治策略设计技巧（二）教学内容2.1递归的概念2.2分治法的基本思想2.3分治法的应用2.3.1一维数组的二分查找2.3.2二维数组查找2.3.3合并排序2.3.4逆序对2.3.5快速排序2.3.6K选择问题2.3.7棋盘覆盖2.3.8快速幂2.3.9大整数乘法和Strassen矩阵乘法2.3.10快速傅里叶变换2.4小结（三）本章重难点教学重点：分治法的思想，适用条件，复杂度计算教学难点：分治法的基本思想和复杂度计算第三章贪心算法（支撑课程目标1、2、3）（一）教学要求理解贪心算法的概念掌握贪心算法的基本要素理解贪心算法与动态规划算法的差异通过范例学习贪心算法设计策略（二）教学内容3.1贪心算法的思想3.2贪心算法的要素3.3贪心选择问题3.4任务调度问题3.5最小生成树3.6单源最短路径3.7哈夫曼编码3.8小结（三）本章重难点教学重点：贪心算法的基本要素和思想教学难点：贪心算法和动态规划的区别第四章回溯法（支撑课程目标1、2、3）（一）教学要求理解回溯法的深度优先策略掌握回溯法的算法框架通过范例学习回溯法设计策略（二）教学内容4.1回溯法的思想4.2排列问题4.3组合问题4.4N-皇后问题4.50-1背包问题4.6物流派送问题4.7小结（三）本章重难点教学重点：回溯法的深度优先搜索策略和框架教学难点：回溯的剪枝和限制函数第五章分支限界法（支撑课程目标1、2、3）（一）教学要求理解分支限界的剪枝策略掌握分支限界的算法框架通过范例学习分支限界算法设计策略（二）教学内容5.1分支限界的思想5.2最小出边界限法5.3未访问城市最小出边之和界限法5.4广度优先搜索的未访问城市最小出边之和限界法5.50-1背包问题5.6小结（三）本章重难点教学重点：分支限界法的剪枝搜索策略，分支限界法的算法框架教学难点：分支限界法的剪枝搜索策略第六章动态规划（支撑课程目标1、2、3）（一）教学要求理解动态规划算法的概念掌握动态规划的基本要素掌握设计动态规划算法的步骤通过范例学习动态规划算法设计策略（二）教学内容6.1动态规划的思想6.2线性动态规划6.3背包类问题6.4记忆化搜索与区间动态规划6.5小结（三）本章重难点教学重点：动态规划的思想及求解步骤教学难点：动态规划思想第七章智能算法（支撑课程目标1、3）（一）教学要求理解智能算法分类掌握粒子群算法的设计思想掌握模拟退火的设计思想掌握禁忌搜索的设计思想（二）教学内容7.1智能算法分类7.2粒子群算法7.3模拟退火算法7.4禁忌搜索（三）本章重难点教学重点：智能算法的思想教学难点：智能算法的实现策略四、课时安排和教学方法（一）教学方法整个教学过程要努力做到将理论知识与实践的紧密结合，阐述基本原理，培养学生问题分析能力。首先，课堂讲授注意采用启发式教学，激励学生思考，并积极参与讨论；通过案例分析，强化学生算法分析方法的应用、思维方法的建立；以课堂讲为主，并以实验课、课外作业、生产实习等教学环节作为课程学习的补充，理论教学与实验训练结合，强化算法设计与分析能力的培养。其次，加强计算机辅助教学，增加SPOC教学环节，并通过课堂互动、分组讨论等多种形式，训练学生分析、综合、小结、归纳的能力，从而巩固学生对所学知识的掌握程度，为后续课程的学习以及自主学习能力的培养打好基础。最后，本门课程是在“新工科”背景下开设的课程，既讲授了算法的基础知识，也要紧跟社会需求培养学生的算法设计能力、分析能力和创新能力。此外，教师课堂教学上要有意识培养学生正确的人生观、世界观，使其具有良好的社会责任感，遵守职业道德。（二）课程思政切入点设计共16个教学周每周1次课每次课2学时教学周次课时安排教学进度（章节讲/知识单元）课程思政点融入方式与教学方法预期教学成效11算法基础概述精益求精工程伦理介绍抖音推荐算法案，算法的美与恶，讨论法培养学生的工匠精神和工程伦理观2-42分治法爱国情怀高效新冠病毒检测试题，案例法培养学生的爱国情怀5-71贪心算法科技自豪感、精益求精最优装载，案例法培养学生的工匠精神和科技自豪感8-101回溯法爱国情怀、精益求精深度搜索，案例法培养学生的爱国敬业和工匠精神11-121分支限界爱国情怀、精益求精广度搜索，案例法培养学生的爱国敬业和工匠精神13-152动态规划科技自豪感、精益求精讨论法培养学生的工匠精神和科技自豪感16-171智能算法精益求精案例法培养学生的工匠精神和科技自豪感（三）课时安排：章节讲课实验第1章算法基础2学时第2章分治法6学时3学时第3章贪心算法4学时2学时第4章回溯法6学时3学时第5章分支限界4学时2学时第6章动态规划6学时4学时第7章智能算法4学时2学时合计32学时16学时五、实践教学安排本门课程是理论和实践相结合的课程，其中实验是很重要的一个教学环节，通过实验可以给学生多一些实操的机会，并有助于在实验中理解并掌握课堂中的基础知识和基本原理。序号实验项目实验类型实验要求1算法基础验证性实验验证最大元素问题的问题规模与运行时间的线性关系；2分治法设计性实验用分治法实现快速排序等问题，分析其算法复杂度；3贪心算法实验设计性实验用贪心算法求解背包等问题，分析其算法复杂度；4回溯法实验设计性实验用回溯法求解旅行商等问题，分析其算法复杂度；5分支限界实验设计性实验用分支限界求解旅行商等问题，分析其算法复杂度；6动态规划实验1设计性实验用动态规划求解线性规划等问题，分析其算法复杂度；7动态规划实验2设计性实验用动态规划求解背包类等问题，分析其算法复杂度；8智能算法实验设计性实验用智能算法求解优化问题，分析其算法复杂度；六、课程教学评价本课程平时成绩占30%，期末成绩70%（视平时开展辅助教学活动而定），平时成绩考核的形式主要有：作业、实验报告、分组任务、课堂互动及章节测验等；期末成绩考核的形式是闭卷考试为主。课程教学目标考核内容评价依据课程目标11.理解算法基本概念，掌握算法时间和空间复杂度分析的基本方法；2.计算算法的时间复杂度和空间复杂度，衡量算法的性能；3．熟悉分治法、贪心法、动态规划、回溯法、分支限界和智能算法等理论知识；章节测试、平时作业、期末考试。课程目标21.运用分治法、贪心法、动态规划、回溯法、分支限界和智能算法求解复杂问题；2.运用更优化算法来求解复杂问题；平时作业、章节测试、实验成绩、期末考试。课程目标31.设计算法的能力；2.编写代码的能力；3.优化算法的能力；4.团队协作能力；分组任务、实验成绩、期末考试。七、成绩评定方法（一）成绩评定依据平时成绩：30%，期末笔试：70%平时成绩占分比例%期末笔试占分比例%课程目标14040课程目标24040课程目标32020（二）课程目标达成度评价课程目标平时成绩目标总分期末笔试目标总分目标总分目标达成期望值课程目标14040400.65课程目标24040400.65课程目标32020200.7八、课程学习资源1.选用教材教材名称（第几版）编者出版社出版时间是否马工程教材列入何规划算法设计与分析田小霞清华大学出版社2024.8否国家级实验教学示范中心计算机学科组2.主要参考书目[1]王晓东,计算机算法设计与分析（第五版）.2018.8，电子工业出版社.3.其它学习资源[1]超星学习通SPOC教学平台;[2]力扣(LeetCode)在线题库,/5;[3]ACWing在线题库，/problem/;[4]洛谷在线题库，.九、课程学习建议1、先修课程：程序设计语言和数据结构；2、做好平时预习复习，要求学生从大一开始按照软件开发流程，可以考虑从蓝桥杯和ACM竞赛入手，逐步培养学生的算法设计与分析学习兴趣；3、注重实验与考核相结合，鼓励学生进行算法竞赛；4、建议在教学过程中，将算法设计与分析的基础知识与实际教学紧密结合，鼓励学生积极参与算法竞赛。对于积极参与并表现优异的学生，建议在平时成绩或总评成绩中给予适当加分，直至在期末考试及格的前提下，按优秀等级记分。（具体由任课老师按照校、院等相关文件确定并报批）。十、评分标准课程目标评分标准90-10080-8970-7960-690-59优良中及格不及格课程目标1熟悉并掌握算法的基础知识，对算法复杂度的基本概念有系统的认知；熟悉算法复杂度的分析过程。掌握算法的基础知识，对算法复杂度的基本概念有较为系统的认知；掌握算法复杂度的分析过程。基本上理解算法的基础知识，对算法复杂度的基本概念有一定的认知；基本上能理解算法复杂度的分析过程。部分理解和掌握算法的基础知识，对算法复杂度的基本概念有零星的认知；了解算法复杂度的分析过程。对算法的基础知识大部分不掌握，不了解算法复杂度的基本概念；不了解算法复杂度的分析过程。课程目标2熟悉并掌握分治法、贪心法、动态规划、回溯法、分支限界和智能算法等理论知识；能够较灵活地应用算法设计策略，具有较强的解决实际问题的能力。掌握分治法、贪心法、动态规划、回溯法、分支限界和智能算法等理论知识；能够较好地使用适合的算法策略，具有一定的解决实际问题的能力。理解分治法、贪心法、动态规划、回溯法、分支限界和智能算法等理论知识；可以比较好地运用算法设计