《计算复杂性概论》求取 ⇩

目录1

第一章　组合复杂性1

§1.1　布尔函数1

§1.2　计算链和组合机6

§1.3　组合复杂性度量10

§1.4　组合复杂性下界为线性的布尔函数15

§1.5　函数集的组合复杂性34

§1.6　一些常用函数的组合复杂性36

§1.7　渐近界46

习题50

第二章　算法的计算复杂性和计算模型54

§2.1　算法与它的计算复杂性54

§2.2　确定型图灵机59

§2.3　确定型图灵机与组合机的相似性62

§2.4　随机存取机RAM66

§2.5　RAM机的程序的计算复杂性71

§2.6　图灵机和RAM机的相关性77

§2.7　PIDGIN ALGOL——一种高级语言82

习题86

§3.1　贪心法和背包问题89

第三章　几个“难”问题的算法设计89

§3.2　动态规划和货郎担问题99

§3.3　回溯法和图的可着色性问题103

§3.4　分枝限界法和带时限的作业调度问题114

习题121

第四章　NP-完全问题124

§4.1　多项式归约与可满足性问题125

§4.2　不确定型图灵机128

§4.3　NP类135

§4.4　NP-完全问题与Cook定理138

§4.5　其它的NP-完全问题例148

§4.6　NP难题和P-SPACE类161

习题163

第五章　近似算法165

§5.1　近似的接近程度衡量165

§5.2　整数背包问题167

§5.3　装箱问题171

§5.4　图的着色问题175

§5.5　货郎担问题178

§5.6　多处理机调度问题181

习题184

参考文献185