Efnisyfirlit

• The Nature of Computation
• Copyright
• Dedication
• Contents
• Figure Credits
• Preface
  • How to read this book
  • A note to the instructor
  • Note on the 2018 printing
• Chapter 1 Prologue
  • 1.1 Crossing Bridges
  • 1.2 Intractable Itineraries
  • 1.3 Playing Chess With God
  • 1.4 What Lies Ahead
  • Problems
  • Notes
• Chapter 2 The Basics
  • 2.1 Problems and Solutions
    • 2.1.1 What’s the Problem?
    • 2.1.2 Solutions and Algorithms
    • 2.1.3 Meet the Adversary
  • 2.2 Time, Space, and Scaling
    • 2.2.1 From Physics to Computer Science
    • 2.2.2 Euclidean Scaling
    • 2.2.3 Asymptotics
  • 2.3 Intrinsic Complexity
  • 2.4 The Importance of Being Polynomial
    • 2.4.1 Until the End of the World
    • 2.4.2 Details, and Why they don’t Matter
    • 2.4.3 Complexity Classes
  • 2.5 Tractability and Mathematical Insight
  • Problems
  • Notes
• Chapter 3 Insights and Algorithms
  • 3.1 Recursion
  • 3.2 Divide and Conquer
    • 3.2.1 Set This House in Order: Sorting
    • 3.2.2 Higher Powers
    • 3.2.3 The Fast Fourier Transform
  • 3.3 Dynamic Programming
    • 3.3.1 Moveable Type
    • 3.3.2 Genome Alignment
  • 3.4 Getting There From Here
    • 3.4.1 Exploration
    • 3.4.2 Middle-First Search
    • 3.4.3 Weighty Edges
    • 3.4.4 But How do we Know it Works?
  • 3.5 When Greed is Good
    • 3.5.1 Minimum Spanning Trees
    • 3.5.2 Building a Basis
    • 3.5.3 Viewing the Landscape
  • 3.6 Finding a Better Flow
  • 3.7 Flows, Cuts, and Duality
  • 3.8 Transformations and Reductions
  • Problems
  • Notes
• Chapter 4 Needles in a Haystack: the Class NP
  • 4.1 Needles and Haystacks
  • 4.2 A Tour of NP
    • 4.2.1 Colorful Graphs
    • 4.2.2 Can’t Get No Satisfaction
    • 4.2.3 Balancing Numbers
    • 4.2.4 Rival Academics and Cliquish Parties
  • 4.3 Search, Existence, and Nondeterminism
    • 4.3.1 NP, NTIME, and Exhaustive Search
    • 4.3.2 There Exists a Witness: The Logical Structure of NP
    • 4.3.3 What’s the N For? The Peculiar Power of Nondeterministic Computers
  • 4.4 Knots and Primes
    • 4.4.1 Primality
    • 4.4.2 Knots and Unknots
  • Problems
  • Notes
• Chapter 5 Who is the Hardest One of All? NP-Completeness
  • 5.1 When One Problem Captures Them All
  • 5.2 Circuits and Formulas
    • 5.2.1 From Programs to Circuits
    • 5.2.2 From Circuits to Formulas
  • 5.3 Designing Reductions
    • 5.3.1 Symmetry Breaking and NAESAT
    • 5.3.2 Choices, Constraints, and Colorings
    • 5.3.3 Setting a Threshold
    • 5.3.4 Fitting Things Together: TILING
    • 5.3.5 Bit by Bit
  • 5.4 Completeness as a Surprise
    • 5.4.1 When Maximizing is Harder than Minimizing
    • 5.4.2 When Good is Harder than Perfect
    • 5.4.3 Hitting the Bullseye
    • 5.4.4 Hard Arithmetic
    • 5.4.5 (Computationally) Complex Integrals
  • 5.5 The Boundary Between Easy and Hard
    • 5.5.1 Choice, or the Lack of it
    • 5.5.2 Paths, Webs, and Barriers
    • 5.5.3 One, Two, and Three Dimensions
  • 5.6 Finally, Hamiltonian Path
  • Problems
  • Notes
