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

1、算法分析与设计课程教学大纲一、课程基本信息课程名称（中文）算法分析与设计课程名称（英文）Algorithm Analysis and Design课程类别1：专业主干课课程性质2必修授课语言3中文授课学期4学分4课程学时及分配总学时讲课实验课外64481664适用专业计算机科学与技术专业教材算法分析与设计(第二版)，李春葆，清华大学出版社授课学院计算机与软件学院先修课程程序设计基础，离散数学，数据结构后续课程操作系统，数据库系统，编译原理，机器学习等课程简介课程基本定位：本课程是计算机科学与技术专业的专业必修课。系统学习计算机算法的有关概念和算法设计的基本技巧。培养学生分析问题和解决问题的能力

2、，使学生掌握算法设计的基本技巧和方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，解决一些较综合的问题，为学生进一步学习后续课程奠定良好的基础核心学习结果：掌握计算机算法的基本概念和特性，了解计算机相关学科中算法分析与设计技巧的重要性，掌握算法时间复杂性的分析方法和基本的算法设计策略，结合具体问题实例，能掌握常见的算法设计策略，了解计算复杂性基本理论，具备灵活运用所学解决实际应用问题的能力主要教学方法：讲授、课堂练习和讨论互动、课后作业和上机实验大纲更新时间2020年8月20日注：1.课程类别：选填“通识核心课/通识拓展课/通修课/学科基础课/专业主干课/专业选修课/专业实践/素质拓展”

3、2.课程性质：选填“选修/必修”3.授课语言：选填“中文/双语/全英文或其他语种”二、课程目标序号课程目标（参考培养目标、毕业要求、课程定位）支撑毕业要求指标点1达成途径1.1系统学习计算机算法的有关概念和算法设计的基本技巧，培养学生分析问题和解决问题的能力3.2能够合理有效地组织、存储和处理数据，正确地进行算法设计、分析和评价；讲授+讨论+实践1.2掌握算法设计的基本技巧和方法5.2在软件工程领域复杂工程问题的建模、模拟或解决过程中，能够使用恰当的技术、软硬件及系统资源和研发工具，提高解决复杂工程问题的能力和效率；讲授+讨论+实践2.1熟练运用一些常用算法，解决一些较综合的问题5.2在软件工

4、程领域复杂工程问题的建模、模拟或解决过程中，能够使用恰当的技术、软硬件及系统资源和研发工具，提高解决复杂工程问题的能力和效率；讲授+讨论+实践2.2为学生进一步学习后续课程奠定良好的基础12.1了解软件工程技术发展中取得重大突破的历史背景，以及当前发展的热点问题，了解信息技术发展的前沿和趋势；讲授+讨论+实践注：1.支撑毕业要求指标点：选填项。需要进行专业认证，有毕业要求指标点可参照的课程必填，无明确毕业要求指标点可参照的可不填。三、理论教学内容章标题教学内容学时思政融入点1学生学习预期成果2教学方式3课程目标第一章算法设计与分析概论41. 算法的概念、算法分析方法3介绍古代算术基础1.了解算

5、法设计及评价的基本方法2.了解STL在算法设计中的作用讲授+讨论1.12.STL在算法设计中的应用1讲授+讨论1.2第二章递归算法设计41.递归的概念、递归算法设计方法1突出我国的道家哲学思维1.掌握递归的基本方法2.熟悉构造非递归算法3.掌握递推算法讲授+讨论+演示2.12.22. 递归算法到非递归算法的转化2讲授+讨论+演示2.12.23.递推问题求解1讲授2.12.2第三章分治法41.分治法的策略和求解过程11.理解分治算法特征2. 能够利用分治算法求解问题3.了解并行算法基本结构讲授2.12.22.采用分治法求解排序问题、查找问题、最大连续子序列和等问题2讲授+讨论+演示2.12.23

6、. 并行计算的概念1讲授+讨论+演示2.12.2第四章蛮力法41. 蛮力法的特点、蛮力法的基本应用示例21.掌握暴力求解方法2.掌握深度搜索和广度搜索算法讲授2.12.22. 图的深度优先和广度优先遍历算法2讲授+讨论+演示2.12.2第五章回溯法41. 解空间概念和回溯法算法框架11.熟悉回溯算法框架2.掌握回溯算法求解过程讲授2.12.22. 采用回溯法求解0/1背包问题3讲授+讨论+演示2.12.2第六章分枝限界法61. 分枝限界法的特点和算法框架11.熟悉分枝定界算法框架，理解规划问题求解策略2.熟悉分枝定界算法及问题求解讲授2.12.22. 队列式分枝限界法和优先队列式分枝限界法2讲

