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

《《算法分析与设计》课程教学大纲.docx》由会员分享，可在线阅读，更多相关《《算法分析与设计》课程教学大纲.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析与设计课程教学大纲一、课程基本信息中文名称：算法分析与设计英文名称：Algorithm Analysis and Design开课学院：计算机科学学院课程编码：Z学分：2总学时：36适用专业：计算机技术专业硕士，软件工程专业硕士修读基础：程序设计基础、数据结构课程负责人：黄诚（副教授）主讲教师：黄诚（副教授）二、课程目的任务1 .课程地位作用本课程是计算机科学领域的基础课程，理解算法学理论知识、掌握算法设计和分析 方法，以提高学生的复杂程序设计能力。2 .课程主要内容.学生应达到的基本要求学生通过本课程的学习，能够理解算法及其相关概念，掌握算法效率分析技术，学 握经典算法设计策略的思路

2、及应用，熟悉常见算法问题类型及其常见求解方法，最终具 备问题描述、方案分析、设计算法、编码实现的能力。三、教学内容与学时分配1、算法基础（课内4学时）教学内容：（1）问题和算法的定义：计算问题、问题实例、算法（2）算法的基本特性：通用性、确定性、有限性（3）算法的描述方式（4）计算问题求解框架教学要求：（1）深入理解算法模型的基础概念（2）掌握算法的定义及本质（3）深入理解算法的基本特性（4）熟悉不同的算法描述方式及实际运用（5）理解问题求解框架：问题描述、求解策略、算法设计与分析、程序实现重点：（1）算法定义及其基本特性的理解和掌握（2）熟悉和运用算法的伪代码描述方式（3）理解策略选择、算法

3、设计和程序实现之间的联系和区别难点：理解和把握算法设计策略的抽象性与具体化之间的关系2、算法分析（课内4学时）教学内容：（1）算法的评价指标（2）算法复杂性概念（3）算法时间复杂性分析基本框架（4）算法复杂度的渐近分析原理（5）算法效率类型（5）非递归算法分析（6）递归算法分析（7）求解递归方程教学要求：（1）理解算法评价的不同方面及基本指标：正确性、复杂性（2）掌握算法复杂性定义及内容（3）掌握时间复杂性分析的基本框架：输入规模度量确定、基本操作及其执行次数求 和、渐近符号使用的分析、输入特征的分情况讨论（4）掌握渐近阶符号的数学定义及实质概念（5）深入理解时间复杂性渐近分析的应用：算法的比

4、较、评价、分类（6）掌握非递归和递归算法的分析方法步骤（7）掌握递归方程的基本求解方法：迭代、特征方程、主定理重占.（1）深入理解算法运行时间度量方法（2）熟练掌握时间复杂性分析方法（3）深入理解渐近分析原理与算法效率类型（4）熟练掌握递归方程的主要求解方法难点：（1）理解和掌握算法运行时间的间接度量方法：基本操作的执行次数求和（2）理解和运用递归方程的特征方程求解法3、直接求解法（课内2学时）教学内容：（1）排序与搜索的直接求解算法：选择排序、顺序查找（2）直接求解算法的设计及实现（3）计算几何问题（最近点对等）的直接求解算法及其效率分析（4）组合问题（TSP、0-1背包等）的穷举搜索算法设

5、计及效率分析教学要求：（1）理解直接求解法的本质：基于问题的定义或相关概念（2）掌握典型问题的直接求解算法及其效率分析结果（3）理解典型问题穷举搜索算法设计重点：（1）熟悉并掌握典型问题的直接求解、穷举搜索算法和效率（2）进一步熟练掌握算法时间复杂性的分析和比较难点：理解问题的领域知识、复杂程度与算法设计和分析的难易性之间的关系4、分治法（课内4学时）教学内容：（1）分治法思路及其简单应用（2）归并排序算法、快速排序算法与分治法类型（3）典型问题（大整数乘法等）的分治算法设计（4）计算几何问题（最近点对等）的分治算法设计教学要求：（1）深入理解分治法基本思路：分解输入、合并子解（2）理解分治法

6、类型：处理前分治、分治前处理（3）熟悉典型问题的分治算法设计思路、过程和实现（4）掌握（递归型）分治算法设计及效率分析方法重点：深入理解和掌握分治法的设计思路、适用条件、具体应用及效率分析难点：复杂问题求解中子解合并的方法5、减治法（课内4学时）教学内容：（1）减治法定义及其子类（2）减常量法求解思路及其典型应用（插入排序、组合对象生成等）（3）减常因子法求解思路及其典型应用（折半搜索等）（4）减可变规模法求解思路及其典型应用（插值搜索、快速选择等）教学要求：（1）理解减治法基本思想，掌握减治法3个变种的定义（2）掌握典型（排序、组合对象生成等）问题中的减常量算法设计思路（3）掌握典型（计算、