• Chapter 6 The Deep Question: P vs. NP
  • 6.1 What if P=NP?
    • 6.1.1 The Great Collapse
    • 6.1.2 As Below, So Above
    • 6.1.3 The Demise of Creativity
  • 6.2 Upper Bounds Are Easy, Lower Bounds Are Hard
    • 6.2.1 Sorting Black Boxes
    • 6.2.2 But are the Boxes Really Black?
  • 6.3 Diagonalization and the Time Hierarchy
  • 6.4 Possible Worlds
  • 6.5 Natural Proofs
    • 6.5.1 Circuit Complexity Classes
    • 6.5.2 PARITY is Not in AC0
    • 6.5.3 Pseudorandom Functions and Natural Proofs
    • 6.5.4 Where To Next?
  • 6.6 Problems in the Gap
  • 6.7 Nonconstructive Proofs
    • 6.7.1 Needles, Pigeons, and Local Search
    • 6.7.2 Parity and Hamiltonian Paths
    • 6.7.3 Sources, Sinks, and Fixed Points
    • 6.7.4 Nonconstructivism and Nondeterminism
  • 6.8 The Road Ahead
  • Problems
  • Notes
• Chapter 7 The Grand Unified Theory of Computation
  • 7.1 Babbage’s Vision and Hilbert’s Dream
    • 7.1.1 Computing with Steam
    • 7.1.2 The Foundations ofMathematics
  • 7.2 Universality and Undecidability
    • 7.2.1 Diagonalization and Halting
    • 7.2.2 The Halting Problem
    • 7.2.3 Recursive Enumerability
    • 7.2.4 A Tower of Gods
    • 7.2.5 From Undecidable Problems to Unprovable Truths
  • 7.3 Building Blocks: Recursive Functions
    • 7.3.1 Building Functions from Scratch
    • 7.3.2 Primitive Programming with BLOOP, and a Not-So-Primitive Function
    • 7.3.3 Run Until You’re Done: while Loops and μ-Recursion
    • 7.3.4 A Universal Function
  • 7.4 Formis Function: the λ-Calculus
    • 7.4.1 Functions are Forms
    • 7.4.2 Numbers are Functions Too
    • 7.4.3 The Power of λ
    • 7.4.4 Universality and Undecidability
  • 7.5 Turing’s Applied Philosophy
    • 7.5.1 Meet the Computer
    • 7.5.2 The Grand Unification
    • 7.5.3 The Church–Turing Thesis
  • 7.6 Computation Everywhere
    • 7.6.1 Computing with Counters
    • 7.6.2 Fantastic Fractions
    • 7.6.3 The Game of Tag
    • 7.6.4 The Meaning of Life
    • 7.6.5 Tiling the Plane
    • 7.6.6 From Chaos to Computation
  • Problems
  • Notes
• Chapter 8 Memory, Paths, and Games
  • 8.1 Welcome to the State Space
  • 8.2 Show Me The Way
  • 8.3 L and NL-Completeness
    • 8.3.1 One Bit at a Time: Log-Space Reductions
    • 8.3.2 REACHABILITY is NL-Complete
  • 8.4 Middle-First Search and Nondeterministic Space
  • 8.5 You Can’t Get There From Here
  • 8.6 PSPACE, Games, and Quantified SAT
    • 8.6.1 Logic and the REACHABILITY Game
    • 8.6.2 PSPACE-Completeness and the SAT Game
    • 8.6.3 Evaluating Game Trees
  • 8.7 Games People Play
    • 8.7.1 Geography
    • 8.7.2 Go
    • 8.7.3 Games One Person Plays
  • 8.8 Symmetric Space
  • Problems
  • Notes
