计算复杂性 下载 mobi epub pdf 电子书 2024

☆☆☆☆☆
简体网页||繁体网页

点击这里下载

类似图书 点击查看全场最低价

---

编辑推荐

　　著名理论计算机科学家Papadimitriou对计算复杂性全面而深刻的阐述，从事计算理论研究的研究生和相关人员的优秀参考书。

内容简介

　　计算机复杂理论的研究是计算机科学zui重要的研究领域之一，而Chistos.H.Papadimitriou是该领域zui著名的专家之一。本书是一本全面阐述计算机复杂性理论及其近年来进展的教科书，主要包含算法图灵机、可计算性等有关计算复杂理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外如多项式空间等复杂性类的介绍。

目录

Computational Complexity出版者的话译者序前言第一部分算法第1章问题与算法1.1图的可达性问题1.2最大流问题1.3旅行商问题1.4注解、参考文献和问题第2章图灵机2.1图灵机概述2.2视为算法的图灵机2.3多带图灵机2.4线性加速2.5空间界2.6随机存取机2.7非确定性机2.8注解、参考文献和问题第3章不可判定性3.1通用图灵机3.2停机问题3.3更多不可判定性问题3.4注解、参考文献和问题第二部分逻辑学第4章布尔逻辑4.1布尔表达式4.2可满足性与永真性4.3布尔函数与电路4.4注解、参考文献和问题第5章一阶逻辑5.1一阶逻辑的语法5.2模型5.3永真的表达式5.4公理和证明5.5完备性定理5.6完备性定理的推论5.7二阶逻辑5.8注解、参考文献和问题第6章逻辑中的不可判定性6.1数论公理6.2作为一个数论概念的计算6.3不可判定性与不完备性6.4注解、参考文献和问题第三部分P和NP第7章复杂性类之间的关系7.1复杂性类7.2谱系定理7.3可达性方法7.4注解、参考文献和问题第8章归约和完备性8.1归约8.2完全性8.3逻辑特征8.4注解、参考文献和问题第9章NP完全问题9.1NP中的问题9.2可满足性问题的不同版本9.3图论问题9.4集合和数字9.5注解、参考文献和问题第10章coNP和函数问题10.1NP和coNP10.2素性10.3函数问题10.4注解、参考文献和问题第11章随机计算11.1随机算法11.2随机复杂性类11.3随机源11.4电路复杂性11.5注解、参考文献和问题第12章密码学12.1单向函数12.2协议12.3注解、参考文献和问题第13章可近似性13.1近似算法13.2近似和复杂性13.3不可近似性13.4注解、参考文献和问题第14章关于P和NP14.1NP的地图14.2同构和稠密性14.3谕示14.4单调电路14.5注解、参考文献和问题第四部分P内部的计算复杂性类第15章并行计算15.1并行算法15.2计算的并行模型15.3NC类15.4RNC算法15.5注解、参考文献和问题第16章对数空间16.1L=?NL问题16.2交错16.3无向图的可达性16.4注解、参考文献和问题第五部分NP之外的计算复杂性类第17章多项式谱系17.1优化问题17.2多项式谱系17.3注解、参考文献和问题第18章有关计数的计算18.1积和式18.2�軵类18.3注解、参考文献和问题第19章多项式空间19.1交错和博弈19.2对抗自然的博弈和交互协议19.3更多的PSPACE完全问题19.4注解、参考文献和问题第20章未来的展望20.1指数时间复杂性类20.2注解、参考文献和问题索引

前言/序言

