计算理论基础

计算理论基础
分享
扫描下方二维码分享到微信
打开微信,点击右上角”+“,
使用”扫一扫“即可将网页分享到朋友圈。
作者: [美] (Davis M.D.)
出版社: 人民邮电出版社
2009-05
版次: 1
ISBN: 9787115196576
定价: 79.00
装帧: 平装
开本: 16开
纸张: 胶版纸
页数: 609页
字数: 754千字
正文语种: 英语
  •   《计算理论基础可计算性复杂性和语言(英文版·第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
查看详情
好书推荐 / 更多
计算理论基础
价格的发现复杂约束市场中的拍卖设计
保罗·米尔格罗姆 著
计算理论基础
我的思想与观念:爱因斯坦自选集(袒露心迹之作,畅销60余年,中文版震撼上市)
张卜天 译者;果麦文化 出品;阿尔伯特·爱因斯坦
计算理论基础
宙斯的正义
[英]劳埃德-琼斯(Hugh Lloyd-Jones)
计算理论基础
法镜般的神眼之下(オールドレンズの神のもとで)
[日]堀江敏幸 著;陆求实 译
计算理论基础
末日机器:一个核战争策划者的自白
[美]丹尼尔·埃尔斯伯格
计算理论基础
为政——古代中国的致治理念
梁治平 著
计算理论基础
看不见的女人:家庭事务社会学//守望者·人间世
[英]安·奥克利 著
计算理论基础
甲骨文丛书·一个偶像的黄昏:弗洛伊德的谎言
米歇尔·翁福雷(Michel Onfray) 著;王甦 译
计算理论基础
古罗马的笑:演说家、弄臣和猴子
[英]玛丽·比尔德(Mary Beard)
计算理论基础
呼吸在一米之外(聚焦真实好故事的“天才捕手计划”全新纪实力作,记录大危机时期平凡人的悲喜)
陈拙 著;博集天卷 出品
计算理论基础
旧巢痕:金克木小说体回忆录。一个儿童眼中的旧时风物。一代大家传奇的教育启蒙。
金克木 著
计算理论基础
无声的角落——被隐匿的日本校园之恶
[日]池谷孝司