中国科学技术大学-算法设计与分析基础 教学大纲

课程名称    算法设计与分析基础 vSA%A 47G  
英文名称    The Fundation of Design and Analysis of Algorithms ,H?p9L; qp  
课程编号    不填    总学时    60    学 分    不填 c" 7pf T  
预修课程    数 据 结 构    开课学期    不填 ftPw6  
大纲撰写人    顾 乃 杰 h'x~"k1  
一、教学目标和基本要求 ]t3"0  
    目标：本课程是高等学校计算机系各专业的基础课, 其要求是使学生了解和掌握算法基础这门课程的基本内容, 知道算法设计的基本方法和技术, 学会算法性能分析中的具体方法和技巧, 为计算机应用和科学研究工作中有效求解问题, 以及为今后进一步学习打下基础。 >nDnb4 'C  
    基本要求：使学生能够从的运算三个方面去掌握各种数据结构的特性, 对算法的时、空复杂性有一定的分析能力，使之能够针对具体的应用问题， 选择合适的数据结构及设计结构清晰、正确有效的算法解决之。 QO.gt*"  
二、课程简介 }A7qIys$4  
本课程系统而全面地介绍了算法设计的基本策略和方法, 如:分治法、贪心法、动态规划、回溯法、分枝-限界等等, 并从解决大量计算机科学和应用中出现的问题出发, 描述了应用这些策略和方法而设计有效算法的过程, 并且给出了若于精典算法, 同时,对通过对这些典型算法的时间和空间复杂度的分析,逐步介绍了算法分析的方法和步骤, 以及提高算法性能的技巧, 着重强调了算法优化的思想。 R6XMBYK^  
三、教学重点、难点 C #&6p0U  
重点: 算法设计的基本思想和策略, 算法优化的技巧, 算法性能分析的方法; ([-=NT}Aq  
难点: 将算法优化的思想贯穿在设计过程中, 算法平均性能的分析技巧。 { NJ>[mKg  
d6EY'*0  
四、教材名称及主要参考书 )X;cS} yp  
参考书:《计算机算法基础》,邹海明,余祥宣, 华中理工大学出版社 L"I] mQvd  
    《计算机算法导引》,卢开澄 编著,   清华大学出版社 ~bTae =F P  
YXVJJd$U  
rcmAVl:$>  
五、课程章节主要内容及学时分配 k)V%.Eobf  
#cG479X"  
第一章 绪 论              (2 学时) BpG'e-2  
第一节 基本概念 PX2k,%  
第二节    算法的设计和性能度量 f<:U"E.  
第三节    标准记号与常用函数和公式 }~r6>7I  
第二章 分治与递归策略       (5 学时) ~<- ci  
  第一节 二分检索 7&1~O#  
第二节    矩阵的快速乘法 i:M*L< +  
第三节    快速傅里叶变换（FFT） (Q8?)  
第四节    广义表及递归算法 LDEW00zL  
第三章 排序与选择       （5 学时） #7-@k-<|  
第一节    简单排序和SHELL排序 E(!6n= qR  
第二节    选择排序和堆排序 (}1v^~FXj  
第三节    快速排序和归并排序 +1Rrkok  
第四节    选择问题 04PoBv~g  
第五节    桶排序和基数排序 qD;v/,?  
第四章 贪心策略       （4学时） V
.Ba''E7  
第一节 文件存储     2Uv3_i<  
第二节 背包问题     4m~7 ~-h  
第三节 有限期的作业调度问题 "Z2Tc)  
第五章 串匹配         （4学时） {jM< t  
第一节 一般算法 P%+or*  
第二节 Rabin-Karp算法 w"a 9'r  
第三节 Knuth-Morris-Pratt算法 dxn0HXU  
第四节 Boyer-Moore算法 _TOi [GT  
第六章 动态规划       （8学时） ri<'-wi  
第一节 多段图         ";_K x={  
第二节 最佳二分检索 J7ktfyQ0W  
第三节 资源分配问题 +t>*l>[  
第五节     0/1背包问题 WHgV_o 8  
第六节     货郎担问题     O+o;aa6  
第七节    最长公共子序列 eyf4M;goz}  
第八节    作业调度问题    第七章 回溯法         （5学时） ByhOK}u;P4  
第一节 一般算法 pymx\Hd,  
第二节 皇后问题 dqD;y#/  
第三节 子集和数问题 3V/_I<y  
第四节 图的着色 CO:*x,6au  
第五节 哈密顿环 $v:gBlj%"  
第六节** 背包问题 ,Um5S6 Z  
第八章 检索、遍历与分枝限界法（5学时） t&R!5^R  
第一节 代码最优化 &@4.;u  
第二节    对策树 U~{Sa+  
第三节    资源分配问题 YER:ICQ  
第四节    0/1背包问题 yX7CN5vVl  
第五节    货郎担问题 (B>)2:T1  
第九章 数组压缩存贮与数值计算（8学时）
N 8:"&WM  
第一节 数据的压缩存贮技术 pXP
qDA  
第二节    压缩存贮时的矩阵运算 1Q&cVxA"\  
第三节    多项式的快速乘法 K08 iP IkQ  
第四节    矩阵链乘问题 a
9#W9
eP  
第五节    矩阵分解与逆矩阵 n> MD\ZS  
第十章 数论算法         （6学时） ATMc`z:5T  
第一节    最大公约数与模运算 hz<|W5  
第二节    中国余数定理 CV!;oB&  
第三节    元素的幂运算 >vQ6V'F  
第四节    素数的判定算法 f\h%; X  
第五节    背包公钥密码 Y*Y&)k6t  
第六节    RSA公钥密码 ')C|`(hs  
L3B8IDq  
六、系教学委员会意见 7'_nc!ME  
R]CZw;zS_  
`6rrXU6|  
&}zRH}s;  
组长签字：       年 月 日 n<{
aPLQ  
七、系主任意见 mYj f5  
cICHRp&&  
XDHLEG-u(  
mH'\:oN  
系主任签字：       年 月 日