• Chapter 9 Optimization and Approximation
  • 9.1 Three Flavors of Optimization
  • 9.2 Approximations
    • 9.2.1 Pebbles and Processors
    • 9.2.2 The Approximate Salesman
  • 9.3 Inapproximability
    • 9.3.1 Mind the Gap
    • 9.3.2 CoverMe: MIN VERTEX COVER
    • 9.3.3 Münchhausen’sMethod: MAX INDEPENDENT SET
  • 9.4 Jewels and Facets: Linear Programming
    • 9.4.1 Currents and Flows
    • 9.4.2 The Feasible Polytope
    • 9.4.3 Climbing the Polytope: the Simplex Algorithm
    • 9.4.4 How Complex is Simplex?
    • 9.4.5 Theory and Practice: Smoothed Analysis
  • 9.5 Through the Looking-Glass: Duality
    • 9.5.1 The Lowest Upper Bound
    • 9.5.2 Flows and Cuts, Again
    • 9.5.3 Duality and Complexity
  • 9.6 Solving by Balloon: Interior Point Methods
    • 9.6.1 Buoyancy and Repulsion
    • 9.6.2 The Newton Flow
  • 9.7 Hunting with Eggshells
    • 9.7.1 Convexity, Hyperplanes, and Separation Oracles
    • 9.7.2 Cutting Eggs in Half and Fitting Them in Smaller Eggs
    • 9.7.3 Semidefinite Programming
    • 9.7.4 Convexity and Complexity
  • 9.8 Algorithmic Cubism
    • 9.8.1 Integer Linear Programming
    • 9.8.2 Fuzzy Covers
    • 9.8.3 Easy Polyhedra: Unimodularity
  • 9.9 Trees, Tours, and Polytopes
    • 9.9.1 Spanning Trees
    • 9.9.2 The Relaxed Salesman
  • 9.10 Solving Hard Problems in Practice
    • 9.10.1 Heuristics and Local Search
    • 9.10.2 The Relaxed Salesman: Tree Bounds
    • 9.10.3 The Relaxed Salesman: Polyhedral Bounds
    • 9.10.4 Closing in: Branch and Bound
  • Problems
  • Notes
• Chapter 10 Randomized Algorithms
  • 10.1 Foiling the Adversary
  • 10.2 The Smallest Cut
  • 10.3 The Satisfied Drunkard: WalkSAT
  • 10.4 Solving in Heaven, Projecting to Earth
  • 10.5 Games Against the Adversary
    • 10.5.1 AND-OR Trees and NAND Trees
    • 10.5.2 The Minimax Theorem and Yao’s Principle
    • 10.5.3 Adversarial Inputs on the NAND Tree
  • 10.6 Fingerprints, Hash Functions, and Uniqueness
    • 10.6.1 Slinging Hash across the Solar System
    • 10.6.2 Making Solutions Unique
    • 10.6.3 Affine Functions and Pairwise Independence
    • 10.6.4 It’s Lonely at the Top (or Bottom)
  • 10.7 The Roots of Identity
    • 10.7.1 Digging at the Roots
    • 10.7.2 From Roots to Matchings
  • 10.8 Primality
    • 10.8.1 The Little Theorem That Could: the Fermat Test
    • 10.8.2 Square Roots: the Miller–Rabin Test
    • 10.8.3 Derandomization and the Riemann Hypothesis
    • 10.8.4 Polynomial Identities Again, and the AKS Algorithm
  • 10.9 Randomized Complexity Classes
  • Problems
  • Notes
• Chapter 11 Interaction and Pseudorandomness
  • 11.1 The Tale of Arthur and Merlin
    • 11.1.1 In Which Arthur Scrambles a Graph
    • 11.1.2 In Which Merlin Sees All
    • 11.1.3 In Which Arthur Learns Nothing but the Truth
    • 11.1.4 One-Way Functions, Bit Commitment, and Dinner Plates
  • 11.2 The Fable of the Chess Master
    • 11.2.1 From Formulas to Polynomials
    • 11.2.2 Reducing the Degree
  • 11.3 Probabilistically Checkable Proofs
    • 11.3.1 A Letter fromMerlin
    • 11.3.2 Systems of Equations
    • 11.3.3 Random Subsets of the System
    • 11.3.4 Error Correction
    • 11.3.5 Linearity Testing and Fourier Analysis
    • 11.3.6 Quadratic Consistency
    • 11.3.7 Putting It Together
    • 11.3.8 Gap Amplification
  • 11.4 Pseudorandom Generators and Derandomization
    • 11.4.1 Pseudorandom Generators
    • 11.4.2 Pseudorandomness and Cryptography
    • 11.4.3 From One-Way Functions to Pseudorandom Generators
    • 11.4.4 Derandomizing BPP and Nonuniform Algorithms
    • 11.4.5 Logarithmic Seeds and BPP = P
    • 11.4.6 Hardness and Randomness
    • 11.4.7 Possible Worlds
  • Problems
  • Notes
