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

《算法设计与分析》课程教学大纲（含课程思政）课程代码****课程负责人****课程中文名称算法设计与分析课程英文名称Design andAnalysis ofAlgorithms课程类别必修课程学分数

2.5课程学时数44/32授课对象计算机科学与技术及相关专业本科本课程的前导课程C/C++程序设计、离散数学、数据结构

一、教学目的（黑体五号）本课程是计算机科学与技术专业的专业必修课课程目标如下

1.掌握计算机算法的基本概念和特性，了解计算机相关学科中算法分析与设计技巧的重要性，掌握算法时间复杂性的分析方法

2.掌握基本的算法设计策略，结合具体问题实例学习，重点掌握分治法、贪心法、动态规划法、回溯法、分支限界法等常见的算法设计策略

3.通过理论学习和上机实践的训练，具备灵活运用所学解决实际应用问题的能力

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

三、课程内容与学时分配（黑体五号）主要内容

1.概论算法的概念和算法分析方法教学重点算法时空分析方法教学难点算法时间复杂度渐进符号

0、Q和课程思政好算法的时空平衡”辩证唯物论，引导学生建立客观、理性的辩证思维，树立正确的人生观，善于从政治上看问题，在大是大非面前保持政治清醒［2019年3月习近平总书记主持召开学校思想政治理论课教师座谈会明确要求］

1.单机实验题1蓄栏保留问题2删数问题3求所有最小生成树4改进Dijkstra算法5字符串的编码和解码

2.在线编程题1LeetCode455一分发饼干2LeetCodel35一分发糖果3LeetCode56一合并区间4HDU2037一看电视节目5HDU1009一老鼠的交易6HDU3177一装备问题7HDU21D一取宝贝8POJ2376—分配清洁班次9POJ2726—假日酒店10POJ1328—安装雷达实验7动态规划学时数3o任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目

1.单机实验题1矩阵最小路径和2双核处理问题3划分集合为和相等的两个子集合4员工分配问题

2.在线编程题1LeetCode64一最小路径和2LeetCodel289—下降路径最小和II3LeetCode638—大礼包4LeetCodel39一单词拆分5LeetCode377—组合总和IV6LeetCode354—俄罗斯套娃信封问题7LeetCode583—两个字符串的删除操作8LetCodel22—买卖股票的最佳时机n9HDU2602—收集物品10HDU1114一存钱罐11HDU2044一—只小蜜蜂12POJ1050—最大子矩形和13POJ1157—花店14POJ1159一回文15POJ1243一猜价格游戏16POJ3311一送比萨

六、教材与参考书教材算法设计与分析基础上机实验指导，清华大学出版社，李春葆等，2022参考书算法设计与分析基础，清华大学出版社，李春葆等，2022

七、考核方式实验报告格式规范和完整性40%,实验题目的难度和正确性40%,其他20%

2.常用数据结构及其应用线性表、字符串、栈、队列、双端队列、二叉树、优先队列、树和并查集、图、二叉排序树、平衡二叉树和哈希表，设计好的数据结构教学重点各种STL容器的应用和设计好的数据结构教学难点如何利用各种STL容器设计求解相关问题的算法设计，如何利用数据结构容器高效地设计求解相关问题的算法课程思政数据结构是算法的基本构件，只有选择好的数据结构才能设计出求解问题的好算法弓社会是一个结构化的有机系统，每个人是社会系统的一个构件，引导学生要有家国情怀，心里装着国家和民族，在党和人民的伟大实践中关注时代、关注社会，汲取养分、丰富思想，做一个有用于社会的人［2019年3月习近平总书记主持召开学校思想政治理论课教师座谈会明确要求］

3.基本算法设计方法穷举法、归纳法、迭代法和递归法，递推式计算教学重点各种基本算法设计方法求解问题的思路教学难点如何优化穷举法算法和利用归纳法建立求解问题的递推关系，如何建立求解问题的递归模型课程思政归纳法求解问题的思路弓解决问题的是能力而不是碎片化的知识，能力是每个人自己总结归纳出来的特有的解决问题的一般方法，引导学生在学习中要善于总结归纳，在学习中做一些专题探讨（见算法设计与分析教案）［工匠精神］

4.分治法分治法概述，求解排序问题，求解查找问题，求解组合问题和快速幕算法教学重点分治法的基本策略和框架，快速排序和归并排序，二分查找，查找假币问题（三分查找），最大连续子序列和，求最近点对距离，求/和A问题教学难点利用分治法求解问题的一般思路，快速排序、归并排序和二分查找及其扩展应用课程思政分治法算法策略，大问题分解为若干小问题，由小问题的解合并为大问题的解“每个小问题的解必须是正确的，这就是执行力，通过朝鲜战争中中国人民志愿者英勇顽强的战斗力示例向学生做爱国主义教育［爱国情怀］

5.回溯法问题的解空间，回溯法框架，基于子集树框架的问题求解和基于排列树框架的问题求解教学重点简单装载问题，0/1背包问题，任务分配问题，货郎担问题教学难点利用回溯法求解问题的一般思路，回溯法中的剪支操作课程思政回溯法中的剪支操作“以史为鉴，引导学生认识从中华民族近代苦难历史到中国特色社会主义道路是必然的选择，是中华民族伟大复兴是唯一正确之路［爱国情怀］

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

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

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

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

1、概论

22、常用数据结构及其应用

43、基本算法设计方法

44、分治法

65、回溯法

66、分支限界法

67、贪心法

68、动态规划

89、NP完全问题2小计44课程内容与学时分配表（32学时）一方案1内容学时

