自旋玻璃与消息传递

自旋玻璃是统计物理学一个重要的研究领域，其理论研究成果近年来在计算机科学、信息科学和生命科学等研究领域已有一些引人注目的应用。本书以作者提出的配分函数展开方法为数学基础，从配分函数展开这一角度出发推导出自旋玻璃平均场理论，以及获得对于平均场理论的修正表达式；本书也包含作者在配分函数区域图展开方面的理论工作以及区域图消息传播方程；本书还包含自旋玻璃理论在组合优化、约束满足问题上的应用。本书可供物理学专业和计算机科学专业研究人员参考，也可作为相关专业高年级本科生和研究生的自学参考用书。

前言
数学符号
主要公式列表
第1章 自旋玻璃概述 1
1.1 自旋玻璃模型举例 2
1.1.1 有限维品格体系 2
1.1.2 接近连通网络体系 6
1.1.3 随机网络体系 8
1.2 信息系统中的自旋玻璃问题举例 11
1.2.1 约束满足和组合优化 11
1.2.2 低密度奇偶校验码 14
1.2.3 逆伊辛问题 17
1.2.4 矩阵计算与压缩传感 19
1.3 自旋玻璃相变的定性描述 20
1.3.1 样本系综的平均性质 20
1.3.2 单个样本的统计性质 22
1.3.3 自旋玻璃相变 23
1.4 随机能量模型 27
1.5 随机子集模型 28
1.5.1 各态历经破缺以及典型随机子集 30
1.5.2 构型空间的连通性 32
1.6 关于本书 35
第2章 平衡统计物理简介 36
2.1 能量函数和因素网络 36
2.2 配分函数和平衡自由能 38
2.3 自由能泛函 41
2.4 Bethe-Peierls近似的核心思想 42
2.5 Kikuchi团簇变分法 45
2.6 单自旋热浴动力学过程 50
第3章 信念传播方程 52
3.1 配分函数展开 52
3.2 信念传播方程 57
3.3 Bethe-Peierls近似 61
3.4 复本对称平均场理论 65
3.4.1 Bethe-Peierls自由能的其他两种形式 68
3.4.2 平均能量和熵 69
3.4.3 边际概率分布及其相容性 70
3.4.4 自旋关联函数 71
3.5 复本对称种群动力学过程 74
3.6 规整随机网络模型上的应用 75
3.6.1 铁磁系统 75
3.6.2 自旋玻璃系统 79
3.7 Kikuchi自由能 81
3.8 区域网络表示法和自由能区域网络近似 84
3.8.1 区域网络 84
3.8.2 区域网络配分函数 87
3.8.3 区域网络信念传播方程 88
本章小结 89
第4章 概观传播方程 91
4.1 宏观态 91
4.2 广义配分函数广义自由能和复杂度 93
4.3 广义配分函数展开 96
4.4 概观传播方程 100
4.4.1 推导概观传播方程 100
4.4.2 对橛观传播方程的直观理解 103
4.4.3 求解概观传播方程 107
4.4.4 一阶复本对称破缺种群动力学过程 110
4.5 一阶复本对称破缺平均场理论 111
4.5.1 Monasson-Mezard-Parisi自由能 111
4.5.2 平均Bethe-Peierls自由能及复杂度 113
4.5.3 边际概率分布泛函及其相容性 115
4.6 簇集相变与凝聚相变 116
4.6.1 在y=p处化简概观传播方程 118
4.6.2 可=p处的平均自由能和复杂度 120
4.6.3 簇集相变 121
4.6.4 凝聚相变 122
4.7 规整随机网络模型上的应用 123
4.7.1 可=p处的种群动力学过程 123
4.7.2 两体相互作用 125
4.7.3 多体相互作用 127
4.7.4 零温度极限及基态能量密度估计 131
4.8 广义Kikuchi自由能泛函 136
4.9 高阶广义配分函数展开 140
本章小结 140
第5章 最小节点覆盖问题 142
5.1 节点覆盖和最小节点覆盖 142
5.2 掐叶算法 144
5.3 自旋玻璃模型和复本对称平均场理论 150
5.3.1 配分函数和自由能 150
5.3.2 一般温度下的信念传播方程 151
5.3.3 信念传播剥离算法 152
5.4 警报传播方程 153
5.5 最小覆盖构型的数目 157
5.6 最小节点覆盖构型中的阻挫现象 159
5.6.1 定性讨论 159
5.6.2 长程阻挫序参量 161
5.6.3 固定单节点覆孟状态所引起的扰动大小分布 166
5.6.4 最小覆盖构型能量密度 167
5.7 粗粒化概观传播方程 169
5.8 概观传播剥离算法 175
本章小结 176
第6章 K-满足问题 177
6.1 自旋玻璃模型 177
6.1.1 能量函数 178
6.1.2 计算复杂性 179
6.1.3 随机K-满足问题 181
6.2 解空间熵密度 183
6.2.1 信念传播方程 183
6.2.2 单个样本 187
6.2.3 系综平均 189
6.3 信念传播启发的算法 192
6.3.1 信念传播剥离算法 192
6.3.2 信念传播强化算法 193
6.4 解空间结构相变 195
6.4.1 一阶复本对称破缺平均场理论 196
6.4.2 簇集相变和凝聚相变 199
6.5 概观传播方程的y-0极限情况 204
6.5.1 粗粒化状态与复杂度 204
6.5.2 粗粒化概观传播剥离算法 208
6.5.3 有解无解相变 210
6.6 解空间的非均匀性及社区结构的涌现 211
本章小结 217
第7章 最小反馈节点集问题 218
7.1 无向网络的反馈节点集 218
7.2 无向网络自旋玻璃模型 221
7.2.1 节点状态 221
7.2.2 局部约束 222
7.2.3 配分函数和能量 224
7.3 无向网络复本对称平均场理论 225
7.4 无向网络信念传播剥离算法 231
7.5 有向网络反馈芾点集 232
7.5.1 问题描述 233
7.5.2 自旋玻璃模型 234
本章小结 238
参考文献 239
附录A Erdos-Renyi随机网络的一些结构相变 254
A.1 简单渗流相变 254
A.2 K-核渗流相变 257
附录B 些数值计算技巧 259
B.1 随机递增序列采样 259
B.2 Bootstrap数据分析方法简介 262
B.3 按照概率分布方程(4.93)或方程(4.97)进行取样 262
索引 265
《现代物理基础丛书》已出版书目 268