算法分析与设计
来源：365英国上市公司官网
发布日期：2019-01-21浏览量：次
| 课程编号 |
522.5*075 |
| 课程名称 |
算法分析与设计 |
| 任课老师 |
刘晓鸿 |
| 课程类型 |
必修/学位课 |
| 课程阶段 |
硕士 |
| 学时学分 |
36学时2学分 |
| 基本要求 |
计算机软件的核心是算法，而算法设计与分析是关于算法的方法论，其研究分为两个方面：
1）软件开发中经常遇到的实际问题的解法；
2）分析算法的基本规律和原理。
计算机专业传统上对于非数值方法（主要是分类和查找）有较多的训练,但这在计算机和通信日益发展的今天已经日益显现出了其局限性。在本课程中，除去传统的分类查找算法和一般的设计方法外，加入了对数论中基本算法的介绍，因为溯本求源，许多设计方法都来自于组合学及规划；另外，讨论了实际中使用非常频繁的概率算法，由于随机特性而传统上被回避了。希望通过这一课程的学习，能对现代的算法设计及分析的基本工具能有较全面的掌握。 |
| 内容提要 |
一、 引言
实例：快速分类及斯特拉森矩阵乘法
二、基本工具
2.1递推关系
2.2母函数法
三、若干数论中方法
3.1基本知识
3.2素数判定
孙子定理
Miller Rabin方法
3.3整数因子分解
Pollard的ρ方法
3.4离散对数
四、基本的非数值算法
4.1分类
冒泡排序
选择排序
选择排序
插入排序
快速排序
合并排序
Shell排序
堆排序
基数排序
4.2查找
折半查找
HASH法
B*树
最佳查询树的构造
五、串匹配查找及集合UNION-FIND
5.1SMP算法
5.2UNION-FIND
六、基本算法设计策略
6.1分治法
快速排序算法的设计与分析
快速变换:FFT及快速数论变换
6.2 贪心法
背包问题的算法的设计与分析
带有限期的作业排序算法的设计与分析
最小生成树的算法的设计与分析
6.3 动态规则
0/1背包问题
货郎担问题
Viterbi译码
6.4 基本搜索算法
图的基本搜索BFS及DFS
对策树
6.5 回溯法
8-皇后问题
哈密尔顿回路问题
6.6 分枝—限界
规划中的应用
0/1背包问题
七、概率方法
7.1随机数生成
7.2 Monte Carlo方法
7.3减小方差的方法
7.4 拟Monte Carlo方法
7.5 在优化中的应用
八、 NP难和NP完全问题
8.1 基本概念
8.2 非确定算法
8.3 COOK定理 |
| 教学方式 |
|
| 指定教材 |
|
| 参考书目 |
1． 自编教材
2． Knuth,程序设计技巧，卷二、三
3． Aho, A.V and J. E. Hopcroft Ullman,The Design and
Analysis of Computer Algorithms.Addison Wesley Publishing Company,1974.
4． Horowitz and Sahni，Foundations of Computer
Algorithms.New York: Computer Science Press, 1978.
5． Sara Basse，算法设计与分析，北京：高等教育出版社，2000
6． Neal Koblitz ，A Course in Number Theory and Cryptography 2 nd ed.
7． Harald Niederreiter，Random Number Generation and Quasi-
Monte Carlo Methods，1992 |
| 先修课程 |
|
| 开课学期 |
春 |
