算法设计与分析 教案全套 田小霞

PAGE4PAGE5教师姓名：***职称：TIME\@"yyyy/M/d"2024/8/5教案学年第学期教师所在单位课程名称算法设计与分析专业、年级、班级主讲教师教案编写说明教案又称课时授课计划，是任课教师的教学实施方案。任课教师应根据专业的培养方案，紧扣教学大纲，认真分析教学内容，切合学生实际，提前编写设计好每门课程每个章、节或主题的全部教学活动。教案编写说明如下：1、编号：按施教的顺序标明序号（每次课一个序号）。2、教学时数：是指每次课的教学时数。3、教学课型表示所授课程的类型，请在理论课、实验课、习题课、实践课及其它栏内选择打“√”。4、教学内容：标明章、节或主题。5、教学目的要求。6、教学重点、难点。7、教学方式和手段。8、教学过程（含复习旧课、引入新课、组织教学、启发思维等）。将授课的内容按逻辑层次，有序设计编排。本部分不同专业的授课可有自己的特色。9、讨论、思考题和作业。10、参考资料：列出参考书籍、有关资料。11、日期的填写系指本次课授课的时间。授课教案应根据专业技术领域发展、教学要求变化、学生实际水平，以及教师以往教学的课后小结、批注等进行补充、修改或重写，以保持教学内容的先进性和适用性。请妥善保存各阶段的教案，并配合好学院的教学检查和归档等工作。

编号：1课时安排：2学时教学课型：理论课实验课习题课□实践课□其它□教学内容（教学章、节或主题）：第一章算法基础教学目的要求（分知识、能力和素质三维目标）：知识：理解算法的概念、特性；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念；能力：掌握算法复杂性的渐近性态的数学表述和算法复杂度计算；素养：培养学生的家国情怀和团队协作。教学重点、难点：重点：算法的概念、算法的时间复杂性、算法复杂性的渐近性态的数学表述以及递归的概念。通过讲解、举例方法、课堂练习。难点：算法复杂性与求算法复杂度通过讲解、举例、提问与引导方法。课程思政元素：爱岗敬业、家国情怀，如Tiktok推荐算法和大数据杀熟。教学方式和手段：教学方式：讲授、讨论、案例分析等；教学手段：学习通的抢答，分组任务、主题讨论等；拟定的教学方法和手段要能有效地调动学生的学习积极性，促进学生的积极思考，激发学生的潜能教学过程：提问算法是什么，算法具有什么特性，如何定义算法？主题讨论算法之美和之恶。讲授算法的复杂性，主要包括时间复杂性与空间复杂性。讲授最坏情况、最好情况与平均情况的时间复杂性。讲授算法复杂性在渐近意义下、、，并通过具体例子说明。讲授递归和非递归算法复杂度分析方法。讨论、思考题、作业：1.主题讨论算法之美和之恶。2.分组任务推荐算法讲解报告；3.作业。实验报告：排序问题的程序运行时长与问题规模大小关系。参考资料：竞赛网站：1.PTA辅助实践平台；2.韩师OJ平台。编号：2课时安排：6学时教学课型：理论课实验课习题课□实践课□其它□教学内容（教学章、节或主题）：第二章递归和分治法教学目的要求（分知识、能力和素质三维目标）：知识：理解递归、分治的设计思想和适用条件；理解分治法的算法复杂度分析；能力：运用分治法策略和计算分治法的算法复杂度；素养：培养学生的科学思维，激发创新能力。教学重点、难点：重点：分治的设计思想；分治法的适用条件。通过讲解、举例方法、课堂练习。难点：分治法的算法复杂度分析。通过讲解、举例、主题讨论、随堂练习、问卷调查。课程思政元素：自强不息、积极探索、科学思维。教学方式和手段：教学方式：讲授、讨论、案例分析等；教学手段：学习通的抢答，分组任务、主题讨论等；拟定的教学方法和手段要能有效地调动学生的学习积极性，促进学生的积极思考，激发学生的潜能教学过程：通过课堂甜点的趣味问题(拿牌)，引导学生如何求解问题。通过课堂甜点（找假币）引入分治法，讲解分治法算法的策略思想和适用条件。讲解实例及练习，视频实列有：二分搜索、合并排序、快速排序、棋盘覆盖、逆序对、快速幂。讲解主递推公式。讨论、思考题、作业：1.逆序对在图像处理中的应用。2.快速排序复杂度的计算；3.作业。实验报告：二维数组中查找特定元素，迷宫招驸马。参考资料：竞赛网站：1.PTA辅助实践平台；2.韩师OJ平台。此部分内容基础知识可参考同济大学《高等代数》。

