课程名称 算法设计与分析基础 UQ'\7OS
英文名称 The Fundation of Design and Analysis of Algorithms Ge,;8N88
课程编号 不填 总学时 60 学 分 不填 i%ZW3MrY~
预修课程 数 据 结 构 开课学期 不填 u1t%(_h
大纲撰写人 顾 乃 杰 HHiT]S9
一、教学目标和基本要求 RMd[Yr2e
目标:本课程是高等学校计算机系各专业的基础课, 其要求是使学生了解和掌握算法基础这门课程的基本内容, 知道算法设计的基本方法和技术, 学会算法性能分析中的具体方法和技巧, 为计算机应用和科学研究工作中有效求解问题, 以及为今后进一步学习打下基础。 u @~JiiC%
基本要求:使学生能够从的运算三个方面去掌握各种数据结构的特性, 对算法的时、空复杂性有一定的分析能力,使之能够针对具体的应用问题, 选择合适的数据结构及设计结构清晰、正确有效的算法解决之。 #Xhdn\7
二、课程简介 VS9`{
本课程系统而全面地介绍了算法设计的基本策略和方法, 如:分治法、贪心法、动态规划、回溯法、分枝-限界等等, 并从解决大量计算机科学和应用中出现的问题出发, 描述了应用这些策略和方法而设计有效算法的过程, 并且给出了若于精典算法, 同时,对通过对这些典型算法的时间和空间复杂度的分析,逐步介绍了算法分析的方法和步骤, 以及提高算法性能的技巧, 着重强调了算法优化的思想。 w:s]$:MA8
三、教学重点、难点 &n6$rBr%
重点: 算法设计的基本思想和策略, 算法优化的技巧, 算法性能分析的方法; ,stN
难点: 将算法优化的思想贯穿在设计过程中, 算法平均性能的分析技巧。 +
`
s@
(Q%'N3gk
四、教材名称及主要参考书 /DQc&.jK
参考书:《计算机算法基础》,邹海明,余祥宣, 华中理工大学出版社 dYSr4pb
《计算机算法导引》,卢开澄 编著, 清华大学出版社 { T4
~vXaqCX
p[<Dk$7K
五、课程章节主要内容及学时分配 V6t,BJjS
uwa~-xX6
第一章 绪 论 (2 学时) 0@G")L
Ue0
第一节 基本概念 |~'IM3Jw(Y
第二节 算法的设计和性能度量 j'%$XvI
第三节 标准记号与常用函数和公式 Lg~B'd8m
第二章 分治与递归策略 (5 学时) FL(6?8zK
第一节 二分检索 Np'2}6P
第二节 矩阵的快速乘法 T.Ryy"%F
第三节 快速傅里叶变换(FFT) u}!@ ,/)
第四节 广义表及递归算法 bHg,1y)UC
第三章 排序与选择 (5 学时) Kl2lbe7
第一节 简单排序和SHELL排序 #{
k|I$
第二节 选择排序和堆排序 MF~H"
D
n
第三节 快速排序和归并排序 w"OP8KA:^T
第四节 选择问题 F%i^XA]a*
第五节 桶排序和基数排序 slg ]#Dy
第四章 贪心策略 (4学时) +n<k)E@>J
第一节 文件存储 Ix(?fO#uNF
第二节 背包问题 " R-!(9k^`
第三节 有限期的作业调度问题 nBHnkbKoy
第五章 串匹配 (4学时) 4m*M,# mV
第一节 一般算法 O!Oumw,$
第二节 Rabin-Karp算法 E<C&Cjz:H
第三节 Knuth-Morris-Pratt算法 W
D
T]!
第四节 Boyer-Moore算法 Wx~k&[&E
第六章 动态规划 (8学时) /9zE^YcT
第一节 多段图 U5-@2YcH
第二节 最佳二分检索 n>A98NQ
第三节 资源分配问题 [@Q_(LQ-U
第五节 0/1背包问题 #% of;mJv
第六节 货郎担问题 H}H7lO
第七节 最长公共子序列 [Z~ 2
第八节 作业调度问题 第七章 回溯法 (5学时) a)S+8uU
第一节 一般算法 _UT$,0u_i
第二节 皇后问题 )u/H>;L P
第三节 子集和数问题 WdZ:K,
第四节 图的着色 E@-KGsdhK
第五节 哈密顿环 5Q 'i2*j
第六节** 背包问题 qwK2WE%T
第八章 检索、遍历与分枝限界法(5学时) Zum0J{l
h
第一节 代码最优化 Hew
d4k
第二节 对策树 X^\>:<
第三节 资源分配问题 ?UK|>9y}Z
第四节 0/1背包问题 \=0Vuz
第五节 货郎担问题 &f7fK|}
第九章 数组压缩存贮与数值计算(8学时) B%KG3]
第一节 数据的压缩存贮技术 8a_[B~
第二节 压缩存贮时的矩阵运算 8E8N6
第三节 多项式的快速乘法 A<6%r7&B'
第四节 矩阵链乘问题 r}0\}~'?c
第五节 矩阵分解与逆矩阵 ,R$u?c0>'&
第十章 数论算法 (6学时) =1
P6Vk
第一节 最大公约数与模运算 4J?t_)
第二节 中国余数定理 4GR!y)
第三节 元素的幂运算 !r`, =jK"
第四节 素数的判定算法 RJy=pNztm
第五节 背包公钥密码 S}f?.7
第六节 RSA公钥密码 s;1]tD
}gkM^*$:%
六、系教学委员会意见 vsL[*OeI
hoT/KWD,
G&;j6<h l
x!_<z''
组长签字: 年 月 日 MG /,==
七、系主任意见 En&5)c+js4
q~L^au8
# wc \T
eUl/o1~mXa
系主任签字: 年 月 日