数学女孩 4 随机算法

作品简介

確率とコンピュータの深くて不思議な関係とは？ 「僕」と四人の少女が、乱択アルゴリズムの世界に挑む魅惑の数学物語。 累計10万部を突破し、数学書としては異例のベストセラーとなった「数学ガール」シリーズの第四弾です。 今回のテーマは、乱択アルゴリズムです。私たちは、乱数や確率を用いることで、未来への確定的な予測を行ったり、複雑な解析をシンプルにすることができます。本書では、こうしたランダムの力が生み出す世界を、純粋数学的な側面とプログラム的な側面の両方から解説し、乱択アルゴリズムの理解を目指します。コンピュータの得意な新入生リサが登場し、彼らの淡い恋に新たな進展も見られます。シリーズの読者はもちろん、数学に関心のある読者に最良の一冊です。 第1章「絶対に負けないギャンブル」 第2章「愚直な一歩の積み重ね」 第3章「171億7986万9184の孤独」 第4章「確からしさの不確かさ」 第5章「期待値」 第6章「とらえがたい未来」 第7章「行列」 第8章「ひとりぼっちのランダムウォーク」 第9章「強く、正しく、美しく」 第10章「乱択アルゴリズム」 ------------------------------------- 目录 序言 第1章 绝不会输的赌博 1 1.1 掷骰子 1 1.2 抛硬币 4 1.2.1 两枚硬币 4 1.2.2 一枚硬币 7 1.2.3 彩票的记忆 8 1.3 蒙提霍尔问题 11 1.3.1 3 个信封 11 1.3.2 上帝视角 18 第2章 积跬步，致千里 21 2.1 高中 21 2.1.1 泰朵拉 21 2.1.2 理纱 22 2.1.3 顺序查找 24 2.1.4 逐行调试 28 2.1.5 顺序查找算法分析 34 2.1.6 顺序查找算法分析（能找到v 的情况） 35 2.1.7 顺序查找算法分析（无法找到v 的情况） 38 2.2 算法分析 40 2.2.1 米尔嘉 40 2.2.2 算法分析 41 2.2.3 不同情况的归纳 42 2.2.4 思考意义 45 2.2.5 带有哨兵的顺序查找算法 48 2.2.6 创造历史 52 2.3 自己家 54 第3章 171亿7986万9184份孤独 61 3.1 排列 61 3.1.1 书店 61 3.1.2 豁然开朗 62 3.1.3 具体示例 63 3.1.4 找规律 65 3.1.5 一般化 70 3.1.6 铺就道路 72 3.1.7 那家伙 74 3.2 组合 76 3.2.1 图书室 76 3.2.2 排列 77 3.2.3 组合 79 3.2.4 鲡鱼与绿鲤鱼 82 3.2.5 二项式定理 83 3.3 2n 的分配 88 3.3.1 帕斯卡三角形 88 3.3.2 位模式 92 3.3.3 指数爆炸 94 3.4 幂运算的孤独 96 3.4.1 回家路上 96 3.4.2 家 96 第4章 可能性中的不确定性 99 4.1 可能性中的确定性 99 4.2 可能性中的不确定性 106 4.2.1 相同的可能性 106 4.2.2 真正的武器 107 4.3 可能性的实验 109 4.3.1 解释程序 109 4.3.2 掷骰子比赛 112 4.3.3 轮盘比赛 113 4.4 可能性的倒塌 115 4.4.1 概率的定义 115 4.4.2 概率的意义 118 4.4.3 数学的应用 118 4.4.4 解答疑问 120 4.5 可能性的公理定义 121 4.5.1 柯尔莫哥洛夫 121 4.5.2 样本空间与概率分布函数 121 4.5.3 概率公理 125 4.5.4 子集与事件 126 4.5.5 概率公理P1 129 4.5.6 概率公理P2 130 4.5.7 概率公理P3 131 4.5.8 还没有明白 132 4.5.9 掷出的点数为偶数的概率 134 4.5.10 质地不均匀的骰子和竖立的硬币 137 4.5.11 约定 138 4.5.12 咳嗽 139 第5章 期望 143 5.1 随机变量 143 5.1.1 妈妈 143 5.1.2 泰朵拉 144 5.1.3 随机变量的示例 146 5.1.4 概率分布函数的示例 150 5.1.5 许多词 152 5.1.6 期望 153 5.1.7 公平的游戏 157 5.2 线性法则 159 5.2.1 米尔嘉 159 5.2.2 和的期望等于期望的和 160 5.3 二项分布 165 5.3.1 硬币的话题 165 5.3.2 二项分布的期望 168 5.3.3 划分为和的形式 171 5.3.4 指示器随机变量 172 5.3.5 快乐的作业 174 5.4 直到所有事情发生 175 5.4.1 不知何时 175 5.4.2 能尽全力吗 176 5.4.3 运用学到的知识 180 5.4.4 尽全力 183 5.4.5 意料之外的事情 192 第6章 难以捉摸的未来 197 6.1 约定的记忆 197 6.2 阶 199 6.2.1 更快的算法 199 6.2.2 至多为n阶 201 6.2.3 出题 204 6.2.4 至多为f(n) 阶 206 6.2.5 log n 211 6.3 查找 215 6.3.1 二分查找 215 6.3.2 实例 217 6.3.3 分析 220 6.3.4 前往排序 227 6.4 排序 228 6.4.1 冒泡排序 228 6.4.2 实例 229 6.4.3 分析 231 6.4.4 大O表示法的层级 235 6.5 动态视角、静态视角 237 6.5.1 需要比较多少次呢 237 6.5.2 比较树 239 6.5.3 log n! 的评估 241 6.6 传递和学习 245 6.6.1 传递 245 6.6.2 学习 246 第7章 矩阵 249 7.1 图书室 249 7.1.1 瑞谷老师 249 7.1.2 TETRALIANE 250 7.2 尤里 252 7.2.1 无解 252 7.2.2 无穷多解 254 7.2.3 唯一解 256 7.2.4 信 268 7.3 泰朵拉 269 7.3.1 图书室 269 7.3.2 行与列 269 7.3.3 矩阵与向量的积 271 7.3.4 联立方程式与矩阵 273 7.3.5 矩阵的积 274 7.3.6 逆矩阵 275 7.4 米尔嘉 280 7.4.1 看穿隐藏的谜题 280 7.4.2 线性变换 286 7.4.3 旋转 293 7.5 回家路上 296 第8章 孤零零的随机漫步 301 8.1 家 301 8.1.1 雨天的周六 301 8.1.2 下午茶时间 302 8.1.3 钢琴问题 302 8.1.4 旋律示例 305 8.1.5 解题方法一：毅力比拼 308 8.1.6 解题方法二：一招定胜负 310 8.1.7 一般化 314 8.1.8 摇摆不定的心 319 8.2 清晨的上学路 320 8.3 中午的教室 322 8.3.1 矩阵的练习 322 8.3.2 摇摆不定的心 325 8.4 放学后的图书室 327 8.4.1 流浪问题 327 8.4.2 A2 的意义 331 8.4.3 向着矩阵的n次方前进 332 8.4.4 上半场准备：对角矩阵 333 8.4.5 下半场准备：矩阵与逆矩阵的三明治 335 8.4.6 向着特征值前进 336 8.4.7 向着特征向量前进 342 8.4.8 求An 344 8.5 家 347 8.5.1 摇摆不定的心 347 8.5.2 雨夜 349 第9章 坚强、正直、美丽 351 9.1 家 351 9.2 图书室 358 9.2.1 逻辑题 358 9.2.2 可满足性问题 358 9.2.3 3-SAT 360 9.2.4 满足 363 9.2.5 分配方式的练习 364 9.2.6 NP完全问题 365 9.3 回家路上 367 9.3.1 誓言与约定 367 9.3.2 会议 368 9.4 图书室 369 9.4.1 求解3-SAT问题的随机算法 369 9.4.2 随机漫步 371 9.4.3 向着定量评估前进 376 9.4.4 另一个随机漫步 378 9.4.5 关注循环 379 9.5 家 384 9.5.1 幸运的评估 384 9.5.2 化简和式 388 9.5.3 次数的评估 390 9.6 图书室 391 9.6.1 独立与互斥 391 9.6.2 精确的评估 392 9.6.3 斯特林公式 396 9.7 回家路上 403 9.8 家 405 第10章 随机算法 407 10.1 休闲餐厅 407 10.2 学校 409 10.2.1 中午 409 10.2.2 快速排序算法 410 10.2.3 通过枢纽项划分数列—两只翅膀 413 10.2.4 对子数列排序—递归 417 10.2.5 运行步数的分析 418 10.2.6 分情况讨论 421 10.2.7 *大运行步数 425 10.2.8 平均运行步数 429 10.2.9 回家路上 434 10.3 自己家 435 10.3.1 变形 435 10.3.2 Hn 与log n 441 10.4 图书室 443 10.4.1 米尔嘉 443 10.4.2 随机快速排序 444 10.4.3 观察比较过程 447 10.4.4 期望的线性法则 452 10.4.5 指示器随机变量的期望等于概率 453 10.5 休闲餐厅 456 10.5.1 各种各样的随机算法 456 10.5.2 准备 457 10.6 双仓图书馆 458 10.6.1 Iodine 458 10.6.2 紧张 459 10.6.3 报告 461 10.6.4 传达 462 10.6.5 Oxygen 464 10.6.6 连接 465 10.6.7 庭园 466 10.6.8 约定的印记 468 尾 声 471 后 记 477 参考文献和导读 481

正版观看入口

暂未获取到该作品的精确平台信息，以下为常用正版平台搜索入口，可直接前往搜索。

作品信息

作者

結城浩

出版社 / 连载

ソフトバンククリエイティブ

册数 / 话数

10

发行日期

2011-02-26

ISBN

9784797361001

作品 ID

#103459

常见问题