7、搜索等）问题中的减常因子算法设计思路（4）掌握典型（数值计算、搜索等）问题中的减可变规模算法设计思路（5）掌握选择问题的减可变规模算法设计及实现重点：（1）掌握搜索、组合对象生成的减治算法设计及应用（2）掌握选择（中值）问题的减治算法设计及其扩展应用难点：减可变规模算法的设计与分析6、变治法（课内4学时）教学内容：（1）变治法基本思路（2）基于预排序的算法设计（3）基于实例化简的算法设计（4）基于改变表示的算法设计（5）问题归约及其在算法设计中的应用教学要求：（1）深入理解变治法的实质：变换实例，降低难度（2）掌握基于预排序的常见算法的设计和实现（3）理解和熟悉常见的实例化简算法设计思路（4）

8、熟悉常见的改变表示算法设计思路（5）掌握基于Horner法则的多项式和乘事算法设计（6）理解问题归约的内涵：不同问题实例之间的变换（7）掌握常见的问题归约的（图建模）算法设计重点：（1）基于预排序的算法设计与实现（2）基于Horner法则的算法设计（3）基于图建模的算法设计难点：（1）改变表示中数据表示形式的选择（2）计算问题的结构特征与问题归约7、贪心策略（课内3学时）教学内容：（1）贪心算法的设计思路（2）基于贪心策略的图算法设计（3）典型问题的贪心算法设计与求解教学要求：（1）掌握贪心算法的基本思路：预处理、局部最优选择（2）理解图算法中的贪心策略应用（单源最短路径、MST等）（3）掌握

9、典型问题（活动安排、Huffman编码等）的贪心算法设计（4）理解贪心策略与动态规划的差异重点：贪心算法的主要思路及常见算法设计难点：贪心算法中局部最优选择方法的确定8、动态规划（课内6学时）教学内容：（1）动态规划相关概念及基本思路（2）基于动态规划的图算法设计（3） 0-1背包的动态规划算法设计（4）自顶向下的备忘录算法教学要求：（1）掌握动态规划的算法思路：重复子问题，空间换时间（2）深入理解最优性原理概念：整体最优包含局部最优（3）理解和熟悉图算法中动态规划思路的应用实例（传递闭包、最短路径等）（4）掌握0-1背包的动态规划求解算法设计与实现（5）理解和掌握0-1背包的备忘录式动态规划

10、算法设计与实现重点：（1）动态规划算法的设计思路Floyd算法的设计与实现（2） 0-1背包的动态规划算法设计和应用难点：（1）确定最优解的递归结构（2）动态规划算法工作原理9、回溯法（课内3学时）教学内容：（1）离散问题的状态空间树搜索求解（2）回溯法基本思想（3）典型问题（N皇后、HuamiltonFI路等）的回溯算法设计（4）回溯算法模板及其具体实现（5）组合优化问题（0-1背包、TSP）的回溯算法设计与实现教学要求：（1）深入理解和掌握离散问题的状态空间树含义及其构造（2）掌握回溯法的主要思路：DFS、约束剪枝（3）掌握递归型回溯算法实现模板的具体应用（4）深入理解和掌握0-1背包、T

11、SP问题的回溯算法设计与应用重点：（1）掌握问题解的状态空间树构造及回溯搜索（2）熟悉递归型回溯算法的模板及其实现（3）掌握0-1背包和TSP问题的回溯算法设计及应用难点：状态空间树表示与部分解构造10、分支定界（课内2学时）教学内容：（1）回溯算法中的限界剪枝（2）分支定界的基本思路（3）分支定界与回溯0-1背包的分支定界求解算法设计（3） TSP的分支定界求解算法设计教学要求：（1）掌握分支定界算法的基础方法：界限剪枝、主要思路：最佳优先（2）熟悉队列式分支定界的算法模板（3）掌握0-1背包和TSP问题的分支定界算法设计及应用重点：队列式分支定界算法的设计难点：界限剪枝函数的选择和计算四、考核方式与成绩评定1 .考核方式：小论文及笔试.成绩评定办法：平时讨论（30%）、小论文（20%）、结业笔试（50%）五、教材及主要参考书目算法设计与分析基础（第2版），Anany Levitin,潘彦译，清华大学出版社，2007算法导论（第2版），T.H.Cormen,潘金贵译，机械工业出版社，2006算法学（第3版），D. Harel,霍红卫译，高等教育出版社，2007六：其他需要说明的问题大纲执笔人：黄诚大纲审批机构：计算机科学学院教授委员会2015年9月10日