[套装书]概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）+线性代数高级教程：矩阵理论及应用（2册）

作者

[美] 迈克尔·米森马彻（Michael Mitzenmacher） 伊莱·阿法尔（Eli Upfal）[美]斯蒂芬·拉蒙·加西亚（Stephan Ramon Garcia）罗杰·A. 霍恩（Roger A. Horn）

丛书名

华章数学译丛

出版社

机械工业出版社

ISBN

9782002281132

简要

简介

内容简介书籍数学书籍 ---------------------------概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）--------------------------- 本书详细地介绍了概率技术以及在概率算法与分析发展中使用过的范例。本书分两部分，第一部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容。第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链蒙特卡罗方法、耦合、鞅和平衡配置等比较高深的课题。 本书适合作为高等院校计算机科学和应用数学专业高年级本科生与低年级研究生的教材，也适合作为数学工作者和科技人员的参考书。 ---------------------------线性代数高级教程：矩阵理论及应用--------------------------- 本书涵盖了线性代数尤其是矩阵理论中所有基本且重要的内容，包括：向量空间，内积空间与赋范向量空间，分块矩阵，矩阵的特征值与特征向量、特征多项式与极小多项式，酉三角化与分块对角化，矩阵的相似与标准型，矩阵的三角化、对角化以及多个矩阵的同时对角化，交换的矩阵族，矩阵的各种分解，特征值交错现象与惯性定理，各种特殊而重要的矩阵（酉矩阵、Hermite阵与斜Hermite阵、对称阵与斜对称阵、半正定矩阵与正定矩阵、正规矩阵以及各种特殊的正规矩阵等）等. 此外，书中还配有一定数量、难度适宜的习题，启发读者进一步思考.

目录