• Chapter 12 Random Walks and Rapid Mixing
  • 12.1 A Random Walk in Physics
    • 12.1.1 The Ising Model
    • 12.1.2 Flipping Spins and Sampling States
  • 12.2 The Approach to Equilibrium
    • 12.2.1 Markov Chains, Transition Matrices, and Ergodicity
    • 12.2.2 Detailed Balance, Symmetry, and Walks on Graphs
    • 12.2.3 The Total Variation Distance and Mixing Time
  • 12.3 Equilibrium Indicators
    • 12.3.1 Walking on the Hypercube
    • 12.3.2 Riffle Shuffles
  • 12.4 Coupling
  • 12.5 Coloring a Graph, Randomly
    • 12.5.1 Coupled Colorings
    • 12.5.2 Shortening the Chain
    • 12.5.3 A Clever Switch
    • 12.5.4 Beyond Worst-Case Couplings
  • 12.6 Burying Ancient History: Coupling from the Past
    • 12.6.1 Time Reversal, Spanning Trees and Falling Leaves
    • 12.6.2 From Time Reversal to Coupling from the Past
    • 12.6.3 From Above and Below: Surfaces and Random Tilings
    • 12.6.4 Colorings, Ice, and Spins
    • 12.6.5 The Ising Model, Revisited
  • 12.7 The Spectral Gap
    • 12.7.1 Decaying towards Equilibrium
    • 12.7.2 Walking on the Cycle
  • 12.8 Flows of Probability: Conductance
    • 12.8.1 Conductance
    • 12.8.2 Random Walks on Graphs and UNDIRECTED REACHABILITY
    • 12.8.3 Using Flows to Bound the Conductance
  • 12.9 Expanders
    • 12.9.1 Expansion and Conductance
    • 12.9.2 Finding Witnesses More Quickly
    • 12.9.3 Two Ways to Shear a Cat
    • 12.9.4 Growing Algebraic Trees
    • 12.9.5 The Zig-Zag Product
    • 12.9.6 UNDIRECTED REACHABILITY
  • 12.10 Mixing in Time and Space
  • Problems
  • Notes
• Chapter 13 Counting, Sampling, and Statistical Physics
  • 13.1 Spanning Trees and the Determinant
    • 13.1.1 The Determinant and its Properties
    • 13.1.2 The Laplacian and the Matrix-Tree Theorem
    • 13.1.3 Calculating the Determinant in Polynomial Time
  • 13.2 Perfect Matchings and the Permanent
  • 13.3 The Complexity of Counting
    • 13.3.1 #P and #P-Completeness
    • 13.3.2 The Permanent is Hard
  • 13.4 From Counting to Sampling, and Back
    • 13.4.1 The Caterpillar’s Tale
    • 13.4.2 Approximate Counting and Biased Sampling
  • 13.5 Random Matchings and Approximating the Permanent
    • 13.5.1 A Markov Chain and its Mixing Time
    • 13.5.2 Cycle Sets and Flipping Flows
    • 13.5.3 Counting Consistent Cycle Collections Cleverly
    • 13.5.4 Weighty Holes and Whittling Edges
  • 13.6 Planar Graphs and Asymptotics on Lattices
    • 13.6.1 From Permanents to Determinants
    • 13.6.2 Pfaffian Orientations
    • 13.6.3 Matchings on a Lattice
    • 13.6.4 Once More, With Pfaffians
  • 13.7 Solving the Ising Model
    • 13.7.1 The Partition Function
    • 13.7.2 The One-Dimensional Ising Model
    • 13.7.3 The Two-Dimensional Ising Model
    • 13.7.4 On to Three Dimensions?
  • Problems
  • Notes
