计算理论基础

出版时间：2009  出版社：人民邮电出版社  作者：Martin Davis,Ron Sigal,ELAINE J. WEYUKER  页数：609  
Tag标签：无  

前言

Theoretical computer science is the mathematical study of models ofcomputation. As such, it originated in the 1930s, well before the existenceof modern computers, in the work of the logicians Church, Godel, Kleene,Post, and Turing. This early work has had a profound influence on thepractical and theoretical development of computer science. Not only hasthe Turing machine model proved basic for theory, but the work of thesepioneers presaged many aspects of computational practice that are nowcommonplace and whose intellectual antecedents are typically unknown tousers. Included among these are the existence in principle of all-purpose（or universal） digital computers, the concept of a program as a list ofinstructions in a formal language, the possibility of interpretive programs,the duality between software and hardware, and the representation oflanguages by formal structures, based on productions. While the Spotlightin computer science has tended to fall on the truly breathtaking technolog-ical advances that have been taking place, important work in the founda-tions of the subject has continued as well. It is our purpose in writing thisbook to provide an introduction to the various aspects of theoreticalcomputer science for undergraduate and graduate students that is suffi-ciently comprehensive that the professional literature of treatises andresearch papers will become accessible to our readers.

内容概要

　　《计算理论基础可计算性复杂性和语言(英文版·第2版)》是理论计算机科学领域的名作，是计算机科学核心主题的导论性教材。全书分为可计算性、文法与自动机、逻辑学、复杂性及语义学5个部分，分别讲述了可计算性理论、形式语言、逻辑学与自动演绎、可计算复杂性(包括NP完全问题)和编程语言的语义等主题，并展示了它们之间如何相互关联。《计算理论基础可计算性复杂性和语言(英文版·第2版)》是计算机及相关专业高年级本科生和研究生的理想教学参考书，对于计算机领域的专业人士也是很好的技术参考书。

作者简介

作者：(美国)Maritin D.Davis (美国)Ron Sigal (美国)Elaine J.WeyukerMartin D．Davis，著名计算机科学家和数学家。1950年在普林斯顿大学获得博士学位，与图灵同门(导师均为计算科学大师Alonzo Church)。后长期任教于纽约大学柯朗数学研究所。他是自动演绎理论先驱，还是DPLL算法的发明人之一，Post-Turing机更使其声名远播。除本书外，他还著有经典名著Computability and Unsolvability。Ron Sigal，资深软件工程师。1983年在纽约大学获得计算机科学博士学位。曾先后任教于纽约城市大学、意大利卡塔尼亚大学、耶鲁大学、Hofstra大学。他参与的软件项目有NASA的火星探路者、JBoss等。Elaine J．Weyuker，著名女计算机科学家。美国国家工程院院士、IEEE和ACM会士、AT＆T院士、ACM妇女委员会主席、ACM执行委员，现任AT＆T实验室研究员。她的主要研究领域是软件测试与可靠性。此前曾任纽约大学柯朗数学研究所计算机科学教授近20年。

书籍目录

