Information, physics, and computation / Mézard, Marc

Public ISBD Titre : Information, physics, and computation Type de document : texte imprimé Auteurs : Mézard, Marc, Auteur ; Montanari, Andrea, Auteur Editeur : Oxford : Oxford university press Année de publication : 2009 Collection : Oxford graduate texts Importance : 1 vol. (569 p.) Présentation : ill., couv. ill. en coul. Format : 26 cm ISBN/ISSN/EAN : 978-0-19-857083-7 Note générale : 978-0-19-857083-7 Langues : Anglais (eng) Catégories : Physique Mots-clés : Physique statistique Codage Informatique Index. décimale : 530.13 Mécanique statistique et physique statistique, Résumé : Cet ouvrage présente une approche unifiée d'un domaine de recherche riche et en évolution rapide à l'interface entre la physique statistique, l'informatique théorique / les mathématiques discrètes et la théorie de la codification et de l'information. Il est accessible aux étudiants diplômés et aux chercheurs sans formation spécifique dans aucun de ces domaines. Les sujets sélectionnés incluent des verres de rotation, des codes de correction d'erreurs, la satisfaction et sont au centre de chaque champ. L'approche se concentre sur les grands cas aléatoires et adopte une formulation probabiliste commune en termes de modèles graphiques. Il présente des algorithmes de passage de messages tels que la propagation de croyances et la propagation de sondages, et leur utilisation dans le décodage et la résolution de satisfaction de contraintes. Il explique également les techniques d'analyse comme l'évolution de la densité et la méthode de la cavité, et les utilise pour étudier les transitions de phase. Note de contenu : Sommaire PART 1 BACKGROUND 1 Introduction to information theory 3 1.1 Random variables 3 1.2 Entropy 5 1.3 Sequences of random variables and their entropy rate 8 1.4 Correlated variables and mutual information 10 1.5 Data compression 12 1.6 Data transmission 16 Notes 21 2 Statistical physics and probability theory 23 2.1 The Boltzmann distribution 24 2.2 Thermodynamic potentials 28 2.3 The fluctuation-dissipation relations 32 2.4 The thermodynamic limit 33 2.5 Ferromagnets and Ising models 35 2.6 The Ising spin glass 44 Notes 46 3 Introduction to combinatorial optimization 47 3.1 A first example: The minimum spanning tree 48 3.2 General definitions 51 3.3 More examples 51 3.4 Elements of the theory of computational complexity 54 3.5 Optimization and statistical physics 60 3.6 Optimization and coding 61 Notes 62 4 A probabilistic toolbox 65 4.1 Many random variables: A qualitative preview 65 4.2 Large deviations for independent variables 66 4.3 Correlated variables 72 4.4 The Gibbs free energy 77 4.5 The Monte Carlo method 80 4.6 Simulated annealing 86 4.7 Appendix: A physicist's approach to Sanov's theorem 87 Notes 89 x Contents PART II INDEPENDENCE 5 The random energy model 93 5.1 Definition of the model 93 5.2 Thermodynamics of the REM 94 5.3 The condensation phenomenon 100 5.4 A comment on quenched and annealed averages 101 5.5 The random subcube model 103 Notes 105 6 The random code ensemble 107 6.1 Code ensembles 107 6.2 The geometry of the random code ensemble 110 6.3 Communicating over a binary symmetric channel 112 6.4 Error-free communication with random codes 120 6.5 Geometry again: Sphere packing 123 6.6 Other random codes 126 6.7 A remark on coding theory and disordered systems 127 6.8 Appendix: Proof of Lemma 6.2 128 Notes 128 7 Number partitioning 131 7.1 A fair distribution into two groups? 131 7.2 Algorithmic issues 132 7.3 Partition of a random list: Experiments 133 7.4 The random tost model 136 7.5 Partition of a random list: Rigorous results 140 Notes 143 8 Introduction to replica theory 145 8.1 Replica solution of the random energy model 145 8.2 The fully connected p-spin glass model 155 8.3 Extreme value statistics and the REM 163 8.4 Appendix: Stability of the RS saddle point 166 Notes 169 PART III MODELS ON GRAPHS 9 Factor graphs and graph ensembles 173 9.1 Factor graphs 173 9.2 Ensembles of factor graphs: Definit ions 180 9.3 Random factor graphs: Basic properties 182 9.4 Random factor graphs: The giant component 187 9.5 The locally tree-like structure of random graphs 191 Notes 194 10 Satisfiability 197 10.1 The satisfiability problem 197 Contents xi 10.2 Algorithms 199 10.3 Random K-satisfiability ensembles 206 10.4 Random 2-SAT 209 10.5 The phase transition in random K(> 3)-SAT 209 Notes 217 11 Low-density parity-check codes 219 11.1 Definitions 220 11.2 The geometry of the codebook 222 11.3 LDPC codes for the binary symmetric channel 231 11.4 A simple decoder: Bit flipping 236 Notes 239 12 Spin glasses 241 12.1 Spin glasses and factor graphs 241 12.2 Spin glasses: Constraints and frustration 245 12.3 What is a glass phase? 250 12.4 An example: The phase diagram of the SK model 262 Notes 265 13 Bridges: Inference and the Monte Carlo method 267 13.1 Statistical inference 268 13.2 The Monte Carlo method: Inference via sampling 272 13.3 Free-energy barriers 281 Notes 287 PART IV SHORT-RANGE CORRELATIONS 14 Belief propagation 291 14.1 Two examples 292 14.2 Belief propagation an tree graphs 296 14.3 Optimization: Max-product and min-sum 305 14.4 Loopy BP 310 14.5 General message-passing algorithms 316 14.6 Probabilistic analysis 317 Notes 325 15 Decoding with belief propagation 327 15.1 BP decoding: The algorithm 327 15.2 Analysis: Density evolution 329 15.3 BP decoding for an erasure channel 342 15.4 The Bethe free energy and MAP decoding 347 Notes 352 16 The assignment problem 355 16.1 The assignment problem and random assignment ensembles 356 16.2 Message passing and its probabilistic analysis 357 16.3 A polynomial message-passing algorithm 366 xii Contents 16.4 Combinatorial results 371 16.5 An exercise: Multi-index assignment 376 Notes 378 17 Ising models an random graphs 381 17.1 The BP equations for Ising spins 381 17.2 RS cavity analysis 384 17.3 Ferromagnetic model 386 17.4 Spin glass models 391 Notes 399 PART V LONG-RANGE CORRELATIONS 18 Linear equations with Boolean variables 403 18.1 Definitions and general remarks 404 18.2 Belief propagation 409 18.3 Core percolation and BP 412 18.4 The SAT–UNSAT threshold in random XORSAT 415 18.5 The Hard-SAT phase: Clusters of solutions 421 18.6 An alternative approach: The cavity method 422 Notes 427 19 The 1RSB cavity method 19.1 Beyond BP: Many states 430 19.2 The 1RSB cavity equations 434 19.3 A first application: XORSAT 444 19.4 The special value x = 1 449 19.5 Survey propagation 453 19.6 The nature of 1RSB phases 459 19.7 Appendix: The SP(y) equations for XORSAT 463 Notes 465 20 Random K-satisfiability 20.1 Belief propagation and the replica-symmetric analysis 20.2 Survey propagation and the 1RSB phase 20.3 Some ideas about the full phase diagram 20.4 An exercise: Colouring random graphs Notes 21 Glassy states in coding theory 21.1 Local search algorithms and metastable states 21.2 The binary erasure channel 21.3 General binary memoryless Symmetrie channels 21.4 Metastable states and near-codewords Notes 22 An ongoing story 22.1 Gibbs measures and Jong-range correlation Contents xiii 22.2 Higher levels of replica symmetry breaking 524 22.3 Phase structure and the behaviour of algorithms 535 Notes 538 Appendix A Symbols and notation 541 A.1 Equivalence relations 541 A.2 Orders of growth 542 A.3 Combinatorics and probability 543 A.4 Summary of mathematical notation 544 A.5 Information theory 545 A.6 Factor graphs 545 A.7 Cavity and message-passing methods 545 References 547 Inde Côte titre : Fs/13934-13935 Information, physics, and computation [texte imprimé] / Mézard, Marc, Auteur ; Montanari, Andrea, Auteur . - Oxford : Oxford university press, 2009 . - 1 vol. (569 p.) : ill., couv. ill. en coul. ; 26 cm. - (Oxford graduate texts) . ISBN : 978-0-19-857083-7 978-0-19-857083-7 Langues : Anglais (eng) Catégories : Physique Mots-clés : Physique statistique Codage Informatique Index. décimale : 530.13 Mécanique statistique et physique statistique, Résumé : Cet ouvrage présente une approche unifiée d'un domaine de recherche riche et en évolution rapide à l'interface entre la physique statistique, l'informatique théorique / les mathématiques discrètes et la théorie de la codification et de l'information. Il est accessible aux étudiants diplômés et aux chercheurs sans formation spécifique dans aucun de ces domaines. Les sujets sélectionnés incluent des verres de rotation, des codes de correction d'erreurs, la satisfaction et sont au centre de chaque champ. L'approche se concentre sur les grands cas aléatoires et adopte une formulation probabiliste commune en termes de modèles graphiques. Il présente des algorithmes de passage de messages tels que la propagation de croyances et la propagation de sondages, et leur utilisation dans le décodage et la résolution de satisfaction de contraintes. Il explique également les techniques d'analyse comme l'évolution de la densité et la méthode de la cavité, et les utilise pour étudier les transitions de phase. Note de contenu : Sommaire PART 1 BACKGROUND 1 Introduction to information theory 3 1.1 Random variables 3 1.2 Entropy 5 1.3 Sequences of random variables and their entropy rate 8 1.4 Correlated variables and mutual information 10 1.5 Data compression 12 1.6 Data transmission 16 Notes 21 2 Statistical physics and probability theory 23 2.1 The Boltzmann distribution 24 2.2 Thermodynamic potentials 28 2.3 The fluctuation-dissipation relations 32 2.4 The thermodynamic limit 33 2.5 Ferromagnets and Ising models 35 2.6 The Ising spin glass 44 Notes 46 3 Introduction to combinatorial optimization 47 3.1 A first example: The minimum spanning tree 48 3.2 General definitions 51 3.3 More examples 51 3.4 Elements of the theory of computational complexity 54 3.5 Optimization and statistical physics 60 3.6 Optimization and coding 61 Notes 62 4 A probabilistic toolbox 65 4.1 Many random variables: A qualitative preview 65 4.2 Large deviations for independent variables 66 4.3 Correlated variables 72 4.4 The Gibbs free energy 77 4.5 The Monte Carlo method 80 4.6 Simulated annealing 86 4.7 Appendix: A physicist's approach to Sanov's theorem 87 Notes 89 x Contents PART II INDEPENDENCE 5 The random energy model 93 5.1 Definition of the model 93 5.2 Thermodynamics of the REM 94 5.3 The condensation phenomenon 100 5.4 A comment on quenched and annealed averages 101 5.5 The random subcube model 103 Notes 105 6 The random code ensemble 107 6.1 Code ensembles 107 6.2 The geometry of the random code ensemble 110 6.3 Communicating over a binary symmetric channel 112 6.4 Error-free communication with random codes 120 6.5 Geometry again: Sphere packing 123 6.6 Other random codes 126 6.7 A remark on coding theory and disordered systems 127 6.8 Appendix: Proof of Lemma 6.2 128 Notes 128 7 Number partitioning 131 7.1 A fair distribution into two groups? 131 7.2 Algorithmic issues 132 7.3 Partition of a random list: Experiments 133 7.4 The random tost model 136 7.5 Partition of a random list: Rigorous results 140 Notes 143 8 Introduction to replica theory 145 8.1 Replica solution of the random energy model 145 8.2 The fully connected p-spin glass model 155 8.3 Extreme value statistics and the REM 163 8.4 Appendix: Stability of the RS saddle point 166 Notes 169 PART III MODELS ON GRAPHS 9 Factor graphs and graph ensembles 173 9.1 Factor graphs 173 9.2 Ensembles of factor graphs: Definit ions 180 9.3 Random factor graphs: Basic properties 182 9.4 Random factor graphs: The giant component 187 9.5 The locally tree-like structure of random graphs 191 Notes 194 10 Satisfiability 197 10.1 The satisfiability problem 197 Contents xi 10.2 Algorithms 199 10.3 Random K-satisfiability ensembles 206 10.4 Random 2-SAT 209 10.5 The phase transition in random K(> 3)-SAT 209 Notes 217 11 Low-density parity-check codes 219 11.1 Definitions 220 11.2 The geometry of the codebook 222 11.3 LDPC codes for the binary symmetric channel 231 11.4 A simple decoder: Bit flipping 236 Notes 239 12 Spin glasses 241 12.1 Spin glasses and factor graphs 241 12.2 Spin glasses: Constraints and frustration 245 12.3 What is a glass phase? 250 12.4 An example: The phase diagram of the SK model 262 Notes 265 13 Bridges: Inference and the Monte Carlo method 267 13.1 Statistical inference 268 13.2 The Monte Carlo method: Inference via sampling 272 13.3 Free-energy barriers 281 Notes 287 PART IV SHORT-RANGE CORRELATIONS 14 Belief propagation 291 14.1 Two examples 292 14.2 Belief propagation an tree graphs 296 14.3 Optimization: Max-product and min-sum 305 14.4 Loopy BP 310 14.5 General message-passing algorithms 316 14.6 Probabilistic analysis 317 Notes 325 15 Decoding with belief propagation 327 15.1 BP decoding: The algorithm 327 15.2 Analysis: Density evolution 329 15.3 BP decoding for an erasure channel 342 15.4 The Bethe free energy and MAP decoding 347 Notes 352 16 The assignment problem 355 16.1 The assignment problem and random assignment ensembles 356 16.2 Message passing and its probabilistic analysis 357 16.3 A polynomial message-passing algorithm 366 xii Contents 16.4 Combinatorial results 371 16.5 An exercise: Multi-index assignment 376 Notes 378 17 Ising models an random graphs 381 17.1 The BP equations for Ising spins 381 17.2 RS cavity analysis 384 17.3 Ferromagnetic model 386 17.4 Spin glass models 391 Notes 399 PART V LONG-RANGE CORRELATIONS 18 Linear equations with Boolean variables 403 18.1 Definitions and general remarks 404 18.2 Belief propagation 409 18.3 Core percolation and BP 412 18.4 The SAT–UNSAT threshold in random XORSAT 415 18.5 The Hard-SAT phase: Clusters of solutions 421 18.6 An alternative approach: The cavity method 422 Notes 427 19 The 1RSB cavity method 19.1 Beyond BP: Many states 430 19.2 The 1RSB cavity equations 434 19.3 A first application: XORSAT 444 19.4 The special value x = 1 449 19.5 Survey propagation 453 19.6 The nature of 1RSB phases 459 19.7 Appendix: The SP(y) equations for XORSAT 463 Notes 465 20 Random K-satisfiability 20.1 Belief propagation and the replica-symmetric analysis 20.2 Survey propagation and the 1RSB phase 20.3 Some ideas about the full phase diagram 20.4 An exercise: Colouring random graphs Notes 21 Glassy states in coding theory 21.1 Local search algorithms and metastable states 21.2 The binary erasure channel 21.3 General binary memoryless Symmetrie channels 21.4 Metastable states and near-codewords Notes 22 An ongoing story 22.1 Gibbs measures and Jong-range correlation Contents xiii 22.2 Higher levels of replica symmetry breaking 524 22.3 Phase structure and the behaviour of algorithms 535 Notes 538 Appendix A Symbols and notation 541 A.1 Equivalence relations 541 A.2 Orders of growth 542 A.3 Combinatorics and probability 543 A.4 Summary of mathematical notation 544 A.5 Information theory 545 A.6 Factor graphs 545 A.7 Cavity and message-passing methods 545 References 547 Inde Côte titre : Fs/13934-13935

Exemplaires (2)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
Fs/13934	Fs/13934-13935	livre	Bibliothéque des sciences	Anglais	Disponible Disponible
Fs/13935	Fs/13934-13935	livre	Bibliothéque des sciences	Anglais	Disponible Disponible

---

1 (1 - 1 / 1)