算法分析與设计理论教学大纲.docVIP

算法分析与设计 Design and Analysis of Algorithm 适用范围：2012本科人才培养方案 课程编号：1504108170 学 分：3学分 学 时：48学时（其中：讲课学时：38 实验学时：10 ） 先修课程：C++程序设计、数据结构 适用专业：软件工程 教 材：《计算机算法设计与分析》，王晓东主编，清华大学出版社，2008 开课单位：软件学院 一、课程的性质与任务 课程性质：本课程是软件工程专业软件设计方向的一门专业方向任选课。 课程任务：本课程的任务是使学生通过本大纲所规定的全部教学内容的学习，掌握当前主要算法技术的工作原理，而且能理解该算法产生的背景和设计理念，使其能灵活运用这些技术，结合实际情况设计合适的算法解决问题。 二、课程的基本内容及要求 （一）算法引论 1．课程教学内容 （1）算法与程序 （2）表达算法的抽象机制 （3）描述算法 （4）算法复杂性分析 2．课程重点、难点 重点：描述算法；算法复杂性分析。 难点：算法复杂性分析。 3．课程教学要求 （1）理解程序与算法的区别和内在联系； （2）掌握求解问题的一般步骤； （3）掌握算法复杂性的渐进性的数学表述，能够估算算法运算时间。 （二）?递归与分治策略 1．课程教学内容 （1）递归的概念 （2）分治法的基本思想 （3）二分有哪些信誉好的足球投注网站技术 （4）大整数的乘法 （5）Strassen矩阵乘法 （6）棋盘覆盖 （7）排序 2．课程重点难点 重点：递归和分治策略。 难点：分治策略。 3．课程教学要求 （1）理解递归调用的实现原理 （2）掌握两种递归转换原则； （3）掌握利用分治法解决问题的基本思想； （4）掌握算法的思想。 （三）动态规划 1．课程教学内容 （1）动态规划的基本要素 （2）最长公共子序列 （3）多边形游戏 （4）图像压缩 （5）流水作业调度 （6）0－1背包问题 （7）最优二叉有哪些信誉好的足球投注网站树 2．课程重点难点 重点：动态规划；0－1背包问题。 难点：0－1背包问题。 3．课程教学要求 （1）理解适用动态规划进行优化的问题的基本特点； （2）掌握利用动态规划方法解决问题的基本思想； （3）掌握动态规划算法的基本要素。 （四）贪心算法 1．课程教学内容 （1）贪心算法的基本要素 （2）最优装载 （3）哈夫曼编码 （4）单源最短路径 （5）最小生成树 （6）多机调度问题 （7）贪心算法的理论基础? 2．课程重点难点 重点：贪心算法。 难点：无。 3．课程教学要求 （1）掌握利用贪心算法的基本原理和问题性质分析； （2）掌握算法的复杂度，可靠性分析； （3）掌握贪心算法性质的证明。 （五）回溯法 1．课程教学内容 （1）回溯法的算法框架、符号 （2）装载问题 （3）批作业处理问题 （4）n皇后问题 （5）0-1背包问题 （6）最大团问题 （7）图的m着色问题 （8）旅行售货员问题 （9）圆排列问题 （10）连续邮资问题 2．课程重点难点 重点：回溯法的效率分析。 难点：无。 3．课程教学要求 （1）理解各种剪枝策略； （2）掌握回溯算法程序设计方法； （3）掌握回溯法的效率及稳定性。 （六）分支限界法 1．课程教学内容 （1）分支限界的基本思想 （2）单源最短路径 （3）装载问题 （3）布线问题 （4）旅行售货员问题 （5）0-1背包问题 （6）最大团问题 2．课程重点难点 重点：分支限界；0-1背包问题；最大团问题。 难点：最大团问题。 3．课程教学要求 （1）理解分支限界的基本思想； （2）掌握利用分支限界法解决问题的基本思想； （3）掌握各方法的效率。 （七）概率算法 1．课程教学内容 （1）随机数 （2）数值概率算法 （3）舍伍德算法 （4）拉斯维加斯算法 （5）蒙特卡罗算法 2．课程重点难点 重点：随机数；拉斯维加斯算法；蒙特卡罗算法。 难点：拉斯维加斯算法；蒙特卡罗算法。 3．课程教学要求 （1）理解随机数的概念； （2）掌握概率算法的基本思想； （3）掌握各种算法应用。 （八）NP完全性理论 1．课程教学内容 （1）P类与NP类问题 （2）NP完全问题 （3）合取范式（CNF） （4）顶点覆盖问题 （5）哈密顿回路问题 2．课程重点难点 重点：NP问题。 难点：无。 3．课程教学要求 （1）了解集中模型的定义、能力； （2）掌握P类与NP类问题的划分； （3）掌握顶点覆盖。 （4）掌握哈密顿回路 （九）近似算法 1．课程教学内容 （1）近似算法的基本思想及性能 （2）顶点覆盖问题的近似算法 （3）集合覆盖问题的近似算法 （4）子集合问题的近似算法 2．课程重点难点 重点：近似算法。 难点：无。 3．课程教学要求 （1）了解几个常见NP难问题的定义； （2）掌握近似算法的性能定义； （3）掌握顶点覆盖； （4）