编号：3课时安排：4学时教学课型：理论课实验课习题课□实践课□其它□教学内容（教学章、节或主题）：第四章贪心算法教学目的要求（分知识、能力和素质三维目标）：知识和能力：理解贪心算法的设计思想和特性；理解贪心算法最优选择和最优子结构性；掌握贪心算法的一般步骤；预期达到的效果：能够通过编写代码运用贪心算法解决特定问题；教学重点、难点：重点：贪心算法的概念；贪心算法的基本要素。通过讲解、举例方法、课堂练习。难点：理解贪心算法与动态规划算法的差异通过讲解、举例、主题讨论、随堂练习。课程思政元素：科学思维、实事求是。教学方式和手段：教学方式：讲授、讨论、案例分析等；教学手段：学习通的抢答，分组任务、主题讨论等；拟定的教学方法和手段要能有效地调动学生的学习积极性，促进学生的积极思考，激发学生的潜能教学过程：1.通过课堂趣味问题(硬币兑换)，引导学生理解求解目标，鼓励学生利用贪心探索求解。2.讲解贪心算法的策略思想和基本要素。3.通过0/1背包理解动态规划与贪心算法区别与联系。4.讲解实例及练习，实例有活动安排问题、最优装载问题、哈夫曼编码、单源最短路径、最小生成树，其中视频有：韩山师范学院公开课（贪心算法）和最小生成树。讨论、思考题、作业：1.主题讨论人生的奋斗目标。2.分组任务讲解竞赛题目；3.作业。参考资料：竞赛网站：1.PTA辅助实践平台；2.韩师OJ平台。此部分内容基础知识可参考《数据结构》。后记：教学过程应提供更多展示视频。编号：4课时安排：6学时教学课型：理论课实验课习题课□实践课□其它□教学内容（教学章、节或主题）：第五章回溯法教学目的要求（分知识、能力和素质三维目标）：知识：理解回溯法的深度优先搜索策略；理解算法的剪枝函数；能力：掌握用回溯法解题的算法框架；素养：培养学生的家国情怀和团队协作。教学重点、难点：重点：回溯法的深度优先搜索策略和框架；子集树和排列树。通过讲解、举例方法、课堂练习。难点：回溯的剪枝和限制函数。通过讲解、举例、主题讨论。课程思政元素：崇尚科学、探索精神、勇于创新。教学方式和手段：教学方式：讲授、讨论、案例分析等；教学手段：学习通的抢答，分组任务、主题讨论等；拟定的教学方法和手段要能有效地调动学生的学习积极性，促进学生的积极思考，激发学生的潜能教学过程：1.通过趣味问题(0-1背包和TSP背包)，引导学生理解子集树和排列树，鼓励学生利用深度优先探索求解，讲解剪枝函数、回溯法解题步骤。2.讲解回溯法的策略思想。讲解在解空间树中如何最快寻找最优解。3.讲解实例及练习，实例有0-1背包、最优装载问题、TSP、连续邮资，其中视频有：回溯法的策略思想和N皇后。讨论、思考题、作业：1.主题讨论万能神奇-暴力求解。2.作业。实验报告：乡村旅游规划问题和0-1背包问题。参考资料：竞赛网站：1.PTA辅助实践平台；2.韩师OJ平台。编号：5课时安排：4学时教学课型：理论课实验课习题课□实践课□其它□教学内容（教学章、节或主题）：第六章分支限界教学目的要求（分知识、能力和素质三维目标）：知识：理解分支限界的宽度优先搜索策略；理解算法的限界函数；掌握用分支限界解题的算法框架。

