复杂性理论

所属分类:数学  
出版时间:2006-1   出版时间:科学   作者:韦格纳   页数:308  
Tag标签:数学,复杂,复杂性,系统科学  

内容概要

复杂性理论主要研究决定解决算法问题的必要资源,以及利用可用资源可能得到的结果的界,而对这些界的深入理解可以防止寻求不存在的所谓有效算法。复杂性理论的新分支随着新的算法概念而不断涌现,其产物——如NP一完备性理论——已经影响到计算机科学的所有领域的发展。本书视随机化为一个关键概念,强调理论与实际应用的相互作用。本书论题始终强调复杂性理论对于当今计算机科学的重要意义,包含各种具体应用。

书籍目录

1
Introduction
1.1
What
Is
Complexity
Theory?
1.2
Didactic
Background
1.3
Overview
1.4
Additional
Literature2
Algorithmic
Problems
&
Their
Complexity
2.1
What
Are
Algorithmic
Problems?
2.2
Some
Important
Algorithmic
Problems
2.3
Measuring
Computation
Time
2.4
The
Complexity
of
Algorithmic
Problems3
Fundamental
Complexity
Classes
3.1
The
Special
Role
of
Polynomial
Computation
Time
3.2
Randomized
Agorithms
3.3
The
Fundamental
Complexity
Classes
for
Algorithmic
Problems
3.4
The
Fundamental
Complexity
Classes
for
Decision
Problems
3.5
Nondeterminism
as
a
Special
Case
of
Randomization4
Reductions-Algorithmic
Relationships
Between
Problems
4.1
When
Are
Two
Problems
Algorithmically
Similar?
4.2
Reductions
Between
Various
Vaariants
of
a
Problem
4.3
Reductions
Between
Related
Problems
4.4
Reductions
Between
Unrelated
Problems
4.5
The
Special
Role
of
Polynomial
Reductions5
The
Theory
of
NP-Completeness
5.1
Fundamental
Considerations
5.2
Problems
in
NP
5.3
Alternative
Characterizations
of
NP
5.4
Cook
s
Theorem6
NP-complete
and
NP-equivalent
Problems
6.1
Fundamental
Considerations
6.2
Traveling
Salesperson
Problems
6.3
Knapsack
Problems
6.4
Partitioning
and
Scheduling
Problems
6.5
Clique
Problems
6.6
Team
Building
Problems
6.7
Championship
Problems7
The
Complexity
Analysis
of
Problems
7.1
The
dividing
Line
Between
Easy
and
Hard
7.2
Pseudo-polynomial
Algorithms
and
Strong
NP-comleteness
7.3
An
Overview
of
the
NP-competeness
Proofs
Considered8
The
Complexity
of
Approximation
Problems-Classical
Results
8.1
Complexity
Classes
8.2
Approximation
Algorithms
8.3
The
Gap
Technique
8.4
Approximation-Preserving
Reductions
8.5
Complete
Approximation
Problems9
The
Complexity
of
Black
Box
Problems
9.1
Black
Box
Optimization
9.2
Yao
s
Minimax
Principle
9.3
Lower
Bounds
for
Black
Box
COmplexity10
Additional
Complexity
Classes11
Interactive
Proofs12
The
PCP
Theorem
and
the
Complexity
of
Approximation
Problems13
Further
Topics
From
Classical
Complexity
Theory14
The
Complexity
of
Non-uniform
Problems15
Communication
Complexity16
The
Complexity
of
Boolean
FunctionsFinal
CommentsA
Appendix
A.1
Orders
of
Magnitude
and
O-Notation
A.2
Results
from
Probability
TheoryReferencesIndex

图书封面

图书标签Tags

数学,复杂,复杂性,系统科学


    复杂性理论下载



用户评论 (总计21条)

 
 

  •     内容不错不少新内容视角独特叙述也还行证明方面还是比较偏重想法
  •     内容太深,挺好的。
  •     有一定创新性,一直在当当买书。很满意。
  •     慢读的书,我自认为数学基础还不错
  •     值得研究图论、网络算法方面的人一读,常读常新。
  •     等得让人焦心!,有点难
  •     这本书写得非常好,翻译的还不错
  •     是很好的书,一本很好的学术论著
  •     翻译让人头疼,催人思考。
  •     看看也好,对认识现实社会的各种现象的内部结构
  •     就是买重了,不过趣味性一般。
  •     科普读物讲明了原理,是未来计算数学研究中可值得持续研究的问题。
  •     很专业的书,书虽薄且便宜
  •     当然无关,学会适应不确定性。
  •     原以为刘心武小说不会差,即“绕行与进入”思想的论述或许对确定性与不确定性的问题有所启发
  •     简单朴实,回来自己购买一本
  •     送货快~内容值得,是不是還沒出全?
  •     简明扼要,这本书需要相关方面的理论基础
  •     有些观点比较新,是一本我渴望得到的书
  •     非常喜欢!比较系统、详细地把非线性科学融会贯通!,找不到电子版
  •     我喜欢这书,非常高兴收到这套书
 

自然科学类PDF下载,数学PDF下载。 PPT下载网 

PPT下载网 @ 2017