未读消息消息

购物车

我的订单

个人中心

店铺

我的订单收藏

拍卖

拍卖交易我的竞拍收藏

我的好友资金账户

卖家中心

客服 |

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

客服电话

010-89648155

服务时间

客服咨询 8:00-21:00

纠纷处理 9:00-21:00

图书审核 9:00-18:00

监督与建议

请选择

手机孔网

计算理论基础

作者: [美] 戴维斯（Davis M.D.）著

出版社: 人民邮电出版社

出版时间: 2009-05

版次: 1

ISBN: 9787115196576

定价: 79.00

装帧: 平装

开本: 16开

纸张: 胶版纸

页数: 609页

字数: 754千字

正文语种: 英语

丛书: 图灵原版计算机科学系列

分类: 计算机与互联网

1 张插图图片

23人买过

　　《计算理论基础可计算性复杂性和语言(英文版·第2版)》是理论计算机科学领域的名作，是计算机科学核心主题的导论性教材。全书分为可计算性、文法与自动机、逻辑学、复杂性及语义学5个部分，分别讲述了可计算性理论、形式语言、逻辑学与自动演绎、可计算复杂性(包括NP完全问题)和编程语言的语义等主题，并展示了它们之间如何相互关联。《计算理论基础可计算性复杂性和语言(英文版·第2版)》是计算机及相关专业高年级本科生和研究生的理想教学参考书，对于计算机领域的专业人士也是很好的技术参考书。　　MartinD．Davis，著名计算机科学家和数学家。1950年在普林斯顿大学获得博士学位，与图灵同门（导师均为计算科学大师AlonzoChurch）。后长期任教于纽约大学柯朗数学研究所。他是自动演绎理论先驱，还是DPLL算法的发明人之一，Post-Turing机更使其声名远播。除本书外，他还著有经典名著ComputabilityandUnsolvability。
　　RonSigal，资深软件工程师。1983年在纽约大学获得计算机科学博士学位。曾先后任教于纽约城市大学、意大利卡塔尼亚大学、耶鲁大学、Hofstra大学。他参与的软件项目有NASA的火星探路者、JBoss等。
　　ElaineJ．Weyuker，著名女计算机科学家。美国国家工程院院士、IEEE和ACM会士、AT＆T院士、ACM妇女委员会主席、ACM执行委员，现任AT＆T实验室研究员。她的主要研究领域是软件测试与可靠性。此前曾任纽约大学柯朗数学研究所计算机科学教授近20年。 Contents
IPreliminaries1
1.Setsandn-tuples1
2.Functions3
3.AlphabetsandStrings4
4.Predicates5
5.Quantifiers6
6.ProofbyContradiction8
7.MathematicalInduction9

Part1Computability15
2ProgramsandComputableFunctions17
1.AProgrammingLanguage17
2.SomeExamplesofPrograms18
3.Syntax25
4.ComputableFunctions28
5.MoreaboutMacros32
3PrimitiveRecursiveFunctions39
1.Composition39
2.Recursion40
3.PRCClasses42
4.SomePrimitiveRecursiveFunctions44
5.PrimitiveRecursivePredicates49
6.IteratedOperationsandBoundedQuantifiers52
7.Minimalization55
8.PairingFunctionsandG6delNumbers59
4AUniversalProgram65
1.CodingProgramsbyNumbers65
2.TheHaltingProblem68
3.Universality70
4.RecursivelyEnumerableSets78
5.TheParameterTheorem85
6.DiagonalizationandReducibility88
7.RicesTheorem95
*8.TheRecursionTheorem97
*9.AComputableFunctionThatIsNotPrimitiveRecursive105
5CalculationsonStrings113
1.NumericalRepresentationofStrings113
2.AProgrammingLanguageforStringComputations121
3.TheLanguagesandn126
4.Post-TuringPrograms129
5.Simulationofnin135
6.Simulationofin140
6TuringMachines145
1.InternalStates145
2.AUniversalTuringMachine152
3.TheLanguagesAcceptedbyTuringMachines153
4.TheHaltingProblemforTuringMachines157
5.NondeterministicTuringMachines159
6.VariationsontheTuringMachineTheme162
7ProcessesandGrammars169
1.Semi-ThueProcesses169
2.SimulationofNondeterministicTuringMachinesbySemi-ThueProcesses171
3.UnsolvableWordProblems176
4.PostsCorrespondenceProblem181
5.Grammars186
6.SomeUnsolvableProblemsConcerningGrammars191
7.NormalProcesses192
8ClassifyingUnsolvableProblems197
1.UsingOracles197
2.RelativizationofUniversality201
3.Reducibility207
4.Setsr.e.RelativetoanOracle211
5.TheArithmeticHierarchy215
6.PostsTheorem217
7.ClassifyingSomeUnsolvableProblems224
8.RicesTheoremRevisited230
9.RecursivePermutations231