能力：运用分支限界解题的算法框架求解问题；素养：培养学生的家国情怀和团队协作。教学重点、难点：重点：分支限界的算法策略；分支限界算法的宽度优先和限界函数；FIFO队列和优先级队列。难点：分支限界法的剪枝搜索策略。通过讲解、举例、主题讨论。课程思政元素：集思广益、择优执行。教学方式和手段：教学方式：讲授、讨论、案例分析等；教学手段：学习通的抢答，分组任务、主题讨论等；拟定的教学方法和手段要能有效地调动学生的学习积极性，促进学生的积极思考，激发学生的潜能教学过程：1.通过趣味问题(0-1背包)，引导学生理解FIFO（先进先出）队列和活节点扩展方式，鼓励学生利用广度优先探索求解，讲解限界函数和FIFO解题步骤。2.通过问题(TSP)，引导学生理解优先级队列和活节点扩展方式，鼓励学生利用广度优先探索求解，讲解限界函数和优先级队列的解题步骤。3.讲解分支限界的策略思想。讲解在解空间树中如何最快寻找最优解。4.讲解实例及练习，实例有0-1背包、最优装载问题、TSP、单源最短路径，其中视频有：分支限界算法的课堂实录。讨论、思考题、作业：1.分组任务录制赛题求解过程；2.作业。实验报告：中国旅行商问题或者物流路径选择。参考资料：竞赛网站：1.PTA辅助实践平台；2.韩师OJ平台。编号：6课时安排：6学时教学课型：理论课实验课习题课□实践课□其它□教学内容（教学章、节或主题）：第三章动态规划教学目的要求（分知识、能力和素质三维目标）：知识：理解动态规划的设计思想和特性；理解动态规划子问题重叠性和最优性；能力：掌握动态规划求解步骤；素养：培养学生的科学思维和精益求精，激发创新能力。教学重点、难点：重点：动态规划基本概念；动态规划问题的特征。通过讲解、举例方法、课堂练习。难点：动态规划的基本步骤。通过讲解、举例、主题讨论、随堂练习。课程思政元素：-创新性思维，鼓励学生探索求解，从底向上解决大问题。教学方式和手段：教学方式：讲授、讨论、案例分析等；教学手段：学习通的抢答，分组任务、主题讨论等；拟定的教学方法和手段要能有效地调动学生的学习积极性，促进学生的积极思考，激发学生的潜能教学过程：通过走向升旗台问题，引导学生理解大问题分割子问题和子问题不独立，鼓励学生探索求解；通过数塔引入动态规划法，讲解动态规划的算法策略思想和适用条件；通过0-1背包加深对动态规划算法的理解；讲解实例及练习，实例有石子合并、最长公共子序列、背包问题(KnapsackProblem)、其中视频实列有：最长公共子序列和割绳子（算法工程师面试题）。讨论、思考题、作业：1.动态规划与分治法的差异。3.作业。实验报告：背包问题，石子合并。参考资料：竞赛网站：1.PTA辅助实践平台；2.韩师OJ平台。编号：7课时安排：4学时教学课型：理论课实验课习题课□实践课□其它□教学内容（教学章、节或主题）：第七章智能算法教学目的要求（分知识、能力和素质三维目标）：知识和能力：理解粒子群算法、模拟退火算法和禁忌搜索算法的设计思想和特性；理解智能算法的调优方式；掌握粒子群算法、模拟退火算法和禁忌搜索算法的一般设计步骤。预期达到的效果：能够对特定的问题编写粒子群算法、模拟退火算法和禁忌搜索算法的代码。教学重点、难点：粒子群算法、模拟退火算法和禁忌搜索算法的基本原理；粒子群算法、模拟退火算法和禁忌搜索算法的参数设置。课程思政元素：探索未知、自我突破。教学方式和手段：教学方式：讲授、讨论、案例分析等；教学手段：多媒体教学设备，学习软件如超星学习通，学习通的抢答，分组任务、主题讨论等；拟定的教学方法和手段