1、理论课程教学大纲课程名称 算法设计与分析基础英文名称 The Fundation of Design and Analysis of Algorithms课程编号 不填 总学时 60 学 分 不填预修课程 数 据 结 构 开课学期 不填大纲撰写人 顾 乃 杰一、教学目标和基本要求 目标：本课程是高等学校计算机系各专业的基础课, 其要求是使学生了解和掌握算法基础这门课程的基本内容, 知道算法设计的基本方法和技术, 学会算法性能分析中的具体方法和技巧, 为计算机应用和科学研究工作中有效求解问题, 以及为今后进一步学习打下基础。 基本要求：使学生能够从的运算三个方面去掌握各种数据结构的特性, 对算法
2、的时、空复杂性有一定的分析能力，使之能够针对具体的应用问题， 选择合适的数据结构及设计结构清晰、正确有效的算法解决之。二、课程简介本课程系统而全面地介绍了算法设计的基本策略和方法, 如:分治法、贪心法、动态规划、回溯法、分枝-限界等等, 并从解决大量计算机科学和应用中出现的问题出发, 描述了应用这些策略和方法而设计有效算法的过程, 并且给出了若于精典算法, 同时,对通过对这些典型算法的时间和空间复杂度的分析,逐步介绍了算法分析的方法和步骤, 以及提高算法性能的技巧, 着重强调了算法优化的思想。 三、教学重点、难点重点: 算法设计的基本思想和策略, 算法优化的技巧, 算法性能分析的方法;难点:
3、将算法优化的思想贯穿在设计过程中, 算法平均性能的分析技巧。四、教材名称及主要参考书教 材: 算法设计和分析基础, 中国科大计算机系教材参考书:计算机算法基础,邹海明,余祥宣, 华中理工大学出版社计算机算法导引,卢开澄 编著, 清华大学出版社“Introduction to Algorithms”, T. H. Cormen and others, The MIT Press, 1990.五、课程章节主要内容及学时分配第一章 绪 论 (2 学时)第一节 基本概念第二节 算法的设计和性能度量第三节 标准记号与常用函数和公式第二章 分治与递归策略 (5 学时)第一节 二分检索第二节 矩阵的快速乘法
4、第三节 快速傅里叶变换（FFT）第四节 广义表及递归算法第三章 排序与选择 （5 学时）第一节 简单排序和 SHELL 排序第二节 选择排序和堆排序第三节 快速排序和归并排序第四节 选择问题第五节 桶排序和基数排序第四章 贪心策略 （4 学时）第一节 文件存储第二节 背包问题第三节 有限期的作业调度问题第五章 串匹配 （4 学时）第一节 一般算法第二节 Rabin-Karp 算法第三节 Knuth-Morris-Pratt 算法第四节 Boyer-Moore 算法第六章 动态规划 （8 学时）第一节 多段图第二节 最佳二分检索第三节 资源分配问题第五节 0/1 背包问题第六节 货郎担问题第七节
5、 最长公共子序列第八节 作业调度问题第七章 回溯法 （5 学时）第一节 一般算法第二节 皇后问题第三节 子集和数问题第四节 图的着色第五节 哈密顿环第六节* 背包问题第八章 检索、遍历与分枝限界法（5 学时）第一节 代码最优化第二节 对策树第三节 资源分配问题第四节 0/1 背包问题第五节 货郎担问题第九章 数组压缩存贮与数值计算（8 学时）第一节 数据的压缩存贮技术第二节 压缩存贮时的矩阵运算第三节 多项式的快速乘法第四节 矩阵链乘问题第五节 矩阵分解与逆矩阵第十章 数论算法 （6 学时）第一节 最大公约数与模运算第二节 中国余数定理第三节 元素的幂运算第四节 素数的判定算法第五节 背包公钥密码第六节 RSA 公钥密码六、系教学委员会意见组长签字： 年 月 日七、系主任意见系主任签字： 年 月 日