Part2GrammarsandAutomata235
9RegularLanguages237
1.FiniteAutomata237
2.NondeterministicFiniteAutomata242
3.AdditionalExamples247
4.ClosureProperties249
5.KleenesTheorem253
6.ThePumpingLemmaandItsApplications260
7.TheMyhill-NerodeTheorem263
10Context-FreeLanguages269
1.Context-FreeGrammarsandTheirDerivationTrees269
2.RegularGrammars280
3.ChomskyNormalForm285
4.Bar-HillelsPumpingLemma287
5.ClosureProperties291
*6.SolvableandUnsolvableProblems297
7.BracketLanguages301
8.PushdownAutomata308
9.CompilersandFormalLanguages323
11Context-SensitiveLanguages327
1.TheChomskyHierarchy327
2.LinearBoundedAutomata330
3.ClosureProperties337

Part3Logic345
12PropositionalCalculus347
1.FormulasandAssignments347
2.TautologicalInference352
3.NormalForms353
4.TheDavis-PutnamRules360
5.MinimalUnsatisfiabilityandSubsumption366
6.Resolution367
7.TheCompactnessTheorem370
13QuantificationTheory375
1.TheLanguageofPredicateLogic375
2.Semantics377
3.LogicalConsequence382
4.HerbrandsTheorem388
5.Unification399
6.CompactnessandCountability404
*7.G6delsIncompletenessTheorem407
*8.UnsolvabilityoftheSatisfiabilityProbleminPredicateLogic410

Part4Complexity417
14AbstractComplexity419
1.TheBlumAxioms419
2.TheGapTheorem425
3.PreliminaryFormoftheSpeedupTheorem428
4.TheSpeedupTheoremConcluded435
15Polynomial-TimeComputability439
1.RatesofGrowth439
2.PversusNP443
3.CooksTheorem451
4.OtherNP-CompleteProblems457

Part5Semantics465
16ApproximationOrderings467
1.ProgrammingLanguageSemantics467
2.PartialOrders472
3.CompletePartialOrders475
4.ContinuousFunctions486
5.FixedPoints494
17DenotationalSemanticsofRecursionEquations505
1.Syntax505
2.SemanticsofTerms511
3.SolutionstoW-Programs520
4.DenotationalSemanticsofW-Programs530
5.SimpleDataStructureSystems539
6.InfinitaryDataStructureSystems544
18OperationalSemanticsofRecursionEquations557
1.OperationalSemanticsforSimpleDataStructureSystems557
2.ComputableFunctions575
3.OperationalSemanticsforlnfinitaryDataStructureSystems584
SuggestionsforFurtherReading593
NotationIndex595
Index599
内容简介:
　　《计算理论基础可计算性复杂性和语言(英文版·第2版)》是理论计算机科学领域的名作，是计算机科学核心主题的导论性教材。全书分为可计算性、文法与自动机、逻辑学、复杂性及语义学5个部分，分别讲述了可计算性理论、形式语言、逻辑学与自动演绎、可计算复杂性(包括NP完全问题)和编程语言的语义等主题，并展示了它们之间如何相互关联。《计算理论基础可计算性复杂性和语言(英文版·第2版)》是计算机及相关专业高年级本科生和研究生的理想教学参考书，对于计算机领域的专业人士也是很好的技术参考书。
作者简介:
　　MartinD．Davis，著名计算机科学家和数学家。1950年在普林斯顿大学获得博士学位，与图灵同门（导师均为计算科学大师AlonzoChurch）。后长期任教于纽约大学柯朗数学研究所。他是自动演绎理论先驱，还是DPLL算法的发明人之一，Post-Turing机更使其声名远播。除本书外，他还著有经典名著ComputabilityandUnsolvability。
　　RonSigal，资深软件工程师。1983年在纽约大学获得计算机科学博士学位。曾先后任教于纽约城市大学、意大利卡塔尼亚大学、耶鲁大学、Hofstra大学。他参与的软件项目有NASA的火星探路者、JBoss等。
　　ElaineJ．Weyuker，著名女计算机科学家。美国国家工程院院士、IEEE和ACM会士、AT＆T院士、ACM妇女委员会主席、ACM执行委员，现任AT＆T实验室研究员。她的主要研究领域是软件测试与可靠性。此前曾任纽约大学柯朗数学研究所计算机科学教授近20年。
目录:
Contents
IPreliminaries1
1.Setsandn-tuples1
2.Functions3
3.AlphabetsandStrings4
4.Predicates5
5.Quantifiers6
6.ProofbyContradiction8
7.MathematicalInduction9