1、概论

22、常用数据结构及其应用

23、基本算法设计方法

44、分治法

45、回溯法

66、分支限界法

47、贪心法

48、动态规划

69、NP完全问题0小计32课程内容与学时分配表（32学时）一方案2内容学时

1、概论

22、常用数据结构及其应用

03、基本算法设计方法

04、分治法

65、回溯法

66、分支限界法

67、贪心法

68、动态规划

69、NP完全问题0小计32U、教材与参考书（黑体五号）i教材算法设计与分析基础.李春葆等.北京清华大学出版社，2022参考书

[1]算法导论.Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein著.潘金贵，顾铁成，李成法、叶懋译.北京机械工业出版社，2009

[2]算法设计技巧与分析.AlsuwaiyelM.H.著，吴伟昶等译.北京电子工业出版社,2004

[3]算法设计与分析.王红梅.北京清华大学出版社，2006

[4]计算机算法设计与分析.王晓东.北京电子工业出版社.2012

[5]算法设计与分析基础学习与上机指导.李春葆等，清华大学出版社，2022

五、考核方式（黑体五号）期末考试（60%）,上机实验（20%）,作业（10%）,其他（10%）《算法设计与分析实验》课程教学大纲课程代码****课程负责人****课程中文名称算法设计与分析实验课程英文名称Algorithm designand analysisexperiment课程类别必修课程学分数

0.5课程学时数15〜21授课对象计算机科学与技术及相关专业本科本课程的前导课程C/C++程序设计、离散数学、算法设计与分析

一、教学介绍算法设计与分析实验是算法设计与分析的配套课程，主要通过上机编程巩固算法设计与分析的基本原理和方法，掌握数据组织和算法设计和实现技术，培养综合运用算法设计与分析策略高效解决问题的能力主要穷举法、归纳法、迭代法和递归法等基本算法设计方法以及分治法、蛮力法、回溯法、

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

三、实验基本要求与方式

1、基本要求课前要求任课教师布置好实验题目、实验要求和实验目的，要求实验教师为实验准备好必须的设备和软件；要求学生提前编写完成实验要求的程序代码课中要求任课教师随时解答学生提出的实验问题，同时要注重启发和引导学生，使学生养成独立思考、解决问题的能力，检查学生的实验内容；实验教师要及时解决实验设备可能出现的故障，保证实验顺利地进行学生则应该按照实验要求，认真编写和调试源代码，完成实验内容课后提交实验报告

2、实验方式单机实验题输入相应的数据，通过检测输出结果，验证是否实现了实验的要求在线编程题在在线编程平台提交代码，查看提交结果，分析代码运行的时间和空间

四、实验报告实验报告按学院要求格式书写，包含封面含学号，姓名等，目录，每个实验的题目，解答思路，程序框架，源代码，提交结果图在线编程题给出包含提交通过、运行时间和空间的截屏图，实验体会选

五、实验内容与学时分配说明所有实验题的题目描述见《教材》，在线编程实验题目见LeetCode、北京大学POJ和杭州电子科技大学HUD网站实验1常用数据结构及其应用学时数0〜3任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目

1.单机实验题1高效地插入、删除和查找22一种特殊的队列3方块操作

2.在线编程题1LeetCode328—奇偶链表2LeetCode394—字符串解码3LeetCode215一数组中的第左个最大元素4HDU1280—前加大的数5POJ2236—无线网络实验2基本算法设计方法学时数〜3任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目

1.单机实验题1最长重复子串2求子矩阵元素和3求〃阶螺旋矩阵4验证梵塔问题

2.在线编程题1LeetCode344—反转字符串2LeetCode206—反转链表3LeetCode24一两两交换链表中的结点4LeetCode62一不同路径5HDU1003—最大子序列和6HDU1143一三平铺问题7POJ2231一奶牛的总音量8POJ1050—最大子矩形实验3分治法学时数3o任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目

1.单机实验题1将一个整数数组划分为两个和差最大的子数组2四路归并排序3查找假币问题4求众数5求汉诺塔H6求Fibonacci数列

2.在线编程题1LeetCode240一搜索二维矩阵n2LeetCode35一搜索插入位置3LeetCode33一搜索旋转排序数组4LeetCodel62一寻找峰值5HDU2141—能否找到X6HDU2199一解方程7HDU1040一排序8HDU1157—求中位数9HDU1007一套圈游戏10POJ2255一由二叉树中序和先序序列产生后序序列11POJ1854—转换为回文的交换次数12POJ1995—求表达式值实验4回溯法学时数3任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目

1.单机实验题1象棋算式2子集和3迷宫路径4哈密顿回路

2.在线编程题1LeetCode216一组合总和ni2LeetCode39—组合总和

33.LeetCodel31一分割回文串4HDU1027—第k小的排列5HDU2553—N皇后问题6HDU2616一杀死怪物7POJ3187一向后数字和8POJ1321一棋盘问题9POJ2488一骑士游历10POJ1040一运输问题11POJ1129—最少频道数实验5分支限界法学时数3o任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目

1.单机实验题1原始森林中解救A2装载问题3最小机器重量设计问题I4最小机器重量设计问题H5货郎担问题

2.在线编程题1LeetCode847—访问所有结点的最短路径2LeetCodel376一通知所有员工所需的时间3HDU1242一救援问题4HDU1548—奇怪的电梯5HDU1869—六度分离6HDU2425—徒步旅行7HDU1072—变形迷宫8POJ2312—坦克游戏实验6贪心法学时数3任课教师根据学生情况在以下各种类型的实验题目中选择若干实验题目。