未读消息消息

店铺

我的订单收藏

拍卖

拍卖交易我的竞拍收藏

我的好友资金账户

客服 |

帮助中心 9:00-20:30 在线留言

客服电话

010-89648155

服务时间

客服咨询 8:00-21:00

纠纷处理 9:00-21:00

图书审核 9:00-18:00

监督与建议

请选择

手机孔网

Computability, Complexity, and Languages, Second Edition：Fundamentals of Theoretical Computer Science (Computer Science and Scientific Computing)

Computability, Complexity, and Languages, Second Edition：Fundamentals of Theoretical Computer Science (Computer Science and Scientific Computing)

分享

作者: Martin Davis , Ron Sigal , Elaine J. Weyuker

出版社: Morgan Kaufmann

出版时间: 1994-02

ISBN: 9780122063824

装帧: 精装

开本: 其他

页数: 609页

分类: 外文古旧书>英文书>计算机与互联网

1人买过

Preface
Acknowledgments
Dependency Graph
1 Preliminaries
1. Sets and n-tuples
2. Functions
3. Alphabets and Strings
4. Predicates
5. Quantifiers
6. Proof by Contradiction
7. Mathematical Induction
Part 1 Cmnputability
2 Programs and Computable Functions
1. A Programming Language
2. Some Examples of Programs
3. Syntax
- 4. Computable Functions
5. More about Macros
3 Primitive Recursive Functions
1. Composition
2. Recursion
3. PRC Classes
4. Some Primitive Recursive Functions
5. Primitive Recursive Predicates
6. Iterated Operations and Bounded Quantifiers
7. Minimalization
8. Pairing Functions and Gijdel Numbers
4 A Universal Program
1. Coding Programs by Numbers
- -- 2. The Halting Problem
3. Universality
4. Recursively Enumerable Sets
5. The Parameter Theorem
6. Diagonalization and Reducibility
-_’ 7. Rice’ s Theorem
*8. The Recursion Theorem
*9. A Computable Function That Is Not Primitive Recursive
5 Calculations on Strings
1. Numerical Representation of Strings
2. A Programming Language for String Computations
3. The Languages Y and Yn
4. Post-Turing Programs
5. Simulation of-F”, in 9
6. Simulation of Yin Y
6 Turing Machines
1. Internal States
2. A Universal Turing Machine
3. The Languages Accepted by Turing Machines
4. The Halting Problem for Turing Machines
5. Nondeterministic Turing Machines
6. Variations on the Turing Machine Theme
7 Processes and Grammars
1. Semi-Thue Processes
2. Simulation of Nondeterministic Turing Machines by
Semi-Thue Processes
3.
4.
5.
6.
*7.
Unsolvable Word Problems
Post’ s Correspondence Problem
Grammars
Some Unsolvable Problems Concerning Grammars
Normal Processes
8 Classifying Unsolvable Problems
1. Using Oracles
2. Relativization of Universality
3. Reducibility
4. Sets r.e. Relative to an Oracle
5. The Arithmetic Hierarchy
6. Post’ s Theorem
7. Classifying Some Unsolvable Problems
8. Rice’ s Theorem Revisited
9. Recursive Permutations
Part 2 Grammars and Automata
9 Regular Languages
1. Finite Automata
2. Nondeterministic Finite Automata
3. Additional Examples
4. Closure Properties
5. Kleene’ s Theorem
6. The Pumping Lemma and Its Applications
7. The Myhill-Nerode Theorem
10 Context-Free Languages
1. Context-Free Grammars and Their Derivation Trees
2. Regular Grammars
3. Chomsky Normal Form
4. Bar-Hillel’ s Pumping Lemma
5. Closure Properties
*6. Solvable and Unsolvable Problems
7. Bracket Languages
8. Pushdown Automata
9. Compilers and Formal Languages
11 Context-Sensitive Languages
1. The Chomsky Hierarchy
2. Linear Bounded Automata
3. Closure Properties
Part 3 Logic
12 Propositional Calculus
1. Formulas and Assignments
2. Tautological Inference
3. Normal Forms
4. The Davis-Putnam Rules
5. Minimal Unsatisfiability and Subsumption
6. Resolution
7. The Compactness Theorem
13 Quantification Theory
1. The Language of Predicate Logic
2. Semantics
3. Logical Consequence
4. Herbrand’ s Theorem
5. Unification
6. Compactness and Countability
*7. Godel’ s Incompleteness Theorem
*8. Unsolvability of the Satisfiability Problem in Predicate Logic
Part 4 Complexity
14 Abstract Complexity
1. The Blum Axioms
2. The Gap Theorem
3. Preliminary Form of the Speedup Theorem
4. The Speedup Theorem Concluded
15 Polynomial-Time Computability
1. Rates of Growth
2. P versus NP
3. Cook’ s Theorem
4. Other NP-Complete Problems
Part 5 Semantics
16 Approximation Orderings
1. Programming Language Semantics
2. Partial Orders
3. Complete Partial Orders
4. Continuous Functions
5. Fixed Points
17 Denotational Semantics of Recursion Equations
1. Syntax
2. Semantics of Terms
3. Solutions to W-Programs
4. Denotational Semantics of W-Programs
5. Simple Data Structure Systems
6. Infinitary Data Structure Systems
18 Operational Semantics of Recursion Equations
1. Operational Semantics for Simple Data Structure Systems
2. Computable Functions
3. Operational Semantics for Infinitary Data Structure Systems
内容简介:
Preface
Acknowledgments
Dependency Graph
1 Preliminaries
1. Sets and n-tuples
2. Functions
3. Alphabets and Strings
4. Predicates
5. Quantifiers
6. Proof by Contradiction
7. Mathematical Induction
Part 1 Cmnputability
2 Programs and Computable Functions
1. A Programming Language
2. Some Examples of Programs
3. Syntax
- 4. Computable Functions
5. More about Macros
3 Primitive Recursive Functions
1. Composition
2. Recursion
3. PRC Classes
4. Some Primitive Recursive Functions
5. Primitive Recursive Predicates
6. Iterated Operations and Bounded Quantifiers
7. Minimalization
8. Pairing Functions and Gijdel Numbers
4 A Universal Program
1. Coding Programs by Numbers
- -- 2. The Halting Problem
3. Universality
4. Recursively Enumerable Sets
5. The Parameter Theorem
6. Diagonalization and Reducibility
-_’ 7. Rice’ s Theorem
*8. The Recursion Theorem
*9. A Computable Function That Is Not Primitive Recursive
5 Calculations on Strings
1. Numerical Representation of Strings
2. A Programming Language for String Computations
3. The Languages Y and Yn
4. Post-Turing Programs
5. Simulation of-F”, in 9
6. Simulation of Yin Y
6 Turing Machines
1. Internal States
2. A Universal Turing Machine
3. The Languages Accepted by Turing Machines
4. The Halting Problem for Turing Machines
5. Nondeterministic Turing Machines
6. Variations on the Turing Machine Theme
7 Processes and Grammars
1. Semi-Thue Processes
2. Simulation of Nondeterministic Turing Machines by
Semi-Thue Processes
3.
4.
5.
6.
*7.
Unsolvable Word Problems
Post’ s Correspondence Problem
Grammars
Some Unsolvable Problems Concerning Grammars
Normal Processes
8 Classifying Unsolvable Problems
1. Using Oracles
2. Relativization of Universality
3. Reducibility
4. Sets r.e. Relative to an Oracle
5. The Arithmetic Hierarchy
6. Post’ s Theorem
7. Classifying Some Unsolvable Problems
8. Rice’ s Theorem Revisited
9. Recursive Permutations
Part 2 Grammars and Automata
9 Regular Languages
1. Finite Automata
2. Nondeterministic Finite Automata
3. Additional Examples
4. Closure Properties
5. Kleene’ s Theorem
6. The Pumping Lemma and Its Applications
7. The Myhill-Nerode Theorem
10 Context-Free Languages
1. Context-Free Grammars and Their Derivation Trees
2. Regular Grammars
3. Chomsky Normal Form
4. Bar-Hillel’ s Pumping Lemma
5. Closure Properties
*6. Solvable and Unsolvable Problems
7. Bracket Languages
8. Pushdown Automata
9. Compilers and Formal Languages
11 Context-Sensitive Languages
1. The Chomsky Hierarchy
2. Linear Bounded Automata
3. Closure Properties
Part 3 Logic
12 Propositional Calculus
1. Formulas and Assignments
2. Tautological Inference
3. Normal Forms
4. The Davis-Putnam Rules
5. Minimal Unsatisfiability and Subsumption
6. Resolution
7. The Compactness Theorem
13 Quantification Theory
1. The Language of Predicate Logic
2. Semantics
3. Logical Consequence
4. Herbrand’ s Theorem
5. Unification
6. Compactness and Countability
*7. Godel’ s Incompleteness Theorem
*8. Unsolvability of the Satisfiability Problem in Predicate Logic
Part 4 Complexity
14 Abstract Complexity
1. The Blum Axioms
2. The Gap Theorem
3. Preliminary Form of the Speedup Theorem
4. The Speedup Theorem Concluded
15 Polynomial-Time Computability
1. Rates of Growth
2. P versus NP
3. Cook’ s Theorem
4. Other NP-Complete Problems
Part 5 Semantics
16 Approximation Orderings
1. Programming Language Semantics
2. Partial Orders
3. Complete Partial Orders
4. Continuous Functions
5. Fixed Points
17 Denotational Semantics of Recursion Equations
1. Syntax
2. Semantics of Terms
3. Solutions to W-Programs
4. Denotational Semantics of W-Programs
5. Simple Data Structure Systems
6. Infinitary Data Structure Systems
18 Operational Semantics of Recursion Equations
1. Operational Semantics for Simple Data Structure Systems
2. Computable Functions
3. Operational Semantics for Infinitary Data Structure Systems

查看详情

相关分类

Literature&Fiction文学与虚构 ScienceFiction&Fantasy科幻与玄幻 Romance浪漫小说 Mystery&Thrillers神秘与惊悚 Teens青少年读物 Biographies&Memoirs传记与自传 Comics&GraphicNovels动漫与绘画小说 ELT英语学习 Reference参考书 StandardTest标准考试 Business&Investing商业与投资 Self-Help励志自助

目前没有书店销售此书，我们为您搜索到一些相关商品

目前没有书店销售此书