1700507291
数据科学家养成手册 [:1700503577]
1700507292
数据科学家养成手册 第11章 算法学
1700507293
1700507294
算法学几乎是计算机领域的必学课程。像前端工程师（以HTML、CSS、JavaScript为工作对象语言）和DBA（数据库管理员，以SQL和shell命令作为工作对象语言）这样不用编写完整程序代码的人员，以及不用编写底层代码的IT工作者，也要了解算法的基本原理，以获得解决日常工作中出现的一些简单问题的思路。
1700507295
1700507296
算法学应该说是从计算机组成原理中慢慢进化出来的一种研究如何“控制”计算机的学科。在用电子管和二极管制造出第一台电子计算机以后，虽然经过几代的技术演进，到现在也只不过是集成度更高了而已，在底层的数理计算逻辑上没有本质变化，仍然在用“与”（AND）、“或”（OR）、“非”（NOT）来对加法进行模拟（如表11-1所示）。
1700507297
1700507298
表11-1 二变量与或结果表
1700507299
1700507300
1700507301
1700507302
1700507303
通过逻辑门单元的“与”、“或”、“非”可以实现加法和减法（实质上还是加法），其他任何计算在底层都是用加法和减法来实现的——是的，任何计算。
1700507304
1700507305
让计算机按照人类想定的方式去运行并得到结果，就是我们刚才所说的“控制”。计算机非常愚笨，完全没有主动思考的能力，每个操作都要由人来告诉它控制的逻辑，而它自己也只有遵守的份儿。那么，如何控制更为合理有效就是一个分支学科所要研究的范畴了。算法研究的事情就是：让计算机按照何种程序逻辑才能尽可能高效且正确地运算出结果。
1700507306
1700507307
1700507308
1700507309
1700507310
数据科学家养成手册 [:1700503578]
1700507311
数据科学家养成手册 11.1 离散的世界
1700507312
1700507313
电子计算机使用的寄存器、内存单元、磁介质存储单元、半导体介质存储单元都有一个共同的特性，那就是每个基本单元只有“导通”（1）和“截止”（0）两个状态，这是由最初的电子计算机的物理实现基础所导致的。所以，一切计算机中的数理逻辑也只能用1和0来表示。如果用1位（bit）来表示数据含义，最多只能表示2个不同的数据含义；2位就是4个；32位就是4294967296个，这也是32位电子计算机在不开启PAE(1)模式的情况下所支持的最大寻址空间——4G；64位就是18446744073709551616——16E(2)（1844.7亿亿），在现阶段的民用领域是非常巨大的数字了。
1700507314
1700507315
虽然18446744073709551616这个数字非常巨大，但在表示实数这样稠密的数据集合时仍然捉襟见肘。根据实数稠密性原理，任意两个不相等的实数之间都有无穷多个实数，也就是说，不论未来电子计算机的寻址能力是128位、256位还是32768位，对于描述整个实数域来说仍远远不够。所以，小数（浮点数）的表示只能用类似科学计数法的方式用“有效数字”乘以“10的n次方”表示。
1700507316
1700507317
在电子计算器上，通常用科学计数法表示巨大的计算结果（如图11-1所示）。根据微软的相关技术白皮书，双精度Double变量以带符号的IEEE 64位（8字节）双精度浮点数形式存储，负值的取值范围为-1.79769313486231570E+308到-4.94065645841246544E-324，正值的取值范围为4.94065645841246544E-324到1.79769313486231570E+308(3)。虽然对无限稠密的实数来说，这保留下来的区区18位有效数字和理想的实数域有着天壤之别，可对于人类现阶段的绝大部分工商业活动来说已经足够了。与有损压缩中的哲学思维一样，这些即使舍弃也对人的感知影响极为微小的因素是可以在考虑“性价比”的前提下做适当取舍的。这种思维方式在数据科学领域的实践过程中始终如一。
1700507318
1700507319
在以有限去仿真无限，以离散去仿真连续的情况下，永远存在这种问题。所以，对那些我们无法精确感知的，感知了也无法把控的，把控了也对提高效益没有意义的场合，确实需要斟酌精度提升的必要性。
1700507320
1700507321
在离散数学里有一个非常重要的概念叫作“笛卡儿乘积”（Cartesian Product）。笛卡儿乘积实际上是离散的面积、体积的概念。假设有一个集合X，有n个元素 {x1, x2,…, xn}；另外有一个集合Y，有m个元素 {y1, y2,…, ym}：
1700507322
1700507323
1700507324
1700507325
1700507326
图11-1 电子计算器上的科学计数法
1700507327
1700507328
1700507329
1700507330
1700507331
用一个矩阵表示这个笛卡儿乘积的结果x2y1, x2y2, …, x2ym
1700507332
1700507333
1700507334
1700507335
1700507336
通过观察可以发现，在这样一个矩阵中，每个元素的和相当于整个矩阵的面积，也就是这样一个表达式
1700507337
1700507338
1700507339
1700507340