---------------------------概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）--------------------------- 译者序 第2版前言 第1版前言 第1章　事件与概率1 1.1　应用：验证多项式恒等式1 1.2　概率论公理2 1.3　应用：验证矩阵乘法6 1.4　应用：朴素贝叶斯分类器9 1.5　应用：最小割随机化算法11 1.6　练习13 第2章　离散型随机变量与期望17 2.1　随机变量与期望17 2.1.1　期望的线性性18 2.1.2　詹森不等式19 2.2　伯努利随机变量和二项随机变量20 2.3　条件期望21 2.4　几何分布24 2.5　应用：快速排序的期望运行时间27 2.6　练习29 第3章　矩与离差33 3.1　马尔可夫不等式33 3.2　随机变量的方差和矩33 3.3　切比雪夫不等式36 3.4　中位数和平均值38 3.5　应用：计算中位数的随机化算法40 3.5.1　算法40 3.5.2　算法分析41 3.6　练习44 第4章　切尔诺夫界与霍夫丁界46 4.1　矩母函数46 4.2　切尔诺夫界的导出和应用47 4.2.1　泊松试验和的切尔诺夫界47 4.2.2　例：投掷硬币50 4.2.3　应用：估计参数50 4.3　某些特殊情况下更好的界51 4.4　应用：集合的均衡53 4.5　霍夫丁界54 *　4.6　应用：稀疏网络中的数据包路由选择56 4.6.1　超立方体网络上排列的路由选择56 4.6.2　蝶形网络上排列的路由选择61 4.7　练习65 第5章　球、箱子和随机图69 5.1　例：生日悖论69 5.2　球放进箱子70 5.2.1　球和箱子模型70 5.2.2　应用：桶排序71 5.3　泊松分布72 5.4　泊松近似75 5.5　应用：散列法81 5.5.1　链散列81 5.5.2　散列：二进制数字串82 5.5.3　Bloom过滤器83 5.5.4　放弃对称性85 5.6　随机图85 5.6.1　随机图模型85 5.6.2　应用：随机图中的哈密顿圈87 5.7　练习92 5.8　探索性作业95 第6章　概率方法97 6.1　基本计数论证97 6.2　期望论证99 6.2.1　应用：求最大割99 6.2.2　应用：最大可满足性100 6.3　利用条件期望消除随机化101 6.4　抽样和修改102 6.4.1　应用：独立集合102 6.4.2　应用：有较大围长的图103 6.5　二阶矩方法103 6.6　条件期望不等式105 6.7　洛瓦兹局部引理107 6.7.1　应用：边不相交的路径109 6.7.2　应用：可满足性109 *　6.8　利用洛瓦兹局部引理的显式构造110 6.9　洛瓦兹局部引理：一般情况113 *　6.10　洛瓦兹算法局部引理114 6.11　练习118 第7章　马尔可夫链及随机游动122 7.1　马尔可夫链：定义及表示122 7.1.1　应用：2可满足性的随机化算法124 7.1.2　应用：3可满足性的随机化算法127 7.2　状态分类130 7.3　平稳分布133 7.4　无向图上的随机游动138 7.5　Parrondo悖论141 7.6　练习144 第8章　连续分布与泊松过程149 8.1　连续随机变量149 8.1.1　R中的概率分布149 8.1.2　联合分布与条件概率150 8.2　均匀分布152 8.3　指数分布155 8.3.1　指数分布的其他性质155 *　8.3.2　例：有反馈的球和箱子157 8.4　泊松过程159 8.4.1　到达间隔分布161 8.4.2　组合与分解泊松过程162 8.4.3　条件到达时间分布163 8.5　连续时间马尔可夫过程165 8.6　例：马尔可夫排队论167 8.6.1　均衡的M/M/1排队167 8.6.2　均衡的M/M/1/K排队169 8.6.3　M/M/∞排队中的顾客数170 8.7　练习171 第9章　正态分布176 9.1　正态分布176 9.1.1　标准正态分布176 9.1.2　一般单变量正态分布177 9.1.3　矩母函数179 *　9.2　二项分布的极限180 9.3　中心极限定理182 *　9.4　多维正态分布184 9.5　应用：生成正态分布的随机值187 9.6　最大似然点估计189 9.7　应用：针对混合高斯分布的EM算法192 9.8　练习195 第10章　熵、随机性和信息198 10.1　熵函数198 10.2　熵和二项式系数200 10.3　熵：随机性的测度201 10.4　压缩205 *　10.5　编码：香农定理207 10.6　练习213 第11章　蒙特卡罗方法218 11.1　蒙特卡罗方法218 11.2　应用：DNF计数问题219 11.2.1　朴素算法220 11.2.2　DNF计数问题的完全多项式随机方案221 11.3　从近似抽样到近似计数223 11.4　马尔可夫链蒙特卡罗方法226 11.5　练习229 11.6　最小支撑树的探索作业231 *第12章　马尔可夫链的耦合232 12.1　变异距离和混合时间232 12.2　耦合234 12.2.1　例：洗牌235 12.2.2　例:超立方体上的随机游动235 12.2.3　例：固定大小的独立集合236 12.3　应用：变异距离是不增的237 12.4　几何收敛239 12.5　应用：正常着色法的近似抽样240 12.6　路径耦合243 12.7　练习246 第13章　鞅250 13.1　鞅250 13.2　停时251 13.3　瓦尔德等式254 13.4　鞅的尾部不等式256 13.5　Azuma-Hoeffding不等式的应用257 13.5.1　一般形式257 13.5.2　应用：模式匹配259 13.5.3　应用：球和箱子260 13.5.4　应用：色数260 13.6　练习260 第14章　样本复杂度、VC维度以及拉德马赫复杂度264 14.1　“学习”问题265 14.2　VC维度266 14.2.1　VC维度的其他例子267 14.2.2　增长函数268 14.2.3　VC维度的合成界269 14.2.4　ε-网和ε-样本270 14.3　ε-网定理271 14.4　应用：PAC学习274 14.5　ε-样本定理276 14.5.1　应用：不可知学习279 14.5.2　应用：数据挖掘279 14.6　拉德马赫复杂度281 14.6.1　拉德马赫复杂度和样本错误283 14.6.2　估计拉德马赫复杂度284 14.6.3　应用：二值分类的不可知学习285 14.7　练习286 第15章　两两独立及通用散列函数288 15.1　两两独立288 15.1.1　例：两两独立的二进制数字的构造288 15.1.2　应用：消去最大割算法的随机性289 15.1.3　例：构造关于一个素数模的两两独立的值290 15.2　两两独立变量的切比雪夫不等式291 15.3　通用散列函数族293 15.3.1　例：一个2维通用散列函数族295 15.3.2　例：强2维通用散列函数族295 15.3.3　应用：完美散列297 15.4　应用：在数据流中寻找重量级的源终点299 15.5　练习302 第16章　幂律及相关的分布305 16.1　幂律分布：基本定义和性质305 16.2　语言中的幂律307 16.2.1　Zipf定律和其他例子307 16.2.2　语言优化307 16.2.3　猴子随意打字308 16.3　偏好链接309 16.4　幂律在算法分析中的应用312 16.5　其他相关的分布314 16.5.1　对数正态分布314 16.5.2　具有指数截断的幂律315 16.6　练习315 第17章　平衡分配和布谷鸟散列318 17.1　两种选择的影响力318 17.2　两种选择：下界322 17.3　两种选择影响力的应用324 17.3.1　散列法324 17.3.2　动态资源分配325 17.4　布谷鸟散列325 17.5　布谷鸟散列的扩展332 17.5.1　带删除的布谷鸟散列332 17.5.2　处理故障333 17.5.3　更多的选择和更大的箱子334 17.6　练习335 延伸阅读339 ---------------------------线性代数高级教程：矩阵理论及应用--------------------------- 译者序 前言 记号 第0章预备知识 01函数与集合 02纯量 03矩阵 04线性方程组 05行列式 06数学归纳法 07多项式 08多项式与矩阵 09问题 010一些重要的概念 第1章向量空间 11什么是向量空间 12向量空间的例子 13子空间 14线性组合与生成空间 15子空间的交、和以及直和 16线性相关与线性无关 17问题 18注记 19一些重要的概念 第2章基与相似性 21什么是基 22维数 23基表示与线性变换 24 基变换与相似性 25维数定理 26问题 27一些重要的概念 第3章分块矩阵 31行与列的分划 32秩 33分块分划与直和 34分块矩阵的行列式 35换位子与Shoda定理 36Kronecker乘积 37问题 38注记 39一些重要的概念 第4章内积空间 41毕达哥拉斯定理 42余弦法则 43平面中的角与长度 44内积 45内积导出的范数 46赋范向量空间 47问题 48注记 49一些重要的概念 第5章标准正交向量 51标准正交组 52标准正交基 53GramSchmidt方法 54Riesz表示定理 55基表示 56线性变换与矩阵的伴随 57Parseval等式与Bessel不等式 58Fourier级数 59问题 510注记 511一些重要的概念 第6章酉矩阵 61内积空间中的等距 62酉矩阵 63置换矩阵 64Householder矩阵与秩1射影 65QR分解 66上Hessenberg矩阵 67问题 68注记 69一些重要的概念 第7章正交补与正交射影 71正交补 72相容线性方程组的极小范数解 73正交射影 74最佳逼近 75不相容线性方程组的最小平方解 76不变子空间 77问题 78注记 79一些重要的概念 第8章特征值、特征向量与几何重数 81特征值特征向量对 82每个方阵有一个特征值 83有多少个特征值 84特征值在何处 85特征向量与交换矩阵 86实矩阵的实相似 87问题 88注记 89一些重要的概念 第9章特征多项式与代数重数 91特征多项式 92代数重数 93相似与特征值重数 94对角化与特征值重数 95可对角化矩阵的函数计算 96换位集 97AB与BA的特征值 98问题 99注记 910一些重要的概念 第10章酉三角化与分块对角化 101Schur三角化定理 102CayleyHamilton定理 103极小多项式 104线性矩阵方程与分块对角化 105交换矩阵与三角化 106特征值调节与Google矩阵 107问题 108注记 109一些重要的概念 第11章Jordan标准型 111Jordan块与Jordan矩阵 112Jordan型的存在性 113Jordan型的唯一性 114Jordan标准型 115微分方程与Jordan标准型 116收敛的矩阵 117幂有界矩阵与Markov矩阵 118矩阵与其转置阵的相似性 119AB与BA的可逆Jordan块 1110矩阵与其复共轭矩阵的相似性 1111问题 1112注记 1113一些重要的概念 第12章正规矩阵与谱定理 121正规矩阵 122谱定理 123偏离正规性的亏量 124FugledePutnam定理 125循环矩阵 126一些特殊的正规矩阵类 127正规矩阵与其他可对角化矩阵的相似性 128正规性的某些特征 129谱分解 1210问题 1211注记 1212一些重要的概念 第13章半正定矩阵 131半正定矩阵 132半正定矩阵的平方根 133Cholesky分解 134二次型的同时对角化 135Schur乘积定理 136问题 137注记 138一些重要的概念 第14章奇异值分解与极分解 141奇异值分解 142紧致奇异值分解 143极分解 144问题 145注记 146一些重要的概念 第15章奇异值与谱范数 151奇异值与逼近 152谱范数 153奇异值与特征值 154谱范数的上界 155伪逆阵 156谱条件数 157复对称阵 158幂等阵 159问题 1510注记 1511一些重要的概念 第16章交错与惯性 161Rayleigh商 162Hermite阵之和的特征值交错 163加边Hermite阵的特征值交错 164Sylvester判别法 165Hermite阵的对角元素与特征值 166Hermite阵的相合与惯性 167Weyl不等式 168正规矩阵的相合与惯性 169问题 1610注记 1611一些重要的概念 附录A复数 参考文献 索引

有问题微信扫码联系

• ※[套装书]组织行为学(第4版)+运营管理（第5版）+MATLAB与数学实验(第2版)（3册）
• ※动态股权：中国合伙人分钱分权的新技术
• ※超级店长业绩倍增实战宝典
• ※[套装书]图论导引（原书第2版）典藏版+拓扑学（原书第2版）（2册）
• ※[套装书]概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）+图论导引（原书第2版）典藏版（2册）
• ※[套装书]概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）+线性代数高级教程：矩阵理论及应用（2册）
• ※[套装书]斯坦福算法博弈论二十讲+概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）（2册）
• ※[套装书]斯坦福算法博弈论二十讲+雾计算与边缘计算：原理及范式（2册）
• ※[套装书]企业迷思：北大管理公开课+未来管理的挑战（2册）
• ※[套装书]企业迷思：北大管理公开课+管理者而非MBA（2册）
• ※[套装书]聚裂：云+AI+5G的新商业逻辑+商业之巅：新商业时代的12个锦囊妙计（2册）

桂ICP备20004708号-4