计算理论基础

计算理论基础
分享
扫描下方二维码分享到微信
打开微信,点击右上角”+“,
使用”扫一扫“即可将网页分享到朋友圈。
作者: [美] (Davis M.D.)
2009-05
版次: 1
ISBN: 9787115196576
定价: 79.00
装帧: 平装
开本: 16开
纸张: 胶版纸
页数: 609页
字数: 754千字
正文语种: 英语
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
查看详情
系列丛书 / 更多
计算理论基础
算法(英文版•第4版)
[美]塞奇威克(Robert Sedgewick)、[美]韦恩(Kevin Wayne) 著
计算理论基础
计算机程序设计艺术(第2卷 英文版·第3版):半数值算法
[美]高德纳 著
计算理论基础
计算机程序设计艺术,卷4A:组合算法(一)(英文版)
[美]Donald E.Knuth 著
计算理论基础
计算机程序设计艺术(第3卷 英文版·第2版):排序与查找
[美]高德纳(Knuth D.E) 著
计算理论基础
C++Primer(英文版)(第4版)
李普曼 著
计算理论基础
UNIX环境高级编程
史蒂文斯、拉戈 著
计算理论基础
信息检索:算法与启发式方法(英文版·第2版)
[美]格罗斯曼、[美]弗里德 著
计算理论基础
数据结构与算法分析:C++描述(英文版)(第3版)
[美]维斯 著
计算理论基础
Web数据挖掘:超文本数据的知识发现
[印]查凯莱巴蒂 著
计算理论基础
TCP/IP 详解(卷2):实现(英文版)
[美]赖特(Gary R.Wright)、[美]史蒂文斯(W.Richard Stevens) 著
计算理论基础
IPv6详解,第1卷,核心协议实现:IPv6时代的《TCP/IP详解》!
[美]李清、[日]神明达哉、[日]岛庆一 著
计算理论基础
TCP/IP详解 卷1:协议(英文版):协议-TCP/IP详解-英文版
[美]史蒂文斯 著
相关图书 / 更多
计算理论基础
计算机基础与实训教程
顾玲芳 编
计算理论基础
计算机网络攻击与防护
刘念;陈雪松;谈洪磊
计算理论基础
计算机组成原理与汇编语言
田民格、秦彩杰、林观俊、田佳琪
计算理论基础
计算天文
冯毅
计算理论基础
计算思维培养与无人机创意编程
范谊 陈宇 张锦东
计算理论基础
计算机组成原理与系统结构(第3版)
冯建文 章复嘉 赵建勇 包健 编著
计算理论基础
计算小状元 小学数学 2年级上册 bs版 小学数学单元测试 新华
作者
计算理论基础
计算机应用基础
苗苗
计算理论基础
计算机系统原理(2023年版) 全国高等教育自学考试指导委员会
全国高等教育自学考试指导委员会
计算理论基础
计算机组装与维护(第3版高等院校计算机应用技术规划教材)
孙中胜 编
计算理论基础
计算机辅助翻译教程()
赵秋荣
计算理论基础
计算机三维建模方法
易健宏 编著;李凤仙
您可能感兴趣 / 更多
计算理论基础
宇宙视觉史:从宇宙大爆炸到时间的尽头
[美]查尔斯·刘 著;高爽 译者;[美]马克西姆· 马洛维奇科 绘;未读 出品
计算理论基础
写出我心 普通人如何通过写作表达自己(平装本)
[美]娜塔莉·戈德堡(Natalie Goldberg)
计算理论基础
写出我心3 写作疗愈的真正秘密
[美]娜塔莉·戈德堡(Natalie Goldberg)
计算理论基础
神套路:为什么我们总被带节奏(狂热与网红时代醍醐灌顶之作,教给普通人安身立命的不二法门!)
[美]阿里·阿莫萨维 著;[哥伦比亚]亚历杭德罗·希拉尔多 绘
计算理论基础
阿伦森自传
[美]埃利奥特·阿伦森(Elliot Aronson) 著;沈捷 译;湛庐文化 出品
计算理论基础
街头官僚:公共服务中的个人困境
[美]迈克尔·李普斯基(Michael Lipsky)
计算理论基础
史前至蒙古帝国时期的内欧亚大陆史
[美]大卫·克里斯蒂安 著;潘玲 译;杨建华 校
计算理论基础
意大利文艺复兴新艺术史
[美]迈克尔·韦恩·科尔 著;[美]斯蒂芬·J·坎贝尔;邵亦杨
计算理论基础
老人与海 彩图注音版 一二三四年级5-6-7-8-9岁小学生课外阅读经典 儿童文学无障碍有声伴读世界名著童话故事
[美]海明威
计算理论基础
养育的觉醒:全面激发孩子自驱力,教你如何心平气和做妈妈
[美]凯文·莱曼 著;唐晓璐 译;斯坦威 出品
计算理论基础
自律我也能做到(全9册)
[美]康妮·科维尔·米勒 著;[阿根廷]维多利亚·阿萨纳利 绘
计算理论基础
你在等什么?
[美]斯科特·明钦 著;[中]易万 译;[美]马特 ·斐兰 绘