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