計(jì)算理論基礎(chǔ)

前言

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.

內(nèi)容概要

　　《計(jì)算理論基礎(chǔ)可計(jì)算性復(fù)雜性和語(yǔ)言(英文版·第2版)》是理論計(jì)算機(jī)科學(xué)領(lǐng)域的名作，是計(jì)算機(jī)科學(xué)核心主題的導(dǎo)論性教材。全書(shū)分為可計(jì)算性、文法與自動(dòng)機(jī)、邏輯學(xué)、復(fù)雜性及語(yǔ)義學(xué)5個(gè)部分，分別講述了可計(jì)算性理論、形式語(yǔ)言、邏輯學(xué)與自動(dòng)演繹、可計(jì)算復(fù)雜性(包括NP完全問(wèn)題)和編程語(yǔ)言的語(yǔ)義等主題，并展示了它們之間如何相互關(guān)聯(lián)?！队?jì)算理論基礎(chǔ)可計(jì)算性復(fù)雜性和語(yǔ)言(英文版·第2版)》是計(jì)算機(jī)及相關(guān)專業(yè)高年級(jí)本科生和研究生的理想教學(xué)參考書(shū)，對(duì)于計(jì)算機(jī)領(lǐng)域的專業(yè)人士也是很好的技術(shù)參考書(shū)。

作者簡(jiǎn)介

作者：(美國(guó))Maritin D.Davis (美國(guó))Ron Sigal (美國(guó))Elaine J.WeyukerMartin D．Davis，著名計(jì)算機(jī)科學(xué)家和數(shù)學(xué)家。1950年在普林斯頓大學(xué)獲得博士學(xué)位，與圖靈同門(mén)(導(dǎo)師均為計(jì)算科學(xué)大師Alonzo Church)。后長(zhǎng)期任教于紐約大學(xué)柯朗數(shù)學(xué)研究所。他是自動(dòng)演繹理論先驅(qū)，還是DPLL算法的發(fā)明人之一，Post-Turing機(jī)更使其聲名遠(yuǎn)播。除本書(shū)外，他還著有經(jīng)典名著Computability and Unsolvability。Ron Sigal，資深軟件工程師。1983年在紐約大學(xué)獲得計(jì)算機(jī)科學(xué)博士學(xué)位。曾先后任教于紐約城市大學(xué)、意大利卡塔尼亞大學(xué)、耶魯大學(xué)、Hofstra大學(xué)。他參與的軟件項(xiàng)目有NASA的火星探路者、JBoss等。Elaine J．Weyuker，著名女計(jì)算機(jī)科學(xué)家。美國(guó)國(guó)家工程院院士、IEEE和ACM會(huì)士、AT＆T院士、ACM婦女委員會(huì)主席、ACM執(zhí)行委員，現(xiàn)任AT＆T實(shí)驗(yàn)室研究員。她的主要研究領(lǐng)域是軟件測(cè)試與可靠性。此前曾任紐約大學(xué)柯朗數(shù)學(xué)研究所計(jì)算機(jī)科學(xué)教授近20年。

書(shū)籍目錄

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

章節(jié)摘錄

插圖：

媒體關(guān)注與評(píng)論

“如果說(shuō)有哪一本計(jì)算理論方面的書(shū)所有的大學(xué)圖書(shū)館都應(yīng)該收藏，那就是這本書(shū)！”　　——Choice雜志

編輯推薦

《計(jì)算理論基礎(chǔ)可計(jì)算性復(fù)雜性和語(yǔ)言(英文版·第2版)》是理論計(jì)算機(jī)科學(xué)領(lǐng)域不朽的名作之一，它成功地將該領(lǐng)域所涵蓋的可計(jì)算性理論、形式語(yǔ)言理論、復(fù)雜性理論和邏輯學(xué)這幾個(gè)分散主題完美地融為一體進(jìn)行闡述，展示了它們之間的內(nèi)在關(guān)聯(lián)，深刻地體現(xiàn)出理論計(jì)算機(jī)科學(xué)之美?！队?jì)算理論基礎(chǔ)可計(jì)算性復(fù)雜性和語(yǔ)言(英文版·第2版)》內(nèi)容嚴(yán)謹(jǐn)，可讀性強(qiáng)，配有豐富的習(xí)題，適合作為計(jì)算機(jī)和數(shù)學(xué)專業(yè)高年級(jí)本科生及研究生相關(guān)課程的教材，對(duì)于從事理論研究和軟件開(kāi)發(fā)的專業(yè)技術(shù)人員也是不可多得的參考書(shū)。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    計(jì)算理論基礎(chǔ) PDF格式下載

---