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

《算法分析与设计》课程教学大纲一、课程概述课程名称算法分析与设计英文名称AlgorithmAnalysisandDesign课程性质数学与自然科学类课程代码22124005总学时48学时（理论32+实验16）学分2.5开课学期第五学期先修课程程序设计语言、数据结构适用专业计算机科学与技术开课单位计算机与电气工程学院二、课程简介《算法分析与设计》是计算机科学与技术专业的专业必修课程之一。系统学习计算机算法的有关概念和算法设计的基本技巧，培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本技巧和方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，解决一些较综合的问题，为学生进一步学习后续课程奠定良好的基础。本课程在程设计语言和数据结构等课程基础上，系统介绍算法概念、算法复杂度、常见的算法设计策略等知识。同时，课程设置16个学时的实验内容，针对具体问题实例，通过上机调试/测试，验证问题的正确性。利用高级程序设计语言把算法转化为程序，并进行数据测试和程序运行，使学生能够进一步掌握算法设计策略及计算复杂性基本理论，具备灵活运用所学知识解决实际问题的能力。基于课程特点和认知规律，以学生思想方法启迪和思维能力培养为着眼点，深度融合课程思政到教学中，将方法论和辩证思维融入算法的原理、技术和实现，引领知识传授、能力培养和价值塑造，提升课程的思想内涵和教学高度。三、课程目标课程目标1能根据计算机算法的基本原理和方法，研究常用的算法，并结合具体问题实例，培养对算法计算复杂性的正确分析能力，并学会运用算法基本原理和设计思想对实际问题进行建模和推导。（支撑毕业要求指标点1.3）课程目标3能运用所学算法设计思想针对实际问题进行基本数据结构和基本算法的综合设计、分析和编程，考虑规划中的安全问题及环境制约因素。（支撑毕业要求指标点3.2）课程目标4能结合文献资料，对计算机领域的热门话题和前沿知识有独特见解，利用互联网信息资源，获取更多新知识，设计并实现常见的智能算法。（支撑毕业要求指标点4.1）四、课程目标对毕业要求指标点的支撑表4-1课程目标对毕业要求指标点的支撑矩阵毕业要求毕业要求指标点课程目标1341工程知识1.3掌握问题抽象的基本方法，熟悉常见的数学模型，能将相关知识和数学模型方法用于专业问题的推导和分析。0.33设计/开发解决方案3.2能针对特定需求进行系统设计和模块设计，不断优化设计，并在设计中体现创新意识。0.24研究4.1能够通过文献研究和运用不断出现的新技术、新方法，解决计算机应用领域的复杂工程问题。0.3注：支撑矩阵的元素之和课程毕业要求矩阵的权值贡献保持一致。五、教学内容及实施手段表5-1教学内容与进度要求章节小节内容要求具体要求学生成果目标学时第1章算法引论1.1算法概述认知算法的定义、特性、描述方法会描述算法1、321.2算法复杂性分析分析使用大O记号、Ω记号、Θ记号估算算法的复杂度会估算算法复杂度第2章递归与分治策略2.1递归的概念理解满足递归的条件，递归调用工作栈过程会用递归方法解决实际问题1、3、422.2分治的基本思想分治算法的一般步骤以及复杂度计算会用高级语言描述分治算法，并计算时间和空间复杂度22.3分治策略设计范例分析二分搜索技术、合并排序、快速排序和线性时间选择等问题的分治策略设计方法及复杂度分析会用高级语言描述，并分析算法复杂度2第3章动态规划3.1动态规划的基本概念及算法框架理解动态规划算法概念，求解问题的两个重要性质及设计步骤会将问题转化为多个阶段图1、343.2动态规划算法应用运用最长公共子序列、0-1背包问题、最优二叉搜索树等问题的动态规划算法设计策略及复杂度分析会对具体问题写出正确的推导公式第4章贪心算法4.1贪心算法的基本概念及算法框架理解贪心算法的概念，设计的基本要素，贪心算法与动态规划算法的差异会识别问题的贪心性质1、3、424.2贪心算法设计范例分析活动安排问题、最优装载、哈夫曼编码、单源最短路径、最小生成树等问题的贪心算法设计策略及复杂度分析会设计出贪心策略4第5章回溯法5.1回溯法的基本概念及算法框架理解回溯法的深度优先搜索策略，回溯法解题的算法框架会利用回溯法的基本思想解决实际问题1、3、445.2回溯法设计范例分析常见回溯算法策略的设计方法及复杂度分析会设计出回溯策略，并分析算法效率和稳定性2第6章分支限界法6.1分支限界法基本概念及算法框架；理解分支限界法与回溯法的异同会利用分支限界法的基本思想解决问题1、3、446.2分支限界法范例运用常见分支限界法的设计方法会设计出分支限界法策略第7章算法优化策略7.1算法设计策略的比较与选择理解根据简单算法、分治算法、动态规划算法针对最大子段和问题进行比较与分析会分析不同算法之间的优缺点1、3、447.2问题的算法特征贪心策略及改进、算法三部曲、算法实现及复杂性会分析问题的算法特征表5-2实验/上机部分教学内容与进度要求序号实验/上机项目实验内容与方法实验类型学时必做/选做目标1递归算法设计用递归方法去设计，并分析算法时间复杂度验证性2必做1、3、42分治算法策略设计掌握分治法的基本思想，了解适用于分治法求解的问题类型，并分析算法的复杂度。验证性2必做1、3、43动态规划算法设计掌握动态规划的基本思想，学习动态规划递推方程，并能编写动态规划算法验证性2必做1、3、44贪心算法设计掌握贪心算法的概念，熟练贪心算法解决问题的基本步骤，并学会利用贪心算法解决实际问题。验证性2必做1、3、45回溯算法设计掌握回溯算法思想及递归原理，并利用回溯法解决实际问题。验证性2必做1、3、460-1背包问题对比分析理解贪心算法与动态规划算法针对同一个问题对比分析验证性2必做1、3、47TSP问题对比分析理解回溯法与动态规划算法针对同一个问题对比分析验证性2必做1、3、48单源最短路径问题对比分析理解分支限界法与贪心算法针对同一个问题对比分析验证性2必做1、3、4表5-3课程实施手段序号课程目标采用手段具体目标1课程目标1采用多媒体课件、电子教案、传统教学方法和线上教学辅助结合提高效率，增强教学的直观性和课堂教学的信息量2课程目标3以课堂教学为主，理论教学、案例教学、问题驱动与课后作业相结合强化学生工程观点的建立和工程分析能力的培养3课程目标4小组讨论采用启发式教学，通过学生协作、自主学习的答辩模式进行让学生自主分工、查阅资料、研究分析与制作汇报，培养学生提出问题、分析问题和解决问题的能力六、课程思政高等教育的立身之本在于立德树人，要坚持把立德树人作为中心环节，课程思政是新时代立德树人的一个立意高远的创新。课程思政逐渐成为教育界的理论和实践热点。2020年5月教育部印发了《高等教育课程思政建设指导纲要》，使课程思政建设成为一门课程的必要内容。任何教育都要回答三个问题：“为谁培养人”、“培养怎样的人”和“怎样培养人”。《算法分析与设计》积极主动呼应国家要求，从思政内容和思政案例进行具体规划设计，如表6-1和6-2。表6-1课程思政内容课程思政教学内容①诚信：认真付出，努力做事，坚持科学观和实事求是精神。②友善：保持平和、宽容的心去对人做事，团结协作，尊长爱幼。③爱岗：富有不断学习和探索进取的工作态度，热爱本专业。④敬业：做事可以吃苦耐劳，工作能够精益求精。⑤其它：科学发展观及积极向上的人生观。表6-2课程思政具体案例序号所属章节/案例名称案例教学目标思政元素1第2章递归与分治策略快速排序/奋斗青春通过案例引出排序算法和排序算法效率的重要性，激发学生的兴趣并应发大学积极思考，引导学生回顾“冒泡排序”的实现过程，快速排序是对冒泡排序的一种改进方法。敬业、进取：通过手机APP（学习强国、手机淘宝、美团外卖）中随处可见的排序功能，引出信息技术对人们学习、工作和生活的改变，进而提升学生对本专业的认可度和职业的认同感；结合快速排序创始人、图灵奖获得者托尼.霍尔教授在26岁提出快速算法的故事，以此展开理想信念教育，诠释奋斗的青春最美丽，激励同学们认真学习，为美好明天而奋斗。2第3章动态规划最长公共子序列/风雨同舟，共克时艰通过新型冠状病毒与蝙蝠冠状病毒的基因组序列对比，引出“最长公共子序列”问题。爱国、敬业：结合我国对2019-nCoV的治疗和防控，向所有抗疫英雄们致敬，融入爱国主义教育；2019-nCoV与RaTG13的基因序列对比，指导研制检测试剂、疫苗和治疗药物，科学家们共克难题，融入职业理想教育和社会责任教育；DNA序列比对引出教学内容“最长公共子序列”问题。3第4章贪心算法最短路径/智慧交通在熟悉路径规划算法的基础上，会考虑到基于环境友好的路径规划问题，即Eco-Routing问题，行程分享等功能涉及到隐私保护问题。培养学生考虑环境与法律因素：讲解路径规划的相关内容时，以滴滴快车等为例讲解互联网企业在业务与程序开发时需关注的环境、法律等问题。七、考核及成绩评定（1）考核方法本课程考核采用如下方式，即：总成绩=课堂参与*10%+课后作业*10%+小组研讨*10%+实验考评*10%+期末考试*60%，其中，除期末考试之外的部分统称为平时成绩。考核方式及权重占比如表7-1所示。表7-1各考核方式及权重占比分配表课程目标考核方式及成绩占比（%）课程目标成绩占比（%）课堂参与（10%）课后作业（10%）小组研讨（10%）实验考评（10%）期末考试（60%）课程目标144333042课程目标344332032课程目标422441026考核方式成绩比例合计（%）1010101060100（2）考核内容及评价标准①期末考试：占总成绩的60%。闭卷考试，考试时间120分钟，成绩采用百分制，卷面成绩总分100分，考试范围包括所有课程目标。具体考试时间安排在期末考试周由教务处统一通知。②课堂参与：占总成绩的10%。同时结合随机点名考勤和互动，每缺一次扣5%，扣完10%为止，无故缺勤3次以上者取消本门课程的考核资格，评分标准如表7-2所示。表7-2部分课堂参与评价标准目标考核内容优秀（90-100分）良好（80-89分）中等（70-79分）及格（60-69分）不及格（0-59分以下）1、3、4课堂测试1：判断课件中某个算法的正确性完全判断正确，并能说明正确或错误原因80%以上判断正确，并说明正确或错误原因，书写比较清晰、规范70%以上判断正确，并能说明正确或者错误原因，书写基本清晰、规范60%以上的判断正确，并能说明正确或者错误原因，书写不够清晰、规范未能通过测试课堂测试2：利用分治策略和动态规划算法设计一个“芯片测试”方案和RNA二级结构预测能用分治策略和动态规划算法思想设计方案，方案设计完全合理，算法描述表达清楚。能用分治策略和动态规划算法思想设计方案，方案设计比较合理，算法描述表达比较清楚。能用分治策略和动态规划算法思想设计方案，方案设计基本合理，算法描述表达基本清楚。能用分治策略和动态规划算法思想设计方案，方案设计不够合理，算法描述表达不够清楚。未能通过测试课堂测试3：利用算法设计、分析和实现马的遍历问题能用算法设计、分析和实现马的遍历问题，方案合理并考虑一些影响因数，实现较优。能用算法设计、分析和实现马的遍历问题，方案比较合理并考虑一些影响因数，实现较好。能用算法设计、分析和实现马的遍历问题，方案基本合理并考虑一些影响因数，算法基本实现。能用算法设计、分析和实现马的遍历问题，方案基本合理但欠考虑一些影响因数，算法实现部分。未能通过测试课堂测试4：利用分支限界等设计并实现一种常见智能算法能完全正确描述该智能算法思想，能用高级语言实现该算法能较好描述该智能算法思想，能用高级语言实现较好该算法能基本正确描述该智能算法思想，能用高级语言实现该算法能基本正确描述该智能算法思想，但不能用高级语言实现该算法未能通过测试③课后作业：占总成绩的10%。本门课程每章均布置作业，布置次数不低于5次，每次作业的占比均分，根据学生作业是否按时上交、是否独立完成以及作业完成准确性与可读性评分，评分标准如表7-3所示。表7-3课后作业评价标准考核内容优秀（90-100分）良好（80-89分）中等（70-79分）及格（60-69分）不及格（60分以下）作业按时足量提交，90%以上的概念与计算正确，方案合理，书写清晰、规范按时足量提交，80%以上的概念与计算正确，方案较合理，书写比较清晰、规范缺量提交，70%以上的概念与计算正确，方案基本合理，书写基本清晰、规范补交，60%以上的概念与计算正确，方案不够合理，书写不够清晰、规范不交作业④小组研讨：占总成绩的10%。根据学生课堂回答问题和小组讨论课上表现评分，每次课堂通过小型答辩完成；汇报小组按照学号轮流方式进行，采用组内推荐方式确定具体汇报人。评分按查阅文献情况、团队协作、素材准备、问题分析、现场叙述交流和回答问题情况等进行评价。小组讨论主题由任课老师根据教学内容针对每章拟定，评价方式如表7-4所示。表7-4小组讨论评价方式表考核内容比例优良中差素材准备15%12-159-116-80-5团队协作15%12-159-116-80-5问题分析25%21-2514-208-130-7报告交流25%21-2514-208-130-7问题回答20%16-2011-156-100-5⑤实验成绩：占总成绩的10%。分为八个实验，针对目标1、3、4进行考核，每个实验100分，计算平均值，评价方式如表7-5所示。表7-5实验成绩评定标准课程目标考核内容优秀良好中等及格不及格1、3、4实验一递归算法设计实验二分治策略算法设计设计方案通过并实现，能解决实验过程中出现的问题；能够独立完成报告的撰写，内容全面；能够详细记录实验过程，对实验数据进行正确分析、讨论，并能得到有效结论。设计方案通过并实现，并能解决实验过程中出现的部分问题；能够独立完成报告的撰写，内容比较全面；实验过程记录比较详细，分析、讨论比较得当，并能得到有效结论。在同学、老师的帮助下设计方案通过并实现；能够独立完成报告的撰写，内容基本全面；实验过程记录基本详细，分析、讨论基本得当，能够得到部分有效结论。在同学、老师的帮助下程序部分设计方案通过并实现；能够独立完成报告的撰写，内容不够全面；实验过程记录不够详细，分析、讨论不够得当，实验结论不够合理。未做实验或未交实验报告实验三动态规划算法设计实验四贪心算法设计实验五回溯法算法设计实验六利用贪心算法与动态规划算法针对0-1背包问题及背包问题进行对比分析实验七利用回溯法与动态规划算法针对TSP问题进行对比分析实验八利用分支限界法与贪心算法针对单源最短路径问题进行对比分析⑥按照工程教育认证标准和学校人才培养要求，考核以学生能力是否有效达成为基准。为保障学生课程培养能力的达成，规定期末考试卷面成绩低于45分（不含45分）总评成绩一律为不及格。⑦考核周期为一个学年。为使评价结果尽快反馈给各个教学环节，促使各个教学环节