• Chapter 14 When Formulas Freeze: Phase Transitions in Computation
  • 14.1 Experiments and Conjectures
    • 14.1.1 First Light
    • 14.1.2 Backtracking and Search Times
    • 14.1.3 The Threshold Conjecture
  • 14.2 Random Graphs, Giant Components, and Cores
    • 14.2.1 Erdős–Rényi Graphs
    • 14.2.2 The Branching Process
    • 14.2.3 The Giant Component
    • 14.2.4 The Giant Component Revisited
    • 14.2.5 The k-Core
  • 14.3 Equations of Motion: Algorithmic Lower Bounds
    • 14.3.1 Following a Single Branch
    • 14.3.2 Smarter Algorithms
    • 14.3.3 When Can We Use Differential Equations? Card Games and Randomness
  • 14.4 MagicMoments
    • 14.4.1 Great Expectations: First Moment Upper Bounds
    • 14.4.2 Closing the Asymptotic Gap: the Second Moment
    • 14.4.3 Symmetry Regained
    • 14.4.4 Weighted Assignments: Symmetry Through Balance
  • 14.5 The Easiest Hard Problem
    • 14.5.1 The Phase Transition
    • 14.5.2 The First Moment
    • 14.5.3 The Second Moment
  • 14.6 Message Passing
    • 14.6.1 Entropy and its Fluctuations
    • 14.6.2 The Factor Graph
    • 14.6.3 Messages that Count
    • 14.6.4 Marginal Distributions
    • 14.6.5 Loopy Beliefs
    • 14.6.6 Beliefs in Random k -SAT
  • 14.7 Survey Propagation and the Geometry of Solutions
    • 14.7.1 Macrostates, Clusters, and Correlations
    • 14.7.2 Entropies, Condensation, and the Legendre Transform
    • 14.7.3 Belief Propagation Reloaded
    • 14.7.4 Results and Reconciliation with Rigor
  • 14.8 Frozen Variables and Hardness
  • Problems
  • Notes
• Chapter 15 Quantum Computation
  • 15.1 Particles, Waves, and Amplitudes
  • 15.2 States and Operators
    • 15.2.1 Back to the State Space
    • 15.2.2 Bras and Kets
    • 15.2.3 Measurements, Projections, and Collapse
    • 15.2.4 UnitaryMatrices
    • 15.2.5 The Pauli and Hadamard Matrices, and Changing Basis
    • 15.2.6 Multi-Qubit States and Tensor Products
    • 15.2.7 Quantum Circuits
  • 15.3 Spooky Action at a Distance
    • 15.3.1 Cloning and Entanglement
    • 15.3.2 Alice, Bob, and Bell’s Inequalities
    • 15.3.3 Faster-Than-Light Communication, Mixed States, and Density Matrices
    • 15.3.4 Using Entanglement to Communicate
  • 15.4 Algorithmic Interference
    • 15.4.1 Two for One: Deutsch’s Problem
    • 15.4.2 Hidden Parities and the Quantum Fourier Transform
    • 15.4.3 Hidden Symmetries and Simon’s Problem
  • 15.5 Cryptography and Shor’s Algorithm
    • 15.5.1 The RSA Cryptosystem
    • 15.5.2 From Factoring to Order-Finding
    • 15.5.3 Finding Periodicity with the Quantum Fourier Transform
    • 15.5.4 Tight Peaks and Continued Fractions
    • 15.5.5 From the FFT to the QFT
    • 15.5.6 Key Exchange and DISCRETE LOG
  • 15.6 Graph Isomorphism and the Hidden Subgroup Problem
    • 15.6.1 Groups of Symmetries
    • 15.6.2 Coset States and the Nonabelian Fourier Transform
    • 15.6.3 Quantum Sampling and the Swap Test
  • 15.7 Quantum Haystacks: Grover’s Algorithm
    • 15.7.1 Rotating towards the Needle
    • 15.7.2 Entangling with the Haystack
  • 15.8 Quantum Walks and Scattering
    • 15.8.1 Walking the Line
    • 15.8.2 Schrödinger’s Equation and Quantum Diffusion
    • 15.8.3 Scattering off a Game Tree
  • Problems
  • Notes
