1、算法设计与分析教学大纲教学内容及要求一、课程简介设计良好的程序不仅仅需要语言的学习，更需要合理的数据组织和清晰高效的算法,这正是计算机科学领域里数据结构和算法设计所研究的主要内容。此门课程面向计算机软件工程专业，目前设置为专业基础课程。该课程覆盖了计算机软件开发中使用到的大部分算法，并且具有一定的深度和广度，侧重于理论与技能的相互结合。课程主要包含了时空复杂度分析、递归与分治、动态规划、贪心算法、回溯法、分支限界法等内容。二、教学目的与要求通过本课程的学习，学生可以对软件实现中常用算法有一个比较全面的了解，在能够解决问题的基础上学会分析算法、估算相应的时空复杂度、调整相应的算法结构以达到较好的
2、效果。该门课程的学习要求掌握一门高级计算机语言的基本应用，以及具备常用数据结构的基本知识。三、主要内容与学时分配第1章 算法引论 (6课时)目的与要求：了解计算机算法的概念、算法复杂度渐进表示的含义以及计算方法、分析方法重点与难点：算法复杂度的计算内容：算法的概念、算法与其他计算机课程之间的关系、算法复杂度的表示、分析与计算第2章 递归与分治策略 (8课时)目的与要求：了解和掌握最基本的算法设计方法、递归算法的复杂度计算方法、分而治之算法的设计和分析重点与难点：递归算法的实现过程与机制、分治法的计算效率内容：递归的概念、分治法的基本思想、二分搜索技术、合并排序、快速排序第3章 动态规划 (8课
3、时)目的与要求：了解和掌握动态规划算法的基本要素、解决最优化问题的基本过程与思路重点与难点：最优解性质与结构特征的刻画、最优值的递归定义与计算内容： 动态规划算法的基本思想、最长公共子序列、0-1背包问题第4章 贪心算法 (8课时)目的与要求：了解和掌握贪心算法的基本要素、贪心算法与动态规划算法的主要差别、算法问题的解决思路与计算复杂性重点与难点：算法问题的贪心选择性质、最优子结构性质内容：贪心算法的基本思想、活动安排问题、单源最短路径、最小生成树第5章 回溯法 (8课时)目的与要求：了解和掌握回溯法的解空间、基本思想、递归与迭代回溯、子集树与排列树、算法应用的典型问题重点与难点：解空间的深度
4、优先实现、剪枝函数的确定内容：回溯法的算法框架、批处理作业调度、0-1背包问题 第6章 分支限界法 (8课时)目的与要求：了解和掌握分支限界法的基本思想、分支限界与回溯法的区别、具体代码实现重点与难点：扩展节点的生成方式及其实现内容：分支限界法的基本思想、单源最短路径问题、0-1背包问题第7章 高级主题 （10课时)目的与要求：了解概率算法、NP算法、近似算法等非经典但很实用的算法设计思想，在遇到实际问题时能知道如何求解问题重点与难点：概率算法、NP算法、近似算法的基本思想内容： 数值概率算法等等、典型NP完全问题介绍、旅行售货员问题近似算法等等。教材及参考书目1、王晓东. 算法设计与分析（第2版）. 清华大学出版社，2010年2、刘璟. 计算机算法引论设计与分析技术. 科学出版社，2005年2 / 2
