- 计算的本质(英文版)/香农信息科学经典
- - 作者：(美)克里斯托弗·摩尔//(德)斯蒂芬·默滕斯|责编:陈亮
  - 出版社：世图出版公司
  - ISBN：9787523206591
  - 出版日期：2023/09/01
  - 页数：985
- 售价：91.2

内容大纲
计算复杂性是现代数学中最美的领域之一，它与从物理学到生物学的其他科学也息息相关。但这种美往往被不必要的形式主义所掩盖，而交互式证明、密码学和量子计算等令人兴奋的最新成果常常被认为过于“先进”，无法向普通学生展现。这本书的目的是通过以一种清晰而愉悦的方式解释理论计算机科学的深刻思想来予以弥合。书中包括很多有趣且深刻的主题：Pvs。NP问题；迷宫和棋牌游戏的复杂性；优化和估计；随机化算法、交互式证明和伪随机性；马尔可夫链和相变；以及量子计算等。
作者介绍
目录
Figure Credits
Preface
1  Prologue
  1.1  CrossingBridges
  1.2  IntractableItineraries
  1.3  Playing ChessWith God
  1.4  What LiesAhead
  Problems
  Notes
2  The Basics
  2.1  Problems and Solutions
  2.2  Time，Space，and Scaling
  2.3  Intrinsic Complexity
  2.4  The Importance ofBeingPolynomial
  2.5  TractabilityandMathematicalInsight
  Problems
  Notes
3  Insights and Algorithms
  3.1  Recursion
  3.2  Divide and Conquer
  3.3  DynamicProgramming
  3.4  GettingThere FromHere
  3.5  When Greedis Good
  3.6  FindingaBetterFlow
  3.7  Flows，Cuts，and Duality
  3.8  Transformations andReductions
  Problems
  Notes
4  NeedlesInaHaystack：theClassNP
  4.1  Needles andHaystacks
  4.2  AT0ur 0fNP
  4.3  Search。Existence，andNondeterminism
  4.4  Knots and Primes
  Problems
  Notes
5  WhO is the Hardest One of All?NP-Completeness
  5.1  Ⅵmen 0ne Problem CapturesThemAll
  5.2  Circuits andFormulas
  5.3  DesigningReductions
  5.4  Completeness as aSurprise
  5.5  The BoundaryBetween EasyandHard
  5.6  Finally,Hamfltonian path
  Problems
  Notes
6 The Deep Question：P vs.NP
  6.1  WhatifP=NP
  6.2  UpperBounds are Easy,LowerBoundsAre Hard
  6.3  Diagonalization andthe Time Hierarchy
  6.4  PossibleWbrlds
  6.5  NaturalProofs

  6.6  Problemsinthe Gap
  6.7  Nonconstructive PrOOfs
  6.8  The RoadAhead
  Problems
  Notes
7  The Grand Unified Theory of Computation
  7.1  Babbage~Vision and Hilbert's Dream
  7.2  Universalityand Undecidabnit、
  7.3  BuildingBlocks：Recursive Functions
  7.4  Formis Function：the A—Calculus
  7.5  Turing'sApplied Philosophy
  7.6  ComputationEverywhere
  Problems
  Notes
8  Memory,Paths,and Games
  8.1  Wlelcometothe State Space
  8.2  ShowMe TheWay
  8.3  LandNL.Completeness
  8.4  Middle.First Search and Nondeterministic Space
  8.5  Y0u Cant GetThereFromHere
  8.6  PSPACE，Games，and Quantified SAT
  8.7  Games People Play
  8.8  Symmetric Space
  Problems
  Notes
9  Optimization and Approximation
  9.1  Three Flavors ofOptimization
  9.2  Approximations
  9.3  Inapproximability
  9.4  Jewels andFacets：LinearProgramming
  9.5  Throughthe Looking-Glass：Duality
  9.6  SolvingbyBalloon：InteriorPointMethods
  9.7  Huntingwitll EggsheHs
  9.8  A1gorithmic Cubism
  9.9  Trees，Tours，andPolytopes
  9.10  SolvingHard ProblemsinPractice
  Problems
  Notes
10  Randomized Algorithms
  10.1  FoilingtheAdversary
  10.2  111e SmallestCut
  10.3  The Satisfied Drunkard：WalkSAT
  10.4  Solvingin Heaven.Projectingto Earth
  10.5  GamesAgainsttheAdversary
  10.6  Fingerprints，HashFunctions，andUniqueness
  10.7  The Roots ofIdentity
  10.8  Primalit、
  10.9  Randomized ComplexityClasses
  Problems
  Notes

11  Interacflon and Pseudorandomness
  11.1  TheTale ofArthurandMerlin
  11.2  The Fable ofthe Chess Master
  11.3  ProbabilisticallyCheckable Proofs
  11.4 Pseudorandom Generators and Derandomization
  Problems
  Nores
12  Random Walks and Rapid Mixing
  12.1  A Random、^mkin Physics
  12.2  The Approachto Equfl~rium
  12.3  EquflibriumIndicators
  12.4  Coupling
....
  12.5  Coloring aGraph.Randomly
  12.6  BuryingAncientHistory：CouplingfromthePast
  12.7  The Spectral Gap
  12.8  FlOWS ofProbabnity：Conductance
  12.9  Expanders
  12.10  MixinginTime andSpace
  Problems
  Notes
13  Counting,Sampling，and StatisflcM Physics
  13.1  SpanningTrees andthe Determinant
  13.2  PerfectMatchings andthe Permanent
  13.3  The ComplexityofCounting
  13.4  From Countingto Sampling.and Back
  13.5  RandomMatchings andApproximatingthePermanent
  13.6  P1anal：Graphs andAsymptotics onLattices
  13.7  SolvingtheIsingModel
  Problems
  Notes
14  When Formulas Freeze：Phase Transitons in Computation
  14.1  Experiments and Coniectures
  14.2  Random Graphs，Giant Components，and Cores
  14.3  Equations of Motion：Algorithmic Lower Bounds
  14.4  Magic Moments
  14.5  The Easiest Hard Problem
  14.6  Message Passing
  14.7  Survey Propagation and the Geometry of Solutions
  14.8  Frozen Variables and Hardness
  Problems
  Notes
15  Quantum Computation
  15.1  Particles，Waves,and Amplitudes
  15.2  States and Operators
  15.3  SpookyAction at a Distance
  15.4  Algorithmic Interference
  15.5  Cryptography and Shor's Algorithm
  15.6  Graph Isomorphism and the Hidden Subgroup Problem
  15.7  Quantum Haystacks：Grover's Algorithm

  15.8  Quantum Walks and Scattering
  Problems
  Notes
A  MathematicalTools
  A.1  The Story Of 0
  A.2  Approximations and Inequalities
  A.3  Chance and Necessity
  A.4  Dice and Drunkards
  A5  C0ncentration Inequalities
  A.6  Asymptotic Integrals
  A.7  Groups，Rings，and Fields
  Problems
References
Index

内容大纲

作者介绍

目录

同类热销排行榜

推荐书目