03020280《算法分析与设计》课程教学大纲(408).docVIP

算法分析与设计课程 教 学 大 纲  算法分析与设计课程教学大纲 （总学时数：48（40＋8），学分数：3） 一、课程的性质、任务和目的 以算法设计策略为知识单元系统地介绍计算机算法的设计方法和分析方法。在教学中除介绍算法的基本概念、计算复杂性分析以外，重点介绍递归算法、分治算法、贪心算法、动态规划算法、回溯算法和分支定界算法的基本思想及应用，为计算机专业的学生提供一个广泛扎实的计算机算法知识基础。 二、课程的基本内容和要求 （一）算法概述 教学内容： 算法与程序 算法分析的基本概念和理论 简单程序的算法复杂性分析 教学要求： 了解算法的基本概念，算法在程序设计中的重要性。掌握程序复杂度度量的基本方法。 （二）递归的基本概念 教学内容： 递归的概念 阶乘函数 Fibonacci数列 Ackerman函数 Hanoi塔问题 整数划分问题 教学要求： 掌握递归程序复杂度的计算方法，了解经典递归问题解法。学会使用递归方法分析解决实际问题。 （三）分治策略 教学内容： 分治法的基本思想 递归方程解的展开方法 二分有哪些信誉好的足球投注网站技术 大整数的乘法 Strassen矩阵乘法 合并排序 快速排序 棋盘覆盖问题 循环赛日程表 教学要求： 掌握分治策略的基本思想以及用分治法解决问题的一般技巧。重点掌握二分有哪些信誉好的足球投注网站技术。 （四）动态规划法 教学内容： 动态规划算法的基本思想 动态规划算法的基本要素 矩阵连乘问题 最长公共子序列 最大子段和问题 0/1背包问题 流水作业调度 图像压缩问题 凸多边形最优三角剖分 动态规划的加速原理* 教学要求： 掌握动态规划解决问题的一般过程，掌握矩阵连乘问题的计算技巧。学会使用动态规划解决实际问题。 （五）贪心算法 教学内容： 找零钱问题 贪心算法的基本要素 机器调度问题 活动安排问题 最优装载问题 单源最短路径问题 哈夫曼编码 最小生成树 贪心算法的理论基础* 教学要求： 掌握贪心法解决问题的一般步骤，掌握贪心法和动态规划方法的异同。学会使用贪心法解决实际问题。 （六）回溯法 教学内容： 回溯法的基本框架 0/1背包问题 迷宫老鼠 装载问题 N后问题 骑士遍历问题 批处理作业调度 回溯法的效率分析* 教学要求： 掌握回溯法解决问题的一般步骤，掌握回溯法与贪心法、动态规划法的异同以及不同算法的效率分析。学会使用回溯法解决实际问题。 （七）分支限界法 教学内容： 分支限界法的基本思想 迷宫老鼠问题 布线问题 0/1背包问题 装载问题 批处理作业调度问题 教学要求： 掌握分支限界法解决问题的基本思想，注意比较与前四种算法的异同，学会使用分支限界法解决实际问题。 （八）NP完全性理论* 教学内容： 计算模型 P类与NP类问题 NP完全问题 一些典型的NP完全问题 教学要求： 了解NP基本理论，了解NP问题和非NP问题的异同，研究新方法解决NP问题的可能性 说明：本章为选修部分，可根据教学情况安排为讲授或自学。 三、学时分配表 序号 内容 讲授 实验 小计 1 算法概述 2 0 2 2 递归的基本概念 2 0 2 3 分治策略 4 1 5 4 动态规划法 10 2 12 5 贪心算法 8 1 9 6 回溯法 6 2 8 7 分支限界法 6 2 8 8 NP完全性理论* 2 0 2 9 其它 2 0 2 小 计 40 8 48 四、实验学时分配表 序号 内 容 要 求 小计 实验一 分治策略 掌握分治策略的基本思想以及用分治法解决问题的一般技巧 1学时 实验二 动态规划 掌握动态规划解决问题的一般过程，学会使用动态规划解决实际问题。 2学时 实验三 贪心算法 掌握贪心法解决问题的一般步骤，学会使用贪心法解决实际 1学时 实验四 回溯法 掌握回溯法解决问题的一般步骤，学会使用回溯法解决实际问题。 2学时 实验五 分支限界法 掌握分支限界法解决问题的基本思想，学会使用分支限界法解决实际问题。 2学时 小计 8学时 五、有关说明 教学建议 在教学中安排一定的习题讨论时间，使学生锻炼分析问题的能力。教学中的一些习题建议学生安排上机，这样才能全面掌握常用算法的分析和设计技术。 课程建议教材 《计算机算法设计与分析》 王晓东编著 电子工业出版社 课程建议参考书 《计算机算法基础》 邹海明编著 华中理工大学出版社 《计算机算法设计与分析》苏德富编著 电子工业出版社 本课程的先修课程和实践性环节的名称和内容 安排在《C语言》、《数据结构》课程之后开设。 执 笔 人：陈利民 审 定 人：胡智喜 批 准 人：徐煜明 5 课程代码