7、授+讨论+演示2.12.23. 分枝限界法求解0/1背包等问题3讲授+讨论+演示2.12.2第七章贪心法41. 贪心法的策略、求解过程的性质11.掌握贪心算法基本求解策略2.掌握贪心算法基本问题讲授2.12.22. 贪心法求解活动安排问题、背包等问题3讲授+讨论+演示2.12.2第八章动态规划61. 动态规划的原理和求解步骤21.理解动态规划问题的一般结构2.掌握基本的动态规划求解方式讲授2.12.22. 采用动态规划法求解问题4讲授+讨论+演示2.12.2第九章图算法设计41.构图的最小生成树11.掌握图的基本算法2.了解用图求解优化问题的方法讲授+讨论+演示2.12.22图的最短路径方法2

8、讲授+讨论+演示2.12.23.网络流初步1讲授+讨论+演示2.12.2第十章计算几何31. 几何计算中常用的矢量运算11.熟悉几何问题的计算方法2.掌握基本的几何计算算法讲授+讨论+演示2.12.22. 求解凸包问题、最近点对问题和最远点对问题的典型算法2讲授+讨论+演示2.12.2第十一章计算复杂性理论简介31. 介绍图灵机计算模型1简介计算机理论科学基础1.了解图灵机的基本结构2.了解可计算问题的表示方式讲授1.11.22. P类和NP类问题以及NPC问题2讲授2.12.2第十二章概率算法和近似算法21. 概率算法和近似算法的特点11.了解近似计算基本结构2.熟悉近似算法的设计方法讲授2

9、.12.22. 基本近似算法设计方法1讲授+讨论+演示2.12.2注：1.思政融入点：至少写3条，简述该课程教学中将思政教育内容与专业教育内容有机融合的知识点（下同）。 2.学生学习预期成果：描述学生在学完本节内容后应获得的知识、能力或素养水平（下同） 3.教学方式:包括讲授、讨论、案例、演示等，但不限于所列，根据课程实际需要列举四、实践（实验或实习）教学1编号实验或实习项目名称教学内容学时实验类型思政融入点学生学习预期成果课程目标1递归问题OJ练习递归问题求解2综合性理解递归问题求解策略1和22分治问题OJ练习分治问题求解2综合性理解分治问题求解策略1和23蛮力方法OJ练习蛮力方法2综合性理

10、解暴力方法求解策略1和24回溯方法OJ练习回溯方法2综合性理解回溯方法求解策略1和25分枝定界OJ练习整数规划问题求解2综合性理解分枝定界优化求解策略1和26贪心OJ练习贪心方法2综合性理解贪心问题求解策略1和27动态规划OJ练习DP问题求解2综合性理解DP问题求解策略1和28图算法OJ练习图算法2综合性理解图算法1和2注：1.此表可用于课内实践教学环节或某门综合实践课程2.实验类型：选填”验证性/综合性/设计性”；实习类型：选填“认识实习/生产实习/毕业实习”五、课程评价（一）考核内容、考核方式与课程目标对应关系课程目标考核内容课程目标在各考核方式中占比平时表现课程作业期中考试期末考试1.1

11、算法性能衡量与优化20%10%10%1.2问题求解策略与算法的设计10%30%10%40%2.1基本问题的求解方法10%30%70%45%2.2设计合适的算法求解较为复杂的问题10%10%5%合计100%100%100%100%各考核方式占总成绩权重（自行赋值）10%10%20%10%20%50%70%注：1. 课程目标在考核方式及占比：主要根据课程目标自行设计和制定多元化考核方式，表中所列仅为参考（红色数据可删除）。但所列考核方式必须覆盖全体学生，可根据当学期具体教学情况酌情调整。2. 各考核方式占总成绩权重：根据课程实际情况对各考核方式占总成绩的权重予以赋值。（二）考核方式评分标准1课程作

12、业评分标准课程目标评分标准占比90-100（优）80-89（良）70-79（中）60-69（及格）0-59（不及格）1.作业认真效果优作业态度认真效果良态度基本认真效果一般态度一般，效果差作业不足或抄袭作业2.作业认真效果优作业态度认真效果良态度基本认真效果一般态度一般，效果差作业不足或抄袭作业2期中/期末考试评分标准（笔试类评分标准可在大纲中按以下格式予以说明，也可在通过“试卷分析表”予以说明）课程目标评分标准占比90-100（优）80-89（良）70-79（中）60-69（及格）0-59（不及格）1.准确理解和解答部分理解和解答能理解和解答基本理解和答题不能正确理解2.准确理解和解答部分理解和解答能理解和解答基本理解和答题不能正确理解注：考核方式和课程目标在考核方式中占比应与“（一）考核内容、考核方式与课程目标对应关系”一致。所列考核环节，除了笔试类均须依次给出评分标准，格式同上。笔试类课程考核评分标准可以在本课程大纲里进行说明，也可以通过提交“试卷分析表”予以说明。五、参考书目及学习资料1 Thomas H. Cormen，Charles E. Leise