课程名称 算法设计与分析基础 -aGv#!aIl
英文名称 The Fundation of Design and Analysis of Algorithms /Mf45U<
课程编号 不填 总学时 60 学 分 不填 ~ K^Z 4
预修课程 数 据 结 构 开课学期 不填 <;x+ ?j
大纲撰写人 顾 乃 杰 8|7fd| 6~
一、教学目标和基本要求 xYM! m cA
目标：本课程是高等学校计算机系各专业的基础课, 其要求是使学生了解和掌握算法基础这门课程的基本内容, 知道算法设计的基本方法和技术, 学会算法性能分析中的具体方法和技巧, 为计算机应用和科学研究工作中有效求解问题, 以及为今后进一步学习打下基础。 >k ^=+
基本要求：使学生能够从的运算三个方面去掌握各种数据结构的特性, 对算法的时、空复杂性有一定的分析能力，使之能够针对具体的应用问题， 选择合适的数据结构及设计结构清晰、正确有效的算法解决之。 lp?ge
av
二、课程简介
<acAc2
本课程系统而全面地介绍了算法设计的基本策略和方法, 如:分治法、贪心法、动态规划、回溯法、分枝-限界等等, 并从解决大量计算机科学和应用中出现的问题出发, 描述了应用这些策略和方法而设计有效算法的过程, 并且给出了若于精典算法, 同时,对通过对这些典型算法的时间和空间复杂度的分析,逐步介绍了算法分析的方法和步骤, 以及提高算法性能的技巧, 着重强调了算法优化的思想。 $$ \| 3rj!
三、教学重点、难点 FFH-Kw,
重点: 算法设计的基本思想和策略, 算法优化的技巧, 算法性能分析的方法; dvsOJj/b
难点: 将算法优化的思想贯穿在设计过程中, 算法平均性能的分析技巧。 =Ze~6vS,
&nj@t>5Bs$
四、教材名称及主要参考书 4|J
y]
参考书:《计算机算法基础》,邹海明,余祥宣, 华中理工大学出版社 ~&k1P:#R
《计算机算法导引》,卢开澄 编著, 清华大学出版社 -CY?~W L&
y S7[= S
Lc*i[J<s
五、课程章节主要内容及学时分配 ~ mK9S^[
X"8Jk 4y
第一章 绪 论 (2 学时) ~|Gtm[9Ru
第一节 基本概念 j4H,*f
c
第二节 算法的设计和性能度量 .knRH^
第三节 标准记号与常用函数和公式 <JYV
G9s}
第二章 分治与递归策略 (5 学时) 2={`g/WeE
第一节 二分检索 Uh?SDay
第二节 矩阵的快速乘法 ZxbWgM5rm
第三节 快速傅里叶变换（FFT） FL0(q> $*8
第四节 广义表及递归算法 A#2 Fd7&
第三章 排序与选择 （5 学时） 3 boINmX
第一节 简单排序和SHELL排序 F7 #
第二节 选择排序和堆排序 qN}0$x>p
第三节 快速排序和归并排序 R(r89bTQ
第四节 选择问题 : B$
d
第五节 桶排序和基数排序 s+C&\$E
第四章 贪心策略 （4学时） DDc?G Y:
第一节 文件存储 sh:sPzQ%Jv
第二节 背包问题 0z_e3H{P27
第三节 有限期的作业调度问题 @aY 8VL7C0
第五章 串匹配 （4学时） ArbfA~jXB
第一节 一般算法 rC[*
x}
第二节 Rabin-Karp算法 ZnI_<
iFR*
第三节 Knuth-Morris-Pratt算法 FJp~8
x=
第四节 Boyer-Moore算法 (Pbdwzao
第六章 动态规划 （8学时） 68+ 9^
第一节 多段图 ^6H fq^ejt
第二节 最佳二分检索 UOy`N~\gh+
第三节 资源分配问题 #fRhG^QKp
第五节 0/1背包问题 | 94"bDL3~
第六节 货郎担问题 #
0 dN!l;
第七节 最长公共子序列 L#M9 !
第八节 作业调度问题 第七章 回溯法 （5学时） (@p E
第一节 一般算法 Siq2 Glg _
第二节 皇后问题 uv/I`[@HK8
第三节 子集和数问题 .]k+hc`
第四节 图的着色 1*Yf[;L
第五节 哈密顿环 c'vxT<8fWW
第六节** 背包问题 Wr a W
第八章 检索、遍历与分枝限界法（5学时） | -e* ^|
第一节 代码最优化 .a8N 5{`
第二节 对策树 _rR+u56y-
第三节 资源分配问题 ( Ub=s C
第四节 0/1背包问题 lQ<2Vw#Yl
第五节 货郎担问题 9gZMfP
第九章 数组压缩存贮与数值计算（8学时） Vl %AN;o
第一节 数据的压缩存贮技术 d(3F:dbk
第二节 压缩存贮时的矩阵运算 c*-8h{}
第三节 多项式的快速乘法 .{1G"(z
第四节 矩阵链乘问题 &=Gz[1
L
第五节 矩阵分解与逆矩阵 2?u>A3^R
第十章 数论算法 （6学时） J;W(}"cFq
第一节 最大公约数与模运算 ig 4wwd@|
第二节 中国余数定理 "w9LQ=mW
第三节 元素的幂运算 Nwr.mtvh
第四节 素数的判定算法 {>H#/I8si
第五节 背包公钥密码 % 6+J]U
第六节 RSA公钥密码 }zY)H9J~
K{.s{;#
六、系教学委员会意见 bW(+Aw=O
X,: pT\G
C)~YWx@v
gh=s#DQsFw
组长签字： 年 月 日 Q/m))!ikMt
七、系主任意见 K QXw~g?
7?-eR-
$e& ( ncM
R $HI JM
系主任签字： 年 月 日
