《算法分析与设计》课程教学大纲 一、课程基本信息 课程代码：16134603 课程名称：算法分析与设计 英文名称：Algorithmic Analysis and Design 课程类别：专业课 时：48 分：3 适用对象：信息与计算科学专业本科生 考核方式：考试 先修课程：计算机技术基础，程序设计基础，数据结构与算法 二、课程简介 《算法分析与设计》也作《算法设计与分析》，讲授传统算法设计技术与算法分 析的方法以及在一些经典问题中的应用。讨论和介绍计算机算法的复杂性理论，结合 对一些熟悉的算法进行分析和总结，强化基础理论知识，对一些大型工程软件的分析 会有一定的辅助作用。它主要介绍计算机科学及应用领域常见的有代表性的非数值算 法及算法设计的若干重要方法，同时，介绍算法分析的基本知识。阐述计算模型和时 间复杂性的定义：讨论递归技术和算法分析的基本手段：介绍算法设计的几类方法， 如分治法、回溯法、贪心法、动态规划法、分枝限界法等，并结合某些有实用意义的 经典算法来加深设计方法的探讨，由浅入深地进行算法效率分析，使学生在掌握各种 算法设计方法和分析基本技术的同时，也是逻辑思维得到锻炼。 通过该课程的学习培养学生的算法设计与分析能力，增强程序设计与实践能力， 引导学生的思维过程，培养计算思维能力。通过本课程的学习，使学生能够正确理解 算法设计与分析中的基本概念，掌握算法设计的基本策略和方法，能对建立的算法进 行理论分析，并达到一定的算法设计与分析能力。 Algorithmic Analysis and Design is also called Algorithmic Design and Analysis which teaches traditional algorithmic design techniques and algorithmic analysis methods and their applications in some classical problems.This paper discusses and introduces the complexity theory of computer algorithms,analyzes and summarizes some familiar algorithms,strengthens the basic theoretical knowledge,and will be helpful to the analysis of some large-scale engineering software.It mainly introduces some typical non-numerical algorithms and some important methods of algorithm design in the field of computer science and application.At the same time,it introduces the basic knowledge of algorithm 1
1 《算法分析与设计》课程教学大纲 一、课程基本信息 课程代码：16134603 课程名称：算法分析与设计 英文名称：Algorithmic Analysis and Design 课程类别：专业课 学 时：48 学 分：3 适用对象: 信息与计算科学专业本科生 考核方式：考试 先修课程：计算机技术基础，程序设计基础，数据结构与算法 二、课程简介 《算法分析与设计》也作《算法设计与分析》，讲授传统算法设计技术与算法分 析的方法以及在一些经典问题中的应用。讨论和介绍计算机算法的复杂性理论，结合 对一些熟悉的算法进行分析和总结，强化基础理论知识，对一些大型工程软件的分析， 会有一定的辅助作用。它主要介绍计算机科学及应用领域常见的有代表性的非数值算 法及算法设计的若干重要方法，同时，介绍算法分析的基本知识。阐述计算模型和时 间复杂性的定义；讨论递归技术和算法分析的基本手段；介绍算法设计的几类方法， 如分治法、回溯法、贪心法、动态规划法、分枝限界法等，并结合某些有实用意义的 经典算法来加深设计方法的探讨，由浅入深地进行算法效率分析，使学生在掌握各种 算法设计方法和分析基本技术的同时，也是逻辑思维得到锻炼。 通过该课程的学习培养学生的算法设计与分析能力，增强程序设计与实践能力， 引导学生的思维过程，培养计算思维能力。通过本课程的学习，使学生能够正确理解 算法设计与分析中的基本概念，掌握算法设计的基本策略和方法，能对建立的算法进 行理论分析，并达到一定的算法设计与分析能力。 Algorithmic Analysis and Design is also called Algorithmic Design and Analysis, which teaches traditional algorithmic design techniques and algorithmic analysis methods and their applications in some classical problems. This paper discusses and introduces the complexity theory of computer algorithms, analyzes and summarizes some familiar algorithms, strengthens the basic theoretical knowledge, and will be helpful to the analysis of some large-scale engineering software. It mainly introduces some typical non-numerical algorithms and some important methods of algorithm design in the field of computer science and application. At the same time, it introduces the basic knowledge of algorithm
analysis.This paper expounds the definition of computational model and time complexity. discusses recursive techniques and basic methods of algorithm analysis,and introduces several methods of algorithm design.such as divide-and-conquer method.backtracking method,greedy method,dynamic programming method,branch-and-bound method,etc. In-depth algorithm efficiency analysis,so that students master a variety of algorithm design methods and analysis of basic technology.but also to exercise logical thinking. Through the study of this course,the students'ability of algorithm design and analysis is trained.the ability of program design and practice is enhanced.the students'thinking process is guided,and the ability of computing thinking is trained.Through the study of this course,students can correctly understand the basic concepts of algorithm design and analysis.master the basic strategies and methods of algorithm design,and analyze the established algorithm theoretically,and achieve a certain ability of algorithm design and analysis 三、课程性质与教学目的 《算法设计与分析》是一门理论性与实践性兼顾的课程，是软件工程、计算机科 学与技术、网络工程及相关专业的基础课程。课程是“编译原理”和“软件工程”等 专业核心课程的基础课，为学习专业课程及提高软件设计水平打下良好的基础。 本果程问学生系统讲述软件设计中常用的算法设计与分析方法。学生通过对算法 设计策略的系统学习与研究，理解和掌握算法设计的主要方法，锻炼独立分析问题和 解决问的能力，为开发高效的软件系统及相关领域的研究工作哭定坚实的基础。 通过本课程的学习，要求学生理解计算机算法效率分析与设计所涉及的基本概念 和基础知识，掌握基本的算法分析方法和常见的算法设计方法，能熟练应用课程介绍 的算法设计方法来解决软件开发中的实际问题。通过对算法实例的分析，进一步加深 对算法设计方法的认识和理解。 课程融入思政的总体思路：结合课程在算法设计方面具有的基础性和优化性两个 提点，通过日常课堂的算法设计与分析教学，培养学生“以我为主”，自己设计算法 的自力更生的思想意识，培养学生精益求精的优化意识。 四、教学内容及要求 第一章算法概述 (一基本教学内容 1、计算机求解问题的步骤 2、算法及其要索和特性 3、 算法描述方法 4、算法的计算机实现 教学重点：算法的计算机实现
2 analysis. This paper expounds the definition of computational model and time complexity, discusses recursive techniques and basic methods of algorithm analysis, and introduces several methods of algorithm design, such as divide-and-conquer method, backtracking method, greedy method, dynamic programming method, branch-and-bound method, etc. In-depth algorithm efficiency analysis, so that students master a variety of algorithm design methods and analysis of basic technology, but also to exercise logical thinking. Through the study of this course, the students'ability of algorithm design and analysis is trained, the ability of program design and practice is enhanced, the students' thinking process is guided, and the ability of computing thinking is trained. Through the study of this course, students can correctly understand the basic concepts of algorithm design and analysis, master the basic strategies and methods of algorithm design, and analyze the established algorithm theoretically, and achieve a certain ability of algorithm design and analysis. 三、课程性质与教学目的 《算法设计与分析》是一门理论性与实践性兼顾的课程，是软件工程、计算机科 学与技术、网络工程及相关专业的基础课程。课程是“编译原理”和“软件工程”等 专业核心课程的基础课，为学习专业课程及提高软件设计水平打下良好的基础。 本课程向学生系统讲述软件设计中常用的算法设计与分析方法。学生通过对算法 设计策略的系统学习与研究，理解和掌握算法设计的主要方法，锻炼独立分析问题和 解决问题的能力，为开发高效的软件系统及相关领域的研究工作奠定坚实的基础。 通过本课程的学习，要求学生理解计算机算法效率分析与设计所涉及的基本概念 和基础知识，掌握基本的算法分析方法和常见的算法设计方法，能熟练应用课程介绍 的算法设计方法来解决软件开发中的实际问题。通过对算法实例的分析，进一步加深 对算法设计方法的认识和理解。 课程融入思政的总体思路：结合课程在算法设计方面具有的基础性和优化性两个 提点，通过日常课堂的算法设计与分析教学，培养学生“以我为主”，自己设计算法 的自力更生的思想意识，培养学生精益求精的优化意识。 四、教学内容及要求 第一章 算法概述 （一）基本教学内容 1、计算机求解问题的步骤 2、 算法及其要素和特性 3、 算法描述方法 4、 算法的计算机实现 教学重点：算法的计算机实现
教学难点：算法设计描述 (二)基本要求 1、知识要求 1)理解计算机求解问题的步骤 2)熟悉算法及其特征： 2、能力要求 通过本章的学习，学生能够在实际的算法设计中做出合理选择，扬长避短，确定 合适的计算方法，比较不同算法的优缺点。 (三)课程思政 通过讲授用计算机解决问题的规范步骤以及各阶段算法描述方法逐步细化的 过程，引导学生初步掌握解决复杂问题应当分阶段攻关、逐步深入的科研方法。 第二章算法分析基础 (一)基本教学内容 1、算法分析体系及计量 2、算法分析案例 教学重点：算法分析要点，渐进时间复杂度分析方法： 教学难点：递归算法的渐进时间复杂度分析。 (二)基本要求 1、知识要求：了解算法分析体系，掌握渐进时间复杂度分析方法。 2、能力要求：通过学习，学生能够掌握对非递归算法和递归算法的时间复杂分析 方法。 (三)课程思政 通过闸明事前分析法比事后分析法的合理之处，让学生进一步认识理论研究 的重要性：通过算法时间复杂度的对比，让学生初步树立优化思想。 第三章算法优化 (一)基本教学内容 1、循环与递归算法设计 2、算法中的数据结构 3、算法优化 教学重点：循环与递归算法设计，算法优化： 教学难点：算法优化。 (一)基本要求： 1、知识要求：掌握循环与递归算法设计，熟悉算法优化的方法。 2、能力要求：通过学习，学生能够对进行循环与递归算法设计，对一些算法进行 3
3 教学难点：算法设计描述 （二）基本要求 1、知识要求 1) 理解计算机求解问题的步骤； 2) 熟悉算法及其特征； 2、能力要求 通过本章的学习，学生能够在实际的算法设计中做出合理选择，扬长避短，确定 合适的计算方法，比较不同算法的优缺点。 （三）课程思政 通过讲授用计算机解决问题的规范步骤以及各阶段算法描述方法逐步细化的 过程，引导学生初步掌握解决复杂问题应当分阶段攻关、逐步深入的科研方法。 第二章 算法分析基础 （一）基本教学内容 1、算法分析体系及计量 2、算法分析案例 教学重点：算法分析要点，渐进时间复杂度分析方法； 教学难点：递归算法的渐进时间复杂度分析。 （二）基本要求 1、知识要求：了解算法分析体系，掌握渐进时间复杂度分析方法。 2、能力要求：通过学习，学生能够掌握对非递归算法和递归算法的时间复杂分析 方法。 （三）课程思政 通过阐明事前分析法比事后分析法的合理之处，让学生进一步认识理论研究 的重要性；通过算法时间复杂度的对比，让学生初步树立优化思想。 第三章 算法优化 （一）基本教学内容 1、循环与递归算法设计 2、算法中的数据结构 3、算法优化 教学重点：循环与递归算法设计，算法优化； 教学难点：算法优化。 （二）基本要求： 1、知识要求：掌握循环与递归算法设计，熟悉算法优化的方法。 2、能力要求：通过学习，学生能够对进行循环与递归算法设计，对一些算法进行
优化处理。 (三)课程思政 通过进一步让学生了解计算机解决问题的基本原理，让学生进一步看清楚机 器的优点和缺点，树立“人是决定因素，同时应当草握工具以更好改造世界”的 正确观念。 第四章基本算法策略 (一)基本教学内容 1、迭代算法 2、蛮力法 3、分而治之算法 4、贪婪算法 5、动态规划 6、不同算法的比较 教学重点：不同算法的应用。 教学难点：算法的设计。 (二)基本要求： 1、知识要求：熟悉各种算法策略。 2、能力要求：通过学习，学生能够利用不同算法解决问题。 (三)课程思政 通过对比蛮力法与其他类型的算法策略，让学生树立既要能苦干、也要能巧 干的辩证思相：通讨对比各种管官法的话用条件，让学生讲一光认识到要具体问形 具体分析：通过对各类复杂算法的学校，让学生树立刻苦专研、精益求精的科学 精神。 第五章搜索算法 (一)基本教学内容 1、图搜索概念 2、广度优先搜索 3、深度优先搜索算法 4、回溯法 5、分支限界法 教学重点：图搜索概念，不同的图搜索算法 教学难点：图搜索算法。 (二)基本要求： 1、知识要求：理解图搜索概念，掌握各种图搜索算法。 2、能力要求：通过学习，学生能够利用不同图搜索算法解决问题 4
4 优化处理。 （三）课程思政 通过进一步让学生了解计算机解决问题的基本原理，让学生进一步看清楚机 器的优点和缺点，树立“人是决定因素，同时应当掌握工具以更好改造世界”的 正确观念。 第四章 基本算法策略 （一）基本教学内容 1、迭代算法 2、蛮力法 3、分而治之算法 4、贪婪算法 5、动态规划 6、不同算法的比较 教学重点：不同算法的应用。 教学难点：算法的设计。 （二）基本要求： 1、知识要求：熟悉各种算法策略。 2、能力要求：通过学习，学生能够利用不同算法解决问题。 （三）课程思政 通过对比蛮力法与其他类型的算法策略，让学生树立既要能苦干、也要能巧 干的辩证思想；通过对比各种算法的适用条件，让学生进一步认识到要具体问题 具体分析；通过对各类复杂算法的学校，让学生树立刻苦专研、精益求精的科学 精神。 第五章 搜索算法 （一）基本教学内容 1、图搜索概念 2、广度优先搜索 3、深度优先搜索算法 4、回溯法 5、分支限界法 教学重点：图搜索概念，不同的图搜索算法。 教学难点：图搜索算法。 （二）基本要求： 1、知识要求：理解图搜索概念，掌握各种图搜索算法。 2、能力要求：通过学习，学生能够利用不同图搜索算法解决问题
(三)课程思政 重点通过分支限界法逐步深入的学习过程，引导学生培养逐步深入解决问题、 逐步改进的科研方法。 五、各教学环节学时分配 教学环节 学 习 讨 其他 教学时数 实验 实习 课 课 环节 计 课程内容 第一章 第二章 4 第三章 10 4 14 第四章 6 16 第五章 8 2 10 合计 36 12 48 六、推荐教材和教学参考资源 教材： 吕国英，等.算法设计与分析（第3版），清华大学出版社，2015.6 参考书： [山王晓东.《计算机算法分析与设计（第4版）》北京，电子工业出版社，2012 2]赵端阳编著.《算法分析与设计》.北京：清华大学出版社，2012. [3]石志国，刘冀伟，姚亦飞编著.《算法分析与设计(C+描述)》.北京：清华大学 出版社，2010. 4霍红卫译.《算法分析与设计》北京：人民邮电出版社，2006. [们吴伟旭方世昌译.《算法分析与设计》.北京：电子工业出版社，2004 七、其他说明 大纲修订人：陈建超 修订日期：2020.12.28 大纲审定人： 审定日期： 5
5 （三）课程思政 重点通过分支限界法逐步深入的学习过程，引导学生培养逐步深入解决问题、 逐步改进的科研方法。 五、各教学环节学时分配 教学环节 教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 实习 其他 教学 环节 小 计 第一章 4 4 第二章 4 4 第三章 10 4 14 第四章 10 6 16 第五章 8 2 10 合计 36 12 48 六、推荐教材和教学参考资源 教材： 吕国英，等. 算法设计与分析(第 3 版)，清华大学出版社，2015.6. 参考书： [1] 王晓东.《计算机算法分析与设计（第 4 版）》.北京，电子工业出版社，2012. [2] 赵端阳 编著.《算法分析与设计》.北京：清华大学出版社，2012. [3] 石志国，刘冀伟，姚亦飞 编著.《算法分析与设计（C++描述）》.北京：清华大学 出版社，2010. [4] 霍红卫 译.《算法分析与设计》.北京：人民邮电出版社，2006. [5] 吴伟旭 方世昌译.《算法分析与设计》.北京：电子工业出版社，2004. 七、其他说明 大纲修订人：陈建超 修订日期：2020.12.28 大纲审定人： 审定日期：
6
6