资源｜谷歌与MIT联袂巨著：《计算机科学的数学》开放下载
lizzysnow 2017-03-07
选自CSAIL.Mit
机器之心编译
参与：蒋思源、吴攀
谷歌和麻省理工学院联袂出品的《计算机科学的数学》昨日已经开放下载了，读者可点击「https://courses.csail.mit.edu/6.042/spring17/mcs.pdf」下载。
该书用了千页的篇幅讲述了五大板块的内容。其中第一篇就由证明到数据型讲述了数学分析的基本内容，该篇幅为计算机科学的开发者们提供了宝贵的推理和逻辑演绎能力。随后在第二篇「结构」中，该书以数论开始讲述，首先就重点介绍了数论的主题整数集的性能，并由此衍生到计算机科学最基础的结构图论（Graphs）或者说是网络（networks）。在随后的两章节中，该书又向我们介绍了计算理论和概率论，这一部分在我们构建机器学习模型时十分重要和有效。
在该书中，作者在第四章着重介绍了对机器学习算法有重要作用的概率论，其中从概率论那一部分的目录和简介可以看出来作者主要讲述了基本的概率定义和数字特征与假设检验基础，随后由这些基本概率论的定义引出了统计学模型，包括中心极限定理，切比雪夫不等式和马尔可夫理论等重要内容。而这些统计学概念和模型却又正好是机器学习的方法基础。下面让我们一起来看看该书的章节目录：
I 数学分析（Proofs）
简介（Introduction）
0.1 参考文献（References）
1 什么是证明？（What is a Proof?）
1.1 命题（Propositions）
1.2 谓词（Predicates）
1.3 公理化方法（The Axiomatic Method）
1.4 我们的公理（Our Axioms）
1.5 证明命题的含义（Proving an Implication）
1.6 证明「有且仅有」（Proving an「If and Only If」）
1.7 案例证明（Proof by Cases）
1.8 反证法（Proof by Contradiction）
1.9 证明的实战演练（Good Proofs in Practice）
1.10 参考文献（References）
2 良序原则（The Well Ordering Principle）
2.1 良序证明（Well Ordering Proofs）
2.2 良序证明模式（Template for Well Ordering Proofs）
2.3 素数因子分解（Factoring into Primes）
2.4 良序集合（Well Ordered Sets）
3 逻辑公式（Logical Formulas）
3.1 命题中的命题（Propositions from Propositions）
3.2 计算机程序中的命题逻辑（Propositional Logic in Computer Programs）
3.3 等价性和有效性（Equivalence and Validity）
3.4 命题的代数（The Algebra of Propositions）
3.5 SAT 问题（The SAT Problem）
3.6 谓词公式（Predicate Formulas）
3.7 参考文献（References）
4 数学上的数据类型（Mathematical Data Types）
4.1 集合（Sets）
4.2 序列（Sequences）
4.3 函数（Functions）
4.4 二元关系（Binary Relations）
4.5 有限基数（Finite Cardinality）
5 简介（Induction）
5.1 一般归纳法（Ordinary Induction）
5.2 强归纳法（Strong Induction）
5.3 强归纳法、一般归纳法和良序法（Strong Induction vs. Induction vs. Well Ordering）
6 状态机（State Machines）
6.1 状态和转换（States and Transitions）
6.2 不变量原则（The Invariant Principle）
6.3 部分正确性和终止（Partial Correctness & Termination）
6.4 稳定婚姻问题（The Stable Marriage Problem）
7 递归数据型（Recursive Data Types）
7.1 递归定义和结构归纳法（Recursive Definitions and Structural Induction）
7.2 Matched Brackets 字符串（Strings of Matched Brackets）
7.3 非负整数递归函数（Recursive Functions on Nonnegative Integers）
7.4 算术表达式（Arithmetic Expressions）
7.5 递归数据型在计算机科学中的简介（Induction in Computer Science）
8 无限集（Infinite Sets）
8.1 无限基数集（Infinite Cardinality）
8.2 停止问题（The Halting Problem）
8.3 集合的逻辑（The Logic of Sets）
8.4 这些真的有效吗？（Does All This Really Work?）
II 结构（Structures）
Introduction
9 数论（Number Theory）
9.1 可分性（Divisibility）
9.2 最大公约数（The Greatest Common Divisor）
9.3 神秘的素数（Prime Mysteries）
9.4 算术的基本定理（The Fundamental Theorem of Arithmetic）
9.5 Alan Turing
9.6 模运算（Modular Arithmetic）
9.7 余数运算（Remainder Arithmetic）
9.8 Turing's Code (Version 2.0)
9.9 乘法逆运算和消除（Multiplicative Inverses and Cancelling）
9.10 欧拉定理（Euler's Theorem）
9.11 RSA 公钥加密（RSA Public Key Encryption）
9.12 SAT 与它有什么关系？（What has SAT got to do with it?）
9.13 参考文献（References）
10 有向图和部分排序（Directed graphs & Partial Orders）
10.1 顶点度（Vertex Degrees）
10.2 步长与路径（Walks and Paths）
10.3 临近矩阵（Adjacency Matrices）
10.4 Walk Relations
10.5 有向非循环图标和时序（Directed Acyclic Graphs & Scheduling）
10.6 局部排序（Partial Orders）
10.7 通过集合遏制表征局部排序（Representing Partial Orders by Set Containment）
10.8 线性排序（Linear Orders）
10.9 乘积排序（Product Orders）
10.10 等价关系（Equivalence Relations）
10.11 关系属性总结（Summary of Relational Properties）
11 通信网络（Communication Networks）
11.1 路由（Routing）
11.2 Routing Measures）
11.3 网络设计（Network Designs）
12 简单图（Simple Graphs）
12.1 Vertex Adjacency and Degrees）
12.2 美国性别人口统计（Sexual Demographics in America）
12.3 一些常见的图（Some Common Graphs）
12.4 同构（Isomorphism）
12.5 二部图&匹配（Bipartite Graphs & Matchings）
12.6 Coloring
12.7 Simple Walks
12.8 连接（Connectivity）
12.9 森林和树（Forests & Trees）
12.10 References
13 平面图（Planar Graphs）
13.1 在平面中绘制图（Drawing Graphs in the Plane）
13.2 平面图的定义（Definitions of Planar Graphs）
13.3 欧拉公式（Euler's Formula）
13.4 在平面图中限定边的数量（Bounding the Number of Edges in a Planar Graph）
13.5 Returning to K5 and K3;3
13.6 Coloring Planar Graphs
13.7 Classifying Polyhedra
13.8 平面图的另一种特征化（Another Characterization for Planar Graphs）
III 计数（Counting）
Introduction
14 逼近求和（Sums and Asymptotics）
14.1 养老金的价值（The Value of an Annuity）
14.2 幂级数求和 Sums of Powers）
14.3 逼近求和（Approximating Sums）
14.4 Hanging Out Over the Edge）
14.5 乘积（Products）
14.6 Double Trouble
14.7 渐进的符号表示（Asymptotic Notation）
15 基数法则（Cardinality Rules）
15.1 由计算另一项计算该项（Counting One Thing by Counting Another）
15.2 计算序列（Counting Sequences）
15.3 广义乘积法则（The Generalized Product Rule）
15.4 除法法则（The Division Rule）
15.5 子集计算（Counting Subsets）
15.6 重复序列（Sequences with Repetitions）
15.7 Counting Practice: Poker Hands
15.8 鸽巢原理（The Pigeonhole Principle）
15.9 包含与排斥（Inclusion-Exclusion）
15.10 组合证明（Combinatorial Proofs）
15.11 References
16 母函数（Generating Functions）
16.1 无穷级数（Infinite Series）
16.2 使用母函数进行计数（Counting with Generating Functions）
16.3 部分分式（Partial Fractions）
16.4 求解线性递归（Solving Linear Recurrences）
16.5 形式幂级数（Formal Power Series）
16.6 References
IV 概率论（Probability）
Introduction
17 事件和概率空间（Events and Probability Spaces）
17.1 Let's Make a Deal
17.2 四步法（The Four Step Method）
17.3 Strange Dice
17.4 生日原则（The Birthday Principle）
17.5 集合论和概率论（Set Theory and Probability）
17.6 References
18 条件概率（Conditional Probability）
18.1 Monty Hall Confusion
18.2 定义和符号（Definition and Notation）
18.3 条件概率的四步法（The Four-Step Method for Conditional Probability）
18.4 为什么树状图如此有效（Why Tree Diagrams Work）
18.5 全概法则（The Law of Total Probability）
18.6 辛普森悖论（Simpson's Paradox）
18.7 独立性（Independence）
18.8 相互独立性（Mutual Independence）
18.9 概率与置信度（Probability versus Confidence）
19 随机变量（Random Variables）
19.1 随机样本（Random Variable Examples）
19.2 独立性（Independence）
19.3 分布函数（Distribution Functions）
19.4 期望（Great Expectations）
19.5 线性期望（Linearity of Expectation）
20 平均偏差（Deviation from the Mean）
20.1 马尔可夫定理（Markov‘s Theorem）
20.2 切比雪夫定理（Chebyshev's Theorem）
20.3 方差的性质（Properties of Variance）
20.4 随机样本估计（Estimation by Random Sampling）
20.5 估计置信度（Confidence in an Estimation）
20.6 随机变量加和（Sums of Random Variables）
20.7 Really Great Expectations
21 随机步（Random Walks）
21.1 Gambler’s Ruin
21.2 图表中的随机步（Random Walks on Graphs）
V Recurrences
Introduction
22 Recurrences
22.1 The Towers of Hanoi
22.2 Merge Sort
22.3 Linear Recurrences
22.4 Divide-and-Conquer Recurrences
22.5 A Feel for Recurrences
参考书目（Bibliography）
符号词汇表（Glossary of Symbols）
索引（Index）
