文档介绍：1
算法分析与 计算复杂性理论
2
课程简介
课程名称
算法分析与计算复杂性理论
Analysis of Algorithms and
Theory plexity
基本目的
掌握组合算法设计的基本技术
掌握算法分析的基本方法
掌握计算复杂性理论的基本概念
学****应用算法理论处理实际问题
3
课程内容
顺序算法设计的基本技术
分治策略动态规划
回溯算法贪心法
概率算法
顺序算法分析的基本方法
评价算法的标准算法复杂性的估计
问题复杂性的下界算法分析的实例
计算复杂性理论
Turing机
计算复杂性的概念
NP完全性理论及其应用
NP完全理论的拓广
预计进度安排
内容
学时
内容
学时
1
前言
1
9
Turing机
2
2
数学基础
2
10
计算复杂性理论
2
3
分治策略
4
11
NP完全性理论
2
4
动态规划
4
12
Cook定理
1
5
回溯与分支估界
4
13
NP完全性证明
5
6
贪心法
4
14
NP完全理论应用
2
7
概率算法
3
15
NP完全理论的拓广
2
8
算法分析技术
6
16
小结
1
5
教材与参考书
1. Algorithm Design, Jon Kleinberg, Eva Tardos, Addison-Wesley, 清华大学出版社影印版,2006.
2. Introduction to Algorithms(Second Edtion), Thomas H. Cormen, Charles E. Leiserson, Ronald , The MIT Press 2001. 高教出版社影印版,2002.
3. 计算机和难解性: NP完全性理论导引, M. R. 加里, D. S. 约翰逊, 张立昂等译,科学出版社, 1987.
*4. 计算复杂性导论,堵丁柱,葛可一,王洁,高教出版社2002.
*5. Limits to putation: P- Completeness Theory, Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo, Oxford University Press, 1995.
学****安排
成绩评定:
小论文:结合研究工作,50%
期末笔试:50%
7
引言: 理论上的可计算与现实上的可计算
算法研究的重要性
理论上的可计算
——可计算性理论
现实上的可计算
——计算复杂性理论
8
投资问题
问题:
m元钱,投资给n个项目,效益函数 fi(x),表示第 i 个项目
投入x元钱的效益,i=1,2,…,n. 如何分配每个项目的钱数使
得总效益最大?
采用什么算法?效率怎样?
令xi 是第 i 个项目的钱数
9
蛮力算法的代价
Stirling公式:
非负整数解<x1, x2, …, xn> 的个数估计:
蛮力算法——穷举法代价太大
能否利用解之间的依赖关系找到更好的算法?
结论:需要算法设计技术
10
T(n) = 2 T(n1) + 1,T(1) = 1,
A B C
思考:是否存在更好的解法?
Reve难题:Hanoi塔变种,柱数增加,允许盘子相等.
其他变种:奇偶盘号分别放置
解得 T(n) = 2n 1
1秒移1个,64个盘子要多少时间?(5000亿年)
Hanoi塔问题