　　我仅仅希望简单叙述请赋予我这一特权因为我们已经被灌输了带有这么多音乐的歌声音乐正在沉沦而我们的艺术变得如此矫饰以至于装饰品已经腐蚀了她的容颜是时候说一些简单的语言了因为明天我们的心灵将起帆远航——Giorgos Seferis本书适合作为低年级研究生或者高年级本科生学习计算复杂性理论的教材。计算复杂性是计算机科学中思考为什么有些问题用计算机难以解决的领域。这个领域以前几乎不存在，而现在却迅速扩展，并构成了理论计算机科学研究活动的主要内容。现在没有一本书可以全面介绍复杂性——当然也包括这本书在内。本书只是包含了我认为可以清楚和相对简单地表示的结果以及在我看来是复杂性领域的中心内容。
　　我认为复杂性是计算(复杂性类)和应用(问题)之间复杂而核心的部分。开篇就向读者灌输这一观点有点为时过早，不过我还是要冒险一试，而且这也将是全书20章中反复强调的观点。完全性的结论明显是这一进展的中心环节。逻辑也是如此，它能很好地表达和抓住计算这一概念，是非常重要的应用。因此计算、问题和逻辑是贯穿本书的三大主脉络。
　　内容快速浏览目录，第1章介绍问题和算法——因为当复杂性与简单性比较时，复杂性最好理解。第2章讨论图灵机，同时明确我们的方式将不依赖于机器。第3章介绍非确定性（它不仅是复杂性的最高形式，而且还具有重大的方法学影响）。
　　接着讨论逻辑。这一部分最可能会被复杂性理论同行视为另类。但是它对于我看待复杂性的观点非常重要，对于计算机科学非常基本，又很少作为走向计算机科学家的成功之路看待，所以我感到我必须做一次尝试。第4章介绍布尔逻辑（包括Horn子句的算法属性，以及布尔电路和香农定理）。第5章介绍一阶逻辑及其模型论和证明论，还包括完全性定理，以及足够的二阶逻辑以引出随后的NP的Fagin特征——非常有用但是往往被忽视，其意义相当于Cook定理。第6章是对G�塪el不完全性定理的独立证明，该证明是逻辑表达计算早期的重要例子。
　　然后重点介绍复杂性。第7章介绍已知的复杂性类之间的关系——包括Savitch和 Immerman�睸zelepscényi关于空间复杂性的定理。第8章介绍归约和完全性概念，紧接着，作为例子，介绍Cook定理和电路值问题的P完全性，同时比较用逻辑表示P和NP的特征。第9章包含很多NP完全的结果，同时介绍各种证明方法。第10章讨论coNP和函数问题。第11章介绍随机算法、与之对应的复杂性类以及用现实随机源的实现方法。电路和它们与复杂性、随机化的关系也在此介绍。第12章很简短，粗略介绍密码学和协议。第13章讨论近似算法，以及最近通过概率可验证性证明得出的一些不可行性方面的结果。另一方面，第14章讨论P=?NP问题的结构性方面，比如，中间度、同构、稠密性和谕示。它还包含了Razborov关于单调电路的下界证明。
　　第15章进一步关注P、并行算法及其复杂性，第16章重点讨论对数空间，包括无向图路径的随机游走算法。最后，除了NP以外，第17章给出多项式谱系（包括优化问题的Krentel特征）；第18章讲述计数问题和关于积和式的Valiant定理；第19章介绍多项式空间的许多方面（最有趣的是关于交互式协议的Shamir定理）；本书最后对难解性领域做了简短展望。
　　本书并没有特别的数学基础要求——除了要有一定程度的“数学成熟度”，而数学成熟度这个名词，一般不在序言中给予定义。所有的定理都从基本原理给予证明（除了第13章关于近似性引用了两个定理外），同时更多的相关结果在每章最后一节中说明。证明和构造经常会比文献里讲述的简单得多。实际上，本书包含了多个与复杂性相关的主题或专题简介：基础数论（用来证明Pratt定理），Solovay�睸trassen素数测定和RSA密码协议（第10、11、12章）；基础概率（第11章和其他章节）；组合数学和概率方法（第10、13、14章）；递归理论（第3、14章）；逻辑（第4、5、6章）。由于复杂性问题总是和相对应的算法概念的全面发展联系在一起（第1章的有效算法，第11章的随机算法，第13章的近似算法和第15章的并行算法），所以本书也可以作为算法引论——虽然仅仅粗略分析，但是可以应用在各种情况。
　　注解和问题每章的最后一节包含了相关的文献、注解、练习和问题。很多问题涉及更深的结论和课题。就我看来，这是一章中最重要的部分（经常也是最长的），读者应该将它作为本书的一部分来阅读。它经常给出历史观点，并把该章放到了更广泛的领域中。所有这些题目都是可做的，至少在提示下去图书馆查阅答案（我已经发现这样做至少对我的学生来说，不亚于另一次智商测验）。对这些题目没有标记难易，不过对于真正的难题还是给出了警示标记。
　　教学本书的重点显然是复杂性，所以我们将它设计成（以及用作）计算机科学家关于计算理论的入门级读物。我和我的同事在过去的三年中用它作为加州大学圣地亚哥分校硕士研究生第一年为期10周的教材。前两周学习前4章，这些内容对于本科生来说，一般都已熟悉。逻辑学安排在紧接着的3周中，经常省略完全性证明。剩下的5周学习第7章，作为NP完全性的严格训练（不包括在该校的算法课内），选择第11～14章中的一两节。一学期的课程可以涵盖以上4章。如果你想跳过逻辑学部分，可以加上第15章（然而，我相信这样做会错过本书相当好的一部分内容）。
　　本书至少还可以用于两门课程：前9章的主题对于计算机科学家很关键，所以它可以自豪地替代高年级本科生初级理论课程中的自动机和形式语言（特别是，因为现在的编译课程都已独立出来）。我也两次使用后面的11章作为理论方向的第二学期课程，其目标是带领有兴趣的研究生进入复杂性的研究课题——或者至少帮助他们成为计算机理论会议上见多识广的听众。
　　感谢我关于复杂性的想法是我的老师、学生和同事长期鼓舞和启迪的结果。我非常感谢所有这些人：Ken Steiglitz、Jeff Ullman、Dick Karp、Harry Lewis、John Tsitsiklis、Don Knuth、Steve Vavasis、Jack Edmonds、Albert Meyer、Gary Miller、Patrick Dymond、Paris Kanellakis、David Johnson、Elias Koutsoupias（他也在图表、最后检查和索引上给予我很多帮助）、Umesh Vazirani、Ken Arrow、Russell Impagliazzo、Sam Buss、Milena Mihail、Vijay Vazirani、Paul Spirakis、Pierluigi Crescenzi、Noga Alon、Stathis Zachos、Heather Woll、Phokion Kolaitis、Neil Immerman、Pete Veinott、Joan Feigenbaum、Lefteris Kirousis、Deng Xiaotie、Foto Afrati、Richard Anderson，最主要的是Mihalis Yannakakis和Mike Sipser。他们阅读了本书的草稿并提出了建设性意见、想法和建议——否则就会让我为他们的沉默而紧张。在所有对我的课件提出评论的学生中，我记得名字的只有David Morgenthaller、Goran Gogic、Markus Jacobsson和George Xylomenos（但我记住了其余人的笑容）。最后，感谢Richard Beigel、Matt Wong、Wenhong Zhu和他们在耶鲁的复杂性班，他们找出了本书初稿中的许多错误。自然，我对剩下的错误负责——尽管我认为我的朋友当初可以找出更多的错误。
　　我非常感激Martha Sideri的鼓励和支持，以及她的注解、看法和封面设计。
　　我在加州大学圣地亚哥分校工作时完成本书，但这期间我也访问了AT&T;公司的贝尔实验室、Bonn大学、Saarbrücken的Max�睵lanck研究所、Patras大学和那里的计算机学院以及巴黎 Sud 大学。我对于算法和复杂性的研究受到美国国家科学基金、Esprit项目AlCOM以及加州大学圣地亚哥分校信息和计算机科学主席Irwin Mark和Joan Klein Jacobs的资助。
　　与Addison Wesley的Tom Stone及其同事一起完成本书出版是愉快的。最后，我使用了Don Knuth的TeX排版，我的宏是从Jeff Ullman很多年前给我的那些中演变而来的。
　　Christos H.Papadimitriou



alt="" />


计算复杂性 下载 mobi epub pdf txt 电子书 格式

评分☆☆☆☆☆

经典。

评分☆☆☆☆☆

挺好的，喜欢下次继续购买

评分☆☆☆☆☆

很不错的计算复杂性教材，内容丰富，很值得一看。

评分☆☆☆☆☆

很好也很难找的书，没想到这里有中文版，赞一个！

评分☆☆☆☆☆

好评。。。。。。。。。。

评分☆☆☆☆☆

不错不错不错不错不错

评分☆☆☆☆☆

发货及时，印刷很好，内容不错……

评分☆☆☆☆☆

很不错的计算复杂性教材，内容丰富，很值得一看。

评分☆☆☆☆☆

很好也很难找的书，没想到这里有中文版，赞一个！

类似图书 点击查看全场最低价