1. 计算的本质——从机械到电子

1.1 什么是计算机？

美国的专利律师在写专利文件时，为扩大专利的覆盖范围，不会直接使用"计算机"这个词，而是用下面的话来描述专利范围：

一个具有运算能力，可能还有一定存储能力的机器设备，受指令控制，包括但是不限于计算机、智能手机、平板电脑、电子个人助理、阅读器、程控交换机、智能传感器（含各种可穿戴设备）、有处理器的医疗仪器、服务器、存储设备等。

任何能计算、有存储能力、受指令控制的机器都可以被算作计算机。上述三要素中，按照习惯可进一步划分为硬件和软件。其中，硬件是计算单元、存储单元，软件是指令序列。

1.2 计算机发展史

• 古希腊也出现过算盘，但因为没有类似与珠算口诀的指令序列，不能称之为计算机。

• 计算机历史可以追溯到2000年前中国的算盘，算盘上的珠子有帮助计数的功能，即具有存储能力；另外，中国的算盘是依靠一套珠算口诀控制操作的，即指令序列，人只需要机械的操作。

• 但算盘这种“原始”计算机存在一定的使用门槛：即需要牢记口诀，还要训练手的肌肉记忆。

• 到1642年，法国出现最早的机械计算机，可进行加减法运算。

• 19世纪，先后出现了莱布尼兹转轮（解决进位操作）和差分机（微积分运算）。

• 之后，有人想到用程序控制机械计算机，但一开始想法陷入了一个误区：用复杂方法解决复杂问题。

• 布尔代数则提供了一个工具，通过二进制将算术和数理逻辑统一起来。

• 楚泽则用实践证明：使用任何布尔代数可以实现任何十进制的运算，并实现复杂的逻辑控制。

• 香农则从理论上指出任何逻辑控制和计算都和开关电路等价,在布尔代数和算术运算之间搭起了一座桥梁。

• 图灵机：计算的本质是机械运动。解决的是可以经过有限步计算的有明确答案的问题。

• 如今，人工智能所解决的问题，也没有超过计算机的界限。只是现在有很多问题找到了转化为数学问题的桥梁。

感兴趣的进一步可阅读《计算之魂》一书序言中关于这段历史的介绍。

2. 毫厘千里之差——大O概念

2.1 背景

早期软件算法简单，多用来科学计算，使用次数少，不重视质量。
随着计算机在商业上的普及，程序设计得是否合理、效率的高低、占用资源的多少，就需要认真考虑了。

2.2 高德纳介绍

1. 计算机算法分析的鼻祖，提出了评估计算机算法的标准
2. 编写了计算机科学领域的“圣经”——《计算机程序设计艺术》
3. 迄今为止最年轻的图灵奖获得者
4. 开发了排版软件TeX
5. 硅谷地区众多图灵奖获得者中名气最大、最会编程的人

2.3 大数和数量级的概念

在衡量算法时，人们会想到"速度快"、占用空间少。关键在于用多少数据来测试算法的速度和空间，因为使用不同数量的数据测试时，两个算法的相对表示可能会完全不一样。

例如：
场景1：使用1万个数据进行测试，算法A运行1毫秒，算法B则需要运行10毫秒。
场景2：使用100万个数据进行测试，算法A运行10000毫秒，算法B运行6000毫秒。

1965年，算法复杂度概念提出，科学家开始考虑用一种公平一致的算法比较不用算法的性能。

高德纳严格量化衡量算法，其思想为：

1. 在比较算法的快慢时，只需要考虑数据量特别大，大到近乎无穷大时的情况。
2. 决定算法快慢的因素虽然可能有很多，但是所有的因素都可以被分为两类：第一类是不随数据量变化的因素，第二类是随数据量变化的因素。
3. 两种算法在复杂度上相差哪怕只有一点点，N很大之后，效率可能就差出万亿倍了。

3. 思考题

思考题0.1

如何通过指令控制，将一副扑克牌变成一种简单的计算机？（ 难度系数4颗星）

答：算盘具有运算能力、存储能力，受指令控制依靠一套珠算口诀控制操作的，人只需要机械操作，可视为简单的计算机。下面通过借助算盘的控制算法(珠算口诀)来实现。

