《算法分析与设计课程教学计划教案.docx》由会员分享，可在线阅读，更多相关《算法分析与设计课程教学计划教案.docx（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计与分析课程教案（Design & Analysis of Computer Algorithms）一、课程基本信息 课程编号：10134060课程类别：专业必修课适用专业：计算机科学与技术学分：3总 学 时：52，其中讲授 44 学时，实验 8 学时先修课程：程序设计基础、离散数学、数据结构后续课程：课程简介：本课程是软件工程专业的重要专业课，是软件技术中面向设计，处于核心地位的教育课程，无论是计算机系统、系统软件还是解决计算机的各种应用课题都可归结为算法设计。本课程系统介绍许多经典的非数值算法，算法分析的基本方法，以及算法复杂性的相关知识。主要教学方法与手段：课堂多媒体课件结合实验选
2、用教材：沈孝钧编著计算机算法基础、机械工业出版社、2014年。必读书目：1. Thomas H. Cormen，etc. Introduction to Algorithms,Second edition.MIT Press,2001.3。2. 王晓东，算法设计与分析，清华大学出版社，2003.1。选读书目：1. Sara Baase，Allen Van Gelder，Computer Algorithms : Introduction to Design and Analysis (Third Edition)（影印版），高等教育出版社，2001.6。2. Sartaj Sahni，数据结构
3、、算法与应用，北京：机械出版社，2000。二、课程总目标：本课程通过系统讲授算法分析的基本方法，使学生掌握基本的算法设计技术。在算法分析设计的数学基础训练中，以提高学生算法设计与分析的素质和能力。通过该课程的学习和上机实习，使学生掌握通用算法的几种设计方法，以及学会对算法的时间和空间的复杂性进行分析，建立下界理论的概念；同时通过讲授 NP 理论的主要概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础。三、课程教学内容与教学要求1、教学内容与学时分配课程总学时：48其中讲授学时：40实验(上机)学时：8 课程安排见下表：2 第二章分治法67第七章 NP 完全问题73 第三章动态规划64
4、第四章图遍历算法65 第五章贪心算法6合计44序号章目名称讲授学时 序号分配章目名称1第一章 算法基础知识66第六章 最大流算法讲授学时分配72. 教学要求（1） 以培养学生独立思考、分析问题和解决问题的能力为主要目标，进行讨论式教学，不要求学生死记硬背。（2） 本课程强调严谨的思考方法，培养学生利用所学的数学知识分析解决问题能力。第一章算法基础知识教学目标：了解算法的基本概念及其与其他学科的关系，掌握算法复杂度的渐进表示及复杂性分析的基本方法和正确性证明的基本技术。教学内容： 第一节基本概念一、算法的概念和特征二、算法与其他 IT 学科的联系三、评价算法的标准第二节算法分析一、算法的正确性分
5、析二、算法的复杂性分析教学要求：重点介绍算法复杂度的渐进表示，以及算法复杂性分析的替换法、递归树法和 master 定理。第二章分治法教学目标：掌握分治策略分析问题的基本思路和分析方法， 了解典型的分治策略算法。教学内容：第一节分治策略简介一、分治策略的基本步骤二、折半查找和归并排序第二节快速排序的性能分析一、快速排序算法二、复杂性分析第三节中位数选择与最接近点对一、随机中位数选择算法二、确定的中位数选择算法三、最接近点对第四节大整数相乘与矩阵乘一、大整数相乘二、矩阵乘教学要求：重点介绍分治策略设计算法的基本步骤及分治法解决问题的设计思路。第三章动态规划教学目标：掌握动态规划分析问题的基本思路
6、和分析方法， 了解典型的动态规划算法。教学内容：第一节最长公共子序列与动态规划一、最长公共子序列二、动态规划方法第二节矩阵连乘一、矩阵连乘问题二、动态规划算法第三节 最优二叉查找树一、最优二叉查找树问题二、动态规划算法教学要求：重点介绍动态规划设计算法的基本步骤、最优子结构性质的证明方法和利用最优子结构性质写出求解最优解值递归关系的过程。第四章图遍历算法教学目标：掌握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 广度优先搜索一、广度优先搜索算法 二、广度优先算法的应用第二节 深度优先搜索算法一、深度优先搜索算法 二、深度优先搜索的性质三、深度优先搜索的应用教学要求
7、：重点讲授广度优先搜索和深度优先搜索算法和区间套及白路径定理。第五章贪心算法教学目标：掌握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 活动场所选择与贪心策略一、活动场所选择二、贪心策略第二节 贪心算法的应用一、哈夫曼编码问题二、最小费用生成树教学要求：重点介绍贪心策略分析问题的基本方法及思路， 和贪心选择性质证明的基本思路。第六章最大流算法教学目标：掌握最大流问题的定义，最大流-最小割定理，福特-福克森算法。了解埃德蒙-卡普算法。教学内容： 第一节 基本概念一、最大流问题定义 二、最大流最小割定理第二节 最大流算法一、Ford-Fulkerson 算法二、Edm
8、ond-Karp 算法教学要求：重点介绍最大流-最小割定理，剩余网络及福特- 福克森算法。本课程是软件工程专业的重要专业课，是软件技术中面向设计，处于核心地位的教育课程，无论是计算机系统、系统软件还是解决计算机的各种应用课题都可归结为算法设计。本课程系统介绍许多经典的非数值算法，算法分析的基本方法，以及算法复杂性的相关知识。主要教学方法与手段：课堂多媒体课件结合实验选用教材：沈孝钧编著计算机算法基础、机械工业出版社、2014年。必读书目：1. Thomas H. Cormen，etc. Introduction to Algorithms, Second edition.MIT Press,2
9、001.3。2. 王晓东，算法设计与分析，清华大学出版社，2003.1。选读书目：1. Sara Baase，Allen Van Gelder，Computer Algorithms : Introduction to Design and Analysis (Third Edition)（影印版），高等教育出版社，2001.6。2. Sartaj Sahni，数据结构、算法与应用，北京：机械出版社，2000。二、课程总目标：本课程通过系统讲授算法分析的基本方法，使学生掌握基本的算法设计技术。在算法分析设计的数学基础训练中，以提高学生算法设计与分析的素质和能力。通过该课程的学习和上机实习，使学
10、生掌握通用算法的几种设计方法，以及学会对算法的时间和空间的复杂性进行分析，建立下界理论的概念；同时通过讲授 NP 理论的主要概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础。三、课程教学内容与教学要求1、教学内容与学时分配课程总学时：48其中讲授学时：40实验(上机)学时：8 课程安排见下表：序号章目名称讲授学时 序号分配章目名称1第一章 算法基础知识第二章 分治法第三章 动态规划第四章 图遍历算法66第六章 最大流算法讲授学时分配72346667第七章 NP 完全问题75 第五章 贪心算法6合计442. 教学要求（1） 以培养学生独立思考、分析问题和解决问题的能力为主要目标，进行讨
11、论式教学，不要求学生死记硬背。（2） 本课程强调严谨的思考方法，培养学生利用所学的数学知识分析解决问题能力。第七章算法基础知识教学目标：了解算法的基本概念及其与其他学科的关系，掌握算法复杂度的渐进表示及复杂性分析的基本方法和正确性证明的基本技术。教学内容： 第一节基本概念一、算法的概念和特征二、算法与其他 IT 学科的联系三、评价算法的标准第二节算法分析一、算法的正确性分析二、算法的复杂性分析教学要求：重点介绍算法复杂度的渐进表示，以及算法复杂性分析的替换法、递归树法和 master 定理。第八章分治法教学目标：掌握分治策略分析问题的基本思路和分析方法， 了解典型的分治策略算法。教学内容：第一
12、节分治策略简介一、分治策略的基本步骤二、折半查找和归并排序第二节快速排序的性能分析一、快速排序算法二、复杂性分析第三节中位数选择与最接近点对一、随机中位数选择算法二、确定的中位数选择算法三、最接近点对第四节大整数相乘与矩阵乘一、大整数相乘二、矩阵乘教学要求：重点介绍分治策略设计算法的基本步骤及分治法解决问题的设计思路。第九章动态规划教学目标：掌握动态规划分析问题的基本思路和分析方法， 了解典型的动态规划算法。教学内容：第一节最长公共子序列与动态规划一、最长公共子序列二、动态规划方法第二节矩阵连乘一、矩阵连乘问题二、动态规划算法第三节 最优二叉查找树一、最优二叉查找树问题二、动态规划算法教学要求
13、：重点介绍动态规划设计算法的基本步骤、最优子结构性质的证明方法和利用最优子结构性质写出求解最优解值递归关系的过程。第十章图遍历算法教学目标：掌握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 广度优先搜索一、广度优先搜索算法 二、广度优先算法的应用第二节 深度优先搜索算法一、深度优先搜索算法 二、深度优先搜索的性质三、深度优先搜索的应用教学要求：重点讲授广度优先搜索和深度优先搜索算法和区间套及白路径定理。第十一章贪心算法教学目标：掌握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 活动场所选择与贪心策略一、活动场所选择二、贪心策略第二节
14、贪心算法的应用一、哈夫曼编码问题二、最小费用生成树教学要求：重点介绍贪心策略分析问题的基本方法及思路， 和贪心选择性质证明的基本思路。第十二章最大流算法教学目标：掌握最大流问题的定义，最大流-最小割定理，福特-福克森算法。了解埃德蒙-卡普算法。教学内容： 第一节 基本概念一、最大流问题定义 二、最大流最小割定理第二节 最大流算法一、Ford-Fulkerson 算法二、Edmond-Karp 算法教学要求：重点介绍最大流-最小割定理，剩余网络及福特- 福克森算法。第十三章NP 完全问题教学目标：掌握 P 类，NP 类和NPC 的定义。了解 NP 完全问题的证明过程及思路。教学内容： 第一节 基
15、本概念一、P 和NP 二、NP 完全性第二节 NP 完全问题的证明一、NP 完全的证明方法二、NP 完全问题的证明教学要求：重点讲授P 类、NP 类和 NPC 的定义，Cook 定理和NP 完全的证明方法及过程。3. 实验序实验项目号名称学时实验内容和实验目标实验性质实验内容：实现插入排序、归并排1排序算法比较4序和快速排序算法。实验目标：掌握分治算法的实现， 了解算法的比较方法。实验内容：布置的有关动态规划问题作业。实验目标:掌握采用动态规划思路分析问题的方法和动态规划算法的设计实现。实验内容：布置的有关贪心算法问题作业。实验目标：掌握贪心策略分析问题的方法和贪心算法的设计实现。验证2动态规
16、划算法2验证设计3贪心算法2验证设计四、课程考核考试以闭卷为主(70%)，着重检查对算法分析与设计的基本方法掌握情况，及培养学生分析问题解决问题的能力。平时成绩30%，考察作业、读书报告和出勤率。第十四章NP 完全问题教学目标：掌握 P 类，NP 类和NPC 的定义。了解 NP 完全问题的证明过程及思路。教学内容： 第一节 基本概念一、P 和NP二、NP 完全性第二节 NP 完全问题的证明一、NP 完全的证明方法二、NP 完全问题的证明教学要求：重点讲授P 类、NP 类和 NPC 的定义，Cook 定理和NP 完全的证明方法及过程。3. 实验软件工程专业的重要专业课，是软件技术中面向设计， 处
17、于核心地位的教育课程，无论是计算机系统、系统软件还是解决计算机的各种应用课题都可归结为算法设计。本课程系统介绍许多经典的非数值算法，算法分析的基本方法，以及算法复杂性的相关知识。主要教学方法与手段：课堂多媒体课件结合实验选用教材：沈孝钧编著计算机算法基础、机械工业出版社、2014年。必读书目：1. Thomas H. Cormen，etc. Introduction to Algorithms, Second edition.MIT Press,2001.3。2. 王晓东，算法设计与分析，清华大学出版社，2003.1。选读书目：1. Sara Baase，Allen Van Gelder，Co
18、mputer Algorithms : Introduction to Design and Analysis (Third Edition)（影印版），高等教育出版社，2001.6。2. Sartaj Sahni，数据结构、算法与应用，北京：机械出版社，2000。二、课程总目标：本课程通过系统讲授算法分析的基本方法，使学生掌握基本的算法设计技术。在算法分析设计的数学基础训练中，以提高学生算法设计与分析的素质和能力。通过该课程的学习和上机实习，使学生掌握通用算法的几种设计方法，以及学会对算法的时间和空间的复杂性进行分析，建立下界理论的概念；同时通过讲授 NP 理论的主要概念及一些近似算法，为学
19、生从事计算机算法的研究工作奠定基础。三、课程教学内容与教学要求1、教学内容与学时分配课程总学时：48其中讲授学时：40实验(上机)学时：8 课程安排见下表：2 第二章分治法67第七章 NP 完全问题73 第三章动态规划64 第四章图遍历算法65 第五章贪心算法6合计44序号章目名称讲授学时 序号分配章目名称1第一章 算法基础知识66第六章 最大流算法讲授学时分配72. 教学要求（1） 以培养学生独立思考、分析问题和解决问题的能力为主要目标，进行讨论式教学，不要求学生死记硬背。（2） 本课程强调严谨的思考方法，培养学生利用所学的数学知识分析解决问题能力。第十五章算法基础知识教学目标：了解算法的基
20、本概念及其与其他学科的关系，掌握算法复杂度的渐进表示及复杂性分析的基本方法和正确性证明的基本技术。教学内容： 第一节基本概念一、算法的概念和特征二、算法与其他 IT 学科的联系三、评价算法的标准第二节算法分析一、算法的正确性分析二、算法的复杂性分析教学要求：重点介绍算法复杂度的渐进表示，以及算法复杂性分析的替换法、递归树法和 master 定理。第十六章分治法教学目标：掌握分治策略分析问题的基本思路和分析方法， 了解典型的分治策略算法。教学内容：第一节分治策略简介一、分治策略的基本步骤二、折半查找和归并排序第二节快速排序的性能分析一、快速排序算法二、复杂性分析第三节中位数选择与最接近点对一、随
21、机中位数选择算法二、确定的中位数选择算法三、最接近点对第四节大整数相乘与矩阵乘一、大整数相乘二、矩阵乘教学要求：重点介绍分治策略设计算法的基本步骤及分治法解决问题的设计思路。第十七章动态规划教学目标：掌握动态规划分析问题的基本思路和分析方法，了解典型的动态规划算法。教学内容：第一节最长公共子序列与动态规划一、最长公共子序列二、动态规划方法第二节矩阵连乘一、矩阵连乘问题二、动态规划算法第三节 最优二叉查找树一、最优二叉查找树问题二、动态规划算法教学要求：重点介绍动态规划设计算法的基本步骤、最优子结构性质的证明方法和利用最优子结构性质写出求解最优解值递归关系的过程。第十八章 图遍历算法教学目标：掌
22、握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 广度优先搜索一、广度优先搜索算法 二、广度优先算法的应用第二节 深度优先搜索算法一、深度优先搜索算法 二、深度优先搜索的性质三、深度优先搜索的应用教学要求：重点讲授广度优先搜索和深度优先搜索算法和区间套及白路径定理。第十九章贪心算法教学目标：掌握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 活动场所选择与贪心策略一、活动场所选择二、贪心策略第二节 贪心算法的应用一、哈夫曼编码问题二、最小费用生成树教学要求：重点介绍贪心策略分析问题的基本方法及思路， 和贪心选择性质证明的基本思路。第二十章
23、最大流算法教学目标：掌握最大流问题的定义，最大流-最小割定理，福特-福克森算法。了解埃德蒙-卡普算法。教学内容： 第一节 基本概念一、最大流问题定义 二、最大流最小割定理第二节 最大流算法一、Ford-Fulkerson 算法二、Edmond-Karp 算法教学要求：重点介绍最大流-最小割定理，剩余网络及福特- 福克森算法。本课程是软件工程专业的重要专业课，是软件技术中面向设计，处于核心地位的教育课程，无论是计算机系统、系统软件还是解决计算机的各种应用课题都可归结为算法设计。本课程系统介绍许多经典的非数值算法，算法分析的基本方法，以及算法复杂性的相关知识。主要教学方法与手段：课堂多媒体课件结合
24、实验选用教材：沈孝钧编著计算机算法基础、机械工业出版社、2014年。必读书目：1. Thomas H. Cormen，etc. Introduction to Algorithms, Second edition.MIT Press,2001.3。2. 王晓东，算法设计与分析，清华大学出版社，2003.1。选读书目：1. Sara Baase，Allen Van Gelder，Computer Algorithms : Introduction to Design and Analysis (Third Edition)（影印版），高等教育出版社，2001.6。2. Sartaj Sahni，
25、数据结构、算法与应用，北京：机械出版社，2000。二、课程总目标：本课程通过系统讲授算法分析的基本方法，使学生掌握基本的算法设计技术。在算法分析设计的数学基础训练中，以提高学生算法设计与分析的素质和能力。通过该课程的学习和上机实习，使学生掌握通用算法的几种设计方法，以及学会对算法的时间和空间的复杂性进行分析，建立下界理论的概念；同时通过讲授 NP 理论的主要概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础。三、课程教学内容与教学要求1、教学内容与学时分配课程总学时：48其中讲授学时：40实验(上机)学时：8 课程安排见下表：2 第二章分治法67第七章 NP 完全问题73 第三章动态规
26、划64 第四章图遍历算法65 第五章贪心算法6合计44序号章目名称讲授学时 序号分配章目名称1第一章 算法基础知识66第六章 最大流算法讲授学时分配72. 教学要求（1） 以培养学生独立思考、分析问题和解决问题的能力为主要目标，进行讨论式教学，不要求学生死记硬背。（2） 本课程强调严谨的思考方法，培养学生利用所学的数学知识分析解决问题能力。第二十一章 算法基础知识教学目标：了解算法的基本概念及其与其他学科的关系，掌握算法复杂度的渐进表示及复杂性分析的基本方法和正确性证明的基本技术。教学内容： 第一节基本概念一、算法的概念和特征二、算法与其他 IT 学科的联系三、评价算法的标准第二节算法分析一、
27、算法的正确性分析二、算法的复杂性分析教学要求：重点介绍算法复杂度的渐进表示，以及算法复杂性分析的替换法、递归树法和 master 定理。第二十二章 分治法教学目标：掌握分治策略分析问题的基本思路和分析方法， 了解典型的分治策略算法。教学内容：第一节分治策略简介一、分治策略的基本步骤二、折半查找和归并排序第二节快速排序的性能分析一、快速排序算法二、复杂性分析第三节中位数选择与最接近点对一、随机中位数选择算法二、确定的中位数选择算法三、最接近点对第四节大整数相乘与矩阵乘一、大整数相乘二、矩阵乘教学要求：重点介绍分治策略设计算法的基本步骤及分治法解决问题的设计思路。第二十三章 动态规划教学目标：掌握
28、动态规划分析问题的基本思路和分析方法， 了解典型的动态规划算法。教学内容：第一节最长公共子序列与动态规划一、最长公共子序列二、动态规划方法第二节矩阵连乘一、矩阵连乘问题二、动态规划算法第三节 最优二叉查找树一、最优二叉查找树问题二、动态规划算法教学要求：重点介绍动态规划设计算法的基本步骤、最优子结构性质的证明方法和利用最优子结构性质写出求解最优解值递归关系的过程。第二十四章图遍历算法教学目标：掌握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 广度优先搜索一、广度优先搜索算法 二、广度优先算法的应用第二节 深度优先搜索算法一、深度优先搜索算法 二、深度优先搜索的性质
29、三、深度优先搜索的应用教学要求：重点讲授广度优先搜索和深度优先搜索算法和区间套及白路径定理。第二十五章 贪心算法教学目标：掌握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 活动场所选择与贪心策略一、活动场所选择二、贪心策略第二节 贪心算法的应用一、哈夫曼编码问题二、最小费用生成树教学要求：重点介绍贪心策略分析问题的基本方法及思路， 和贪心选择性质证明的基本思路。第二十六章 最大流算法教学目标：掌握最大流问题的定义，最大流-最小割定理，福特-福克森算法。了解埃德蒙-卡普算法。教学内容： 第一节 基本概念一、最大流问题定义 二、最大流最小割定理第二节 最大流算法一、F
30、ord-Fulkerson 算法二、Edmond-Karp 算法教学要求：重点介绍最大流-最小割定理，剩余网络及福特- 福克森算法。第二十七章 NP 完全问题教学目标：掌握 P 类，NP 类和NPC 的定义。了解 NP 完全问题的证明过程及思路。教学内容： 第一节 基本概念一、P 和NP 二、NP 完全性第二节 NP 完全问题的证明一、NP 完全的证明方法二、NP 完全问题的证明教学要求：重点讲授P 类、NP 类和 NPC 的定义，Cook 定理和NP 完全的证明方法及过程。3. 实验序实验项目号名称学时实验内容和实验目标实验性质实验内容：实现插入排序、归并排1排序算法比较4序和快速排序算法。
31、实验目标：掌握分治算法的实现， 了解算法的比较方法。实验内容：布置的有关动态规划问题作业。实验目标:掌握采用动态规划思路分析问题的方法和动态规划算法的设计实现。实验内容：布置的有关贪心算法问题作业。实验目标：掌握贪心策略分析问题的方法和贪心算法的设计实现。验证2动态规划算法2验证设计3贪心算法2验证设计五、课程考核考试以闭卷为主(70%)，着重检查对算法分析与设计的基本方法掌握情况，及培养学生分析问题解决问题的能力。平时成绩30%，考察作业、读书报告和出勤率。第二十八章 NP 完全问题教学目标：掌握 P 类，NP 类和NPC 的定义。了解 NP 完全问题的证明过程及思路。教学内容： 第一节 基
32、本概念一、P 和NP二、NP 完全性第二节 NP 完全问题的证明一、NP 完全的证明方法二、NP 完全问题的证明教学要求：重点讲授P 类、NP 类和 NPC 的定义，Cook 定理和NP 完全的证明方法及过程。3. 实验序实验项目学实验内容和实验目标实验号名称时性质实验内容：实现插入排序、归并排1 排序算法4序和快速排序算法。验证比较实验目标：掌握分治算法的实现，了解算法的比较方法。实验内容：布置的有关动态规划问动态规划题作业。验证2 2实验目标:掌握采用动态规划思路算法分析问题的方法和动态规划算法的设计设计实现。实验内容：布置的有关贪心算法问3 贪心算法2题作业。验证实验目标：掌握贪心策略分
33、析问题设计的方法和贪心算法的设计实现。软件工程专业的重要专业课，是软件技术中面向设计，处于核心地位的教育课程，无论是计算机系统、系统软件还是解决计算机的各种应用课题都可归结为算法设计。本课程系统介绍许多经典的非数值算法，算法分析的基本方法，以及算法复杂性的相关知识。主要教学方法与手段：课堂多媒体课件结合实验选用教材：沈孝钧编著计算机算法基础、机械工业出版社、2014年。必读书目：1. Thomas H. Cormen，etc. Introduction to Algorithms, Second edition.MIT Press,2001.3。2. 王晓东，算法设计与分析，清华大学出版社，2
34、003.1。选读书目：1. Sara Baase，Allen Van Gelder，Computer Algorithms : Introduction to Design and Analysis (Third Edition)（影印版），高等教育出版社，2001.6。2. Sartaj Sahni，数据结构、算法与应用，北京：机械出版社，2000。二、课程总目标：本课程通过系统讲授算法分析的基本方法，使学生掌握基本的算法设计技术。在算法分析设计的数学基础训练中，以提高学生算法设计与分析的素质和能力。通过该课程的学习和上机实习，使学生掌握通用算法的几种设计方法，以及学会对算法的时间和空间的复
35、杂性进行分析，建立下界理论的概念；同时通过讲授 NP 理论的主要概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础。三、课程教学内容与教学要求1、教学内容与学时分配课程总学时：48其中讲授学时：40实验(上机)学时：8 课程安排见下表：序号章目名称讲授学时 序号分配章目名称1第一章 算法基础知识第二章 分治法66第六章 最大流算法讲授学时分配7267第七章 NP 完全问题73 第三章 动态规划4 第四章 图遍历算法5 第五章 贪心算法666合计442. 教学要求（1） 以培养学生独立思考、分析问题和解决问题的能力为主要目标，进行讨论式教学，不要求学生死记硬背。（2） 本课程强调严谨的思
36、考方法，培养学生利用所学的数学知识分析解决问题能力。第二十九章 算法基础知识教学目标：了解算法的基本概念及其与其他学科的关系，掌握算法复杂度的渐进表示及复杂性分析的基本方法和正确性证明的基本技术。教学内容： 第一节基本概念一、算法的概念和特征二、算法与其他 IT 学科的联系三、评价算法的标准第二节算法分析一、算法的正确性分析二、算法的复杂性分析教学要求：重点介绍算法复杂度的渐进表示，以及算法复杂性分析的替换法、递归树法和 master 定理。第三十章分治法教学目标：掌握分治策略分析问题的基本思路和分析方法， 了解典型的分治策略算法。教学内容：第一节分治策略简介一、分治策略的基本步骤二、折半查找
37、和归并排序第二节快速排序的性能分析一、快速排序算法二、复杂性分析第三节中位数选择与最接近点对一、随机中位数选择算法 二、确定的中位数选择算法三、最接近点对第四节大整数相乘与矩阵乘一、大整数相乘二、矩阵乘教学要求：重点介绍分治策略设计算法的基本步骤及分治法解决问题的设计思路。第三十一章 动态规划教学目标：掌握动态规划分析问题的基本思路和分析方法， 了解典型的动态规划算法。教学内容：第一节最长公共子序列与动态规划一、最长公共子序列二、动态规划方法第二节矩阵连乘一、矩阵连乘问题二、动态规划算法第三节 最优二叉查找树一、最优二叉查找树问题二、动态规划算法教学要求：重点介绍动态规划设计算法的基本步骤、最
38、优子结构性质的证明方法和利用最优子结构性质写出求解最优解值递归关系的过程。第三十二章图遍历算法教学目标：掌握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 广度优先搜索一、广度优先搜索算法 二、广度优先算法的应用第二节 深度优先搜索算法一、深度优先搜索算法二、深度优先搜索的性质三、深度优先搜索的应用教学要求：重点讲授广度优先搜索和深度优先搜索算法和区间套及白路径定理。第三十三章 贪心算法教学目标：掌握图遍历的广度优先算法和深度优先算法，了解图遍历算法的应用。教学内容：第一节 活动场所选择与贪心策略一、活动场所选择二、贪心策略第二节 贪心算法的应用一、哈夫曼编码问题二
39、、最小费用生成树教学要求：重点介绍贪心策略分析问题的基本方法及思路， 和贪心选择性质证明的基本思路。第三十四章 最大流算法教学目标：掌握最大流问题的定义，最大流-最小割定理，福特-福克森算法。了解埃德蒙-卡普算法。教学内容： 第一节 基本概念一、最大流问题定义 二、最大流最小割定理第二节 最大流算法一、Ford-Fulkerson 算法二、Edmond-Karp 算法教学要求：重点介绍最大流-最小割定理，剩余网络及福特- 福克森算法。本课程是软件工程专业的重要专业课，是软件技术中面向设计，处于核心地位的教育课程，无论是计算机系统、系统软件还是解决计算机的各种应用课题都可归结为算法设计。本课程系
40、统介绍许多经典的非数值算法，算法分析的基本方法，以及算法复杂性的相关知识。主要教学方法与手段：课堂多媒体课件结合实验选用教材：沈孝钧编著计算机算法基础、机械工业出版社、2014年。必读书目：1. Thomas H. Cormen，etc. Introduction to Algorithms, Second edition.MIT Press,2001.3。2. 王晓东，算法设计与分析，清华大学出版社，2003.1。选读书目：1. Sara Baase，Allen Van Gelder，Computer Algorithms : Introduction to Design and Analy
41、sis (Third Edition)（影印版），高等教育出版社，2001.6。2. Sartaj Sahni，数据结构、算法与应用，北京：机械出版社，2000。二、课程总目标：本课程通过系统讲授算法分析的基本方法，使学生掌握基本的算法设计技术。在算法分析设计的数学基础训练中，以提高学生算法设计与分析的素质和能力。通过该课程的学习和上机实习，使学生掌握通用算法的几种设计方法，以及学会对算法的时间和空间的复杂性进行分析，建立下界理论的概念；同时通过讲授 NP 理论的主要概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础。三、课程教学内容与教学要求1、教学内容与学时分配课程总学时：48其中
42、讲授学时：40实验(上机)学时：8 课程安排见下表：2 第二章分治法67第七章 NP 完全问题73 第三章动态规划64 第四章图遍历算法65 第五章贪心算法6合计44序号章目名称讲授学时 序号分配章目名称1第一章 算法基础知识66第六章 最大流算法讲授学时分配72. 教学要求（1） 以培养学生独立思考、分析问题和解决问题的能力为主要目标，进行讨论式教学，不要求学生死记硬背。（2） 本课程强调严谨的思考方法，培养学生利用所学的数学知识分析解决问题能力。第三十五章 算法基础知识教学目标：了解算法的基本概念及其与其他学科的关系，掌握算法复杂度的渐进表示及复杂性分析的基本方法和正确性证明的基本技术。教
43、学内容： 第一节基本概念一、算法的概念和特征二、算法与其他 IT 学科的联系三、评价算法的标准第二节算法分析一、算法的正确性分析二、算法的复杂性分析教学要求：重点介绍算法复杂度的渐进表示，以及算法复杂性分析的替换法、递归树法和 master 定理。第三十六章 分治法教学目标：掌握分治策略分析问题的基本思路和分析方法， 了解典型的分治策略算法。教学内容：第一节分治策略简介一、分治策略的基本步骤二、折半查找和归并排序第二节快速排序的性能分析一、快速排序算法二、复杂性分析第三节中位数选择与最接近点对一、随机中位数选择算法二、确定的中位数选择算法三、最接近点对第四节大整数相乘与矩阵乘一、大整数相乘二、矩阵乘教学要求：重点介绍分治策略设计算法的基本步骤及分治法解决问题的设计思路。第三十七章 动态规划教学目标：掌握动态规划分析问题的基本思路和分析方法， 了解典型的动态规划算法。教学内容：第一节最长公共子序列与动态规划一、最长公共子序列二、动态规划方法第二节矩阵连乘一、矩阵连乘问题二、动态