ContentsI Preliminaries 11. Sets and n-tuples 12. Functions 33. Alphabets and Strings 44. Predicates 55. Quantifiers 66. Proof by Contradiction 87. Mathematical Induction 9Part 1 Computability 152 Programs and Computable Functions 171. A Programming Language 172. Some Examples of Programs 183. Syntax 254. Computable Functions 285. More about Macros 323 Primitive Recursive Functions 391. Composition 392. Recursion 403. PRC Classes 424. Some Primitive Recursive Functions 445. Primitive Recursive Predicates 496. Iterated Operations and Bounded Quantifiers 527. Minimalization 558. Pairing Functions and G6del Numbers 594 A Universal Program 651. Coding Programs by Numbers 652. The Halting Problem 683. Universality 704. Recursively Enumerable Sets 785. The Parameter Theorem 856. Diagonalization and Reducibility 887. Rice s Theorem 95*8. The Recursion Theorem 97*9. A Computable Function That Is Not Primitive Recursive 1055 Calculations on Strings 1131. Numerical Representation of Strings 1132. A Programming Language for String Computations 1213. The Languages and n 1264. Post-Turing Programs 1295. Simulation of n in 1356. Simulation of in 1406 Turing Machines 1451. Internal States 1452. A Universal Turing Machine 1523. The Languages Accepted by Turing Machines 1534. The Halting Problem for Turing Machines 1575. Nondeterministic Turing Machines 1596. Variations on the Turing Machine Theme 1627 Processes and Grammars 1691. Semi-Thue Processes 1692. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes 1713. Unsolvable Word Problems 1764. Post's Correspondence Problem 1815. Grammars 1866. Some Unsolvable Problems Concerning Grammars 1917. Normal Processes 1928 Classifying Unsolvable Problems 1971. Using Oracles 1972. Relativization of Universality 2013. Reducibility 2074. Sets r.e. Relative to an Oracle 2115. The Arithmetic Hierarchy 2156. Post's Theorem 2177. Classifying Some Unsolvable Problems 2248. Rice's Theorem Revisited 2309. Recursive Permutations 231Part 2 Grammars and Automata 2359 Regular Languages 2371. Finite Automata 2372. Nondeterministic Finite Automata 2423. Additional Examples 2474. Closure Properties 2495. Kleene's Theorem 2536. The Pumping Lemma and Its Applications 2607. The Myhill-Nerode Theorem 26310 Context-Free Languages 2691. Context-Free Grammars and Their Derivation Trees 2692. Regular Grammars 2803. Chomsky Normal Form 2854. Bar-Hillel's Pumping Lemma 2875. Closure Properties 291*6. Solvable and Unsolvable Problems 2977. Bracket Languages 3018. Pushdown Automata 3089. Compilers and Formal Languages 32311 Context-Sensitive Languages 3271. The Chomsky Hierarchy 3272. Linear Bounded Automata 3303. Closure Properties 337Part 3 Logic 34512 Propositional Calculus 3471. Formulas and Assignments 3472. Tautological Inference 3523. Normal Forms 3534. The Davis-Putnam Rules 3605. Minimal Unsatisfiability and Subsumption 3666. Resolution 3677. The Compactness Theorem 37013 Quantification Theory 3751. The Language of Predicate Logic 3752. Semantics 3773. Logical Consequence 3824. Herbrand's Theorem 3885. Unification 3996. Compactness and Countability 404*7. G6del's Incompleteness Theorem 407*8. Unsolvability of the Satisfiability Problem in Predicate Logic 410Part 4 Complexity 41714 Abstract Complexity 4191. The Blum Axioms 4192. The Gap Theorem 4253. Preliminary Form of the Speedup Theorem 4284. The Speedup Theorem Concluded 43515 Polynomial-Time Computability 4391. Rates of Growth 4392. P versus NP 4433. Cook's Theorem 4514. Other NP-Complete Problems 457Part 5 Semantics 46516 Approximation Orderings 4671. Programming Language Semantics 4672. Partial Orders 4723. Complete Partial Orders 4754. Continuous Functions 4865. Fixed Points 49417 Denotational Semantics of Recursion Equations 5051. Syntax 5052. Semantics of Terms 5113. Solutions to W-Programs 5204. Denotational Semantics of W-Programs 5305. Simple Data Structure Systems 5396. Infinitary Data Structure Systems 54418 Operational Semantics of Recursion Equations 5571. Operational Semantics for Simple Data Structure Systems 5572. Computable Functions 5753. Operational Semantics for lnfinitary Data Structure Systems 584Suggestions for Further Reading 593Notation Index 595Index 599

章节摘录

插图：

媒体关注与评论

“如果说有哪一本计算理论方面的书所有的大学图书馆都应该收藏，那就是这本书！”　　——Choice杂志

编辑推荐

《计算理论基础可计算性复杂性和语言(英文版·第2版)》是理论计算机科学领域不朽的名作之一，它成功地将该领域所涵盖的可计算性理论、形式语言理论、复杂性理论和逻辑学这几个分散主题完美地融为一体进行阐述，展示了它们之间的内在关联，深刻地体现出理论计算机科学之美。《计算理论基础可计算性复杂性和语言(英文版·第2版)》内容严谨，可读性强，配有丰富的习题，适合作为计算机和数学专业高年级本科生及研究生相关课程的教材，对于从事理论研究和软件开发的专业技术人员也是不可多得的参考书。

用户评论 (总计3条)

•   感觉邮电社计算机科学系列印装不如数学统计学系列，这本字很大，原版书也很少看到字这么大的，纸一般，印刷效果也中等。内容全面，数学功力不足，看着比较吃力。感觉比原来见到的几本计算理论和自动机的书籍比难一些，涵盖了逻辑和语义的部分内容。不足就是没有习题答案甚至提示，也没有参考文献（？？？），是不又被出版社当没用的去了！！！
•   去年这个时候买的，一起买了8本书。买了之后没看，先看其他的书了。结果今天一翻，这纸张，比盗版的还不如。字体很大，一页压根印不下多少。
•   因为第一次收到的书，觉得旧；打了客服后，很快就给换了。