横向13列可用1、2、3、4、5、6、7、8、9、10、J、Q、R表示。
纵向上2珠子(0,1,2三状态)，下5珠子(0,1,2,3,4,5三状态)， 共 $3\ast 6=18$ 种，对同大小的扑克的四种花色进行排列组合，即可得到24种结果，因此可用不同排列组合的同大小不同花色的扑克模拟纵向的操作。
至此，即可借助类似于算盘的控制算法(珠算口诀)来实现将一副扑克牌变成一种简单的计算机。

思考题0.2

利用“与非”(AND-NOT)运算实现布尔代数中的与、或、非三种运算。（ 难度系数2颗星）

答：简单的数字电路逻辑问题。如下：

思考题0.3

如果计算的本质是机械运动，那么信息处理和能量就存在—个对应关系。比如，我们可以计篇一下1946 年的 ENIAC 消耗 1 度电 ( 1千瓦时）能完成多少次计算，今天的华为P30 手机消耗1 度电能完成多少次计算。（ 难度系数2颗星）

答：参考计算之魂思考题0.3——ENIAC和华为P30

ENIAC：
功率：150KW；计算速度：5000次/s；
华为P30（麒麟980芯片）：
功率：4W；最高主频：2.6GHz；

ENIAC

1度电 = 1千瓦时 = 1KW·h = 1000(W) * 3600(s)= 3.6e6(J）；
ENIAC的功率为150KW意味着这个大家伙每秒钟要消耗的能量为E(E) = 150 * 1000 * 1 = 1.5e5(J)；
ENIAC每秒计算次数为5000次；
于是，可得ENIAC计算1次需要消耗的能量E1 = E(E) / 5000 = 1.5e5 / 5000 = 30(J)；
所以，ENIAC消耗一度电，可以进行的运算次数T(E) = 3.6e6 / 30 = 1.2e5(次)。

麒麟980芯片

麒麟980芯片每秒要消耗的能量为E§ = 4 * 1 = 4(J)；
由最高主频可得，麒麟980芯片每秒计算次数为2.6e12次；
于是，可得麒麟980芯片计算1次需要消耗的能量E2 = E§ / 2.6e9 (J);
最终，麒麟980消耗1度电，可以进行的运算次数T§ = 3.6e6 * 2.6e9 / 4 = 2.34e15(次)。

思考题0.4

在数字计算机出现之前曾经出现过模拟计算机，如何证明后者等价于前者的某个子集？（ 难度系数3颗星）

答： 1. 模拟计算机依靠机械装置实现计算，精度提高空间有限。2. 图灵机可解决的问题为可计算问题，数字计算机可解决的问题为可计算问题的子集，即工程可解问题。
首先，模拟计算机解决的问题属于可计算问题；同时，又是复杂度有限，工程可解的问题，属于工程可解问题。较之于数字计算机，精度有限，故属于工程可解问题的子集，即模拟计算机等价于数字计算机的某个子集。

思考题1.1

世界上还有什么产品类似于计算机，是软硬件分离的？（ 难度系数1颗星）

答： 计算机，可定义为任何能计算、有存储能力、受指令控制的机器。其中，硬件是计算单元、存储单元，软件是指令序列。至于为什么要进行软硬件分离？从ENIAC专用计算机到EDVAC通用计算机的历史可以看出，是为了通用，让我们只需要修改或更新软件而无需更换硬件来完成某些需求。
因此，日常生活中很多产品都符合软硬件分离的设计，如智能手机、智能电视、可穿戴电子设备、汽车等。

思考题1.2

如果一个程序只运行一次，在编写它的时候，你是采用最直观但是效率较低的算法，还是依然寻找复杂度最优的算法？（难度系数2颗星）

答：在力所能及、条件允许的范围内，应该尽可能寻找复杂度最优的算法，虽然程序只运行一次，但最直观但是效率较低的算法可能会带来内存和时间上的浪费。如果是处理海量数据，这种效率较低的算法是得不偿失的。依然寻找复杂度最优的算法便类似于“磨刀不误砍柴工”的效果了。