Part1Computability15
2ProgramsandComputableFunctions17
1.AProgrammingLanguage17
2.SomeExamplesofPrograms18
3.Syntax25
4.ComputableFunctions28
5.MoreaboutMacros32
3PrimitiveRecursiveFunctions39
1.Composition39
2.Recursion40
3.PRCClasses42
4.SomePrimitiveRecursiveFunctions44
5.PrimitiveRecursivePredicates49
6.IteratedOperationsandBoundedQuantifiers52
7.Minimalization55
8.PairingFunctionsandG6delNumbers59
4AUniversalProgram65
1.CodingProgramsbyNumbers65
2.TheHaltingProblem68
3.Universality70
4.RecursivelyEnumerableSets78
5.TheParameterTheorem85
6.DiagonalizationandReducibility88
7.RicesTheorem95
*8.TheRecursionTheorem97
*9.AComputableFunctionThatIsNotPrimitiveRecursive105
5CalculationsonStrings113
1.NumericalRepresentationofStrings113
2.AProgrammingLanguageforStringComputations121
3.TheLanguagesandn126
4.Post-TuringPrograms129
5.Simulationofnin135
6.Simulationofin140
6TuringMachines145
1.InternalStates145
2.AUniversalTuringMachine152
3.TheLanguagesAcceptedbyTuringMachines153
4.TheHaltingProblemforTuringMachines157
5.NondeterministicTuringMachines159
6.VariationsontheTuringMachineTheme162
7ProcessesandGrammars169
1.Semi-ThueProcesses169
2.SimulationofNondeterministicTuringMachinesbySemi-ThueProcesses171
3.UnsolvableWordProblems176
4.PostsCorrespondenceProblem181
5.Grammars186
6.SomeUnsolvableProblemsConcerningGrammars191
7.NormalProcesses192
8ClassifyingUnsolvableProblems197
1.UsingOracles197
2.RelativizationofUniversality201
3.Reducibility207
4.Setsr.e.RelativetoanOracle211
5.TheArithmeticHierarchy215
6.PostsTheorem217
7.ClassifyingSomeUnsolvableProblems224
8.RicesTheoremRevisited230
9.RecursivePermutations231

Part2GrammarsandAutomata235
9RegularLanguages237
1.FiniteAutomata237
2.NondeterministicFiniteAutomata242
3.AdditionalExamples247
4.ClosureProperties249
5.KleenesTheorem253
6.ThePumpingLemmaandItsApplications260
7.TheMyhill-NerodeTheorem263
10Context-FreeLanguages269
1.Context-FreeGrammarsandTheirDerivationTrees269
2.RegularGrammars280
3.ChomskyNormalForm285
4.Bar-HillelsPumpingLemma287
5.ClosureProperties291
*6.SolvableandUnsolvableProblems297
7.BracketLanguages301
8.PushdownAutomata308
9.CompilersandFormalLanguages323
11Context-SensitiveLanguages327
1.TheChomskyHierarchy327
2.LinearBoundedAutomata330
3.ClosureProperties337

Part3Logic345
12PropositionalCalculus347
1.FormulasandAssignments347
2.TautologicalInference352
3.NormalForms353
4.TheDavis-PutnamRules360
5.MinimalUnsatisfiabilityandSubsumption366
6.Resolution367
7.TheCompactnessTheorem370
13QuantificationTheory375
1.TheLanguageofPredicateLogic375
2.Semantics377
3.LogicalConsequence382
4.HerbrandsTheorem388
5.Unification399
6.CompactnessandCountability404
*7.G6delsIncompletenessTheorem407
*8.UnsolvabilityoftheSatisfiabilityProbleminPredicateLogic410

Part4Complexity417
14AbstractComplexity419
1.TheBlumAxioms419
2.TheGapTheorem425
3.PreliminaryFormoftheSpeedupTheorem428
4.TheSpeedupTheoremConcluded435
15Polynomial-TimeComputability439
1.RatesofGrowth439
2.PversusNP443
3.CooksTheorem451
4.OtherNP-CompleteProblems457

Part5Semantics465
16ApproximationOrderings467
1.ProgrammingLanguageSemantics467
2.PartialOrders472
3.CompletePartialOrders475
4.ContinuousFunctions486
5.FixedPoints494
17DenotationalSemanticsofRecursionEquations505
1.Syntax505
2.SemanticsofTerms511
3.SolutionstoW-Programs520
4.DenotationalSemanticsofW-Programs530
5.SimpleDataStructureSystems539
6.InfinitaryDataStructureSystems544
18OperationalSemanticsofRecursionEquations557
1.OperationalSemanticsforSimpleDataStructureSystems557
2.ComputableFunctions575
3.OperationalSemanticsforlnfinitaryDataStructureSystems584
SuggestionsforFurtherReading593
NotationIndex595
Index599

查看详情

计算理论基础

内容简介:

作者简介:

目录: