算法设计与分析 教学大纲（含课程思政）、实验教学大纲.docx

《算法设计与分析 教学大纲（含课程思政）、实验教学大纲.docx》由会员分享，可在线阅读，更多相关《算法设计与分析 教学大纲（含课程思政）、实验教学大纲.docx（11页珍藏版）》请在第一文库网上搜索。

1、算法设计与分析课程教学大纲（含课程思政）课程代码：*课程负责人：*课程中文名称：算法设计与分析课程英文名称：DesignandAna1ysisofA1gorithms课程类别：必修课程学分数：2.5课程学时数：44/32授课对象：计算机科学与技术及相关专业本科本课程的前导课程：C/C+程序设计、离散数学、数据结构一、教学目的（黑体五号）本课程是计算机科学与技术专业的专业必修课。课程目标如下：1 .掌握计算机算法的基本概念和特性，了解计算机相关学科中算法分析与设计技巧的重要性，掌握算法时间复杂性的分析方法。2 .掌握基本的算法设计策略，结合具体问题实例学习，重点掌握分治法、贪心法、动态规划法、回

2、溯法、分支限界法等常见的算法设计策略。3 .通过理论学习和上机实践的训练，具备灵活运用所学解决实际应用问题的能力。二、教学要求（黑体五号）通过课堂讲授、课堂练习和讨论互动、课后作业和上机实验等教学手段，系统掌握计算机算法的有关概念和算法设计的基本策略。使学生掌握计算机算法的基本概念和特性，了解计算机相关学科中算法设计技术的重要性，掌握算法复杂性的分析方法。结合典型示例和实战问题求解过程，使学生重点掌握穷举法、归纳法、迭代法和递归法等基本算法设计方法以及分治法、蛮力法、回溯法、分支限界法、贪心法和动态规划法等算法设计策略，了解计算复杂性基本理论，具备灵活运用所学解决复杂工程应用问题的能力。三、课

3、程内容与学时分配（黑体五号）主要内容：1 .概论：算法的概念和算法分析方法。教学重点：算法时空分析方法。教学难点：算法时间复杂度渐进符号0、C和0。课程思政：好算法的时空平衡O辩证唯物论，引导学生建立客观、理性的辩证思维，树立正确的人生观，善于从政治上看问题，在大是大非面前保持政治清醒2019年3月习近平总书记主持召开学校思想政治理论课教师座谈会明确要求2 .常用数据结构及其应用：线性表、字符串、栈、队列、双端队列、二叉树、优先队列、树和并查集、图、二叉排序树、平衡二叉树和哈希表，设计好的数据结构。教学重点：各种ST1容器的应用和设计好的数据结构。教学难点：如何利用各种ST1容器设计求解相关问

4、题的算法设计，如何利用数据结构容器高效地设计求解相关问题的算法。课程思政：数据结构是算法的基本构件，只有选择好的数据结构才能设计出求解问题的好算法O社会是一个结构化的有机系统，每个人是社会系统的一个构件，引导学生要有家国情怀，心里装着国家和民族，在党和人民的伟大实践中关注时代、关注社会，汲取养分、丰富思想，做一个有用于社会的人2019年3月习近平总书记主持召开学校思想政治理论课教师座谈会明确要求。3 .基本算法设计方法：穷举法、归纳法、迭代法和递归法，递推式计算。教学重点：各种基本算法设计方法求解问题的思路。教学难点：如何优化穷举法算法和利用归纳法建立求解问题的递推关系，如何建立求解问题的递归

5、模型。课程思政：归纳法求解问题的思路O解决问题的是能力而不是碎片化的知识，能力是每个人自己总结归纳出来的特有的解决问题的一般方法，引导学生在学习中要善于总结归纳，在学习中做一些专题探讨（见算法设计与分析教案）工匠精神4 .分治法：分治法概述，求解排序问题，求解查找问题，求解组合问题和快速鼎算法。教学重点：分治法的基本策略和框架，快速排序和归并排序，二分查找，查找假币问题（三分查找），最大连续子序列和，求最近点对距离，求?和川问题。教学难点：利用分治法求解问题的一般思路，快速排序、归并排序和二分查找及其扩展应用。课程思政：分治法算法策略，大问题分解为若干小问题，由小问题的解合并为大问题的解O每个

6、小问题的解必须是正确的，这就是执行力，通过朝鲜战争中中国人民志愿者英勇顽强的战斗力示例向学生做爱国主义教育爱国情怀。5 .回溯法：问题的解空间，回溯法框架，基于子集树框架的问题求解和基于排列树框架的问题求解。教学重点：简单装载问题，0/1背包问题，任务分配问题，货郎担问题。教学难点：利用回溯法求解问题的一般思路，回溯法中的剪支操作。课程思政：回溯法中的剪支操作o以史为鉴，引导学生认识从中华民族近代苦难历史到中国特色社会主义道路是必然的选择，是中华民族伟大复兴是唯一正确之路爱国情怀。6 .分支限界法：分支限界法概述，限界函数设计，广度优先搜索，队列式分支限界法和优先队列式分支限界法。教学重点：各

7、种基本广度优先搜索，图的单源最短路径，0/1背包问题，任务分配问题和货郎担问题。教学难点：利用分支限界法求解问题的一般思路，分支限界法中的限界函数设计。课程思政：分支限界法中限界函数设计O人工智能中的启发式算法设计，我国政府制定了新一代人工智能发展规划，将人工智能上升到国家战略层面，并提出人工智能产业要成为新的重要经济增长点，而且要在2030年达到世界领先水平，让中国成为世界主要人工智能创新中心，为跻身创新型国家前列和经济强国奠定重要基础。让学生认识人工智能的国家战略，投身国家科技建设中科技报国7 .贪心法：贪心法原理和要点，贪心法框架，求解组合问题，求解图问题，求解调度问题和哈夫曼编码。教学

8、重点：活动安排问题I,背包问题，Prim算法、KrUSka1算法和DijkS1ra算法，不带惩罚的调度问题和带惩罚的调度问题。教学难点：利用贪心法求解问题的一般思路，如何在求解问题中选择正确的贪心策略。课程思政：贪心法算法设计必须采用正确的贪心选择策略O引导学生认识一个经济学问题即财富第3次分配。财富初次分配就是要让那些有知识、善于创新并努力工作的人得到更多的劳务报酬，首先富裕起来；财富第二次分配就是政府利用税收等手段来帮助弱势群体，建立全面、系统、适度、公平和有效的社会保障体系；财富第三次分配是富人们在自愿的基础上拿出自己的部分财富，帮助穷人改善生活、教育和医疗的条件爱国情怀。8 .动态规划

9、：动态规划原理和要点，一维动态规划，二维动态规划，三维动态规划,字符串动态规划，背包动态规划，树形动态规划，区间动态规划。教学重点：动态规划原理和要点，一维动态规划，二维动态规划，三维动态规划，背包动态规划。教学难点：利用动态规划求解问题的一般思路，动态规划算法中的空间优化。课程思政：动态规划用于求最优解，“规划”本质就是将求解过程分为若干阶段，利用前面阶段的最优解求后面阶段的最优解o中国的发展分为若干个五年计划，新的五年计划都是在前期总结的基础上考虑国家发展和总目标制定的，形成最优社会发展方向，引导学生认识社会主义制度和中国模式的优越性爱国情怀。9 .NP完全问题：P类、NP类和NP完全问题

10、。教学重点：P类、NP类和NP完全问题的概念。教学难点：NP完全问题。课程思政：NP完全问题是目前已知最难的问题O上海洋山深水港四期是全球领先、亚洲首个全自动化码头，集装箱装卸转运全部由智能设备完成，无人驾驶自动导引车，自动堆箱轨塔吊，是美国九大港口的吞吐总量，占到目前全球港口年吞吐量的十分之一。其智能化程度之高让不少外国网友惊叹，“跟看科幻片似的”。数百台车辆实现自动调度属于NP完全问题，该港采用5G智慧解决方案。让学生体会中国社会主义建设的自豪感工匠精神，科技报国。课程内容与学时分配表（44学时）内容学时1、概论22、常用数据结构及其应用43、基本算法设计方法44、分治法65、回溯法66、

11、分支限界法67、贪心法68、动态规划89、NP完全问题2小计44课程内容与学时分配表（32学时）一方案1内容学时1、概论22、常用数据结构及其应用23、基本算法设计方法44、分治法45、回溯法66、分支限界法47、贪心法48、动态规划69、NP完全问题O小计32课程内容与学时分配表（32学时）一方案2内容学时1、概论22、常用数据结构及其应用O3、基本算法设计方法O4、分治法65、回溯法66、分支限界法67、贪心法68、动态规划69、NP完全问题0小计32四、教材与弁考书（黑体五号）教材：算法设计与分析基础.李春葆等.北京：清华大学出版社，2023参考书：1算法导论.ThomasH.Corme

12、n,Char1esE.1eiserson,Rona1d1.Rivest,C1iffbrdStein著.潘金贵，顾铁成，李成法、叶懋译.北京：机械工业出版社，20092算法设计技巧与分析.A1suwaiye1MH.著，吴伟昶等译.北京：电子工业出版社,20043算法设计与分析.王红梅.北京：清华大学出版社，20064计算机算法设计与分析.王晓东.北京：电子工业出版社.20125算法设计与分析基础学习与上机指导.李春葆等，清华大学出版社，2023五、考核方式（黑体五号）期末考试（60%）,上机实验（20%）,作业（10%）,其他（10%）算法设计与分析实验课程教学大纲课程代码：*课程负责人：*课程

13、中文名称：算法设计与分析实验课程英文名称：A1gorithmdesignandana1ysisexperiment课程类别：必修课程学分数：0.5课程学时数：1521授课对象：计算机科学与技术及相关专业本科本课程的前导课程：CC+程序设计、离散数学、算法设计与分析一、教学介绍算法设计与分析实验是算法设计与分析的配套课程，主要通过上机编程巩固算法设计与分析的基本原理和方法，掌握数据组织和算法设计和实现技术，培养综合运用算法设计与分析策略高效解决问题的能力。主要穷举法、归纳法、迭代法和递归法等基本算法设计方法以及分治法、蛮力法、回溯法、分支限界法、贪心法和动态规划法等算法设计策略。二、教学目的算法

14、设计与分析实验课程的总目标是培养学生能够根据需要开展实验研究，正确地描述数据和组织数据，并应用数据处理方法，编写程序，分析实验结果以获得合理有效的结论，具备解决复杂工程问题的能力。算法设计与分析实验分为单机实验和在线编程。单机实验是在自己计算机或者实验室计算机上完成，目的让学生领会算法的原理、验证算法的正确性和采用常用的算法策略求解问题。在线编程实验是在1eeteOde、POJ或者HDU在线编程平台中完成，目的是培养学生研究问题、合理地选择数据结构和算法策略构建解决方案，并分析比较各种方案优劣的能力。三、实验基本要求与方式1、基本要求课前：要求任课教师布置好实验题目、实验要求和实验目的，要求实

15、验教师为实验准备好必须的设备和软件；要求学生提前编写完成实验要求的程序代码。课中：要求任课教师随时解答学生提出的实验问题，同时要注重启发和引导学生，使学生养成独立思考、解决问题的能力，检查学生的实验内容；实验教师要及时解决实验设备可能出现的故障，保证实验顺利地进行。学生则应该按照实验要求，认真编写和调试源代码，完成实验内容。课后：提交实验报告。2、实验方式单机实验题：输入相应的数据，通过检测输出结果，验证是否实现了实验的要求。在线编程题：在在线编程平台提交代码，查看提交结果，分析代码运行的时间和空间。四、实验报告实验报告按学院要求格式书写，包含封面（含学号，姓名等），目录，每个实验的题目，解答思路，程序框架，源代码，提交结果图（在线编程题给出包含提交通过、运行时间和空间的截屏图），实验体会（选）。五、实验内容与学时分配说明：所有实验题的题目描述见教材，在线编程实睑题目见1eeteOde、北京大学POJ和杭州电子科技大学HUD网站。