• Appendix A Mathematical Tools
  • A.1 The Story of O
  • A.2 Approximations and Inequalities
    • A.2.1 Norms
    • A.2.2 The Triangle Inequality
    • A.2.3 The Cauchy–Schwarz Inequality
    • A.2.4 Taylor Series
    • A.2.5 Stirling’s Approximation
  • A.3 Chance and Necessity
    • A.3.1 ANDs and ORs
    • A.3.2 Expectations and Markov’s and Chebyshev’s Inequalities
    • A.3.3 The Birthday Problem
    • A.3.4 Coupon Collecting
    • A.3.5 Bounding the Variance: the Second Moment Method
    • A.3.6 Jensen’s Inequality
  • A.4 Dice and Drunkards
    • A.4.1 The Binomial Distribution
    • A.4.2 The Poisson Distribution
    • A.4.3 Entropy and the Gaussian Approximation
    • A.4.4 Random Walks
  • A.5 Concentration Inequalities
    • A.5.1 Chernoff Bounds
    • A.5.2 Martingales and Azuma’s inequality
  • A.6 Asymptotic Integrals
    • A.6.1 Laplace’s Method
    • A.6.2 TheMethod of Stationary Phase
  • A.7 Groups, Rings, and Fields
    • A.7.1 Subgroups, Lagrange, and Fermat
    • A.7.2 Homomorphisms and Isomorphisms
    • A.7.3 The Chinese Remainder Theorem
    • A.7.4 Rings and Fields
    • A.7.5 Polynomials and Roots
  • Problems
• References
• Index

UM RAFBÆKUR Á HEIMKAUP.IS

Bókahillan þín er þitt svæði og þar eru bækurnar þínar geymdar. Þú kemst í bókahilluna þína hvar og hvenær sem er í tölvu eða snjalltæki. Einfalt og þægilegt!

Rafbók til eignar
Rafbók til eignar þarf að hlaða niður á þau tæki sem þú vilt nota innan eins árs frá því bókin er keypt.

Þú kemst í bækurnar hvar sem er
Þú getur nálgast allar raf(skóla)bækurnar þínar á einu augabragði, hvar og hvenær sem er í bókahillunni þinni. Engin taska, enginn kyndill og ekkert vesen (hvað þá yfirvigt).

Auðvelt að fletta og leita
Þú getur flakkað milli síðna og kafla eins og þér hentar best og farið beint í ákveðna kafla úr efnisyfirlitinu. Í leitinni finnur þú orð, kafla eða síður í einum smelli.

Glósur og yfirstrikanir
Þú getur auðkennt textabrot með mismunandi litum og skrifað glósur að vild í rafbókina. Þú getur jafnvel séð glósur og yfirstrikanir hjá bekkjarsystkinum og kennara ef þeir leyfa það. Allt á einum stað.

Hvað viltu sjá? / Þú ræður hvernig síðan lítur út
Þú lagar síðuna að þínum þörfum. Stækkaðu eða minnkaðu myndir og texta með multi-level zoom til að sjá síðuna eins og þér hentar best í þínu námi.



Fleiri góðir kostir
- Þú getur prentað síður úr bókinni (innan þeirra marka sem útgefandinn setur)
- Möguleiki á tengingu við annað stafrænt og gagnvirkt efni, svo sem myndbönd eða spurningar úr efninu
- Auðvelt að afrita og líma efni/texta fyrir t.d. heimaverkefni eða ritgerðir
- Styður tækni sem hjálpar nemendum með sjón- eða heyrnarskerðingu