教学大纲

课程名称：算法基础
预修课程：数据结构、程序设计语言
开课学期：
总 学 时：60
学 分：
大纲撰写人：顾乃杰

一、教学目标及要求

目标：本课程是高等学校计算机系各专业的基础课, 其要求是使学生了解和掌握算法基础这门课程的基本内容, 知道算法设计的基本方法和技术, 学会算法性能分析中的具体方法和技巧, 为计算机应用和科学研究工作中有效求解问题, 以及为今后进一步学习打下基础。
基本要求：使学生能够从的运算三个方面去掌握各种数据结构的特性, 对算法的时、空复杂性有一定的分析能力，使之能够针对具体的应用问题， 选择合适的数据结构及设计结构清晰、正确有效的算法解决之。

二、教学重点和难点

重点: 算法设计的基本思想和策略, 算法优化的技巧, 算法性能分析的方法;
难点: 将算法优化的思想贯穿在设计过程中, 算法平均性能的分析技巧。

三、教材及主要参考书教材

教 材: 《计算机算法设计与分析》, 王晓东，电子工业出版社
参考书:《计算机算法基础》,邹海明,余祥宣, 华中理工大学出版社
《计算机算法导引》,卢开澄 编著, 清华大学出版社
"Introduction to Algorithms", T. H. Cormen and others, The MIT Press, 1990.

四、课程章节及学时分配

第一章 绪 论 (2 学时)
第一节 基本概念
第二节 算法的设计和性能度量
第三节 标准记号与常用函数和公式

第二章 分治与递归策略 (5 学时)
第一节 二分检索
第二节 矩阵的快速乘法
第三节 快速傅里叶变换（FFT）
第四节 广义表及递归算法

第三章 排序与选择 （5 学时）
第一节 简单排序和SHELL排序
第二节 选择排序和堆排序
第三节 快速排序和归并排序
第四节 选择问题
第五节 桶排序和基数排序

第四章 贪心策略 （4学时）
第一节 文件存储
第二节 背包问题
第三节 有限期的作业调度问题

第五章 串匹配 （4学时）
第一节 一般算法
第二节 Rabin-Karp算法
第三节 Knuth-Morris-Pratt算法
第四节 Boyer-Moore算法

第六章 动态规划 （8学时）
第一节 多段图
第二节 最佳二分检索
第三节 资源分配问题
第五节 0/1背包问题
第六节 货郎担问题
第七节 最长公共子序列
第八节 作业调度问题

第七章 回溯法 （5学时）
第一节 一般算法
第二节 皇后问题
第三节 子集和数问题
第四节 图的着色
第五节 哈密顿环
第六节 背包问题

第八章 检索、遍历与分枝限界法（5学时）
第一节 代码最优化
第二节 对策树
第三节 资源分配问题
第四节 0/1背包问题
第五节 货郎担问题

第九章 数组压缩存贮与数值计算（8学时）
第一节 数据的压缩存贮技术
第二节 压缩存贮时的矩阵运算
第三节 多项式的快速乘法
第四节 矩阵链乘问题
第五节 矩阵分解与逆矩阵

第十章 数论算法 （6学时）
第一节 最大公约数与模运算
第二节 中国余数定理
第三节 元素的幂运算
第四节 素数的判定算法
第五节 背包公钥密码
第六节 RSA公钥密码