# 欢迎光临 本文档内容出自 Crash Course 上传在 [YouTube](https://www.youtube.com/playlist?list=PL8dPuuaLjXtNlUrzyH5r6jN9ulIgZBpdo) 的 Computer Science 课程（2017 年），授课教师为 @Carrie Anne Philbin ，于 2022 年 10 月观看完中译版视频，此为课程笔记，由 [枝因（viyi）](https://viyi.cc/about_me/)撰写制作。 课程全集为 40 集，自行分为 5 个小节，对应视频分 P 如下： 1. 计算机组成：p1\~9+17 2. 程序设计：p10\~16 3. 操作系统：p18\~27 4. 计算机网络：p28\~33 5. 拓展补充：p34\~40 相关参考资料如下：[中译版视频传送门](https://www.bilibili.com/video/BV1EW411u7th)；[字幕组开源项目](https://github.com/1c7/crash-course-computer-science-chinese)；[完整版文字笔记](https://shimo.im/docs/PJAUY30F1uYksv0h/read)。 祝您网上冲浪愉快。 # 1 计算机组成 对应分 P 为 p1\~9+17, @GoogTech 整理的该小节笔记脑图见[此处](https://www.processon.com/view/link/61ef6e8f0e3e7439ae917672#map)，@取名苦手小明 的文字版笔记见[此处](https://shimo.im/docs/vkCKkj3YxGtygrVg/read)。 # 1.1 早期的计算（Early Computing） ### 1.1.1 信息时代（Electronic Age） 三次工业革命推动全球发展： 1. 第一次（蒸汽）：用机械提高农业、工业、畜牧业的规模，又名机器时代（the Age of Machines）。 2. 第二次（电力）：第二次工业革命以电力的大规模应用为代表，电灯的发明为标志，用上了石油作为能源。 3. 第三次（电脑）：个人电脑的普及，互联网的出现，信息时代的到来。 ### 1.1.2 早期计算历史 > "At each increase of knowledge, as well as on the contrivance of every new tool, human labor becomes abridged." by Charles Babbage > > 「随着知识的增长和新工具的诞生，人工劳力会越来越少。」——查尔斯·巴贝奇

早期计算历史

# 1.2 电子计算（Electronic Computing） ### 1.2.1 诞生背景 20 世纪人类社会规模的飞速增长，二战动员人数的数量级已经达亿，全球贸易和运输更加紧密，工程和科学的复杂程度达到新高。随之而来的是数据量的暴增，这使人们需要更自动化、更强大的计算能力。 ### 1.2.2 电子元器件发展历史

电子元器件的发展历史

一些趣闻： 1. 硅谷（Silicon Valley）：美国加利福尼亚州圣克拉拉谷（Santa Clara Valley）的别称，因此地多为晶体管和半导体的开发（其最常见材料为硅）企业而得名。 2. 晶体管的发明者之一威廉·肖克利（William Shockley）在硅谷创立了肖克利半导体实验室（Shockley Semiconductor Laboratory）。 3. 因不满肖克利的管理方法和行为，实验室中的八人（Traitorous eight）成立了仙童半导体（airchild Semiconductor），其员工后来创立了英特尔（Intel）——当今世界上最大的计算机芯片制造商。 ### 1.2.3 电子计算机发展历史

电子计算机发展历史

# 1.3 布尔逻辑与逻辑电路（Boolean Logic & Logic Gates） > 抽象（Abstraction） > > 在计算机科学中，抽象化是将资料与程序，以它的语义来呈现出它的外观，但是隐藏起它的实现细节。 > > 抽象化是用来减少程序的复杂度，使得程序员可以专注在处理少数重要的部分。 > > (cr. [wikipedia](https://zh.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E5%8C%96_\(%E8%A8%88%E7%AE%97%E6%A9%9F%E7%A7%91%E5%AD%B8\)), link [🆚 数学抽象](https://ray-eldath.me/programming/three-important-ideas/)) ### 1.3.1 为何选择二进制 计算机从十进制的机电设备进化到了二进制（Binary）\ 的电子设备，电路的开闭表示真（true）和假（false）两种状态。 尽管晶体管可以表示超过两种状态（以不同大小的电流经过），但可表示的状态越多，越容易受噪音的扰动，就越难以区分。而二进制的 1 和 0 很容易在电路中用「通」和「断」区分出来。 同时，布尔代数作为一种仅处理两种状态的数学分支，为计算机提供了完备的运算法则和方法。 ### 1.3.2 布尔代数 布尔代数（Boolean Algebra）由英国数学家乔治·布尔（George Boole）发明，因出于对亚里士多德基于哲学的逻辑方法进行数学式扩展的兴趣，其用逻辑方程系统而正式地证明真理，并于 1847 年的首部著作《逻辑的数学分析》中进行了介绍。 布尔代数中使用 true 和 false 两个变量进行逻辑操作，其基本运算如下： > 1. 布尔代数的基本运算可以很容易地用晶体管构建，将晶体管的控制线当作 input，将底部的电极线当作 output，则输入输出同步： > >
> 2. 能控制电流的路径称为「门」（Gate）。 > 3. 电路图中的拱门表示 2 条线没有连接，仅仅只是跨越。 > >
### 1.3.3 NOT 非 数学符号： $\neg$ Tips：真假倒置 真值表： | A | !A | | :-: | :-: | | 真 | 假 | | 假 | 真 | 晶体管电路： * 上方的电极线当作 output，下方电极线接地。 * 半导体通电 True （Input on），则线路接地，无输出电流，为 False。 * 半导体不通电 False （Input off），则输出电流从上方输出，为 True。
### 1.3.4 AND 与 数学符号：$\land$ Tips：一假则假，两真为真。 真值表： | A | B | A && B | | :-: | :-: | :----: | | 真 | 真 | 真 | | 真 | 假 | 假 | | 假 | 真 | 假 | | 假 | 假 | 假 | 晶体管电路： * 两晶体管串联，当且仅当 2 个晶体管都通电，输出才有电流（True）。

1&&1->1

### 1.3.5 OR 或 数学符号：$\lor$ Tips：一真为真，两假则假。 真值表： | A | B | A \|\| B | | :-: | :-: | :------: | | 真 | 真 | 真 | | 真 | 假 | 真 | | 假 | 真 | 真 | | 假 | 假 | 假 | 晶体管电路： * 两晶体管并联，均无电流时晶体管阻塞，输出无电流为 False。

0||0->0

### 1.3.6 XOR 异或 数学符号：$\oplus$ Tips：不同为真，相同则假。 真值表： | A | B | A XOR B | | :-: | :-: | :-----: | | 假 | 假 | 假 | | 假 | 真 | 真 | | 真 | 假 | 真 | | 真 | 真 | 假 | 晶体管电路：

0 XOR 1->1

### 1.3.7 逻辑门电路 作为用晶体管搭建的复杂电路的抽象，将逻辑门电路简化，用于构建更大的组件，而不至于太复杂。与、或、非以及异或门电路符号如下：

逻辑门电路符号

# 1.4 二进制表示法（Representing Numbers and Letters with Binary） > “Everything is number.”by Pythagoras > > 「万物皆数。」——毕达哥斯拉 ## 1.4.1 二进制 在二进制中，每个符号就是二进制元数字（0/1）中的一个二进制位 （binary digit） 或是称之为一位 （bit）。 二进制基数为 2，位权为 2 的整数次幂。用 0 和 1 这两个数字表示，逢二进一。
$2^0$$2^1$$2^2$$2^3$$2^4$$2^5$$2^6$$2^7$$2^8$$2^9$$2^{10}$$2^{11}$
124816326412825651210242048
| $2^{12}$ | $2^{13}$ | $2^{14}$ | $2^{15}$ | $2^{16}$ | | :------: | :------: | :------: | :------: | :------: | | 4096 | 8192 | 16384 | 32768 | 65536 |

二进制算术加法

计算机中的数据常用 8 位表示，又名 1 字节（1 bit = 1Byte）。8 位二进制可按 3 位为一组（高位补零）转换为八进制： | 八进制 | 二进制 | | :-: | :-: | | 0 | 000 | | 1 | 001 | | 2 | 010 | | 3 | 011 | | 4 | 100 | | 5 | 101 | | 6 | 110 | | 7 | 111 | ## 1.4.2 进制转换 十进制转二进制则「除基逆序取余」，二进制转十进制则「乘位权后相加」。

二进制转十进制

## 1.4.3 单位换算 因 $10^3=1000$ 与 $2^{10}=1024$ 是近似值，故在某些时候 KB 所描述的两种含义经常混用（i.e. 1KB = 1000 or 1024 Byte 均正确）。 通常来说描述存储容量或是文件大小时以 2 为底，描述频率或速率时以 10 为底。e.g. 32 位或 64 位计算机是指每次按块处理数据的单块长度位 32b 或 64b（32b 可表示的最大数约为 43 亿，64b 则为 $9.2^{10}$）。
十进制术语缩写数值二进制术语缩写数值数值差别
kilobyteKB$10^3$kibibyteKiB$2^{10}$2%
megabyteMB$10^6$mebibyteMiB$2^{20}$5%
gigabyteGB$10^9$gibibyteGiB$2^{30}$7%
terabyteTB$10^{12}$tebibyteTiB$2^{40}$10%
e.g. 1KB = 1000B = 8000b；1MB = 1000KB etc. ## 1.4.4 负数与浮点数 为了便于存储数据，计算机将内存中的位置标记称为「位址」（memory addresses）。当硬盘（memory）的容量到达 GB 和 TB 这样上万亿字节的量级时，需要用 32/64 位的数字来表示位址。 地址无需区分数字的正负，在其他情况下则需要区分（银行存款）。此时可用 32 位中的第 1 位标识正负（1 负 0 正），剩下的 31 位表示数字本身（实数），可表示范围为 ±20 亿左右（ $-2^{31}$ \~ $2^{31}-1$ ）。 非整数因其小数点可以在数字中浮动而称为「浮点数」（Floating Point Numbers），其最常见的表示标准是 IEEE 754 标准。该标准使用类似于科学计数法的方式存储十进制值。 具体表示方法为「浮点数 = 有效位数 × 指数」，以 32 位浮点数为例，第 1 位表示正负，第 2\~9 位则表示指数，剩下 23 位存储有效位数。e.g. 625.9 = 0.6259（有效位数）× $10^3$（指数）

IEEE754 浮点数表示

## 1.4.5 字符 英国作家弗朗西斯·培根（Francis Bacon）曾用 5 位序列来编码 26 个英文字母，在 1600s 传递机密信件。5 位最多可表示 $2^5=32$ 个数字，足够容纳英文字母，但无法表示符号与数字以及大小写字母。

弗朗西斯·培根（Francis Bacon）的编码方式

### ASCII ASCII 全称为美国信息交换标准代码（American Standard Code for Information Interchange），于 1963 年发明，使用 7 位代码表示 128 个不同的值。 在 ASCII 中，除了大小写字母、数字以及常用符号之外，还有一些特殊命令符号。比如使用换行符（图中 10）进行换行。

ASCII 码表

ASCII 的出现使得不同公司所制造的设备之间能够交换数据，我们将这种能够通用交换信息的能力称为「互用性」（interoperability）。 ASCII 为英文设计，在其他非英语国家不够通用。因电脑中 1 字节有 8 位，ASCII 中未使用的 128\~256 可供各个国家进行再次编码。常见用途如下： * 美国：主要用于编码附加符号，如数学符号、图形元素或是常用重音字符。 * 俄罗斯：用于表示西里尔（Cyrillic）字符。 * 希腊：表示希腊字母。 ### Unicode 尽管 ASCII 留有空余编码，但对非拉丁语系的国家仍不适用（比如中国和日本）。因此各国均发明了多字节编码方案，但互不兼容，由此带来新的问题——乱码（因过于常见，在日本甚至有个词 mojibake 表示这种情况）。 Unicode 于 1992 年诞生，采用统一编码方案解决乱码问题。最常见的 Unicode 是 16 位的，可表示的量级达百万，甚至有空位放 Emoji 😉。 # 1.5 ALU 算术逻辑单元 （How Computers Calculate） ALU 算术逻辑单元（Arithmetic and Logic Unit）是计算机中负责运算的组件。 最著名的 ALU 之一是 Intel 74181，其于 1970 年发布，是第一个封装在单个芯片中的完整 ALU。 Intel 74181 使用了 70 个逻辑门，但无法执行乘除运算。

Intel 74181

ALU 由 1 个算术单元（arithmetic）和 1 个逻辑单元（logic unit）组成，算术单元可用于进行加减法运算或是增量运算（x+1），逻辑单元执行逻辑操作（如布尔代数中的基本运算）。 ## 1.5.1 算术单元 ### 半加器 半加器（half adder）由异或门和与门组成，仅能计算 1 位加法。两个输入（0 或 1）有 4 种可能的输出（1 = true，0 = false），不计进位的情况（1+1=0，高位舍弃）可用「异或门」搭建：
当且仅当两个输入均为 1 时需要进位，该规则和「与门」相同，两者连接则为半加器：

半加器

### 全加器 使用半加器做两个三位二进制数加法时，需要多加一个进位上的数字（共计 3 个数相加）。
全加器的真值表如下：
全加器的逻辑门电路如下：
### 8 位行波进位加法器 全加器可以处理两个三位二进制数的加法运算，两个八位二进制数的加法可以从低位逐列相加，用 1 个半加器和 7 个全加器搭建：

八位行波进位加法器

当计算结果的位数大于可用于表示的位数，则会出现「溢出」（overflow），这会导致 error 和不可预期的结果。 为防止溢出，可以使用更多的全加器来完成 16 位或是 32 位数字的操作。但使用更多的逻辑门会提高造价，同时进位计算的耗时也更多，在每秒几十亿次的运算下该延迟仍然会造成影响。所以现代计算机所采用的加法电路为「超前进位加法器」（carry-look-ahead），其速度更快。 ### 乘除法 ALU 的算术单元基本都支持下图中的 8 种操作，简单 ALU 可以通过累加/累减来实现四则运算中的乘除法（慢但有效），复杂 ALU 会用更多的逻辑门构建乘法电路。

ALU 算术单元支持的八种操作

## 1.5.2 逻辑单元 逻辑单元（logic unit）用于执行逻辑操作，比 AND、OR 和 NOT 操作，也可以用于进行简单的数值测试。注意此处的 0 和 1 遵守布尔代数的逻辑运作，而非算术加减。 下图的逻辑单元门电路用于检测输出是否为 0（可用于确认两数字是否相等），OR 或门遇 1 出 1，最后用 NOT 非门取反后，凡有 1 则为 0，检测结果为 False 假，意为输出不为 0（其中至少有一位是 1）。

检测输出是否为 0 的逻辑单元电路

## 1.5.3 ALU 抽象 8 位 ALU 需要用上百个逻辑门搭建，因此工程师用镂空大 V 符号来表示 ALU 组件：

ALU

简图如下：

8 位 ALU 基本图形

除了两个 8 位的输出和一个输入之外，8 位 ALU 还需要用 4-bits「操作码」（Operation Code）确认执行操作类型，同时还会输出一些 1-bit 的标志位（Flags）表示特定状态，常见类型如下： * 溢出位（Overflow）检测是否发生溢出情况。 * 零标志位（Zero）：检测输出是否为零。 * 负标志位（Negative）：检测输出是否为负数。 # 1.6 寄存器 & 内存（Registers and RAM） 计算机的存储器（Memory）可分为两种类型： 1. 随机存取存储器（Random Access Memory, RAM）：仅在有电的情况下存储内容，常用作内存。 * SRAM( Static Random Access Memory，静态随机存取存储器）：“静态”是指这种存储器只要保持通电，里面储存的数据就可以恒常保持（接下来用锁存器做的就是它）。 * DRAM( Dynamic Random Access Memory，动态随机存取存储器)：“动态”是指所储存的数据需要周期性地更新。 * Flash：允许多次写入的非易失性存储器。 * NVRAM( Non-Volatile Random Access Memory）：非易失性随机存取存储器。 2. 持久存储器（Persistent Memory）：电源关闭时，数据也不会丢失。 ## 1.6.1 AND-OR 锁存器 用 OR 或门可以记录 1，用 AND 与门可以记录 0： ![记录 0 或 1](/files/zA5Hk80ZDugBsXwWK0Dx) 将两者如下图所示连接则构成 AND-OR 锁存器，可以锁定（latch）一个值来存储 1 位信息，故有此名。其有两个输入：「设置」为 1 则输出为 1，「复位」为 1 则输出为 0，两者均为 0 则输出最后记录的数字。 ![AND-OR 锁存器](/files/CdrTjtKyKKn9605yNDNt) 另，通常将放入数据的动作称为「写入」（writing），拿出数据的动作称为「读取」（reading）。 ## 1.6.2 门锁（Gated Latch） AND-OR 锁存器需要用两个输入记录一个数字，使用起来较为麻烦，因此引入可以控制读写的「门锁」（Gated Latch）来存储 1 bit。门锁在输入输出之外，添加了一条允许写入线（Write Enable）——启用时允许写入数据，反之锁定（locked）。 ![门锁](/files/KbRXLffDk235A9LVYtGp) ## 1.6.3 八位锁存器（8-bit Latch） 将 8 个门锁用 1 根允许写入线连接，构成八位锁存器，可用于存储 8 位信息。先将允许写入线置 1，写入数据后将其置 0 则可完成存储。 ![八位锁存器](/files/wUihOasnWrpDFvAv6Wmo) ## 1.6.4 锁存器矩阵（Latches Matrix） ### 连接 使用 16 × 16 个可存储 1 bit 的锁存器矩阵来存储 256 位，当需要启用某个锁存器时就打开相对应的行线、列线和允许写入线。 ![锁存器矩阵](/files/TN3pqOLSxuMBSHEDbuW0) 在交叉处使用 AND 与门连接，当且仅当行线、列线、单个锁存器的允许写入线均为 1 时，才允许该锁存器进行写入。 ![\[使用与门连接](/files/xDbhQitXBcPTbmsMchu7) 这也意味着可以使用 1 根数据线来连接矩阵中的所有锁存器用于传输数据，因为可根据行列线进行需要开启的锁存器。类似地，可以使用 1 根允许写入线来控制从矩阵中的某个锁存器读取数据。 因此，256 位的锁存器矩阵仅需 35 条线连接—— 1 条数据线、1 条允许写入线、1 条允许读取线以及 16 行、16 列用于选择锁存器的线。 ### 选择 4 位二进制数可表示的最大数字为 16，刚好足够满足对 16 × 16 的矩阵进行行数、列数的地址编码。 可以使用 8 位二进制数来唯一标识行列交叉处的锁存器，比如第 12 行第 8 列的锁存器可以表示为 1100 1000，这就是前文 1.4.4 节中提过「位址」（memory addresses）。 为了使机器读懂这个位址，需要使用 2 个支持 16 路的「多路复用器」（multiplexer）来分别处理行列地址，输入 4 位的数字后，多路复用器会连通相应的行/列线。 ![多路复用器](/files/apXwdE4k0uwKWXSaVoxk) 16 × 16 的单位锁存器矩阵可以存储 256 个 bit，将 8 个 256-bit 的存储器连接起来构成大小为 256Bytes 的存储器。 ![256Bytes 的存储器](/files/TAYljIEcAWNswEwbEUzG) 在 256Bytes 存储器中，一个八位数字是将每位各自存储在一个 256-bit 内存中，1 个 256-bit 存储器中的某位比特与其余 7 个 256-bit 存储器中的某 7 位比特共享同一个地址。因此，256Bytes 内存中也只有 256 个地址，各自代表 1Byte 的大小，可读写 8bit 值。 简单起见，将这个 256Bytes 的存储器当作整体抽象为一个可寻址存储器。 ![8 位可寻址存储器](/files/mp7mlPwMNJhQ14l4E2ZI) ## 1.6.5 RAM 8 位位址最多可以表示 256 （0\~255）个地址，想要对 TB 或是 GB 级别的存储器寻址则更高位的数字表示地址（比如 16/32 位）。 ![1980s 的 1MB 内存条](/files/fme3st7QTQlNQWW4cMtK) 上图是 1 MB 大小的 RAM 内存条（1980s），通常是由 8 个内存模块（memory modules）构成，1 个内存模块里有 32 个内存方块（squares of memory），1 个内存方块中有 4 个小块（block），1 个小块中有 128 × 64 位的矩阵，单个小块是 8192bits 大小。 因此，1 个内存方块中有 8192 × 4 = 32768 bits，总共有 32 个内存方块，单个内存模块大约在 100w bits 大小，有 8 个内存模块，总共是 800w bits 约等于 1 MB 大小。 # 1.7 CPU 中央处理器（The Central Processing Unit） ## 1.7.1 组成概述 ![CPU 简图](/files/SKh7nYY78GGmsPPomWZt) ### CPU CPU （Central Processing Unit，中央处理单元）是负责通过「指令」指示程序如何操作的器件，其通常由寄存器、控制单元、ALU、时钟等组成。 比如，若要执行加/减的数学指令，则交由 ALU 完成；若是内存指令，则与 RAM 通信配合进行读写操作（APU 与 RAM 用“地址线”、“数据线”和“允许读/写线”进行通信）。 ### 微体系框架 使用高层次的视角观察计算机的方式称为「微体系架构」（microarchitecture），其更注重于逻辑上的「功能」。比如当我们用一条线连接 2 个组件时，这条线只是所有必须线路的抽象，并不代表两者连接仅仅通过一条线。 ### 指令 指令由「操作码」（operation code, opcode）和「地址码」组成，前者用于说明操作指令的 ID，后者则表示数据来自哪里（寄存器或内存地址）。指令用于指示计算机要做什么，多条指令共同组成程序。 ![8-bit 指令](/files/ZsxO163majBqYD8S6GW7) ### 寄存器 CPU 的控制单元中至少有 两个寄存器，一个「指令地址寄存器」（the instruction address register）用于存放当前指令的内存地址，另一个是「指令寄存器」（the instruction register）用于存储当前指令。 另外还有一些寄存器用于临时存储数据和操作数据（如图中的 ABCD，其与 RAM 相连），寄存器也用于存储程序。 ### 时钟 时钟（Clock）负责管理 CPU 运行的节奏，以精确地间隔触发电信号，控制单元用这个信号来推动 CPU 的内部操作。 时钟速度（Clock Speed）是指 CPU 执行“取指令 -> 解码 -> 执行”中每一步的速度，单位为赫兹 Hz （频率单位，1Hz 表示 1 秒 1 个周期）。1MHz 为 1 秒 100w 个时钟周期，如今的电脑或是手机的时钟速度在千兆级别（1 秒 10 亿次时钟周期）。 超频（overclocking）/ 降频（underclocking）是指修改时钟速度，加快或降低 CPU 的速度。超频过多会让 CPU 过热或产生乱码，降频可以省电，对笔记本和手机很重要，通常会动态调整。 1971 年发布的 4 位 CPU Intel 4004 是第一个单芯片 CPU，其微体系架构（microarchitecture）类似与上述所言，其时钟频率达到 740k Hz（每秒 74 万次）。 ![Intel 4004 体系架构](/files/pIWZWf7zjlxP1u4Jetm9) ## 1.7.2 CPU 基本工作原理 CPU 的运作分为三个阶段：取指令（fetch phase）、解码（decode phase）、执行（execute phase）。 ### 取指令 ![取指令](/files/K8uSHHZJF4DjsPlXfO37) （1）指令地址寄存器发地址给 RAM （2）RAM 发该地址内的数据给指令寄存器 （3）指令寄存器接受数据 ### 解码 ![解码](/files/fuVtLahpSspB5L8N4qX4) 指令寄存器根据数据发送指令给控制单元 -> 控制单元解码（使用逻辑门来确认操作码是否为某个指令，示例为 0010-LOAD A、地址 1110-14） ### 执行 📌e.g. LOAD A(取数)： ![LOAD A](/files/Hfqfqdnzo19RrxjNUOhI) （1）使用确认指令（LOAD A）的电路打开寄存器 A 的允许写入线，将从 RAM 读取到的数据存入 A。 （2）指令地址寄存器 +1，继续执行下一指令。 📌e.g. ADD(加法) 操作码 1000 0100 在解码阶段会被解出，1000 指 ADD 相加，则相应的后 4 位会被解释为名为 01 和 00 的两个寄存器地址，分别为寄存器 B 和寄存器 A -> 把寄存器 B 的值加入寄存器 A 中。 ![ADD](/files/7sFyFRSrqNsf6BFs7gGG) （1）调用 ALU，控制单元将寄存器 B 作为 ALU 的第一个输入，将寄存器 A 作为 ALU 的第二个输入，同时传入 ADD 操作码进入 ALU。 （2）ALU 计算完成后将结果暂存于控制单元中的寄存器中，若 ALU 直接将结果存于寄存器 A 中，则会出现不断自加的情况。 （3）控制单元关闭 ALU 后， 将暂存在内部寄存器中的计算结果放入寄存器 A 中。 （4）指令地址寄存器 +1。 📌e.g. STORE(存数) 操作码 0100 1101 在解码阶段会被解出，0100 为 STORE A，1101 是 RAM 地址 13。 ![STORE](/files/CUzaE3lsNljpitYLitWb) （1）打开寄存器 A 的允许读取线，将读取到的数据存入 RAM 。 （2）程序结束，HALT 停止。 # 1.8 指令和程序（Instructions & Programs） 1.8 指令和程序（Instructions & Programs） 2022-10-02 Table of Contents ## 1.8.1 指令集 指令由「操作码」和「地址码」组成，前者用于说明操作指令，后者则表示操作数据的地址（寄存器或内存地址）。记录指令名称、用法、操作码以及所需 RAM 地址/寄存器位址的表格，称为「指令集」。 ![常见指令集\]](/files/2HJpTcrmPUPwGvqrA2QZ) 指令集使得身为硬件的 CPU 是「可编程」（programmable），其可以被软件控制做到硬件本身无法完成的事前，比如下图就是用仅能做加减的 ALU 实现计算余数（e.g. 11 / 5 -> 1）的例子（下图的实现需要多个时钟周期，很低效）。 ![除法指令串](/files/gEUu2xgVJWJgXCqHJvaL) ## 1.8.2 指令执行 ### JUMP 用于改变指令的顺序，或是跳过一些指令。JUMP 的底层实现方式是将指令后四位代表的内存地址的值覆盖掉「指令地址寄存器」里的值。 ![JUMP](/files/W9zCEjAT5bZmfJk8fvRT) 为了避免无限循环（infinite loop）, JUMP 可以设置为有条件的，比如 JUMP NEGATIVE（在 ALU 的负标志位为真 true 时进行 JUMP）、JUMP IF EQUAL（如果相等）、JUMP IF GREATER（如果更大）。 ### HALT 用于停止执行指令程序，同时也是区分指令和数据的标志（指令和数据在同一内存中均以二进制进行存储）。 ## 1.8.3 指令长度 本例中的 CPU 指令为 8 位，前 4 位为操作码，后 4 位为地址码，至多支持 个操作，远远无法满足需求。现代 CPU 通常使用两种方法来拓展指令长度（the instruction length）： （1）使用更多位数表示指令，如 32 位或 64 位。 （2）采用「可变指令长度」（variable-length instructions），指令长度任意，但指令读取稍显复杂。以 8-bit 操作码的 CPU 为例，其遇到 HALT 这类无序额外数据的指令会立即执行，遇到 JUMP 这类需要位置值信息的指令（又名「立即值」（Immediate Value））会明白所需位置值在 JUMP 后面。 ![Intel 4004 指令集](/files/UOGAwHybUmvRXX5b6W1F) 1971 年 Intel 4004 CPU 发布，这是第一个单芯片 CPU，支持 46 个指令。为了表示更多的内存地址，其使用 8-bit 立即值来执行 JUMP。经多年发展，如今的 Intel i7 已有上千指令和指令变种，指令长度在 1\~15 个字节中变化。 # 1.9 高级 CPU 设计（Advanced CPU Designs） ## 1.9.1 瓶颈演变 计算机的计算量日益骤增，从 1Hz 到 1GHz 的 CPU 时钟速度（1.7.1 节），每秒需要执行约十亿条指令是非常庞大计算量。 为了提升计算速度，早期的计算机试图减少晶体管（1.2/1.3 节）的切换时间，但最终碰到了物理瓶颈。 另一种方法是通过硬件电路实现相关操作来加快处理速度，比如通过直接在 CPU 硬件层面中使用专门的电路设计除法，直接给 ALU 提供除法指令，而非像 1.8.1 节中举例的那样通过软件来实现。 现代处理器中有许多类似于除法的专门电路来处理图形操作、解码压缩视频、加密文档等，主要为加快处理速度、减少时钟周期。像是 MMX、3DNOW、SSE 等还有额外电路来做更多复杂操作，用于游戏和加密等场景。 硬件实现的便利使得人们很难删掉指令，于是其不断增加——从 Intel 4004 的 46 条指令到现代 CPU 的 上千条指令，CPU 的计算速度越来越快。新的瓶颈不再是时钟周期，而是读取写入数据的 I/O 操作。 数据的读写需要 RAM 的配合，作为独立部件的 RAM 与 CPU 通过「总线」（bus）连接。尽管接近光速传输的电信号可以通过几厘米的总线很快到达（甚至不计寻址、取数、配置、输出的时间），但与每秒处理上亿条指令的 CPU 来说仍有速度差距。 ## 1.9.2 缓存 缓存（cache）是内置于 CPU 中的仅有 KB/MB 大小的存储器，其作为中转站/临时空间缓和两者的处理速度差异，避免 CPU 在等待 I/O 操作执行时空等。 因数据通常按顺序处理，故 CPU 从 RAM 取数据时，可一次取一批暂存在缓存中。在 CPU 执行时可以直接取用缓存中的数据，仅耗费 1 个时钟周期。 当 CPU 执行复杂的长运算时，缓存也可充当临时空间用于存储计算中间值。 ### 缓存命中 若 CPU 所需数据已在缓存中，称为「缓存命中」（cache hit），反之数据不在缓存中称为「缓存未命中」（cache miss）。 ### 脏位 ![脏位](/files/SHuWwYUhcOPDqBcLCeeT) 当因计算结果暂存在缓存中等原因，使得缓存中数据与 RAM 中的数据值不一致时，需要通过缓存中的特殊标记位「脏位」（dirty bit）记录，以便之后同步。 ### 同步 同步通常发生在缓存已满，但 CPU 又需要使用缓存时。在清理缓存之前，CPU 会先检查脏位，若该位已“脏”则先将数据写回 RAM 后再加载新内容。 ## 1.9.2 指令流水线 指令流水线（instruction pipelining）是指当指令执行的各个阶段使用的是 CPU 不同部分时，将其并行处理（parallelize）的执行方式，像是做饭等水开的时候先去切菜。 原本的「取指 -> 解码 -> 执行」需要 3 个时钟周期才能完成一个指令，并行后可以在每个时钟周期内处理 1 个指令，使得其吞吐量（throughput）翻三番。 ![指令流水线](/files/ivuMzkYenw2DX95nRyXa) 指令流水线加快了处理速度，也带来了新的问题——数据依赖性（a dependency in the instructions）和执行流（exexution flow）的改变。 ### 数据依赖性与乱序执行 指令之间的前后依赖关系称为数据依赖性，比如在读取某个数据时，当前正在执行的指令会修改该数据，我们就会拿到旧数据。流水线处理器（pipelined processors）需要弄清楚这种数据之间的依赖关系，必要时停止流水线操作以避免出错。 在高端的 CPU 中，使用「乱序执行」（out-of-order execution）来最小化流水线的停工时间，这种复杂电路其能够动态性排序有依赖关系的指令。 ### 执行流改变与推测执行 “条件跳转”之类的指令会改变程序的执行流，简单的流水线处理器会等待 JUMP 条件值确定后执行，复杂的流水线处理器为避免出现这种空等延迟会采用「推测执行」（speculative execution）。 推测执行是指高端 CPU 会猜测 JUMP 的结果（在岔路口选择路径），提前将指令放进流水线。猜对则立即运行，猜错就清空流水线。 为了减少猜错清空的次数，CPU 厂商使用更为复杂的方法来预测哪条分支更有可能，称为「分支预测」（branch prediction），现代 CPU 的正确率超过 90%。 ### 超标量处理器 ![超标量处理器](/files/g2uGrylSgkDWwvvfDKit) 理想情况下，指令流水线在 1 个时钟周期完成 1 个指令，而可以在 1个时钟周期完成多个指令的处理器称为「超标量处理器」（superscalar processors）。 这种处理器会一次性处理多条指令（取指令 + 解码），通过增加几个相同的电路执行高频指令，以便同时处理多条指令。比如很多 CPU 中会有 4/8/more 完全相同的 ALU 支持执行多个数学运算。 ## 1.9.3 多核处理器 除了上一小节中谈及的优化 1 个指令流的吞吐量来提升 CPU 性能之外，还可以使用多核处理器同时运行多个指令流。 多核处理器是指在一个 CPU 芯片中有多个独立处理单元，其共享缓存等资源，可以合作进行运算。如双核处理器（dual-core processors）或是四核处理器（quad-core processors）。 ## 1.9.4 超级计算机 当多核处理器也无法满足运算需求时，可以使用多个多核处理器。最常见的是使用 2 个或是 4 个CPU ，而如果要模拟宇宙形成这种怪兽级别的运算（monster calculations）则需要使用超级计算机（supercomputer）的运算能力。 超级计算机一般拥有着上万个 CPU，每个 CPU 有着上百个核心，每个核心的频率达到 GHz，每秒可以进行亿亿次量级的运算。 截至 2022 年 11 月，[世界上最快的计算机](https://www.top500.org/lists/top500/2022/11/)是美国橡树岭国家实验室的 Frontier，总共超过 8 千万个核心，每个核心的运算是 2GHz，每秒可运行 110.2 亿亿次浮点运算，这也称为每秒浮点运算次数（FLOPS）。 # 1.10 集成电路、摩尔定律（Integrated Circuits & Moore's Law） ## 1.10.1 集成电路（Integrated Circuits） ### 数字暴政 1940s\~1960s 中期，计算机由独立部件用线连接而成组成，这些独立部件称为「分立元件」（discrete components）。 若想提升性能，只能增加更多分立元件，这会导致更多更复杂的电线，这种问题称为「数字暴政」（Tyranny of Numbers）。 比如 1.2.3 小节提及的 ENIAC 就使用了 1.7w 多个真空管，7w 个电阻，1w 个电容，500w 个手工焊点。 后来到了 1950s 中期，更小更可靠的晶体管在市场上出现。1959 年 IBM 将 709 计算机中的电子管换为晶体管制造出了 IBM 7090，其速度提升 6 倍，价格只有一半。但商业化的晶体管仍然属于分立元件。 数字暴政问题的严重性在 1960s 达到顶峰，亟待引入新抽象来封装这种复杂性。 ### 集成电路 1958 年，Jack Kilby 使用锗作为材料将独立部件用电线连接集成在一起，使得原先分立元件组合成了新的独立组件单元，集成电路（Integrated Circuits, IC）自此出现。 1959 年，Robert Noyce 所在公司仙童半导体使用了更稳定储量也更多的硅作为集成电路材料，使得集成电路被广泛使用。Noyce 也因此被公认为现代集成电路之父，开创了电子时代（the electronics era）。 ### 印刷电路板 起初的 IC 只集成了几个晶体管，可以将 1.3 节的逻辑门封装成单独组件，但 IC 之间的相互连接仍然不便。于是出现了「印刷电路板」（Printed Circuit Boards, PCB）。 印刷电路板通过蚀刻（etch）金属线的方式将零件连接在一起，无需焊接或是使用一大堆线，并且可以大规模量产。 PCB 和 IC 相结合使得分立元件和电线大幅减少，实现相同功能。 ## 1.10.2 光刻技术（Photolithography） 受限于当时的技术，在 IC 立塞 5 个以上的分立元件还是很困难，直到新的制作工艺「光刻」（Photolithography）出现，其利用光将图案印到材料上，可以使用基础操作来制造复杂电路。以用光刻技术制作晶体管为例： ### 蚀刻（etch） ![光刻基础层](/files/NGKA9BhQ9NW23pruuodY) * 晶圆（silicon wafer）：最基础的硅薄片，一种半导体材料，有时导电有时不导电。 * 氧化层（oxide layer）：保护层。 * 光刻胶（photoresist）：光照后可溶，可以使用特殊化学药剂洗掉。 * 光掩膜（photomask）：用于遮挡不希望被强光照射融化的地方。 强光照射后，未被光掩模遮挡的光刻胶部分会发生化学变化，使用一种化学物质洗去后，氧化层露出： ![强光照射](/files/PATYb5vxvco4n8Lx63uk) 用另一种化学物质（通常是酸）洗去氧化层中间露出部分，注意两侧氧化层被光刻胶保护未被洗去： ![洗氧化层](/files/g6WMByq637BZtYCIsKXy) 使用另一种化学药品洗掉光刻胶，蚀刻完成： ![洗光刻胶](/files/jWWSFmjLKf2KtQfSxO2H) ### 掺杂（doping） 使用高温气体（比如磷）渗透进暴露出的硅，改变硅的电学性质，使得其导电性更好，这一化学过程称为掺杂（doping）。 ![掺杂](/files/vAxvnrIoBZk4qljneutV) （注：半导体的具体物理和化学性质可参见 [Youtuber Derek Muller 的频道 @Veritasium](https://www.youtube.com/watch?v=IcrBqCFLHIY\&t=0s)。） 再重复一次蚀刻，放上光刻胶和光掩模，开出新形状的缺口： ![二次蚀刻](/files/HymqRc8o9KJRczOwWi9B) 用另一种气体对硅进行掺杂，控制好深度和时机，控制其不超过之前的区域： ![二次掺杂](/files/h7emcRNWuxkjZDd0MsOp) ### 金属化（metalization） 材料处理完后，需要在氧化层上制作出通道，用于放置细小金属导线来连接晶体管。依旧使用光刻胶和光掩膜重复蚀刻步骤，刻出通道。 接着放置一层薄金属（铝或者铜），该过程称为金属化（metalization）： ![金属化](/files/K9E2Z99rlxVOrtW3Ywfc) 再通过光刻胶和光掩膜重复蚀刻步骤，将金属上的具体电路蚀刻出： ![晶体管](/files/HMSLMUql56a9FhK70n3Y) 至此一个晶体管（transistor）制作完工。这是一个双极型晶体管（bipolar junction transistor），由三根线连接不同的区域，每个趋于的掺杂方式不同。 ### 微型芯片（chip） 光刻法同样可以制作电阻或电容等其他电子元件和相互连接的电路，其均可制作在一片硅上。 光刻法一次会制作上百万个细节，同时通过焦距改变可以将透过光掩膜的光投射成任意大小，以便于制作出精细细节。 ![光刻投影](/files/OHQ6LP4qyCIJwuA9T74m) IC 中会有许多导线上下交错，连接各个元件。一片晶圆可以制作很多 IC ，整块晶圆制作完成会后切割然后包裹进微型芯片（chip）中，成为它的核心。 ## 1.10.3 罗尔定律（Moore' Law） 因光刻技术的发展，晶体管变小且集成密度变高。从 1960s 初 IC 塞不下超过 5 个晶体管，到 1960s 中期市场出现超过 100 个晶体管的 IC，于是 1965 年戈登摩尔（Gordon Moore）看到了某些趋势： 每两年左右，得益于材料和制造技术的发展，同样大小的空间可以塞进两倍数量的晶体管。 这被称作是罗尔定理，虽然名为“定律”，但其实只是一种正确趋势。 与此同时，芯片的价格也在急剧下降，从 1962 年的平均 50 美元，到 1968 年的 2 美元左右，再到现在几分钱的 IC ，晶体管更小密度更高价格也低廉。 ## 1.10.4 Intel 4004 晶体管越小，所要移动的电荷量就越少，就能越快速滴切换状态，耗电更少。同时，电路更紧凑也意味着信号延迟更低，时钟速度也会更快。 1968 年，罗伯特·诺伊斯（Robert Noyce）和戈登·摩尔联手成立了新公司 Intel——现今最大的芯片制造商，该名字源于 Integrated（集成）和 Electronics（电子）两个词的组合。 发布于 1971 年的 Intel 4004 CPU 是重要的里程碑，其是第一个使用 IC 制作的微型处理器（microprocessor），集成了 2.3k 个晶体管。 ## 1.10.5 超大规模集成（VLSI） 自 Intel 4004 始，CPU 中集成的晶体管数量爆发式增长： * 1980 年，3w 晶体管 * 1990 年，100w 晶体管 * 2000 年，3000w 晶体管 * 2010 年，10 亿晶体管 实现 10 亿这种密度的光刻技术分辨率约为 1w 纳米，是人类头发直径的 1/10。现如今已发展到 14 纳米，比红细胞小 400 倍。 与此同时，大多数电子器件——RAM、显卡、固态硬盘、摄像头感光元件 etc. ——也在指数式发展。 以 iPhone 7 的 A10 CPU 为例，其在 1cm ×1 cm 大小的面积中集成了 33 亿个晶体管。 这样数量级的电路设计显然无法人力一个个完成，自 1970 年代开始，现代工程师就开始使用「超大规模集成」（very-large-scale integration, VLSI）来自动生成芯片设计。 比如使用「逻辑综合」（logic synthesis）这种技术，可以放置像缓存内存（memory cache）一样的完整高级组件，软件会自动高效生成电路。 ## 1.10.6 世代演变与瓶颈 * 计算 1.0（the 1st generation of computer）：真空管 * 计算 2.0（the second generation of electronic computing）：晶体管 * 计算 3.0（the third generation of computing）：IC 出现并用于制作微处理器 * 计算 4.0 （the fourth generation computer）：超大规模集成电路 摩尔定律也许接近终结了，如果进一步做小芯片，会面临两个主要问题： 1. 波长精度极限：光刻法中使用的光的波长精度已经到达极限，无法更精细地使用光掩膜来蚀刻图案。因此，科学家在研制波长更短的光源，用以投射更小的图案。 2. 量子隧道贯穿（quantum tunneling）：当晶体管非常小，电极之间可能只举例几个原子，电子会跳过间隙，这种现象称为量子隧道贯穿。这会使得晶体管漏电，无法成为好的开关器件。实验室中已经造出 1 纳米大小的晶体管，但能否量产未知。 # 2 程序设计 对应视频分 P 为 p10\~16。 # 2.1 编程史话（Early Programming） ### 2.1.1 编程介质 在 [1.7.2 节](https://viyi.cc/docs/computer_organization_principles/1.7-cpu-%E4%B8%AD%E5%A4%AE%E5%A4%84%E7%90%86%E5%99%A8the-central-processing-unit/#172-cpu-%E5%9F%BA%E6%9C%AC%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86)中说明 CPU 工作原理时，我们假设程序已经在计算机内存中了，但实际上程序需要被加载（load into）进内存。 ![编程介质](/files/6NgUyzTB1lTWtSQAHp5R) ### 2.1.2 冯诺依曼结构 「冯诺依曼结构」（Von Neumann Architecture）由数学家和物理学家约翰·冯·诺依曼（John Von Neumann）发明，其特点在于将程序和数据都存储在同一个地方。 冯诺依曼计算机的标志性组成：处理器（带有 ALU）、数据寄存器、指令寄存器、指令地址寄存器、内存（存储数据和指令），如 1.7.1 小节中搭建起来的那样。 第一台采用冯诺依曼结构的存储程序计算机（Von Neumann Architecture Stored-program）是由曼彻斯特大学于 1948 年建造的 Baby（绰号）——离散变量自动电子计算机（Electronic Discrete Variable Automatic Computer, EDVAC）。 # 2.2 编程语言（The First Programming Languages）

编程语言简史

🏆 the holy grail (圣杯)：使用英文直接于计算机对话（plain ol’ English），计算机会理解并执行。 # 2.3 编程原理：语句和函数（Programming Basics Statements & Functions） ## 2.3.1 概述 规定句子结构的一系列规则，叫做「语法」（syntax），编程语言也有相应的语法结构。用编程语言表达完整单个思想的内容，称为「语句」（statement）。 最基本的语句是赋值语句（assignment statement），用于将一个变量赋值给另一个变量，使用「=」连接两个变量，次序为从右往左。e.g. a = 5, b = 10, c = a +b, abc 均为可赋值的量，变量名可任意但需唯一。 ## 2.3.2 控制流语句（Control statements） 用于控制程序的执行顺序。 ### if Statements 又名条件语句（Conditional Statements），基本思想为「如果 X 为真（True），那么执行 Y」（其中 X 为 conditional expression 条件表达式），类似于岔路口，会根据条件表达时的真假执行一次。 ![if](/files/evVO8zxbonW6noOfpKKo) 与 else 结合使用后，当条件为假时，则执行 else 中的代码： ![if-else](/files/WPdpC78D2EwhNK4LVOLc) ### 条件循环（conditional loop） 使用条件循环可根据条件执行多次，如 while 循环——当 while 条件为真时，代码会重复执行。 ![while](/files/ZY3oqVZoLKfDbxTjOQFW) 另一种常见的循环是 for loop ——不判断执行条件而是判断执行次数，for 会循环特定次数。执行后自增 1，直到循环条件不满足。 ![for](/files/FcfPLfJaYJRLLbrIB8Xt) ## 2.3.3 函数 「Less is more. 」 当某段代码需要多次重复使用时，为避免修改繁琐可以将其打包为「函数」（functions），又名「方法」（methods）或是「子程序」（subroutines）。 下图示例是名为「EXPONENT」(指数) 的函数，所需参数为「BASE」(底数) 和「EXP」(exponent, 指数)，「RETURN」用于返回计算结果给调用该函数的代码。 ![指数函数](/files/IwJfqybr8KaJ4QV2tFn5) 函数这样的抽象（abstraction）是现代编程的核心，现代软件采用「模块化编程」（Modularizing programs），其由上千个函数构成。不同的程序员写不同的函数，其各自确保自己的代码工作正常，各个函数各自负责不同的事情，使得整个程序正常运作。 当某个函数的代码行数过百，则应该有东西可以拆成一个新的函数。现代编程语言中有专业人员预先写好的函数集合，称为「库」（library）。 # 2.4 算法入门（Intro to Algorithms） ## 2.4.1 概述 ### 算法 算法（Algorithm）一词源自 1000 多年前的波斯博识者，阿尔·花拉子密(Abū ʿAbdallāh Muḥammad ibn Mūsā al-Khwārizmī), 代数（algebra）之父之一。 算法是指求解问题的具体步骤，一般来说所需步骤越短越好，但有时也会考虑占用内存的情况。 ### 复杂度 算法的输入大小和运行步骤之间的关系叫做「算法复杂度」，使用「大 O 表示法」来衡量运行速度的量级。 ## 2.4.2 选择排序（Selection sort） 遍历找到当前最小数，移动至最前，后从第二个继续循环该遍历，直到最后一个数字。算法时间复杂度为 ，指数级增长，效率较低。 ![选择排序](/files/CUOdUaGScCNl6Y2NOp2L) ## 2.4.3 归并排序（merge sort） 若数组大小大于 1，则将数组对半分割，直至单个数组个数为 1（示例中）。接着从首个开始两两对比每组中第一个数字的大小，归并为 \* 2 个组，循环重复。 算法时间复杂度为 ，n 为比较 + 合并的次数（与输入成正比），log n 是合并步骤的次数（重复对半切是和输入呈对数关系）。 ## 2.4.4 Dijkstra 算法 Dijkstra 是一种图搜索（graph search）算法，图由节点（node）和边（line）相连构成，点到点之间的代价称为成本（cost）或是权重（weight）。 若要计算任意某两点之间的最小代价路线，最简单的蛮力法是尝试每一条路计算总成本，时间复杂度为 ，阶乘量级是最糟糕的。 Dijkstra 算法是 Edsger Dijkstra 发明与 1956 年构思的算法，其[基本思想如下](https://www.bilibili.com/video/BV1EW411u7th?t=492.9\&p=13)：总是从代价最低的节点开始，运行一次后得知相邻节点的代价；再从相邻节点中的最小节点开始向前计算相邻节点的邻居的代价，更新该值，接着计算相邻节点中的第二小节点向前一步的代价，若相邻节点的同一邻居计算结果再次计算时比原值更小，则更新。 1956 年初始版本的 Dijkstra 算法的时间复杂度是 ，经改进后为 ，其中 n 为节点数，l 为边数。 # 2.5 数据结构（Data Structures） 数据结构是用于表示算法所处理的数据在内存中存储的格式，当数据是结构化的，会更便于读取。 不同的数据结构有不同的特性，适用于不同的场景,正确选择数据结构会让工作更为简单。 大多数编程语言自带了预先做好的数据结构，比如 C++ 中的「标准模板库」（Standard Template Library）和 Java 中的「Java 类库」（Java Class Library）。 ## 2.5.1 数组（Array） ### 数组 数组又名列表（list）或是向量（Vector），其连续存储在内存中，可存储多个值。 数组中不同值使用下标（index）区分，下标从 0 开始，使用方括号 \[ ] 表示所访问数组的数值。e.g 数组 j 的第一个元素为 j\[0]，第三个元素为 j\[2]。 本质上是通过计算第一个元素地址的**偏移量**，来得到数组中其他元素的地址。注意区分数组中第 5 个数字和数组中下标为 5 的数，前者下标为 4，后者实际为第六个数。 数组用途广泛，几乎所有的编程语言都自带了很多函数来处理数据，比如数组排序函数。 ### 字符串 字符串（string）是由字母、数字、标点等组成的数组，以二进制值 \0 （null）结尾。处理字符串的常见函数有 strcat，其接受两个数组，将第二个放在第一个结尾处。 ### 矩阵 数组仅能操作一维数据，二维及以上数据需要使用**矩阵（Matrix）**。以二维矩阵为例，取值需要 2 个下标，如 j\[2]\[1] : ![矩阵](/files/lHggkm7L1tqN6NTqDB5E) ## 2.5.2 结构体（struct） 结构体是指将几个逻辑上有关系的变量打包在一起的结构，比如将银行卡和余额打包在一个称为一个结构体放入数组中。 但数组创建时则大小固定，无法动态增加，同时其按序排列，在中间插入某值需移动后续诸多值，着实不便。因而可以使用结构体建立新的数据结构消除相关限制。 ## 2.5.3 链表 通常采用名为 node 的结构体构建，节点（node）是变量（variable）和指针（pointer）构成的结构体，指针是指向一个内存地址的特殊变量。 ![node](/files/jgdkDiEmgdbZxxCL3Kun) ### 单链表（linked list） 多个节点可以组成链表（linked list），通过链表中的每个节点指向下一个节点来实现灵活性。下图所示为「循环链表」（circular linked），若最后一个指针为 0(null)，则为非循环列表。 链表的大小可以动态增减，插入也比数组更加容易，只需改变指针即可（如下图）。在链表中，重新排序、两端缩减、分割以及倒序等操作也很容易进行。 ![链表插入](/files/2JTRPeltqkkpBGQRB2MB) ### 队列（queue） 一种可以使用链表构建的复杂数据结构，采用「先进先出」（First-In First-Out, FIFO）的原则。 处理完一个数据则可以其「出队」（dequeue），将数据加入队列则称为「入队」（enqueue）。入队需要遍历整个链表直至结尾，然后将原先结尾节点的指针指向要加入的节点。 ### 栈（stacks） 栈是一种「后进先出」（Last-In First-Out, LIFO）的数据结构，类似于放羽毛球进筒里。栈中数据的出入称为「进栈」（push）和「出栈」（pop）。 ## 2.5.4 树（tree） 在 node 的基础上再新增一个指针可以构造出树： ![树的结构体](/files/jgYJcRbzqBDkcMqkTL7A) 抽象来看，可以将最高的节点称为「根节点」（root），节点下的所有节点称为「子节点」（children），任何子节点的直属上层节点称为「父节点」（parent node），没有任何子节点的节点（i.e. 树结束的地方）叫做「叶节点」（leaf）。 ![树](/files/Bds1A9D7ozUUoeOLptXS) 上图这种每个节点最多只有两个节点的树称为「二叉树」（binary tree），这是一种特殊的树。树的节点个数是任意的，甚至我们可以在 node 中使用链表来存储所有的子节点。 树的特性是从根到叶是单向进行，而非循环。若数据随意连接，则构成 2.4.4 节中提过的图（graph），图的指向任意，可以使用多个指针的 node 来表示。 # 2.6 阿兰·图灵（Alan Turing） 阿兰·马蒂森·图灵（Alan Mathison Turing）于 1921 年出生在伦敦，从小表现出惊人的数学和科学能力。他对计算机科学的建树始于 1935 年，当时他是剑桥国王学院的硕士生。 ## 2.6.1 丘奇-图灵论题 ### 可判定性问题 可判定性问题（Entscheidungsproblem, 德语）是由德国数学家大卫·希尔伯特提出的问题：「是否存在一种算法，输入正式逻辑语句输出准确的”是”或”否”答案？」，该算法能回答如“是否有一个数大于所有数”之类的数学问题。 1935 年美国数学家阿隆佐·丘奇（Alonzo Church）首次提出解决方法，其开发了名为「Lambda 算子」（Lambda Calculus）的数学表达系统，证明了该算法不存在。该系统能表示任何计算，但其使用的数学技巧难以理解和使用。 与此同时，阿兰·图灵也提出了一种现在名为「图灵机」（Turing Machine）的假想计算机，其计算能力与 Lambda 算子一致但更为简单，因此在新兴的计算机领域更加受欢迎。 ### 图灵机 ![图灵机](/files/nmNZ1FffOK1UO2ZhLsE4) 图灵机 图灵机是一台理论计算设备，由如下部件组成： 1. 纸带：无限长，用于存储符号。 2. 读写头：位于纸带上，可以读取和写入纸带上的符号。 3. 状态变量：用于保存当前变量。 4. 规则：用于描述机器做什么；根据当前状态和读写头中的符号来决定机器的执行 -> 写入符号 or 改变状态 or 移动一格读写头 or 动作组合。 使用图灵机需要定义起始状态和规则，具体示例[参见视频](https://www.bilibili.com/video/BV1EW411u7th?t=154.5\&p=15)。该机器是一台通用计算机，如果有足够的时间和内存（纸带）可以利用规则和状态执行任何计算，这是一个很强大的理论模型。 ### 图灵完备 图灵完备（Turing Completeness）是针对一套数据操作规则而言的概念。数据操作规则可以是一门编程语言，也可以是计算机里具体实现了的指令集。当这套规侧可以实现图灵机模型里的全部功能时，就称它具有图灵完备性。（cr.[知乎 @RanC](https://www.zhihu.com/question/20115374/answer/288346717)） ### 停机问题 停机问题（Halt problem）是指“给定图灵机描述和输入纸带，是否有算法确定机器会永远计算下去，还是会在某一点停机？”，图灵证明了其无法解决，推理如下： ![停机问题](/files/2DLrZzPN5tjQHoKaOqb7) 1. 假想图灵机 H：输入“问题描述 + 纸带数据”，输出 Yes 表示会停机，输出 No 表示不会。 2. 假想图灵机 -H：H 的输出为 Yes，则 -H 的输出为不会停机；H 的输出为 No，则 -H 的输出为会停机。 3. 将 H 和 -H 组成机器，并添加分离器（splitter）使得其只接收一个输入（程序），名为「Bizzaro」(异魔)。 将 Bizzaro 的描述作为其输入（问 H 说当 Bizzaro 的输入是 H 时会如何），则出现悖论： * H 说 Bizzaro 会停机，则通过 -H 进入无限循环。 * H 说 Bizzaro 不会停机，则输出 No 通过 -H 停机。 图灵证明了有个程序使得图灵机 H 无法判断是否会停机，意味着“停机问题”无法用图灵机解决。 ### 可计算性理论 丘奇和图灵对可判定性问题的解答证明了计算机的能力是有极限的，无论有多少的时间或内存，有些问题是计算机无法解决的。 这种对可计算性理论（formalize computability）的讨论，称为「丘奇-图灵论题」（Church-Turing Thesis）。 ## 2.6.2 破译英格玛机 从 1936 年至 1938 年，图灵在丘奇的指导下拿到了普林斯顿的博士学位，毕业后回到剑桥。 再之后，图灵加入了英国政府的密码破译组织。1939 年前后，英国卷入第二次世界大战，图灵的才能被投入战争，其工作内容之一是破解德国的通信加密。 在 1.2.3 节我们在讨论巨人一号时，曾提及图灵在该计算机安装地——英国布莱切利园（Bletchley Park）——制作了 Bombe，一种用于破译纳粹英格玛（Nazi Enigma codes）的机电设备。 英格玛机（Enigma Machine）是一种用于加密（Encryption）明文的设备，加密由机器顶部有 26 齿的齿轮组合决定，机器前还有用于互换两字母的插板，总共有上十亿种可能（具体可参见 4.6.1 节）。 Bombe 是图灵在波兰破译专家成果的基础上设计的，其利用了英格玛机的缺陷——字母加密后绝不会是字母自己本身，减少了对加密信息尝试组合的搜索数量。 德国人时不时会升级英格玛机（e.g. 加个齿轮），图灵和他的同事们则努力破解加密。这些解密得到的情报为盟军赢得了许多优势，有些史学家认为他们将战争缩短了好几年。 ## 2.6.3 图灵测试 战后图灵回到学术界，为早期计算机工作做出贡献，如曼彻斯特 1 号（早期的存储程序计算机）以及人工智能（Aritificial Intelligence, 1956 年被正式命名，见后）。 1950 年，图灵设想了未来计算机能够拥有和人类一样的智力，或至少难以区分。他提出“若计算机能够欺骗人类相信它是人类，才能算是智能”，这成为智能测试的基础，成为「图灵测试」（Turing Test）。 图灵测试的现代版本称为「公开全自动图灵测试」（a completely automated public Turing Test），用于区分计算机和人类，即常见的「验证码」（Captcha）。 同时，计算机领域的最高奖项「图灵奖」（Turing Award）也以图灵的名字命名。 # 2.7 软件工程（Software Engineering） ## 2.7.1 对象 2.3.4 节中提及的「函数」仍然无法应对超大数量级的代码，比如微软的 Office 有共计 4kw 行代码，全抽象成函数少说也有几十万个。 解决方法是将函数打包成新的层级，将相关的函数代码归为一类，打包成为「对象」（objects）。 比如汽车软件和定速巡航有关的函数，像是设定速度、逐渐加速减速、定制定速巡航等，都可以打包为“定速巡航对象”。程序员在使用时，通过最外层的层级逐次往下找：Car. Engine. CruiseControl. setCruiseSpeed(550)。 ## 2.7.2 面向对象编程 将函数打包成为对象的思想称为「面向对象编程」（Object-Oriented, OO），常见的 OO 语言有 Python 和 Java。其本质在于通过封装组件来隐藏复杂度，就像之前把晶体管打包成了逻辑门，很适合大型工程。 一类软件中介为另一类软件中介提供服务的方式，是通过「程序编程接口」（Application Programming Interface, API）实现，使用文档（documentation）可以辅助帮助其他人理解代码的作用。 API 可以控制函数和数据的访问权限，确保安全。若函数被标记为 public，则其他对象可以顺利调用（call）它；若函数被标记为 private，则只有同一个对象内的其他函数可以调用它。 ## 2.7.3 IDE 集成开发环境（Integrated Development Environments, IDE）是指集成了写代码、编译、测试、调试（debug）、实时检查、高亮代码等功能的专门工具，例如 VIM。 大多数程序员会耗费 70%\~80% 的时间用于 debug，好的工具能够帮助程序员防止错误和解决错误。 ## 2.7.4 文档与注释 文档（documentation）是用于对代码的解释说明，通常命名为「README」来告诉其他程序员看代码前先看这个文件。 文档还有助于开发者在几个月后理解自己的代码，同时能够提高复用性，更好地利用其他程序员写好的东西来解决问题，而不是自己造轮子。 注释（comments）同样是解释代码的，只不过是放在源代码中使用特殊标记注明。编译器在编译代码时，会忽略注释，其唯一作用是帮助开发者理解代码。 ## 2.7.5 版本控制 源代码管理（Source Control）又名版本控制（Revision Control）。大型软件公司会把会把代码放到一个中心服务器上，称为「代码仓库」（code repository）。 程序员可以从代码仓库中把想修改的代码借出（check out），该操作可以在 IDE 中完成。修改测试后再提交（commit）回代码仓库。当某段代码被 check out，且可能被修改过时，其他开发者不会动这段代码，防止冲突和重复劳动，有助于分工协作。 代码的主版本（master）应编译正常且尽可能少 bug，若其出现问题则可以回滚（rolled back）到之前的稳定版（stable version）。这经由版本控制管理实现，其跟踪了所有变化，也记录了谁修改了什么代码。 ## 2.7.6 质量保证测试 质量保证测试（Quality Assurance testing, QA）是指个人或团队严格测试软件的方方面面，模拟各种可能情况，试验软件是否出错（找 bug）。 较为粗糙版本称为 alpha 版，是 beta 版的前身，通常只在公司内部测试。软件接近完成但没有 100% 测试过的版本称为 beta 版，有时会向公众发布进行测试。 # 3 操作系统 对应视频分 P 为 p18\~27。 # 3.1 操作系统（Operating Systems） ## 3.1.1 操作系统简史 ![OS 简史](/files/1flMwJYyWMEfO7BZ20Fn) ## 3.1.2 OS 特性 ### 多任务处理（multitasking） 在运行 I/O 相关程序等待调用相关外部设备时，先将程序休眠运行另一个程序，等待 I/O 操作结束后标记为“可继续运行”，在之后某时刻安排给 CPU 执行，实现多个程序的同时运行，在单个 CPU 上共享时间。 ### 内存管理（Memory Allocation） 多任务处理使得每个程序都会占用一些内存，为保证切换程序时相关数据不丢失，我们可以为每个程序分配专属内存块。 当某个程序需要更多内存，则继续向操作系统请求。OS 会决定是否同意分配、分配哪些内存块。这导致程序所分配到的内存可能是非连续的，程序员难以跟踪使用，因此 OS 会将内存地址虚拟化（virtualize），称为「虚拟内存」（Virtual Memory）。 使用虚拟内存后，OS 会自动处理虚拟内存和物理内存之间的映射，程序可以假定自己所分配到的内存总是从地址 0 开始。 ![memory allocation](/files/mIQjD2thrgW8Cq1QDggE) 以程序 A 和 B为例：B 分配到的内存地址是 1000 到 1999，但对于程序而言，它所看到的地址是 0\~999；而对于程序 A 而言，第二次请求分配后，它有了 2000 个连续地址的内存，但实际上第二次分配的物理地址是 2000\~2999。 ### 受保护内存（Memory Protection） 为不同程序分块分配专属内存范围，将其各自隔离同时也可以实现对内存的保护，在防止恶意软件（如病毒）入侵时很有帮助，这样带病毒的程序只会损害自己的内存。 # 3.2 内存 & 储存介质（Memory & Storage） ## 3.2.1 存储器（storage） 1.6 小节设计的 RAM 是一种易失性存储器(volatile memory)，一般来说电脑的内存是非永久性的（non-permanent），断电后数据会丢失。 存储器是一种非易失性（non-volatile）的存储介质，断电不会丢失，直到数据被删除或覆盖。 在以前“易失性”的速度快，“非易失性”的速度慢，但随着技术发展两者差异逐渐缩小。 ## 3.2.2 存储介质发展 ![存储](/files/vrpr4II33ZZjLQGLzFyW) # 3.3 文件系统（Files & File Systems） ## 3.3.1 文件格式（file format） 文件的底层均为二进制 0 和 1，需要用格式明确如何解释这些 0 和 1，同时也便于进行文件管理。文件格式可以自行发明，但最好使用现有的通用标准。以下三种为常见格式： ### 文本文件（txt file） 一种纯文本格式，后缀为 .txt，需配合 ASCII 编码或其他字符标准编码进行解码数字。 ### 波形文件（WAVE File） 用于存储音频数据，后缀为 .wav，其在文件开头存储「元数据」（metadata）——用于说明关于数据的信息，例如码率（bit rate）、声道数、立体声等。 因元数据存储于文件开头，后接实际数据，故又名文件头（Header），下图为 WAVE 格式的前 44 个字节（以及数据 DATA）： ![元数据](/files/ehhLh5ovfrVzUG6GGiQ2) DATA 中也存储着数字，表示每秒捕获了多少次的声音幅度。麦克风可以对声音进行上千次采样，录制好的采样可以用一个数字表示，声压越高数字也越大，这也称为「振幅」（amplitude）。 ![振幅](/files/GsiRfjgCb5RAFoEvrzmy) 在播放时，扬声器会产生与之相同的波形。 ### 位图（Bitmap） 位图用于存储图片，后缀为 .bmp，其文件开头也是元数据，用于说明图片宽度、高度、颜色深度等信息。 计算机中的图片由「像素」（pixels）组成，单个像素又是由红、绿、蓝这三种加色原色/三基色 (additive primary colors) 组成。 ![位图](/files/0w1joBjuyQSyKcrrFkCH) 上图示例为 4×4 像素大小的位图，颜色深度为 24 位——8 位（1 字节）红色，8 位 绿色和 8 位蓝色。 元数据后的 3 个字节解释为第一个像素点的 RGB 值，即 255，255，255 白色，以此类推。解释好 4×3 = 12 个字节后换行，因为元数据中说明了宽度，然后接着往下解释。 ## 3.3.2 文件目录（Directory File） 早期的磁带、磁鼓、磁盘或是集成电路，通过软硬件抽象后可以当作一个“支持存储数据的桶”，桶里基本就只存一个数据的一整个文件，从头到尾直至存满所有数据。 后来随着计算机的计算能力提高和存储容量的提高，开始将文件进行连续存储（back-to-back），因桶里只是存储大量位，故需要用一个特殊文件来记录其他文件的位置。这种特殊文件泛称为「文件目录」（Directory File），通常放置在存储器（ storage）最开头的位置 0 处。 文件目录中存储着其他文件的名字、创建时间、最后修改时间、文件所有者、读写权限以及最重要的文件起始位置和长度。在增删文件或是进行更改文件名等操作时，必须修改目录文件。 ![文件目录](/files/cqEpInRcWdeSCJ6j0lJd) ## 3.3.3 平面文件系统（Flat File System） 文件均位于同一个目录层次的文件管理系统，在文件连续存储的情况下，前一个文件数据的增加会覆盖掉后一个文件。 现代文件系统会将存储空间分块后，将文件拆分存储在多块里，类似于 3.1.2 节中的虚拟内存。分块后会有一些预留空间（slack space），方便文件的改动与管理，因此目录中也要记录文件在哪些块里。 数据的删除仅在目录文件中删掉文件存储在某块中的记录，使得可用空间增加，但不意味着存储空间内的数据已经被擦除或覆盖，因此存在恢复的可能。 因文件并非完整存储，而是分散在切割好的块里，因此文件的增删改会带来「碎片」（fragmentation），块之间的跳转读取对于许多存储技术来说十分不便，因此计算机会通过「碎片整理」（defragmentation）来移动数据排列成正确顺序。 ## 3.3.4 分层文件系统（Hierarchical File System） 文件数量的增多迫使文件需要层次化管理，用文件夹多层嵌套管理文件的方式称为「分层文件系统」（Hierarchical File System），目录文件不仅要指向文件，还要指向其他目录文件。 比如最顶层的根目录（Root Directory）存储着其他文件和文件夹，若要读取其中的子文件夹，必须读取其目录文件。在移动文件至不同文件夹时，只需要修改两个文件夹的目录文件记录，文件的物理存储位置无需改变。 # 3.4 压缩（Compression） ## 3.4.1 游程编码（Run-Length Encoding） 游程编码（Run-Length Encoding）适用于经常出现重复值的文件中，比如下图中有 7 个连续黄色像素，可以插入额外的字节表示有连续 7 个黄色像素，接着删除重复数据。 ![游程编码](/files/p2RSfvTVEeEZCGyI2MMo) 但需要为了能让计算机分辨出“长度”和“字节”，所以需要为所有不同颜色的像素标上长度，有时反而会使得数据量变多。 ## 3.4.2 DFTBA DFTBA 有点像“Don’t forget to be awesome”（别忘了变厉害）的缩写，使用字典（dictionary）来存储代码和数据之间的对应关系，使得数据的表示更为紧凑，同样是无损压缩。 首先将数据分块计算组合出现的频率，使用「霍夫曼树」（Huffman Tree）进行编码——由大卫·霍夫曼（David Huffman）发明于 1950s，具体步骤如下： 列出所有分块组合以及其出现频率，每轮选中最低的两个频率组成一个树的节点，重复组成最终的霍夫曼树。其特点在于出现频率最低的排列在树的最底端，数字也越大。 ![DFTBA](/files/NWIZoxymgdgZrpsYrcrD) 根据霍夫曼树对分块组合进行编码，因树的每条路径唯一，所以编码也不会有冲突。接着根据组合的对应将像素数据替换成相应的 code，如将两个黄色的像素替换为 00。同时将保存对应关系的字典也存储在编码数据前即可。 ![字典编码](/files/nOQneihVGNHLx1ZaFZ0X) ## 3.4.3 有损压缩 解压前后数据完全一致的压缩方法，称为「无损压缩」（lossless compression）。常常组合使用“消除冗余”和“使用更紧凑的表示方式”两者压缩方法来实现，如 GIF, PNG, PDF, ZIP 。 在一些人类看不出区别的时候，使用有损压缩（lossy compression）会更有效率。比如人类无法听到超声波数据，其对人声较为敏感，而对低音只能感觉得到震动。音频有损压缩会利用人类这种感知特性，使用不同的精度来编码不同的频段，比如在网络通话时会根据网速来视情况降低声音质量。 这种通过删除人类无法感知到的数据的编码方式，称为「感知编码」（perceptual coding），属于心理物理学（Psychophysics）领域，依赖于人类的感知模型。 与声音类似，人类的视觉系统也更善于看到尖锐对比（比如物体边缘），而对颜色的细微变化无法感知。因此 JPEG 会利用这种特性，将图片分解为 8×8 的像素块后，删除大量人眼无法分辨的高频率空间数据。 视频作为一长串图片的组合，帧和帧之间有很多像素是一致的，这种情况称为「时间冗余」（temporal redundancy）。 在存储视频时，有些视频编码格式会利用这种相似性，只存储帧与帧之间变化了的部分。更高级些的编码格式——比如视频压缩的常见标准 MPEG-4 ，会找出帧和帧之间变化部分中相似的补丁（patches），然后用简单效果（如移动、旋转等）来实现这种变化。比如用一些补丁代表 up 主手的移动，然后在帧之间直接移动补丁。 但随之而来的问题是，当压缩过于严重时，没有足够空间来更新补丁内的像素，但播放器也依然会照常播放，画面就会错乱。 # 3.5 人机交互（Human Computer Interaction） 「人机交互」（Human-Computer Interaction）是一门研究人类和机器直接进行交互的学科，各种 I/O 设备都提供了界面（interface）以供使用，这对于用户体验（user experience）来说非常重要。 ## 3.5.1 发展简史 ![人机交互](/files/oa5lE3xe5EtRTHUOHQG5) ## 3.5.2 键盘（Keyboards） ### QWERTY 现代打字机是克里斯托弗·莱瑟姆·肖尔斯（Christopher Latham Sholes）在 1868 年发明的，1874 年才完成设计和制造。其使用了一种 QWERTY 的键盘布局，因其取得商业成功所以其他公司开始抄这种设计。 采用这种布局的方式据说是为了把常见字母放得远一些来避免按键卡住，但实际上它把很多常见的字母（比如 th 和 er ）放在了一起，所以这个原因可能是错的或是不够全面。 尽管有许多新的键盘布局被发明并且声称有各种好处，但也许是出于经济学家所说的转换成本（switching barrier），熟悉了 QWERTY 布局的人们并不想学习新的键盘布局。 尽管在一个多世纪后 QWERTY 的地位依旧不可撼动，但其并非完全通用。现在仍然存在许多变体，比如法国的 AZWETY 布局以及中欧常见的 QWERTZ 布局。 ### 十指盲打 打字机最初的发明是为了易读性和文件标准化，而非速度的提升。肖尔斯甚至没想到打字会比手写更快，手写速度大约是每分钟 20 个字母。但随着打字机称为办公室标配，快速打字的需求也渐起。 1880 年，伊丽莎白·朗利（Elizabeth Longley）开始推广十指打字。1888 年，弗兰克·爱德华·麦克林格（Frank Edward McGurrin）学会十指盲打后赢得了备受关注的打字速度比赛后，十指盲打开始流行。专业打字员可以实现每分钟 100 字以上的速度，比手写快得多。 ### 电传打字机 电传打字机（teletype machine）是一种经强化后可以用电报线发送以及接收文本的打字机，按下字母后信号会通过电报线使得另一端的电传打字机将字母打出，使得两人可以长距离沟通。 ## 3.5.3 命令行界面（Command Line Interfaces） 使用简单的文字命令实现和电脑的交互界面，称为「 命令行界面」（Command Line Interfaces），其常见命令如下： * ls: list 的缩写，列出当前目录里的所有文件 * cat: concatenate 的缩写，在 unix 中显示文件内容，需要在命令后传递「参数」（argument）来指定文件名。 * finger: 寻找同一个网络中的其他人。 1970 年代，因针对普通消费者的电视机开始量产，同时处理器和内存也在大战，最早出现在 1950s 的屏幕开始代替电传打字机。出于方便，工程师们直接将现有的电传打字机协议套用在了屏幕上，这些“虚拟电传打字机”最终演化成了我们熟知的「终端」（terminals）。 在 1970s 末，屏幕成了标配。1977 年早期最著名的交互式文字游戏 Zork 出现了，其原始版本只有 66 个可供探索的地方，但仍被广泛地认为是最早的互动式小说。 后来由纯文字的游戏演变出了多人游戏（Multi-User Dungeons, MUD），以及如今的 MMORPG(massive, multiplayer online role-playing games)。 如今大多数程序员的工作中依然在使用命令行界面，且用命令行访问远程计算机是最常见的方式。在 Windows 上输入 cmd 或是在 Mac 上搜 Terminal 均可使用命令行界面。 # 3.6 屏幕 & 2D 图形显示 Screens & 2D Graphics 1960s 的 PDP-1 的电脑、屏幕、电传打字机是分开的，因为早期的文本任务和图形任务是分开的。早期的屏幕无法显示清晰的文字，打印到纸上会有更高的对比度和分辨率。 ![PDP-1](/files/VtfBadZUm4sm616pCOd7) 屏幕早期的典型用途是跟踪程序运行的情况，显示寄存器中临时存储的值等。此时屏幕还很少用于输出计算结果，其会打印到纸上或是更永久的媒介中。 ## 3.6.1 阴射射线管（CRT） 阴射射线管（Cathode Ray Tubes, CRT）的原理是将电子发射到有磷光体图层的屏幕上，当带电粒子的电子撞击图层时，其会发光几分之一秒。 ![CRT](/files/3NUp9qhN1rVMQ5aN9xD2) 而电子的撞击路径可以通过磁场控制，在屏幕内使用线圈或是板子引导电子即可，主要有两种绘制图形的方式： 1. 矢量扫描（Vector Scanning）: 引导电子束描绘出形状，就算发光只持续一小会，但只要重复得够快，就可以得到清晰图像。 2. 光栅扫描（Raster Scanning）: 按照固定路径逐行从上向下、从左到右地不断重复，只在某行特定点打开电子束，从而绘制图形。 液晶显示器（Liquid Crystal Display, LCD）可以显示清晰的像素点，其使用光栅扫描，每秒更新多次单个像素中红绿蓝的颜色，但早期计算机因像素占用太多内存而弃用。 ## 3.6.2 字符生成器 字符生成器（character generator）基本算是第一代显卡，是一种用于从内存中读取字符转换为光栅图形的硬件。 为了节约内存，早期计算机不存储大量像素值，而是存储最典型的 80×25 = 2000 个符号。在字符生成器中的内部 ROM (Read-Only Memory, 只读程序存储器) 中，存储着每个符号的图形，称为「点阵图案」（dot matrix pattern）。 当某 8 位二进制被解读为字符，则会将字母生成器中的点阵图案写进计算机内存中的特殊区域——「屏幕缓冲区」（screen buffer）。程序在显示文字时，修改这个区域里的值即可。 扩展后的 ASCII（比如 IBM CP437 字符集）再加上某些可以用额外比特定义字体颜色和背景颜色的系统，可以实现用字符模仿图形界面，比如 DOS。 ![DOS](/files/O9SGXqGxxkHb4YylC1rV) ## 3.6.3 矢量模式（vector mode） 矢量模式（vector mode）使用矢量指令绘制出线条来组成所有东西，比如早期的矢量系统 Vectrex，使用笛卡尔坐标系来标注电子枪的绘图点，修改相应强度。 ![矢量模式](/files/SDK6lcD7yCxSrJBEGWUR) 这些矢量模式的命令可以按序存储在屏幕缓冲区中被读取，程序可以随时间更新这些值做出动画效果。 最早的电子游戏之一 Spacewar 是 1962 年在 PDP-1 上使用矢量图形制作的。其启发了许多后来的游戏，比如《爆破彗星》（Asteroids），甚至是第一个商业游戏《太空大战》（Computer Space）。 ## 3.6.4 Sketchpad 1962 年，Sketchpad 出于计算机辅助设计（Computer-Aided Design, CAD）的愿景制作出了交互式图形程序（interactive graphical applications）。Sketchpad 被广泛认为是第一个完整的图形程序，其发明人伊万·萨瑟兰（Ivan Sutherland）后来因此获得图灵奖。 Sketchpad 代表着人机交互的关键点，改变了人们对电脑的观念。电脑不仅可以用于计算，还能够帮助人们进行设计或其他事情。 Sketchpad 提供了光笔和各种按钮来使用户可以划线和其他简单形状。光笔的笔尖使用光线传感器，其通过检测判断显示器刷新时间来让电脑知道笔的位置。 在 Sketchpad 上绘制的线可以完美平行、长度相同、正交垂直、动态缩放，实现保存复用和修改，并且提供了图库可以直接拖拽使用。 ## 3.6.5 位图显示（bitmapped displays） 位图显示（bitmapped displays）是指内存中的位（bit）可以对应屏幕上的像素。 绘制任意图形，就像是在修改一个巨大像素值矩阵中的值，这些像素数据存在帧缓冲区（frams buffer）。该区域早期位于电脑内存（computer’s RAM）中，现在存储在高速视频缓存（high-speed Video RAM, VRAM）中。 在 8 位灰度屏幕上，可用的颜色范围为 0（黑）到 255（白）。白色会更偏向绿色或橙色，因为早期显示器不能显示白色。假设低分辨率的位图屏幕分辨率为 60×35，则可以根据坐标系定位像素后把其设为不同颜色。 ![VRAM](/files/y1DQvYxQAXyx5FWEpR2v) 这种绘制矩形的代码也可以包装成函数进行复用，还有其他绘制直线、曲线、图形、文字等内容的函数可以调用。 这种位图的灵活性为交互式操作开启了全新可能，但其成本高昂直至几十年后才有所降低。1971 年，整个美国只有 7w 电传打字机和 7w 终端，而拥有交互式图形屏幕的电脑大约只有 1000 台。 # 3.7 冷战和消费主义（The Cold War and Consumerism） 1940\~1970 年代计算机在短短三十年间经历了巨变，这是由政府和消费者两方推动的。 政府资金推动了计算机的早期研究发展，使得计算机行业有时间等待技术成熟到可以商用，公司、消费者进而将计算机变成了主流，其发展简史如下： ![冷战和消费主义](/files/mKWSOnlnufGgGgEpoesJ) # 3.8 个人计算机革命（The Personal Computer Revolution） ## 3.8.1 微型计算机 相较于那个时代放在公司或大学中的“普通”（normal）计算机，1970s 出现了「微型计算机」（microcomputer），它的出现源于以下因素： 1. 强大、体积小、便宜的单芯片 CPU 2. 集成电路（IC）的进步，可用于充当 RAM/ROM 的低成本固态存储器的出现 3. 磁带和软盘等便宜可靠的存储介质 4. 用电视机稍作改装而成的低成本显示器 ## 3.8.2 Altair 8800 个人计算机出现的准确时间节点难以定义，“第一台个人计算机”的名号存在争议，如 Kenback-1 或 MCM/70。但第一台取得商业成功的个人计算机，通常认为是 Altair 8800。 Altair 8800 是 1975 年亮相于《Popular Electronics》中售价 $439 美元（约为如今的 2k 美元）的个人计算机，由 MITS 公司制造，需要自行组装。组件包相关的产品有内存、纸带读取器，甚至是电传接口——用于从纸带上读取更复杂的程序后，使用电传终端交互。 ## 3.8.3 BASIC 解释器 因 Altair 8800 的程序仍然需要使用机器码写，比尔·盖茨（Bill Gates）和保罗·艾伦 （Paul Allen）为能在 Altair 8800 上运行 BASIC 程序（BASIC 是一门更简单更受欢迎的程序语言），需要一门能将 BASIC 代码转化为可执行机器码的程序，名为「解释器」（interpreter）。 类似于编译器，解释器是在运行时进行转化，而编译器是提前转化。MITS 公司同意他俩试试。 两人在飞机上赶工完成后在总部进行演示时才知道代码可行，但一切进展顺利，MITS 允许该软件在 Altair 8800 上搭载，于是 Altair BASIC 称为微软的第一个产品。 ## 3.8.4 Apple-I Altair 8800 的出现催生出了大量的计算机爱好者，其中最具有传奇色彩的计算机爱好小组是「家酿计算机俱乐部」（the Homebrew Computer Club）。 该小组的第一次聚会在 1975 年 3 月，组织观看第一批运来加州的 Altair 8800 。在这次聚会上，24 岁的斯蒂芬·沃兹尼克（Steve Wozniak）被 Altair 8800 激励开始设想自己的计算机。 1976 年 5 月，斯蒂芬·沃兹尼克向小组成员展示了原型机并分享了电路图，在他的设计中电脑需要连接到电视中显示并且提供了文本界面，这在低成本计算机中十分罕见。 同为小组成员的史蒂夫·乔布斯（Steve Jobs）建议：与其免费分享设计，不如直接出售组装好的主板。但用户仍然需要自行配装键盘、电源以及机箱。 于是苹果公司的第一个产品 Apple-I 于 1976 年 7 月以 $666.66 美元的价格进行发售。 ## 3.8.5 the 1977 Trinity Apple-I 这样自行组装的计算机吸引了爱好者们，但个人消费者和公司却对其不太感冒。 1977 年，市场上出现了 3 款开箱即用的计算机，称为 1977 年的“三位一体”（the 1977 Trinity）： 1. Apple-II：苹果公司提供的第一个有全套设备的产品，其提供了简单色彩图形和声音输出，于低成本机器而言十分了得。Apple-II 卖出上百万套，苹果公司由此成为计算机行业的前沿。 2. TRS-80：由 Tandy 公司生产，由 Radios hack 销售，故有此名。不如 Apple-II 先进，但价格只有其一半，销售量可观。 3. Commodore PET 2001：采用集成了计算机、显示器、键盘和磁带驱动器的一体化设计，目标在于吸引普通消费者。 the 1977 Trinity 均自带 BASIC 解释器，使得不那么精通计算机的人也可以使用 BASIC 写程序，由此带来面向消费者的软件行业开始腾飞，出现针对个人计算机的游戏和生产力工具，像是计算器、文字处理器等。 最热门应用（killer app）是 1979 年的 VisiCalc ，其是第一个电子表格程序，是微软 Excel 和 Google Sheets 的老祖先。 ## 3.8.6 IBM PC the 1977 Trinity 将计算机大规模地带入了家庭、小公司以及学校里，这引起了 IBM 的注意，因忽略不断增长的微型计算机市场，其市场份额从 1970 年的 60% 下降到了 30% 左右。 1980 年，IBM 最便宜的计算机 5120 的价格约为 1w 美元，无法与 Apple-II 这样的产品竞争，IBM 需要另辟蹊径。其派遣了十二名工程师（后称为“肮脏十二人”，the dirty dozen）进行自由地独立设计，不受公司内部政治斗争干涉。 该团队采用了与 IBM 传统做法不同的方式：自己做硬件来节约成本，而后与其他公司合作。1981 年，他们发布了 IBM 个人计算机，简称 IBM PC。 IBM PC 是自由选择下的产物，而非局限于之前的惯例，其使用了 Intel 的芯片、微软的 MS-DOS 操作系统，最重要的是采用了「开放式架构」（open architecture），拥有良好的文档和扩展槽，使得第三方可以做硬件与外设——包括显卡、声卡、外置硬盘、游戏控制杆等其他组件。 这种名为 IBM Compatible（IBM 兼容）的开放架构刺激了创新、引发了竞争，从而带来了庞大的生态系统。 竞争对手公司可以遵循同样的标准制作出自己的 IBM 兼容计算机，因此 Compaq（康柏）和 Dell（戴尔）也开始售卖 PC，进而使得 DOS 迅速成为最欢迎的 PC 操作系统。 在庞大的潜在用户群的诱惑下，软硬件的开发人员将精力更多地放在了 IBM 兼容平台，而潜在消费者也会考虑哪种计算机的软硬件选择更多，正如雪球效应一样。 ## 3.8.7 Macintosh 在一众性能更好但非 IBM 兼容计算机的公司中，只有苹果公司保持着足够的市场份额。苹果公司最终采用了完全相反的方式——「封闭架构」（closed architecture），用户通常无法加新硬件进计算机，通过控制软硬件来提高用户体验与可靠性。 IBM 和苹果这种不同的商业策略是“MAC vs. PC，谁更好”这种争论的起源，但严格意义上来说这个用词并不准确，因为两者均为 Personal Computers。 为了能在低成本个人计算机的竞争中存活下来，苹果需要提供比 PC 和 DOS 更好的用户体验，因此他们于 1984 年发布了 Macintosh，一台提供了图形界面的一体式计算机（带有鼠标），极具突破性且价格适中。 # 3.9 图形用户界面（Graphical User Interfaces） ## 3.9.1 增强人类智力（Augmenting Human Intellect） GUI 的先驱是道格拉斯·恩格尔巴特（Douglas Engelbart），他在二战期间阅读了布什（Vannevar Bush）关于 Memex 的文章，深受启发。 服役结束后的 1955 年他在 UCB 取得博士学位，在 1962 年发布了一份名为「增强人类智能」（Augmenting Human Intellect）的开创性报告。 在这份报告中，他认为人类所面临的问题比解决问题的能力增长得更快，因此有必要寻找一种增强智力的方式。其构想计算机不仅完成自动化的工作，也可以成为未来知识型的员工，用以应对复杂问题的工具。 受到伊凡·苏泽兰（Ivan Sutherland）的几何画板（recently demonstrated Sketchpad）的启发，恩格尔巴特决定动手将愿景变为现实。 在这个过程中，恩格尔巴特意识到他需要引入新的外设来完成他所希望搭建的程序。 “We envisioned problem-solvers using computer-aided working stations to augment their efforts.They required the ability to interact with information displays using some sort of device to move (a cursor) around the screen.” “我们设想人们用计算机辅助工作站来增强工作，用户需要和屏幕上的信息互动，用某种设备在屏幕上移动（光标）。 1964 年，恩格尔巴特和比尔·英格利希（Bill English）设计出了第一个计算机鼠标（mouse）。1968 年，他在秋季计算机连联合会议中展示了他的系统 oN-Line System，这次演示被视为所有 demos 的祖先（the mother of all demos）。 在时长为 90min 的演示中，恩格尔巴特展现了现代计算机的许多功能，如位图图像、视频会议、文字处理、实时协作编辑文件等；以及现代图形界面的的原型，如鼠标与多窗口（但窗口无法重叠）。 因构想过于超前，该系统在商业上失败了，但对计算机研究者的影响巨大，恩格尔巴特因此在 1997 年获得图灵奖。 ## 3.9.2 Xerox ### Xerox Alto 因冷战结束，政府资金减少，恩格尔巴特团队中的许多人进入了施乐公司新成立的”帕洛阿尔托研究中心”（Palo Alto Research Center），即 Xerox PARC。 1973 年，他们在这里开发了第一台真正的图形用户界面（Graphical User Interfaces, GUI）计算机——Xerox Alto（施乐奥托）。其特点在于将 2D 的屏幕当作“桌面”（desktop），就像拿起桌面上的文件一样：用户打开多个程序，程序位于单个框内名为窗口（window），窗口可以重叠；同时还提供了桌面配件，比如计算机和时钟，配件可以自由移动。 ### WIMP 界面 Xerox Alto 并非对现实桌面的完美照搬，而是使用桌面这种隐喻，称为「桌面隐喻」（the Desktop Metaphor）。界面的设计可以使用多种方法，而 Alto 团队采用了窗口，图标，菜单和指针来做，因此称为 WIMP 界面（Windows, Icons, Menus, Pointer interface）。 现在大部分的 GUI 都采用 WIMP 界面，同时还提供了一些基本部件和可复用的基本元素，比如按钮，打勾框，滑动条和标签页。 ### 事件驱动编程 之前的实例中，代码均为从上到下依次执行，但在 GUI 中代码可以在任意时间执行以便于响应事件，这称为「事件驱动编程」(even-driven programming)，用户触发事件——点击按钮、选一个菜单项、按下键盘或滚动窗口——后，代码运行。 ### Xerox Star system Xerox Alto 仅制作了 2000 台用于内部使用或是送给大学实验室，但从未进行商业出售。后来 PARC 团队不断完善软硬件后，于 1981 年发布了「施乐之星系统」(Xerox Star system)，该系统扩展了桌面隐喻： * 文件 = 纸，存放于文件夹中，放置于桌面或是数字文件柜里。 * 使用了来自编辑打字机文件中的术语，如剪切、复制、粘贴。 * 提出了现在文字处理软件中常见的“所见即所得”（What-You-See-Is-What-You-Get , WYSIWYG），即无论你在计算机上做什么，文件打印出来应该长得一样。 施乐之星也如同恩格尔巴特的 oN-Line System 一样，因构想超前和售价高昂未能取得商业成功。同年，价格低廉的 IBM PC 席卷市场。 ## 3.9.3 Mac OS 1979 年 12 月，施乐之星出货前一年半，史蒂夫·乔布斯去施乐公司参观。与谣传的苹果偷走创意相反，是施乐公司主动找到苹果希望合作。施乐还在苹果备受瞩目的首次公开募股(IPO) 前购入了苹果 100w 美元股份，其中的一个额外条款是”公布一切施乐研究中心正在进行的酷工作”。 受到 Xerox PARC 在位图显示器上使用鼠标进行直观操作的启发，史蒂夫和随行的工程师继而开发了新功能，比如菜单栏和满了会膨胀的垃圾桶，于 1983 年发布了苹果第一款有 GUI 和鼠标的产品 Apple Lisa，售价约为 2.5w 美元。尽管比起施乐之星更为便宜，但仍然在市场上失败了。 而苹果的另一个项目——于 1984 年发布的 Macintosh，在开售百天卖了 7w 台，大获成功。但随着最初的热潮消退，因软件生态的落后，苹果公司卖的 Apple II 比 Macs 多得多。 后来，其他个人电脑竞争者紧随其后提供了原始但能用的图形界面，价格仅有 Macs 几分之一，消费者和 PC 软件开发者也为之埋单。 随着苹果的财务状况日益严峻，以及和苹果新 CEO 约翰·斯卡利 的关系日益紧张，史蒂夫乔布斯被赶出了苹果公司。 ## 3.9.4 Windows 1984 年 Macintosh 发布的后几个月，微软发布了 Windows 1.0，它也许不如 Mac OS 漂亮，但让微软在市场中站稳脚跟并奠定了统治地位。十年内，95％ 的个人计算机上都有微软的 Windows。 Windows 早期版本都是基于 DOS，其设计时没想过运行图形界面。Windows 3.1 之后，微软推出了面向消费者的 GUI 操作系统 Windows 95。 Windows 95 提供了精美的界面且提供了 Mac OS 没有的多任务和受保护内存，同时还引入了像是开始菜单、任务栏和 windows 文件管理器等现在仍然常见的 GUI 元素。 当然，微软在 Windows 之前也曾推出过 Microsoft Bob 这样基本仿照现实的操作系统，其并没有获得成功。如今存活下来的 GUI——无论是 Windows，Mac，Linux 或其他——几乎都是施乐奥托 WIMP 界面的变化版，这是自然选择后的结果。 # 3.10 3D 图形（3D Graphics） ## 3.10.1 3D 投影（3 Dimensional Projection） 3D 中使用 X,Y,Z 三点构成某点的坐标，因 2D 电脑屏幕无法将三轴立体坐标完美展示，故使用某种图形算法来将 3D 坐标“拍平”（flattening）显示至 2D 屏幕上，这称为「3D 投影」（3 Dimensional Projection）。 所有的点都从 3D 转成 2D 后，就可以用画 2D 线段的函数来连接这些点，称为「线框渲染」（Wireframe Rendering）。 3D 投影有许多类别，最常见的是正交投影（Orthographic Projection）和透视投影（Perspective Projection）： （1）正交投影：立方体的各个边，在投影中互相平行。 ![正交投影](/files/LOE1CbfKQFps53mCU9RG) （2）透视投影：立方体中的平行线段会在远处收敛于某点。 ![透视投影](/files/rSQqtUvPYs1o2eCbwC3t) 两种 3D 投影的过程类似，所使用的数学表达方式不同而已，具体采用哪种取决于开发人员。 ## 3.10.2 填充（filling） ### 多边形(Polygons) 在 3D 图形学中，一般称三角形为「多边形」(Polygons)，这是最常用于构建复杂图形的基本形状，因为它简单——空间中三点定义一个平面。 ![三角形](/files/Ft6ywNMNiT6DHQqNvtKX) 多个多边形构成的集合称为「网格」（mesh），网格越密，表面越光滑，细节越多，同时也带来更多的计算量。 游戏设计者要平衡画面的真实度和多边形数量，如果多边形数量太多，帧率会下降到肉眼可感知，用户会觉得卡顿。 ### 扫描线渲染 (Scanline Rendering) 扫描线渲染 (Scanline Rendering) 是于 1967 年诞生在犹他州大学的经典填充图形算法。 1. 将图形铺上一层像素网格。 ![](/files/uQ1F8HWF8UzqSuWohFdC) 1. 读取多边形的三个点，找最大和最小的 Y 值，只在这两点间工作。 2. 从上往下，一次处理一行。计算每一行和多边 形相交的 2 个点，填满 2 个相交点之间的像素。 3. 重复逐行填充，直至底部，填充的速度叫 fillrate（填充速率）。 ### 画家算法（Painter’s Algorithm） 3D 场景中会因多边形的重叠错落而产生遮挡（occlusion）现象，其最直接的处理方法时使用排序算法，从远到近排列，然后从远到近渲染。因画家也是先画背景，故名画家算法（Painter’s Algorithm）。 （1）从用到近排序，在有序状态下自最远的多边形开始，使用扫描线算法来填充多边形，一次填充一个。 ![](/files/B5QspsOjcUqOTYTmkWh4) （2）重复填充过程即可，注意实际应用中的多边形未必是如示例中一般与屏幕平行。 ![](/files/fMQMAXDUp7cDBABiBylA) ### 深度缓冲（Z-Buffering） 深度缓冲（Z-Buffering）是另一种处理遮挡现象的方式，无需排序，速度更快。这种方法会记录场景中每个像素和摄像机的距离，在内存里存一个数字矩阵。 （1）每个像素的距离被初始化为”无限大”，该算法会从列表里第一个多边形开始处理（即多边形 A），将其距离和 Z-Buffer 中存储的距离进行对比，始终记录更新最小值。 ![](/files/GfV7ICIbCxwTiU06qWrW) （2）按照列表继续向下对比第二个多边形的距离，直至列表结束。因未进行排序，故记录距离的 Z-buffer （缓冲区）中多边形 C 只有一部分值会被覆盖。 ![](/files/cuRR7OGXHrZTPSIRKcsE) （3）标记完 Z-buffer 后，搭配改进后的扫描线算法使用。加强版扫描线算法不仅可以勘测两线交叉点，还可确认某像素是否在最终场景中可见，如果不可见则跳过。 ![](/files/WZ6QyLsMzY9rsxK6v0hl) 在两个多边形距离相同时，采用深度缓冲会使得多边形在内存中不断移动，两者访问顺序的先后会不断变化。再加上浮点数的舍入误差问题，究竟是将哪个多边形画在上方，是无法预测的。因此，这种情况下会导致出现 [Z-fighting 效果](https://youtu.be/TEAtmCYYKZA?list=PL8dPuuaLjXtNlUrzyH5r6jN9ulIgZBpdo\&t=470)。 ### 背面剔除（Back-Face Culling） 为节约处理时间，忽略多边形背面的处理优化方式，称为「背面剔除」（Back-Face Culling）。比如在游戏角色的头部或是地面，只能够看到朝外的那一面，这会带来一个 bug —— 进入模型后从内部向外看，头部和地面会消失。 ## 3.10.3 抗锯齿（Antialiasing ） 上述例子中三角形填充后边缘都是锯齿，当像素较小时锯齿不明显，但用低配电脑玩游戏时，肯定会出现这种情况。一种减轻锯齿的方法叫抗锯齿(Antialiasing)，其通过判断多边形切过像素的程度，来调整填充颜色。 如果像素在多边形内部，就直接涂颜色；如果多边形划过像素，颜色就浅一些。这样抗锯齿的方法可以实现边缘羽化的效果，在字体和图标中广泛使用。 ## 3.10.4 光照（lighting） 光照（lighting）又名明暗处理（shading），在 3D 场景中的物体表面会有明暗变化，添加灯光后会提高物体的真实感。 以茶壶中 3 个不同位置的多边形为例，其不平行与屏幕，各自面对不同方向，该方向称为「表面法线」（Surface Normal），即下图中垂直于表面的箭头方向。

表面法线

因表面法线的角度不同，光线反射到观察者的强度也不同，不同多边形被照亮的程度也不同。根据距离光源的位置对不同多边形进行着色的方法，称为「平面着色」（Flat Shading），这是最基本的照明算法（lighting algorithm）。 ![平面着色](/files/0XTgqGOJgEj3j0aGlBxZ) 但平面着色的方法使得多边形的边界非常明显，看起来不光滑。因此出现了更多算法来更巧妙地改变颜色、得到更好地效果，比如高洛德着色（Gouraud Shading）和 冯氏着色（Phong Shading）等。 ![](/files/97p4ZxGypTCdGrdGI4Gu) ## 3.10.5 纹理（textures） 纹理（textures）在图形学中指物品的外观而非手感，与照明算法一样，纹理也可以通过多种算法实现各式效果。其中最简单的一种效果称为「纹理映射」（texture mapping）。 ![纹理映射](/files/gsbeQ5nZ1EkFSG1Q2jeE) 纹理映射是指先将多边形的坐标和纹理坐标对应，在使用“扫描线算法”进行填充时，先查看内存中的纹理图像，后从相应区域取平均颜色，再决定该像素使用什么颜色进行填充。 ## 3.10.6 GPU 每个场景中都是由上百万个多边形构成的，渲染如此多个多边形构成的场景需要大量的计算，而无论多大的场景都是需要这样“扫描线填充, 抗锯齿, 光照, 纹理化”一遍一遍地处理。 为了加速渲染过程，有以下几种方法： （1）为这种特定运算来做专门的硬件（即 GPU）来加快速度。 （2）把3D场景分解成多个小部分，并行渲染而非按顺序渲染。 图形处理单元（Graphics Processing Unit, GPU）时为图形而生的处理器，其在显卡（Graphics Cards）之上，附有专用的 RAM 使得 GPU 的多个核心可以高速访问相关网格和纹理。 现代显卡，如 GeForce GTX 1080 TI，有 3584 个处理核心，提供大规模并行处理，每秒可处理上亿个多边形。 # 4 计算机网络 对应视频分 P 为 p28\~33。 # 4.1 计算机网络 (Computer Networks) ## 4.1.1 早期网络 ![早期网络](/files/ecIzJ8qavjUNZmhapJF0) ## 4.1.2 以太网 ### MAC 地址 以太网 (Ethernet) 是早期最著名也最成功的一种局域网 LAN 技术，其使用一条以太网电线连接数台计算机，数据在电缆中进行共享，使用 MAC 地址 (Media Access Control address) 来确认接收数据的对象。 ![MAC 地址](/files/uvjFbcIqTZse0ToWBCIO) 将 MAC 地址放在数据头部作为前缀，当计算机监听到以太电缆中的数据有自己的 MAC 地址时才处理数据。现在制造的每一台计算机都自带唯一的 MAC 地址用于构建以太网和无线网络 (WIFI) 。 ### 载波监听 像以太网这样多台电脑共享一个传输媒介的方法称为「载波侦听多路访问」 (Carrier Sense Multiple Access, CSMA) ： * 载体 (carrier)：指运输数据的共享媒介。以太网的”载体”是铜线，WiFi 的”载体”是传播无线电波的空气。 * 侦听(Sense)：计算机守候在端口等待数据。 * 多路访问 (Multiple Access)：许多计算机同时侦听载体。 载体传输数据的速度 叫「带宽」(Bandwidth)，共享载体会导致网络流量上升时出现「冲突」(collision)——大家都想往载体里传数据，但一次只能有一个。 出现冲突后最简单的处理方式是停止传输，等待网络空闲重试。但其他计算机也会这样做，这很可能导致更多冲突。 ### 指数退避 一台计算机在传输聚聚期间检测到冲突时，会等待“1s+随机时间”后重试。若重试仍然出现冲突，意味着网络出现拥塞 (congestion)，此时则等待 2s。再度重试仍然冲突时，等待 4s 后进行重发尝试。接着是 8s、16s etc. ，以此类推。 这种等待时间指数级增长的方法称为「指数退避」(Exponential Backoff)，以太网和 WIFI 等传输协议均使用这种技巧避免网络拥塞。 ### 冲突域 载体和其中的设备总称为「冲突域」(Collision Domain)，为了减少冲突并提升效率，可以将一个大的冲突域拆解为两个小的冲突域，使用交换机 (Network Switch) 来连接。 ![冲突域](/files/BPM0K9Jd5P9tt9nBlo65) 交换机会维护记录着 MAC 地址所属网络（冲突域）的列表，其仅在必要时进行数据传输，如当 A 向 F 发数据时。 ## 4.2.3 路由 大型网络的构建通常是由多个稍小的网络连接而成的，而一个计算机通过多个网络到达另一个计算机通常也会有多条路径，因此存在「路由」(routing) 问题。 ### 电路交换 如同早期 1910s 的电话系统那样，为两台遥遥相望的计算机或网络通过电路连接后分配一条专用的通信线路，称为「电路交换」(Circuit Switching)。 电路交换的缺点在于不灵活且价格高昂，同时存在线路闲置的情况。其优点在于专属电路无需共享可以随意使用，因此军队、银行等其他机构依然会购买专用线路来连接数据中心。 ### 报文交换 使用类似于邮政系统的站点中转方式进行数据传输，称为「报文交换」(Message Switching)。 在报文交换中，数据会经由不同的路由器 (network routers) 传输至目的地。消息沿着路由跳转的次数称为「跳数」(hop count)，通过对跳数的记录分析，可以分辨相应的路由问题。 若某条报文的跳数被检测出过高异常，则可以推断出路由存在错误，这称为「跳数限制」(Hop Limit)。 报文交换的优点在于可以使用不同的路由使得通信更为可靠、容错率更高。缺点在于报文较大时易堵塞网络，可通过将大报文拆分为「数据包」(packets) 来解决。 ### IP 协议 被分割出的数据包中均带有目标地址，用于告知路由器如何转发。报文的具体格式通过 1970s 创建的「互联网协议」(Internet Protocol, IP) 定义。 遵循 IP 协议的计算机都用于一个 IP 地址，以点分十进制的方式表示，如 172.217.7.238 (Google 某服务器的 IP 地址)。 数百万台计算机在网络上不断交换数据，瓶颈的出现和消失是毫秒级的。因此，路由器平衡会与其他路由器之间的负载，以确保网络中的数据传输可以快速可靠，这叫「阻塞控制」(congestion control)。 当同一报文的不同数据包经由不同线路到达目的地，其到达的先后顺序可能不一致，即出现乱序问题，可以通过 TCP/IP 协议来解决。 ### 分组交换 将大的报文数据拆分成多个小数据包后，通过灵活的路由传递，这种传输数据的运行方式称为「分组交换」(Packet Switching)。 分组交换源于冷战期间的核攻击威胁，具有去中心化的特点，不存在中心权威机构，也没有单点失败问题。 世界上第一个分组交换网络是 ARPANET ，该名字源于赞助此项目的机构“美国高级研究计划局”(Advanced Research Projects Agency)。 ![1974 年的 ARPANET](/files/GzhoKh4ZkKJvJXlZviCi) 上图是 1974 年的 ARPANET 简图。图中每个小圆表示一个地点，比如运行着一个路由器的大学或实验室（拥有单台或多台计算机）。图中还能看到 “PDP-1” 和”IBM 360系统”，甚至还有一个伦敦的 ATLAS 是通过卫星连到网络里的。 如今，全球的路由器协同工作，找出最高效的线路，用各种标准协议运输数据，比如 “因特网控制消息协议”(Internet Control Message Protocol, ICMP) 以及”边界网关协议”(Border Gateway Protocol, BGP) 等。 互联网在这几十年间发展迅速，据估计约有接近 100 亿台联网设备。随着各种智能设备的出现，比如联网冰箱，恒温器以及其他智能家电，它们还组成了「物联网」(internet of things)。 # 4.2 互联网 (The Internet) 互联网是多个网络分布式连接构成的，其中由无数日益增多的互联设备组成。 计算机需要先连接到局域网 (Local Area Network,LAN)—— 即 WIFI 路由器所连接的所有设备组成的小型网络，局域网再连接至广域网 (Wide Area Network, WAN)。 广域网中的路由器又归属于「互联网服务提供商」(Internet Service Provider, ISP)，旗下有多个不同范围大小的广域网互相连接。 ![跳跃主干网络获取资源](/files/Hy6ZbgUyAO4uMaq7dt3I) 若想获取某个资源，数据包（packet）需要先经由互联网主干（由一群超大型、带宽超高路由器组成）到达资源的服务器。 在这个过程中，数据包可能要跳个 10 次才能到达（4 跳进主干，2 跳穿越，4 跳进服务器）。Windows, Mac OS 或 Linux系统，可以用 traceroute 来查看具体跳数。 ## 4.2.1 IP 互联网协议(Internet Protocol, IP) 中规定了数据包 (packet) 在互联网中传输的标准，是非常底层的一种协议。 数据包的头部 (前缀) 是指“关于数据的数据”，又名「原数据」(metadata) 。头部指存储了目标地址，无法用于区分具体将数据交给目标地址的电脑中的哪个程序。 因此需要更高层的协议来区分程序， IP 负责把数据包送到正确的计算机，而 UDP 负责把数据包送到正确的程序中。 ## 4.2.2 UDP 用户数据报协议(User Datagram Protocol, UDP) 是一种传输层协议，其头部包含着端口号 (port) 和校验和 (checksum)等元数据。 每个想要访问网络的程序，会向操作系统申请唯一的端口号。当数据包到达时，根据端口号将数据交付给不同的程序。 ![端口号](/files/OTonsKPeIS9lQV71f2y9) 校验和用于检验数据是否正确，最简单的方式是将数据求和后对比。在 UDP 中，校验和以 16bit 的形式进行存储，若求和高于 16 位所能表示的最大值则舍弃高位。 ![校验和](/files/5tykIOTz9KZnnRSenbvY) 接收方收到数据包后会重新计算一次数据和，再与头部中的校验和进行对比，若不一致，则可判定数据可能因功率波动或电缆故障等原因而出现了错误。 UDP 不提供修复数据或是数据重发的机制，检验出错后 UDP 会直接丢包，且其无法确认数据包是否已经到达。但其优势在于简单快捷，一些视频通话应用更加青睐。 ## 4.2.3 TCP 传输控制协议(Transmission Control Protocol, TCP) 较之 UDP 的“尽力而为”而言更加可靠，其可以确保“所有数据均必须到达”。TCP 协议最初是和 IP 协议一齐出现，称为 TCP/IP 协议，后拆分为两个协议。 ![TCP/IP](/files/41CCfvXX7O1kD6mQ1Nvd) TCP 有许多更高级的功能，最重要的几个特性如下： ### 有序 TCP 数据包有序号(sequence numbers)，就算传输过程中出现了乱序到达的情况，接收方仍然可以利用序号对数据包进行正确排序。 ### 确认码 TCP 要求接收方的电脑收到数据包、检查”校验和”无误后（数据没有损坏），给发送方发一个确认码 (Acknowledgement, ACK) ，代表收到了数据包。 发送方在收到上一个数据包的确认码之后，会接着再发送下一个数据包。 ![ACK](/files/QDHvB9oRez9KRNi0UV0x) 若确认码因延误或丢失使得在一定时间后发送方仍未收到，则发送方会再次重发数据包。若接收方收到重复的数据包，可根据序号加判断是否重复需要丢弃。 此外，TCP 可以一次发送多个数据包，等待接收多个确认码，使得效率提升。 ![多次发送](/files/sYrXmYycXJkYl3fQA29m) ### 拥塞控制 在 TCP 协议中，可以借由确认码的成功率和来回时间来推测网络的拥塞程度，进而调整发送数据包的数量。 简言之，TCP 可以处理乱序、丢失、重发问题，还可以根据网络拥塞情况来自动调整传输速率。 但为了提高可靠性而存在的 ACK 使得数据包数量翻番，信息传输的密度下降，不适用于像是在线射击游戏等对时间要求很高的程序使用。 ## 4.2.4 DNS 计算机根据“IP 地址”和“端口号”对网站进行访问，比如 谷歌的 IP 地址和端口号是 172.217.7.238/80。但数字不利于人类记忆识别，用文字表示的域名 google.com 较之更为友好。 因此，需要使用特殊服务实现“IP 地址/端口号”和“域名”之间的映射对应关系，这种服务称为「域名系统」(Domain Name System, DNS) 。 ![DNS](/files/T97aWUWMkALcfDlXADeH) 输入域名后，浏览器会访问 DNS 服务器去询问其对应的 IP 地址是什么。接着 DNS 会查表，若表项存在则返回相应内容。 因注册的二级域名就已高达数千万个，为了更好地管理，DNS 使用树状结构来存储映射关系。 ![DNS 结构树](/files/vv0xKyOHoxEDgkPugnO9) 域名自右往左为：「顶级域名」(Top Level Domains, TLD) 、二级域名(lower level domains)、子域名(subdomains) etc. 因 DNS 的结构树非常大，因此这些数据都分布在许多 DNS 服务器中，不同的服务器负责树中不同部分的查询返回服务。 ## 4.2.5 OSI 模型 ![OSI 模型](/files/uJRSjgiw6OxetEhMxNHv) 开放式系统互联通信参考模型 (Open System Interconnection, OSI) 是一种将网络通信划分为多层次的概念性框架，每层各自处理一部分问题，利用抽象以便更好地简化通信。具体分层如下： 1. 物理层 (Physical Layer)：线路里的电信号，以及无线网络里的无线信号。 2. 数据链路层 (Data Link Layer)：负责操控”物理层”，有媒体访问控制地址（MAC）、碰撞检测、指数退避，以及其他一些底层协议。 3. 网络层 (Network Layer)：负责各种报文交换和路由。 4. 传输层 (Transport layer)：有 TCP、UDP 等协议，负责在计算机之间进行点到点的传输，同时提供检测和修复错误的服务。 5. 会话层 (Session Layer)：使用 TCP 和 UDP 来创建连接，传递信息，然后关掉连接，这个过程称为「会话」(session) 。 6. 表示层 (the Presentation Layer) ： 7. 应用程序层 (Application Layer) ：其中有浏览器，Skype，HTML解码，在线看电影等。 # 4.3 万维网 (The World Wide Web) 万维网 (World Wide Web) 运行在互联网 (Internet) 上，两者经常混用但不是一回事。 互联网是传递数据的管道，各种程序都会用。其中传输最多数据的程序是分布在全球数百万个服务器上的万维网，可以通过浏览器进行访问。 ## 4.3.1 超文本和超链接 万维网的最基本单位是单个页面 (page)，页面中有内容，也有去往其他页面的「超链接」(hyperlinks)，点击即可跳转。 在超链接出现之前，我们需要在文件系统中找到信息或是把地址输入搜索框，才能在计算机上看到另一个信息。 ![Memex](/files/H4GXQBdqmqSOJMDsm0Ku) Vannevar Bush 所构想机器 Memex 对其有相关的形容： \[!quote] “关联式索引.. 选一个物品会引起另一个物品被立即选中，将两样东西联系在一起的过程十分重要。在任何时候，当其中一件东西进入视线只需点一下按钮，立马就能回忆起另一件。” 在还未出现显示屏的 1945 年，这个想法非常超前。因文字超链接的强大，它有了一个专有名词「超文本」(hypertext)。如今的超文本通常指向另一个网页，然后由浏览器进行渲染。 ## 4.3.2 URL 网页用于互相连接的唯一地址，称为「统一资源定位器」(Uniform Resource Locator, URL)。以访问 crash courses 的网页 thecrashcourse.com/courses 为例： 1. DNS 查找：输入 thecrashcourse.com 域名，输出对应 IP 地址。 2. 建立连接：浏览器请求与运行着网页服务器的 IP 地址建立起 TCP 连接，使用标准端口号 80。 3. 请求服务：使用「超文本传输协议」(Hypertext Transfer Protocol, HTTP) 来向服务器发送指令 “GET /courses”，来请求名为 “courses” 的页面。 4. 返回渲染：请求指令以”ASCII编码”发送到服务器后，服务器返回该地址所对应的网页，浏览器将网页渲染至屏幕上。 ## 4.3.3 HTTP HTTP 的第一个标准 HTTP 0.9 创建于 1991 年，只有一个 “GET” 指令。当用户在网页中点击其他超链接是，计算机会重新发送 GET 请求，浏览网页的过程就是不断重复发送 GET 请求的过程。 在之后的版本，HTTP 添加了放置在请求前的状态码 (status codes)，用于指明请求状态。 ![状态码](/files/N2slFoTukX9kEUrEFBaJ) 200 表示 OK - 网页找到了给你，而 400\~499 则代表客户端出错，比如 404 代表网页不存在。 ## 4.3.4 HTML 因超文本的存储和发送都是以普通文本的形式进行，利用 ASCII 或 UTF-16 进行编码解释，需要通过一种标记方法来区分文本和连接，因此诞生了「超文本标记语言」(Hypertext Markup Language, HTML)。 HTML 第一版的版本号是 0.8，创建于 1990 年，有 18 种HTML指令，通常由一对开始标签和结束标签 (tag) 构成，基本指令如下： * \

标题 \

：一级标题。 * \ 文本 \ ：超链接。 * \
    \
  1. 有序列表\
    2. \
：无序列表。 ![HTML](/files/QVOpfqvZfkYQT3jxhyAG) 将这些文字使用文本编辑器（记事本），另存为 “test.html” 后拖入浏览器即可打开该网页。 最新版本的 HTML 5 由 100 多种标签，包括图片标签、表格标签、表单标签、按钮标签等。 此外，还可以使用「层叠样式表」(Cascading Style Sheets, CSS) 和 JavaScript 等技术，加进网页来做一些更厉害的事。 ## 4.3.5 浏览器 第一个浏览器和服务器是 Tim Berners-Lee 在 1990 年写的，一共花了 2 个月，同时他还建立了 URL, HTML 和 HTTP 这几个最基本的网络标准。 他在瑞士的”欧洲核子研究所”(CERN) 工作，已经研究超文本系统有十几年了。起初这个浏览器和服务器仅在 CERN 内部使用，1991 年对外发布，万维网就此诞生。 ![万维网](/files/Zh6tK13uCPsLTnGMDAhI) 万维网带有开发标准，因此大家都可以开发新的服务器和浏览器。“伊利诺伊大学香槟分校”的一个小组在 1993 年做了 Mosaic 浏览器，这是第一个可以在文字旁边显示图片的浏览器。 此前浏览图片需要单独开启新窗口，Mosaic 还引进了书签等新功能，界面友好，使它很受欢迎。 ![Mosaic](/files/xpDDN19dHhIh7pNnTurI) 1990 年代末有许多浏览器面世，比如 Netscape Navigator, Internet Explorer, Opera, OmniWeb, Mozilla。同时也有很多服务器面世, 比如 Apache 和 微软互联网信息服务(Microsoft’s Internet Information Services, IIS)。在这个黄金时代中，也诞生了许多网络巨头，如创始于 1990 年代中期的亚马逊和 eBay。 ## 4.3.6 搜索引擎 ### 门户网站 随着网页日益增多，寻找所需内容变得困难。起初人们会维护一个链接到其他网站的目录。 其中最有名的叫 “Jerry和David的万维网指南” (Jerry and David’s guide to the World Wide Web)，它在 1994 年改名为 Yahoo。 随着网络越来越大，人工编辑的目录变得不便利，于是出现了「搜索引擎」(search engines)。 ### Jump Station 最像现代搜索引擎的最早搜索引擎是由 Jonathon Fletcher 于 1993 年在斯特林大学创建的 JumpStation，它由三部分组成： 1. 爬虫 (web crawler)：顺着链接不停探索的软件，看到新链接时将其加入自己的列表当中。 2. 索引 (index)：记录爬虫访问过的网页中，出现过哪些关键词。 3. 搜索算法 (search algorithm)：用于排序匹配上关键词的网页先后顺序。 ### Google 早期搜索引擎的算法仅取决于搜索词在页面上的出现次数，有些内容农场会不断重复热门搜索词来吸引人们，拉低信息搜索质量。Google 创造了一个算法来规避这个问题，就此成名。 与其信任网页上的内容，不如信任其他网站链接到这个网站的”反向链接”数量，而反向链接中有信誉的网站占比越大，则可认为网站质量越高。 Google 一开始时是 1996 年斯坦福大学中名为 BackRub 的一个研究项目，两年后分离出来，演变成如今的谷歌。 ## 4.3.7 网络中立性 网络中立性 (Net Neutrality) 是指应该平等对待所有数据包，不论它的内容是什么，其传输速度和优先级应当是一致的。 有些公司会乐意通过故意给某些数据更少带宽和更低优先级的方式，来使得自己的数据优先到达，这种方式为「节流」(Throttled) 。 支持”网络中立性”的人认为失去中立性后，服务商可以推出提速的”高级套餐”，为剥削性商业模式埋下种子，使得龙头企业拥有特权优势，而初创公司出于劣势，不利于创新。另一方面，从技术原因来看，我们也很容易希望即时通讯的消息比邮件的优先级更高、更快到达。 而反对”网络中立性”的人认为，市场竞争会阻碍不良行为。如果供应商把客户喜欢的网站降速，客户会离开供应商。 # 4.4 网络安全 (Cybersecurity) ## 4.4.1 安全特性 计算机安全可以视为保护系统和数据的保密性 (Secrecy), 完整性 (Integrity) 和可用性 (Availability)： * 保密性：只有有权限的人，才能**读取**计算机系统和数据。若黑客泄露信用卡信息，则是攻击保密性。 * 完整性：只有有权限的人，才能**使用和修改**系统和数据。若黑客知道你邮箱密码伪造你的发送邮件，则是攻击完整性。 * 可用性：有相应权限的人，可以**随时访问**计算机系统和数据。用大量假请求来拖垮服务器的「拒绝服务攻击」(Distributed Denial of Service Attack, DDOS)，是在攻击可用性。 ## 4.4.2 威胁模型分析 为实现 4.4.1 节中的对三种特性的维护，安全架构师会从抽象层面对假想敌人做出模拟，为特定情境做准备，这个过程称为「威胁模型分析」(threat model)。 该模型会对攻击者进行大致描述：攻击者能力 (capabilities)、攻击目标 (goals)、可能攻击手段/攻击矢量（attack vector）。 在实际应用过程中，具体如何保护要看是与谁进行对抗。通常威胁模型分析里 会以能力水平区分，比如”某人可以物理接触到笔记本计算机，而且时间无限”，安全架构师要在给定的威胁模型下提供解决方案以保持系统安全。 只要某些假设不被推翻，保护计算机系统、网络和数据的方法有很多。诸多安全问题可以被归结为以下两个问题： 1. who are you? 你是谁？ -> 身份认证 2. what should you have access to? 你能访问什么？-> 访问控制 ## 4.4.3 身份认证 根据来访者的身份给予不同权限，用于区分不同使用者的方式称为「身份认证」 (authentication) ，常用的三种方式分别是：你知道什么 (What you know)、你有什么 (What you have)、你是什么 (what you are)。 对于重要账户，可以采用”双因素” (two-factor) 或”多因素”认证 (multi-factor authentication)，这种两步验证使得安全性大大提升。 ### What you know 基于某个只有计算机和你知道的秘密（如用户名和密码）来确认身份，但若攻击者通过猜测得知，密码组合位数越多、复杂性越高，被猜中的概率越低。 以 4 位的手机 PIN 码为例，计算机可以在 1s 内从 0000 一直试到 9999，这种尝试所有可能性的攻击方式称为「暴力攻击」(brute force attack)。 通常的系统会有次数限制，比如在 PIN 码输入错误 3 次后，需要等待一定时间才能进行重试。但假设攻击者使用数以万计的计算机来形成僵尸网络在不同账户上尝试密码组合，就算每个账户只试一次，也存在命中的可能性。 8 位 PIN 码著有 1 亿种组合，但包含特殊字符的 8 位数密码有超过 600w 亿种组合。为了记忆和复杂度的综合，可以使用三个连续单词的组合，英文大约有 10w 个单词，三个单词的组合约有 1亿亿种可能。而使用不在字典中的单词，会使得密码强度进一步提升。 ### What you have 基于某种用户所拥有的特定物体来确认身份，比如钥匙和锁。通常需要有人在场，使得远程攻击更为困难。但如果攻击者在附件，安全性就会降低——钥匙可以被复制，手机可能被偷，锁可以撬开。 ### What you are 基于人类自身的生物特征来进行身份认证，比如指纹识别器和虹膜扫描仪就是典型的生物识别验证器，安全性最高但好的识别技术十分昂贵，且传感器中识别到的数据每次都会有差异。 相较于具有”确定性”（正确 or 错误）的 “你知道什么”和”你有什么”这两种验证方式，“生物识别”是存在概率性的。系统有可能认不出你或者错认你，同时生物认证也存在无法重设的问题——人只有十个手指，攻击者如果拿到所有指纹就玩完。 ## 4.4.4 访问控制 认证完身份后，可以通过用户相对应的权限 (Permissions) 或是「访问控制列表」(Access Control Lists, ACL) 来明确谁能访问什么，修改什么，使用什么。基本权限如下： * 读 (Read)：允许用户查看文件内容。 * 写 (write)：允许用户修改内容。 * 执行 (execute)：限允许用户运行文件（如程序）。 一种常用的”访问控制列表”配置（即访问控制模型）是为美国国防部”多层安全政策”制定的 Bell-LaPadula 模型，其特点在于「不能向上读，不能向下写」。 以 “公开、机密、绝密” 三个访问级别为例：“机密”权限用户仅能读取 “机密” 和 “公开” 文件，无法读取 “绝密” 文件；“绝密” 权限用户可以读取所有访问级别的文件，但为防止高级别文件泄露，无法修改写入低级别文件。 除此之外，“中国墙”模型 (the Chinese Wall model) 和”比伯”(Biba model) 模型也是较为常见的访问控制模型，模型的优劣取决于具体情况。 ## 4.4.5 独立安全检查和质量验证 进行身份验证和访问控制的前提是软硬件可信，但我们实际上无法确定操作系统有没有被攻击者的恶意软件控制或是安全程序是否有给攻击者留后门。 安全软件在理论上是 “安全的”，但在实现时可能出错存有 bug，我们可以通过一发现漏洞就修复以及当程序被攻破时尽可能减少损害等方式来提高安全性。 系统级安全的圣杯之一是「安全内核」(security kernel)，又称作「可信计算基础」(trusted computing base)：在最小化代码数量的前提下，决定内核中有什么，同时还要确保安全性都是接近可验证的。 正式验证代码安全性是一个活跃的研究领域，现在最好的安全手段是「独立安全检查和质量验证」(Independent Verification and Validation)，这种方法让安全领域的软件开发者来审计代码（通常是开源的），外部开发人员比写原始代码的人更容易找到错误。 同时，也会举行安全大会以便安全专家互相认识并分享想法。 ## 4.4.6 隔离 隔离 (isolation) 是一种在当程序被攻破后控制损害最小化的方式之一，可以通过「沙盒」(sandbox) 程序来实现，沙盒的具体方法是由操作系统给每个程序独有的内存块，其他程序不能使用。 一台计算机可以运行多个虚拟机 (Virtual Machines)，虚拟机模拟计算机，每个虚拟机都在自己的沙箱里。如果一个程序出错，最糟糕的情况是它自己崩溃或是搞坏它处于的虚拟机，而计算机上其他东西都是隔离的，并不会受其影响。 # 4.5 黑客与攻击 (Hackers & Cyber Attacks) ## 4.5.1 hackers 黑客 (hackers) 是指能凭技术知识闯入计算机系统的人，一些通过寻找并修复软件漏洞使得系统更加安全的黑客被称为是「白帽子」(White Hats)。 相对应的，也有窃取、利用、售卖计算机漏洞和数据的 “黑帽” 人士 (Black Hat Hackers) 。他们或出于好玩与好奇，或是为了钱财而成为网络罪犯，或是通过黑客手段来影响社会舆论或是达到政治目的（即黑客行动主义者，hacktivists）。 ## 4.5.2 社会工程学 黑客最常见的入侵方式是通过欺骗别人而非技术手段，这类通过欺骗手段让人泄露机密信息或让别人将电脑系统配置得变得易于攻击的方式称为「社会工程学」(social engineering)。 ### 网络钓鱼 (phishing) 网络钓鱼的典型例子是伪造银行发送邮件，点击链接进入冒牌银行官网，输入的账密信息会发送给攻击者，之后对方就可以假冒你的身份来登录网站。 ### 假托 (Pretexting) 假托是指攻击者伪装成内部人员通过电话将电脑系统配置得更加容易入侵，其第一通电话会让人进行内部转接使得攻击者看起来像是内部 IT 人员。 通过这种方式只需要事先知道关键员工的名字等信息，就可以以假乱真，使对方降低戒备从而修改配置或是泄露出密码等机密信息。 ### 木马 (Trojan horse) 木马是伪装成无害的照片或发票等内容的恶意软件，这些恶意软件有的是会偷取银行凭证之类的数据，有的是会加密文件索要赎金的 “勒索软件” (ransomware)。 ## 4.5.3 NAND 镜像 (NAND Mirroring) 若木马或是电话欺骗无法奏效，则攻击者可能会采取暴力尝试来试图进入系统。大多数现代系统会加长等待时间来抵御这种攻击，每次失败就加长等待时间，甚至失败超过一定次数后，完全锁住。 但最近有一种攻破方式「NAND 镜像」可以绕过这种限制，这种方式需要能够物理接触到电脑，先在内存中接上几根线后复制整个内存。在暴力尝试密码出现设备等待重试的情况时，直接用复制好的内存重新覆盖一次，使得可以无限尝试密码而无序等待。 ## 4.5.4 缓冲区溢出 (buffer overflow) ### 漏洞利用 (Exploit) 通过系统漏洞来获得某些操作能力和访问权限的远程攻击方式，称为「漏洞利用」，最常见的一种漏洞利用是「缓冲区溢出」 (buffer overflow)。 缓冲区 (buffer) 泛指预留在内存中的一块空间，比如在登录界面输入账密时，这些信息会先记录在缓冲区内再验证是否正确，当输入数据超出缓冲区大小时则出现 “溢出” (overflow)，此时溢出数据会覆盖掉缓冲区前后的相邻数据。 ![缓冲区溢出](/files/N5KcCEhywoPjjAxkqyYm) 这种情况有时只会因重要值被垃圾数据覆盖而导致程序或系统崩溃，有时攻击者可以更巧妙地利用这个漏洞 (bug) 来注入有意义的新值到程序的内存中，比如把 “is\_admin” 的值改成 true 获得管理员权限。有了任意修改内存的能力，黑客可以绕过”登录”之类的东西，甚至使用那个程序劫持整个系统。 应对缓冲区溢出有两种常见方式：边界检查 (bounds checking) 和金丝雀 (canaries)。 ### 边界检查 (bounds checking) 边界检查是指在将值复制到缓冲区之前，先检查一下值的长度，许多现代编程语言自带了边界检查的功能。 同时程序也会随机存放变量（比如之前提及的 “is\_admin”）在内存中的位置，使得攻击者不知道应当覆盖内存中的哪部分内容。 ### 金丝雀 (canaries) 金丝雀 (canaries) 源于矿工将金丝雀矿井来警告危险的举动，安全领域的 “金丝雀” 是指在缓冲区留有一些不用的空间，通过追踪空间内的值是否发生变化来确认是否受到攻击。 ## 4.5.5 代码注入 (injection) 代码注入 (injection) 常用于攻击使用数据库的网站，在登陆界面使用一种流行的数据库 API —— “结构化查询语言”(Structured Query Language, SQL) 中的命令插入输入框内，进而对系统进行破坏性操作。 比如在输入用户名的地方写入 “whatever; drop table users”，系统会先查询 whatever 这个用户，接着执行命令 “drop table users” (SQL 命令通过 ； 分隔)，使得攻击者在未入侵系统的情况下删除了全表。 ![代码注入](/files/YXWZeKRsOZ5of2GCLSpW) 即使没有正式访问权限，还是可以通过代码注入来利用 bug 来制造混乱。如果指令更复杂一些也许可以添加新记录到数据库，比如新建一个管理员帐户，甚至可以让数据库泄露数据，使得黑客能够窃取信用卡号码，社会安全号码以及各种其他信息。 如今几乎所有服务器都会防御这种手段，比如通过不允许输入分号或括号等特殊字符来作为第一道防御，再比如通过修改或删除特殊字符来清理输入后再放入数据库查询语句中。 ## 4.5.6 零日漏洞 可行的系统「漏洞利用」(Exploits) 通常会被放置在网上售卖，若该漏洞十分流行或造成的危害很大，则售价越高。有时甚至政府也会购买漏洞利用，使得他们可以通过入侵系统实现间谍活动。 若软件制造者不知道软件有新漏洞被发现了，则称该漏洞为「零日漏洞」(a zero day vulnerability)。黑帽子们会抢在白帽子们做出补丁之前尽可能的利用漏洞来获利，因此保持系统更新非常重要，很多更新都是安全性补丁。 ## 4.5.7 僵尸网络 当有足够多的电脑存在漏洞，使得恶意程序可以在电脑刺激互相传播，这种恶意程序被称为「蠕虫」(worms)。 当攻击者利用蠕虫拿下了诸多电脑，则可以组成「僵尸网络」(botnet) 来进行大规模攻击，比如发送大量垃圾邮件、用别人电脑的计算能力和电费挖 Bitcoin、发起”拒绝服务攻击” (DDoS) 来攻击服务器等。 现在，网络攻击每年损害全球经济差不多 5000 亿，这个数字正在日益渐增。许多专家预测下一次的大战会是网络攻击，因为越来越多的基础设施变得数字化，其造成的伤亡甚至会高于传统战争。 # 4.6 加密 (Cryptography) 世上不存在 100% 安全的系统，漏洞总是会存在，无非是多与少的问题。因此系统架构师为提升系统安全性，通常会部署”多层防御” (defence in depth) 。 计算机安全中最常见的防御形式是密码学(cryptography)，该词来自 crypto 和 graphy，大致翻译成”秘密写作”。其基本概念如下： * 加密算法 (Cipher)：用于将明文转为密文进行信息加密，不知道如何解密的情况下，密文看起来只是乱码。 * 加密 (encryption)：将明文转成密文。 * 解密 (decryption)：将密文恢复成明文。 ## 4.6.1 替换加密 ### 凯撒加密 (Caesar cipher) 朱利叶斯·凯撒 (Julius Caesar) 在很早之前就通过将信件中的字母向前移动三个位置来进行加密，这种名为「凯撒加密」(Caesar cipher) 的加密算法归属于一大类名为「替换加密」(substitution ciphers) 的算法类型。 为了解密，接收者要知道对方使用了什么算法，并且明确要偏移的字母位数。这种算法把每个字母替换成其他字母，其缺点在于替换后的字母出现频率依然有迹可循，密码破译师可以通过统计数据发现相关规律进而破解加密。 1587 年，正因为一个”替换加密”的密文被破译，导致刺杀伊丽莎白女王的阴谋暴露，使得玛丽女王被处决。 ### 英格玛机（Enigma） 1900 年代，人们用密码学做了加密机器，其中最出名的是纳粹在战时用于加密通讯信息的机器英格玛机 (Enigma Machine) ，属于替换加密的一种。 ![英格玛](/files/eSDk0P5q3DrrcWNqaLjx) 如 [2.6.2 节中提及的那样](https://cccs.viyi.cc/2-cheng-xu-she-ji/2.6-alan-tu-ling-alan-turing#id-2.6.2-po-yi-ying-ge-ma-ji)，Enigma 是一台像打字机的机器，另有键盘、灯板和转子齿轮，在键盘和转子 (rotors) 上都有完整的字母表。 ![单个英格玛转子](/files/ADLH2MpX5VZk1yN0pJoZ) 在单个转子重，一面有代表 26 个字母的 26 个接触点，通过线连接到另一面来替换字母。使用多个转子，将上一个转自的输出作为下一个转子的输入。 转子还有 26 个起始位置，可以按不同顺序放入转子，提供更多字母替换映射。转子之后是一个叫”反射器” (reflector) 的特殊电路，其每个引脚会连到另一个引脚并将信号发回给转子。 ![多个转子](/files/x7c8gCtluShGYQO4TUka) 而在机器的前方还有一个插板，可以把输入键盘的字母预先进行替换，使得加密的复杂度进一步提升。 ![插板](/files/Hfo8ckhRWlse4LeyKDtl) 英格玛机器的电路是双向的，加密和解密步骤是一致的，因此只需要确保 发送机和接收机的初始配置一样就行。 英格玛机器的加密特点在于字母加密后一定会变成另一个字母，为了弥补这种简单替换加密的弊端，英格玛会在每输入一个字母后将转子转动一个，使得同一字母会随每次的按键来呈现多种不同映射。 而正如 2.6.2 节中介绍的那样，艾伦·图灵 (Alan Turing) 和同事破解了英格玛的加密过程，并把大部分破解流程做成了自动化。 ### 4.6.2 移位加密 (permutation ciphers) 另一类加密算法称为「移位加密」(permutation ciphers)，其中的一个典例是「列移位加密」 (a columnar transposition cipher) —— 通过读取方向和网格大小来加密信息。 ![列移位加密](/files/DN7qTwzgrmsNDrbazUM0) 若从网格左起开始，从下往上，一次一列，重新组合字母，则可以得到 “SCRMMTH EEA L EN-UFT NO” 的密文。通过读取方向和 5×5 大小的网格尺寸，可以逆推出明文。 ## 4.6.3 加密算法 随着计算机出现，加密从硬件转往软件。早期加密算法中，应用最广泛的是数据加密标准和高级加密标准。 ### 数据加密标准 1977 年，IBM 和 NSA 开发了「数据加密标准」(Data Encryption Standard, DES)，最初使用的密钥是 56bit 长的二进制数，密钥数量为 (约 72 千万亿) 个。 然而随着计算能力的暴增，1999 年一台 25w 美元的计算机可以在两天能遍历所有可能密钥从而暴力破解得到 DES 的密钥，因此该算法不再安全。 ### 高级加密标准 2001 年，为了紧跟算力增加的现状出台了「高级加密标准」(Advanced Encryption Standard, AES) ，其使用 128/192/256 bit 长度的密钥。 一个 128bit 的密钥，使用如今的电脑想要暴力破解需要计算上万亿年才可以。更长的密钥位数，使得暴力破解更为困难。 AES 会将数据切成每块 16 字节的大小，然后用密钥进行一系列替换加密和移位加密，再加上一些其他操作来进一步加密信息，每块数据会重复这个加密过程 10 次以上。 密钥的长度位数和加密过程的重复次数都是基于性能速度和安全性两者之间的权衡，没有人愿意等待几个小时来加密发送邮件。 如今 AES 被广泛使用，比如 iPhone 上加密文件、用 WPA2 协议在 WiFi 中访问 HTTPS 网站等。 ## 4.6.4 密钥交换 以上所讨论的加密技术都有赖于发送者和接收者同时持有密钥进行加密解密。在早期密钥的交换可以通过口头约定或是实体交换，比如德国人给英格玛配了记录每天机器配置的密码本。 为了在公开的互联网传递密钥，我们需要可靠的「密钥交换」(key exchange)——一种不发送密钥，但依然让两台计算机在密钥上达成共识的算法。 ### 单向函数 密钥交换通过「单向函数」(one-way functions) 实现，单向函数是指很容易正向算出结果，但想从结果逆向推算出输入非常困难的数学操作。 以颜色为例，发送方和接收方各自选择不为人知的本命色，双方发送时将本名色混合公开色进行传输，接收时再使用自己的本名色叠加，三色混合而成的颜色 (即密钥) 仅交流双方可知。 ### 迪菲-赫尔曼算法 具体实现是一种名为「迪菲-赫尔曼密钥交换」 (Diffie-Hellman Key Exchange) 的算法，其单向函数是模幂运算。 通过对基数进行幂运算取余后得到模很容易，但想要从余数和基数中逆推出指数是多少就很难，而随着基数变大则会难上加难。 基数 B 和模数 M 是公开的，指数是发送方秘密指定的。阿珍和阿强各自选取一个秘密指数 X 和 Y，发送给对方 B^X mod M / B^Y mod M，接收之后各自对其取 X 或 Y 的次方进行模幂运算，得出仅双方共享的密钥，由此建立起「共享密钥」(shared key)。 ![模幂运算](/files/1wfLsSgXPoXV70iu9ijp) ## 4.6.5 非对称加密 双方用相同的的密钥加密和解密消息，称为「对称加密」(symmetric keys)，凯撒加密，英格玛，AES 都是”对称加密”。 而使用两个不同的密钥——公开的公钥 (public key) 和私有的私钥 (private key)——进行加密的方式，称为「非对称加密」(asymmetric encryption)。其 “不对称” 在于仅仅知道公钥只能加密，但不能解密。 ### 数字签名 类似于锁和箱子，发送方将信息放入箱子锁起后传输，只有接收方的钥匙能开启箱子。同样的，公钥加密后只能私钥来解密，而私钥加密后可以用公钥解密，私钥和公钥时而是箱子时而是锁。 这种做法常用于数字签名，服务器使用私钥加密，任何人都可以用服务器的公钥解密。因为只有私钥的持有人能加密，故签名无法伪造，从而证明数据源自可靠的服务器或个人。 ### RSA 目前最流行的”非对称加密”技术是 RSA，该名字源于发明者 Rivest, Shamir, Adleman。 ![RSA](/files/x6WLlaSPHrhRDsuoZV0g) # 5 拓展讨论 对应视频分 P 为 p34\~40。 # 5.1 机器学习与人工智能 (Machine Learning & Artificial Intelligence) 机器学习 (Machine Learning, ML) 的本质是根据数据做出决定，机器学习算法让计算机可以从数据中学习，然后自行做出预测和决定。 能够根据数据做出一定决断并不意味着它拥有和人类一般的智能 (Artificial Intelligence, AI)。ML 和 AI 经常混用，但计算机科学家通常认为前者是实现后者的技术之一。 ## 5.1.1 分类器 (classifier) 本节以判断飞蛾是”月蛾”还是”帝蛾”为例，进行概念的简单讲解。这类问题称为「分类」 (classification)，用于解决分类问题的算法称为「分类器」 (classifier)。 ### 决策边界 (decision boundaries) 许多分类器会将照片和声音中的「训练数据」(training data) 简化为「特征」(features)，以便于更好地进行 “分类” 判断的取值。其具体步骤如下： （1）人类昆虫学家记录飞蛾的特征值和种类，进行「标记数据」(labeled data)。 ![标记数据](/files/RNncOIyCMTQohd4YTmmU) （2）将数据可视化形成「决策空间」(decision space)，使用机器学习算法找出区分飞蛾的最佳方式，确定「决策边界」 (decision boundaries)。 ![决策边界](/files/Otkm42mdtVwD45twVre0) （3）根据实际数据与决策边界的误差值，绘制「混淆矩阵」(confusion matrix)。 ![混淆矩阵](/files/POr3dyDHRF1QV3ht3jTQ) 决策边界的确定无法 100% 涵盖正确判断，机器学习算法的目的在于「最大化正确分类 + 最小化错误分类」。在上述训练数据中，所确认的决策边界平均识别准确率在 84%。 ### 决策树 (Decision Trees) 将不认识的飞蛾测量特征并绘制到决策空间中，这种数据称为「未标签数据」(unlabeled data)，可以利用决策边界预测判断飞蛾种类。 ![未标签数据](/files/xaZrzvWW6yFRnMbhCglr) 将把决策空间切成几个盒子的简单方法可以用「决策树」(Decision Trees) 来表示，使用 if 语句写出代码就是生成决策树的机器学习算法。 ![决策树](/files/SM3sOH6s1DoY5ECs5Phz) 决策树只是机器学习中的一个简单示例，如今有数百种算法存在且不断出现新算法。一些算法甚至用多个 “决策树” 来预测，计算机科学家称为 “森林” (Forests)。 也有不用树的方法，比如 “支持向量机” (Support Vector Machines)，本质上是用任意线段来切分 “决策空间”，线段可以是多项式或其他数学函数。 ![支持向量机](/files/NpBX23tSj5F0HC01jhgA) 机器学习算法会负责找出最好的线，最准的决策边界。增加至 3 个特征，我们还可以继续用 3D 散点图绘制出决策空间。 ![3D散点图](/files/zHoKt5yG5AueClDuY5hj) 但当引入多个特征，就无法依靠人力在一个上千维度的决策空间里，为超平面(Hyperplane)找出一个方程了，但聪明的机器学习算法可以做到。 ## 5.1.2 人工神经网络 (artificial neural networks) “决策树”和”支持向量机”这样的技术发源自统计学，统计学早在计算机出现前就在用数据做决定，有一大类机器学习算法用了统计学方法。但也有不用统计学的算法，其中最值得注意的是「人工神经网络」(artificial neural networks)。 人类的神经元细胞利用电信号和化学信号来处理和传输消息，它从其他细胞 得到一个或多个输入，然后处理信号并发出信号，从而形成巨大的互联网络来处理复杂的信息。 人工神经元通过类似的方式，接收多个输入后整合并发出一个信号。其不适用电信号或是化学信号，而是使用数据堆叠成多层，形成神经元网络，故有此名。 ![人工神经网络](/files/kiyMweGkCw1U1ePnSg3H) 仍以飞蛾为例，输入数据的特征依旧选定为 “重量” 和 “翼展” 作为第一层「输入层」(input layer) ，在输入层和输出分类结果的「输出层」(output layer) 之间存在「隐藏层」(hidden layer)。 隐藏层负责把输入变成输出，实际上用于判断分类。首先将输入数据乘以权重，求和后再进行偏差值处理（加减固定值），接着再用激活函数 (activation function) / 传递函数 (transfer function) 对输出结果执行最后一次数学修改。 ![隐藏层处理](/files/ilJ4tR7fkuHBsRKbowS3) 权重和偏差值一开始是随机的，算法会通过 “标记数据” 来进行训练和测试，进而调整这些值来逐渐提高准确性。 隐藏层中存在多个神经元 (neuron)，每个神经元都会进行加权、求和、偏置、激活函数的计算过程，并向前进行传播，计算结果最高的就是分类结果。 最重要的是隐藏层可以有很多层，**深度学习 (deep learning )** 因存在多个隐藏层而得名。 ![深度学习](/files/8wR3jAbClBJ51ZZ0eXbq) 训练更复杂的网络需要更多的计算量和数据，尽管神经网络 50 多年前就发明了，但直到处理器和 CPU 的发展才使得深层神经网络在最近成为可能。 几年前，Google 和 Facebook 展示了深度神经网络在照片中识别人脸的准确率和人一样高，这是一个巨大的里程碑。 ## 5.1.3 强化学习 ( Reinforcement Learning) 只能做特定任务 “弱 AI”(Weak AI) 或”窄 AI” (Narrow AI)，比如利用深层神经网络来开车、翻译、诊断医疗状况等，只能做特定的一件事。 真正通用的、像人一样聪明的 AI，叫 “强 AI” (Strong AI)。目前强 AI 暂未出现，但许多人认为随着数字化知识的爆炸性增长可能会加速其的出现，毕竟 AI 吸收新讯息的速度比人类强得多。 比如 IBM 的 Watson(沃森) 吸收了 2 亿个网页的内容，在 2011 年的知识竞答中碾压了人类；2016 年 Google 推出的 AlphaGo（玩围棋的窄 AI）通过和自己的克隆版下无数次围棋来打败人类最好的围棋选手。 像 AlphaGo 这样通过不断试错来学习什么管用、什么不管用，从而自己发现成功的策略的方法很类似与人类的学习方式，这称为「强化学习」(Reinforcement Learning)。 对于很多垂直的问题，强化学习已被广​​泛使用。如果这类技术被广泛使用，可能会创造出类似于人类的 “强 AI” 能够像人类小孩一样学习，但学习速度超快。如果这发生了，对人类可能有相当大的影响。 # 5.2 计算机视觉 (Computer Vision) 计算机视觉 (Computer Vision) 领域的目标是让计算机理解图像和视频。 > “Just like to hear is the not the same as to listen.To take pictures is not the same as to see.” by computer vision professor Fei-Fei Li > > 「听到不等于听懂，看到不等于看懂」——李飞飞，计算机视觉教授 ## 5.2.1 颜色跟踪算法 参见 [3.3.1 节位图的相关说明](https://cccs.viyi.cc/3-cao-zuo-xi-tong/3.3-wen-jian-xi-tong-files-file-systems#wei-tu-bitmap)，我们知道单个像素是由 “红、绿、蓝” 三原色组成的，三种颜色的组合 RGB 值可以定义一个像素的颜色。而最简单的计算机视觉算法是一种 “颜色跟踪算法” (color marker tracking and similar algorithms)。 首先记录单色物体的最中心像素 RGB 值，如粉球中心点像素。为使得程序找到输入图片中最接近该 RGB 值颜色的像素，算法会按序 (如左上始) 逐个检查像素计算于目标颜色的差异。遍历后最接近目标值的像素位置，可能就是所要找的物品 (粉球)。 根据这个思路，可以为视频的每一帧图片都跑一次算法，从而跟踪粉球的位置。其缺陷在于因为光线、阴影等干扰会使得粉球的颜色有所变化，而与所存储的原始粉球 RGB 值不一致。再加上环境中可能存在其他颜色相近的物品，也会对该算法的识别准确率产生影响。 因此颜色跟踪算法的使用环境的控制要求较高，且只适用于单个像素的搜索而无法匹配占有多个像素的特征。 ## 5.2.2 核 (kernel) 当我们需要识别类似于物体边缘 (由多个像素组成) 时，需要采用能够按块处理像素的算法。简化颜色以灰度图片为例进行说明，易得边缘处存在垂直变化，故设定 “某像素是垂直边缘的可能性，取决于左右两边像素的颜色差异程度” 的判断规则。 算法在本例中不仅处理单个像素，而是处理某像素和左右两边的像素这一小区域 (small regions) ，称该区域为「块」(patches)。 判断规则——色差越大越可能是边缘——的数学表达，称为「核」(kernel) 或是「过滤器」(filter) 。 ![核](/files/xU7ntk9LOsJhk0F1iKDI) “核” 内的值 (数字) 用于对块做像素乘法，其总和用于存储更新中心像素的值。这种将 “核” 用于像素块的操作方式，称为「卷积」(convolution)。 ![](/files/9pwL6lI91qolsSwcHscK) 将这个 “核” 用于照片中的每个像素，处理后的结果会突出垂直边缘的像素值，如下图所示。若想突出水平边缘的特征，则需要使用不同的 “核” 再做进一步的处理。 ![垂直边缘敏感核处理效果](/files/t3txlQlta9jloJx0eJhI) 这两个用于边缘增强的 “核” 称为「Prewitt 算子」(Prewitt Operators)，以发明者的名字命名。

Prewitt 算子

各类不同的 “核” 可以用于不同的图像转换，也可以制作对不同模式敏感的 “核”，用于匹配特定形状。 ![各类不同核](/files/KhBSPqSjvafwndcNw4LJ) 多个 “核” 组合在一起识别效率与准确率均会提升，比如用线段敏感的核判断鼻子、用像素岛核来判断眼睛等组合识别人脸。 不是脸但又有一堆脸的特征在正确的位置，这种情况不太可能。这种组合 “核” 是一个早期很有影响力的算法的基础，称为「维奥拉·琼斯 人脸检测算法」(Viola-Jones Face Detection)。 ## 5.2.3 卷积神经网络 5.1.2 节中介绍的人工神经网络，通过最基本的单位 “神经元” 来对多个输入进行处理，乘权求和后得到一个输出。当我们为神经元输入二维像素 (2D pixel data)，则会得到「卷积神经网络」 (Convolutional Neural Networks)。

卷积神经网络

与 5.2.2 小节中预先设定好的 “核” 不同，卷积神经网络中的 “核” 可以自行学习，卷积神经网络可以选择有利于识别图片中特征的核作为某层神经元的处理方式，再将处理好的图像传给下一层进行别的特征识别。 ![卷积神经网络](/files/tCDbVgtRqvH24gjYKqcq) “卷积神经网络” 不是非要很多很多层，但一般会有很多层，来识别复杂物体和场景，所以算是 “深度学习” 的一种。 ## 5.2.4 情感识别算法 识别出人脸后，还可以进一步使用更专用的计算机视觉算法——像是 “情感识别算法”(emotion recognition algorithms) 来定位面部标志，进而判断人类的情绪。 比如定位了鼻尖和嘴角的标志点，可以通过计算点之间的举例来判断是否张嘴或微笑；跟踪眉毛相对于眼睛的位置，可以判断是否表示喜悦或是惊喜；通过这些信息来让电脑知道你的情绪，从而做出合适的行为。这只是计算机通过视觉感知周围的一个例子，你在不同环境会有不同行为，计算机在足够聪明的情况下也应如此。 面部标记点也可以捕捉脸的形状，进行生物识别，可以用于手机解锁或是让政府用摄像头跟踪人。跟踪手臂和全身的标记点，可以让计算机理解用户的身体语言，比如用户给联网微波炉的手势。 抽象是构建复杂系统的关键，计算机视觉也是一样。硬件层面，有工程师在造更好的摄像头，让计算机有越来越好的视力；有了用来自摄像头的数据，可以用视觉算法找出脸和手，用其他算法接着处理来解释图片中的东西；有这些基本信息后，人们可以做出新的交互体验，比如智能电视和智能辅导系统会根据用户的手势和表情来回应。 # 5.3 自然语言处理 (Natural Language Processing) 相较于 [2.2 节中讨论过的 “编程语言”](https://cccs.viyi.cc/2-cheng-xu-she-ji/2.2-bian-cheng-yu-yan-the-first-programming-languages) 这种词汇量较少、非常结构化的语言类型而言，拥有大量词汇、多义词、口音等特点的人类语言与之完全不同。 代码只能在拼写和语法完全正确时才能编译和运行，而在大多数情况下，人类语言就算有拼写或发音错误，对方也能够理解含义。 我们将人类语言称为「自然语言」(Natural Language)，为了使得计算机拥有能够进行语音对话的能力而诞生了「自然语言处理」(Natural Language Processing, NLP)，这是结合计算机科学和语言学的跨学科领域。 ## 5.3.1 分析树 ### 词性 单词组成的句子组合方式有无数种，无法通过字典涵盖所有可能。因此 NLP 早期的基本问题是如何为句子分块，其可以通过词性和语法来判断。 以英语为例，英语语音存在 9 种词性——名词，代词，冠词，动词，形容词，副词，介词，连词和感叹词，单类词性下还存在子类，如单数名词 vs 复数名词、副词最高级 vs 副词比较级等。 ![9 种词性](/files/woOG9yFcgPcToThl3ogf) ### 短语结构规则 但仅依靠词性字典无法处理多重词性的单词在某个语境下的模糊性，需要利用语法辅助判断，故出现「短语结构规则」(phrase structure rules) 来代表语法规则。 ![短语结构规则](/files/azjCRwvMVsZAGS9HQB42) 比如英语中有一条规则是 “句子可以由一个名词短语和一个动词短语组成，名词短语可以是 ‘冠词 + n.’ 或 ‘adj. + n.’ 等”，我们可以给一门语言制定出一堆规则，如上图所示。 ### 分析树 利用这些 “短语结构规则” 可以做出「分析树」(parse tree)，树中注明句子结构和单词词性，使得句子中的数据块更小更易处理。 ![分析树](/files/lIcKk9RM5QDudxVS0kVe) ### 知识图谱 “短语结构规则”和其他把语言结构化的方法，还可以用来生成句子。当数据存在语义信息网络时，这种方法特别有效。实体互相连在一起，提供构造句子的所有成分。 Google 版用结构化方法生成句子的方式称为「知识图谱 」(Knowledge Graph) 。在 2016 年底，包含大概七百亿个事实，以及不同实体间的关系。 ![知识图谱-Siri: Thriller was released in 1983 and sung by Michael Jackson](/files/sILqd39V3hmGrJlmozFv) ## 5.3.2 聊天机器人 处理, 分析, 生成文字是聊天程序的最基本部件，早期的聊天程序大多是基于规则 (rule-based)，后期则使用机器学习进行对话。 基于规则的聊天程序中，会有专家将用户可能会说的话和机器人应该回复的话写成上百个规则，这使得其无法处理复杂对话且难以维护。 一个著名早期例子是 1960 年代中期诞生于麻省理工学院的治疗师聊天机器人 Eliza，它用基本句法规则 (basic syntactic rules) 来理解用户打的文字，然后向用户提问。 如今的聊天机器人和对话系统多使用机器学习完成，通过上 GB 的真人聊天数据来训练聊天机器人用于客服回答，人们也让聊天机器人互相聊天。 在 Facebook 的一个实验里聊天机器人甚至发展出自己的语言，这件事被报道得很吓人，但实际上只是计算机为了提高效率在制定简单协议来帮助沟通。 ## 5.3.3 语音识别 (speech recognition) ### 发展简史 ![语音识别发展简史](/files/Gr1I4j4Oj2yvaWSHiw44) ### 识别原理 基本过程：将波形转为频谱，识别音素，转成文字。 具体示例如下： 通过麦克风内部隔膜震动的频率，捕捉信号形成声音的 “波形” (waveforms)。 ![声波](/files/jt8fdYS59xYlVWvQiCkJ) 将波形用「快速傅里叶变换」(Fast Fourier Transform, FFT) 转换为 “频谱”(spectrogram)。颜色越亮处，该频率的声音越大，类似于立体声系统的 EQ 可视化器。 ![频谱](/files/LfytPDOWlzRkKDpiZU1Q) 因为发音时人类的声带会放大或减少不同的共振，所以频谱中的信号也会呈现出螺纹状，形成或亮或暗的区域。如果从底向上看，可以标出高峰，称这些峰值为「共振锋」(formants)。 ![共振峰](/files/6DUrLxwx0r5JdGQRK3al) 通过对频谱中的 “元音及其共振峰频率组合” 标注值，电脑可以识别出元音，进而识别出整个单词。 ![元音及其共振峰频率组合](/files/WJm8uNh8p8vKRgV6u7oA) 构成单词的声音片段，称为「音素」(phonemes)。英语有大概 44 种音素，所以语音识别的本质成了 “音素识别”。 ![音素](/files/Nd0j1t5Aj7x3wkvNf1EK) 再结合分词、句子始终点确认等方法技术，就可以将语音转成文字。 ### 语言模型 因为口音和发音错误等原因，人们的单词发音有所不同，可以利用语言模型来提高识别准确度。 语言模型中会有单词顺序的统计信息，比如 n. + v. 后大概率是 + adj. 。当识别时不确定 she was 后面紧跟的词是 happy 还是 harpy，语言模型会选可能性更高的 happy。 ## 5.3.5 语音合成 早期语音合成技术，可以清楚听到音素是拼在一起的，比如 1937 年贝尔实验室的手动操作机器。 到了 1980 年代，技术改进了很多，但音素混合依然不够好，产生明显的机器人声。 如今电脑合成的声音，比如 Siri, Cortana, Alexa 好了很多，尽管它们已经非常接近，但还不够像人。 如果语音识别的效果足够好，人们用语音交互的频率会提高，这又给了谷歌，亚马逊，微软等公司更多数据来训练语音系统、提高准确率，这使得人们更愿意使用语音交互，从而形成正反馈循环。 # 5.4 机器人 (Robots) ## 5.4.1 robot 机器人是由计算机控制，可以自动执行一系列动作的机器。 外观并不重要，工厂的机械臂 (industrial arms)、无人机 (drones that fly)、辅助外科医生的蛇状机器人(snake-like medical robots)、以及人形机器人(robotic assistants)，都可以是机器人 (robot)。 有时我们会将虚拟人物称为 “robot”，但将其称作 “bot” 甚至是 “agent” 会更加合适，因为 “robot” 的潜在含义是存在于现实世界中的机器。 robot (机器人) 一词首次出现在 1920 年的一部捷克戏剧，代表人造的类人角色。该词源于斯拉夫语词汇 robota，代表农民在十九世纪欧洲封建社会的强迫劳动。 在持续了一个世纪的称呼中，机器人都是大规模生产、高效不知疲倦、看起来像人的东西，但毫无情感，不会保护自己，没有创造力。 ## 5.4.2 发展简史 ![机器人发展简史](/files/cP6VGtvWcvbNIoSBl0za) ## 5.4.3 控制原理 ### 简单控制回路 用于像是用机器爪子在轨道上来回移动这类简单的运动，可以通过 “简单控制回路” (simple control loop) 来完成，下图是一个判断当前位置和目标位置的「负反馈回路」(negative feedback loop) 示例。 ![负反馈回路](/files/6dxyr1PrAhj1QBTXyZot) 一个基本的负反馈回路由以下 3 部分组成： 1. 传感器 (sensor)：测量现实中想要控制的东西，如水压、马达位置、气温。 2. error：通过传感器来计算与目标值相差的多少。 3. 控制器 (controller)：决定怎么减小 error，控制泵/电机/加热元件或其他物理组件来做出动作。 简单控制回路适用于严格控制的环境，但现实世界中 robot 会受摩擦力、惯性力、风阻力等外力影响，比如上例中爪子如果过重则在惯性力的作用下可能会使得爪子在目标处不断来回移动。 ### PID 控制器 PID 控制器的全称是 “proportional–integral–derivative controller” (比例-积分-微分 控制器)，早期是机械设备，现在由纯软件控制。 ![PID](/files/BR1UMG0oKi04N9V2cct0) 以餐厅内递送食物的机器人为例，其设计目标是以 2m/s 的理想速度进行穿行，需要根据环境中的变化（风阻、地形 etc.）来控制马达动力的大小从而保持理想速度。 PID 控制器会根据当前速度和目标速度的数据，计算以下 3 个值： 1. 比例值 (proportional value)：实际值 (actual value) 和理想值 (desired value) 之差。 * 实际值可能是实时的，也可能存在滞后。 * “实际值”和”理想值”的差距 (比例值) 越大则约用力。 * 实行 “比例控制” (proportional control)。 2. 积分值 (integral value)：一段时间内的误差总和，辅助弥补误差。 * 如上坡可能产生误差，值过大可能比例控制得不够，需更用力 3. 导数值 (derivative value)：理想值与实际值之间的变化率。 * 有助于解决未来可能出现的错误。 * 又名 “预期控制” (anticipatory control)。 这三个值会拥有各自权重，组合使用来控制系统。PID 控制器应用广泛，比如汽车里的巡航控制、无人机用来保持水平得螺旋桨速度控制等。 ## 5.4.4 机器人的发展现状 控制回路负责将机器人的物理属性 (e.g. 当前位置) 变成期望值，这些期望值由更高层软件来负责确定，其做出计划让机器人执行。 利用技术，机器人已经取得了很多成就，比如潜入深海、探索火星。但有趣的是，许多对人类来说很简单的任务，比如双腿直立行走、开门、穿衣服、摸狗等人类无需刻意做的举动，有超级计算机能力的机器人却做不到。 这些问题最有可能通过 5.1 小节讨论过的 “人工智能” 来解决，机器人无需休息且可以多个手臂同时练习，通过数千小时的训练来变得擅长。 近年最大的突破之一是无人驾驶汽车，汽车的输入（转弯 or 变速）很简单，难得是应对路况——判断车道、理解路标、预测车流、车流中穿行、留心行人和骑自行车的以及各种障碍。 无人驾驶汽车非常依赖 5.2 节 p35 集讨论的 “计算机视觉算法”，现在也出现了外貌和行为像人类的 “类人计算机” (primitive androids)。 因可替换且力量、耐力、注意力和准确性远超人类，军队也对机器人很有兴趣。拆弹机器人和无人侦察机如今很常见，完全自主决定且全副武装的机器人也在慢慢出现。 比如韩国的三星 SGR-A1 哨兵炮，这种有智力并且可以杀人的机器人，称为「致命自主武器」(lethal autonomous weapons)。这是一个复杂又棘手的问题，一方面它可以将士兵带离战场挽救生命甚至阻止战争，但另一方面它没有人类般的判断力和同情心，会让战争更加黑暗和复杂。 ## 5.4.5 机器人三定律 科幻作家艾萨克·阿西莫夫 (Isaac Asimov) 早预见了类似于 “致命自主武器” 所带来的危险，他在 1942 年短篇小说 Runaround 中写了 “机器人三定律” (Three Laws of Robotics)，之后在 1985 年的《机器人与帝国》（Robots and Empire）又加了 “定律 0”。 ![机器人定律](/files/Qcf8jc0u0b3HN22taQQF) 简单说这些定律指导机器人的行为准则或者说道德指南，旨在让机器人不要造成伤害，特别是不要伤害人类。 这些规则实践起来相当不足，并且有很多模糊的地方，但阿西莫夫三定律激发了大量科幻小说讨论和学术讨论，如今也有专门讨论机器人伦理的会议。 阿西莫夫写这些虚构规则是为了反对 “机器人都很邪恶” 这种常见描述，他童年读的小说里，机器人脱离控制，然后伤害甚至毁灭创造者的场景很常见。但阿西莫夫认为 机器人有用、可靠，甚至可以让人喜爱。 这种技术的两面性值得我们思考，我们要认真思考计算机的潜力和危害，从而改善这个世界，而机器人最能提醒我们这一点了。 # 5.5 计算机中的心理学 (Psychology of Computing) 系统设计师 (system designers) 会综合运用社会心理学、认知心理学、行为心理学、感知心理学等学科原理，使得物理界面或计算机界面更加具有「易用度」(Usability)。 易用度是指指的是如软件这类人造物体软件达到目的的效率有多高。为了帮助人类工作，我们需要了解人类是怎么观察、思考、反应和互动的。 ## 5.5 人类感知特性 ### 视觉系统 (Visual Perception) 以视觉系统为例，人类擅长为颜色的深浅排序，而不擅长为不同颜色排序 (根据波长)。 ![颜色深浅](/files/cES1QxgeR4kTb6Y2M0rS) 因此，同色不同强度的颜色适合用于表现连续值，而不同颜色更适合用于分类或对比数据。 ![颜色区分](/files/1QPdBhzkF7v4NjiKJuU2) ### 认知系统 (human cognition) 理解人类的认知系统也能帮我们设计更好的界面，比如信息分块 (chunked) 后会更易于读取和记忆。 分块是指把信息分成更小，更有意义的块。人类的短期记忆能记住 5 到 9 个东西，保守估计是在 5 个及以下组块，因此在记忆电话号码时我们更倾向于分块记忆。 尽管对于计算机而言，分块更加耗费时间和空间且效率更低，但这对人类更有效率，因此许多界面设计也利用了 “分块”，比如下拉菜单和带按钮的菜单栏。 ## 5.5.2 直观功能 Don Norman 使得 “直观功能/功能可见性” (affordances) 这个概念在计算机领域流行起来，据他所说，“直观功能” 是在为如何操作物体提供线索，而无需提示说明。 ![affordances](/files/f8qVsyWJVyQ8zcJDtWwG) 这个概念广泛用于 3.9 节 p26 集所讨论的 “图形用户界面”，这也是图形界面比命令行更易用的原因之一。 @Carrie Anne 最喜欢的”直观功能”之一是向用户表明元素是可拖动的样式「滚花」(knurling)，其来源于现实世界中工具上用于提高握力的纹理。 ![knurling](/files/sGcTv8PaK6Qaf2nwg18g) “直观功能” 的心理学概念依据是「认出与回想」(recognition vs. recall)，这就是为什么选择题比填空题容易的原因，一般来说用感觉来触发记忆会容易得多。 ![认出与回想](/files/toVZ1cvyadsgfBRaJPdq) 图形界面用 “图标” (icons) 代表功能，比起依靠记忆来输入命令的命令行界面方便得多，无需回想功能只需认出图标即可。 而让所有菜单选项好找好记，有时候意味着用的时候会慢一些。这与另一个心理学概念「专业知识」 (expertise) 有所冲突。当我们熟悉界面之后，会建立起如何高效完成某个事情的 “心理模型” (mental models) 使得操作速度会加快。 好的界面会提供多种方法来实现目标操作，比如适用于新手的菜单栏操作，以及使用于熟练者的快捷键操作。 ## 5.5.3 情感计算 Rosalind Picard 在 1995 年关于「情感计算」 (Affective Computing) 的论文中，阐述了 “计算机会根据用户状态做出恰当反应” 的愿景。这篇论文开创了心理学、社会科学和计算机科学的跨学科结合，促进了让计算机理解人类情感的研究。 情绪会影响人类学习、沟通和决策等日常活动，“情感系统” (Affect-aware systems) 会利用传感器获得声音、表情以及出汗/心率等生物指标，结合写明人类如何表达情感的计算模型来估算用户情绪，确定怎样用最好的方式来回应用户，以达到使用户冷静/建立信任/完成作业等目标。 Facebook 在 2012 年进行了一项”影响用户”的研究，通过对时间线内容进行积极/消极内容出现频率的控制，他们发现看到积极向上内容的用户发的帖子往往更正面，反之亦然。 这个研究结果相当有争议性，显然 Facebook 和其他网站向你展示的内容会对我们产生影响，这对他们而言是机会也是责任。 由此还衍生出 “计算机程序如何回应人类” 的问题， 如果用户情绪较为负面，即使有点尴尬，电脑也应该试着积极正面地回应用户。而关于什么行为是”正确的”，这还是个开放性的研究问题。 ## 5.5.4 CMC Facebook 的研究试验是「以计算机为媒介沟通」(computer-mediated communication, CMC) 领域的极佳例子，该领域是一个很大的研究领域。 “计算机媒介”(computer-mediated) 既包括在线会议这样的 “同步通讯” (synchronous communication) ，也包括推特、邮件、短信这样的 “异步通信” (asynchronous communication)。研究人员会研究用户怎么用表情包、怎么轮换发言、以及用不同沟通渠道时的用词有什么区别等问题。 一个有趣的发现是，比起面对面沟通，人们更愿意在网上透露自己的信息。 心理学研究也表明，如果想说服某人、传授经验知识或引起注意，双方的眼神注视非常重要。在谈话时看着别人叫 “相互凝视” (mutual gaze)，这在线上场景中常常缺失，从而带来权力不平衡等副作用。 因此研究人员开发了计算机视觉和图形软件来纠正头部和眼睛的位置，使得视频时会觉得对方在直视摄像头，看着他们，这种方式称为 “增强凝视” (augmented gaze)。 ## 5.5.5 恐怖谷 在过去一个世纪，除了工业用途机器人，也有许多用于用于医疗、教育和娱乐的机器人出现。 研究机器人和人类之间如何互动的领域称为「人机交互」(Human-Robot Interaction, HRI)，该领域研究 “人类如何感受机器人的不同形式和不同行为？” “机器人如何明白人类社交暗示而非只是尴尬互动？” 等问题。 人们喜欢 “拟人化” 的物品，对计算机也不例外。我们有对 “将机器人的外表和行为做得尽可能像人一样” 的追求，1940\~50s 的机器人是完全的工业机器，但如今的类人机器越来越像真实人类，以至于某些时候会让人有种怪异不安感。 这个”几乎像人类”和”真的是人类”之间的小曲线(dip in realism)，叫「恐怖谷」(uncanny valley)。 ![恐怖谷](/files/irdVfvRipRMtNFUvU5XK) 对于机器人是否应该有人类一样的行为，也存在争议。很多证据表明，即使机器人的行为不像人类，人类也会用社交习俗对待它们。比如机器人插队或是踩脚，人们也会生气气！ 毫无疑问，心理学 + 计算机科学是强大的组合拥有可以影响日常生活的巨大潜力。这也带来了很多开放式问题。 * 你可能会对计算机撒谎，但计算机应不应该对你撒谎？如果撒谎能让你更高效更快乐呢？ * 社交媒体公司是否应该精心挑选展示给你的内容，让你在网站上多待一会儿、买更多东西？ 这类道德问题不容易回答，但心理学至少可以帮助我们理解不同选择 带来的影响和意义。 # 5.6 教育型科技 (Educational Technology) 计算机带来的最大改变之一是信息的创造和传播能力，如今的互联网的信息数据量级极高——目前有 13 亿个网站存在，仅维基百科就有 500 万篇英文文章，Google 每天提供 40 亿次搜索来访问这些信息；Youtube 上每分钟有 350 万个视频被观看，每分钟用户上传 400 小时的新视频。 尽管很多播放量是 Gangnam Style 和 Despacito，但剩下大部分内容都是教育型内容。可能获取到信息和学习不是一回事，课上提问以及上手实践等互动式课堂的学习途径当然很棒，但我们也相信教育型技术在课内课外带来的帮助。 从纸笔到用 ML 的智能系统，科技几千年来一直在辅助教育。甚至早期人类 在洞穴里画狩猎场景也是为了后代，远距离教育一直推动着教育科技的发展。 自公元 50 年左右，圣保罗 (St. Paul) 就发书信给亚洲设立的新教堂提供宗教课程。从此，自广播和电视、到 DVD 和光碟这几大技术浪潮都自称要改变教育。 事实上，在 1913 年托马斯·爱迪生 (Thomas Edison) 曾预测说：“书籍很快会过时… 用影片来教授所有知识是可能的，学校体系将在未来十年彻底改变”。显然，这还未成为现实。 ## 5.6.1 学习技巧 在讨论教育技术可以帮你做什么之前，有研究表明有些简单事情可以显著提高学习效率： （1）倍速：将学习类视频的速度调整适合自己，能理解视频内容同时也有足够时间进行思考。 （2）暂停：在困难的部分暂停。问自己一些问题看能不能回答；想想视频接下来可能讲什么，然后继续播放看猜对没有。 （3）练习：做视频中的提供的练习。即使不是程序员，你也可以在纸上写伪代码，或试试学编程。 ## 5.6.2 MOOC 把高质量教育内容做成视频传播，在过去一个世纪吸引了很多人，这个老想法的新化身则以「大型开放式课程」(Massive Open Online Courses, MOOC) 出现。 纽约时报宣称 2012 年是 MOOC 年，曾有人认为大学会就此终结，但随着热度褪去这也没能成为现实。也许是因为加大授课规模时，让很少数量的老师或是在完全没有老师的情况下教百万名学生会遇到很多问题，而这引起了 “教育科技家”(educational technologists) 的注意和兴趣。 在线上教育中，有效提供好的反馈是难题之一。有用但有些争议的做法是让学生之间提供相互的反馈，但学生既不是专家也非老师，其无法提供很好的反馈。但我们可以通过算法在数百万个选择里为学生匹配出完美的学习伙伴，也可以让算法完成一部分评分作业。 ## 5.6.3 智能辅导系统 可以提供个性化学习体验的系统泛称为「智能辅导系统」(Intelligent Tutoring Systems) ，通常使用 AI 实现。该系统需要了解用户知道什么，不知道什么，进而在正确的时间提供正确的资料，让用户练习没理解的难的部分而不是给出用户已经学会的内容。 ### 域模型 以研究代数问题的假想辅导系统为例，使用 IF-THEN 语句来描述计算过程中正确步骤所需知识的 “判断规则” (production rule)。 ![表达式规则](/files/wjLiMgmpUt7G8f3TY1VE) 同时其也可以用于代表学生常犯的错误，又名为 “错误规则” (buggy rules)。 ![错误规则](/files/ZMjffKmYCYBkatT5MKEh) 学生做完一个步骤后可能触发多个”判断规则”，系统不能完全弄清是什么原因让学生选了那个答案，因此会将 “判断规则” 会和 “选择算法” (selection algorithm) 结合使用组成「域模型」(Domain Model)，来推断学生错选的可能原因。 “域模型” 采用 “形式化表达/正式写法”来说明特定学科的知识、技能或是解题程序。但其不记录进度，无法带领学习者以正确顺序搞定学科上的所有课程，因此需要 “智能辅导系统” 来负责创建和维护 “学生模型” (student model) 。 ### 贝叶斯知识追踪 “学生模型” 中需要记录学生已经掌握的判断规则，以及还需练习的生疏部分，这将通过「贝叶斯知识追踪」(Bayesian knowledge tracing) 来明晰学生的学习情况。 贝叶斯知识追踪算法把学生的知识 当成一组值对外部不可见隐藏变量 (latent variables)，根据学生答题正确情况来更新学生对知识的掌握程度估算值。该算法记录 4 个答题概率： 1. 已经学会的概率 (probability of already learned previously) 2. 瞎猜的概率 (probability of guess) 3. 失误的概率 (probability of slip) 4. 做题过程中学会的概率 (probability of transit) 之前已经学会的概率取决于答案的正确与否，计算公式有下图 2 种，计算后更新概率值。尽管存在别的方法来追踪学生学习情况，但 “智能辅导系统” 通常用 “贝叶斯知识追踪” 处理。 ![贝叶斯知识追踪](/files/ZYcTgFkQtrNCz5HkEhsi) 为了高效地让学生不断练习技能直至掌握，软件要选择合适的问题呈现给学生，这称为「自适应程序」(adaptive sequencing)，是个性化算法的形式之一。 教师和研究人员在 APP 或网站收集上百万学习者的数据，进而从数据中观察学生回答正确率、常见错误、回答速度、观看视频时哪部分加速以及学生如何在论坛和其他人互动等。 这个研究领域称为「教育数据挖掘」(Educational Data Mining)，它能用上学生所有的 “捂脸” (face palms) 和 “啊哈” (ah ha) 时刻，用以帮助改善未来的个性化学习。 ## 5.6.4 教育科技未来 谈到未来，教育技术人员经常从科幻小说中获得灵感。比如 Neal Stephenson 的《钻石时代》(The Diamond Age) 这本书激励了很多研究人员，该书讲述了年轻女孩在书中虚拟助手的帮助下学习成长过程的故事。 如今有非科幻小说研究者，比如贾斯汀卡塞尔 (Justine Cassell) 在制作虚拟教学助手，助手可以”像人类一样沟通、有人类一样的行为，在陪伴过程中和学习者建立信任，相处融洽，甚至和人类学生成为朋友”。 此外，教育科技和设备如今在逐渐扩展到笔记本和台式电脑之外。比如巨大桌面设备让学生可以团队合作，以及小型移动设备，让学生路上也能学习，同时 “虚拟现实” (Virtual Reality, VR) 和 “增强现实” (Augmented Reality, AR) 也让人们兴奋不已。 如果猜想遥远的未来，教育可能会完全消失，直接在大脑层面进行，把新技能直接下载到大脑。尽管看起来遥远，但科学家们已经在摸索，比如仅仅通过检测大脑信号来得知某人是否知道什么。 这带来了一个有趣的问题：如果我们可以把东西下载到大脑里，我们能不能上传大脑里的东西？ # 5.7 奇点，天网，计算机的未来(The Singularity, Skynet, and the Future of Computing) “Computer science isn’t magic, but it sort of is!Knowing how to use and program computers is sorcery of the 21st century.Instead of incantations and spells, it’s scripts and code.” by Carrie Anne 计算机科学不是魔法，但它有点像魔法。学习使用电脑和编程，是 21 世纪的巫术，只不过用的不是咒语而是代码。—— 凯莉·安 ## 5.7.1 普适计算 1990 年代由马克·威泽尔 (Mark Weiser) 提出「普适计算」 ( Ubiquitous Computing) 的概念，即计算机存在于在所有可想象的东西之中。 “For (fifty) years, most interface design, and most computer design, has been headed down the path of the”dramatic” machine. Its highest idea is to make a computer so exciting, so wonderful, so interesting, that we never want to be without it. A less-traveled path I call the “invisible”; its highest idea is to make a computer so imbedded, so fitting, so natural, that we use it without even thinking about it … The most profound technologies are those that disappear. They weave themselves into the fabric of everyday life until they are indistinguishable from it.” by Mark Weiser, 1990s (五十)年来，大多数界面和计算机设计，都是朝”戏剧性”方向前进想把计算机做得超好，让人一刻也不想离开。另一条少有人走的路 是”无形”的，把计算机整合到所有东西里，用的时候很自然、完全注意不到。最厉害的科技是看不见的科技，它们融入到日常生活的每一部分，直到无法区分。——马克·威泽尔 有人把 “普适计算” 当作是 “反乌托邦” (dystopian) ，但提出者认为其具有非凡潜力。 ## 5.7.2 奇点 “普适计算” 在一定程度上可以描述计算机的未来，而在人们思考计算机的未来时经常会直接想到人工智能。但并非所有东西都需要使用 AI 或是被 AI 优化更新，就像电气革命后出现了电灯泡但蜡烛仍然存在。 最可能的情况是 AI 变成计算机科学家手中的另一门新工具，但真正让人深思和担忧的是 “人工智能是否会超越人类智能？” 这涉及许多因素，比如 “智能的准确定义是什么？”。 尽管 AI 可以在几秒内识别歌曲、驾驶汽车、翻译多种语言，但却无法完成爬楼梯、叠衣服等简单事项，人工智能成长到和人类一样通用，还有很长的路。 因为 “智能” 是难以量化的指标，人们更喜欢用处理能力来区分，但这种衡量智能的方法比较 “以计算为中心” 。以当前的发展速度来看，计算机的计算能力相当于老鼠，距离人类的计算能力似乎看起来还有些距离。 但就算处理器增长速度不再遵循 “摩尔定律” (1.10 节, p17 集)，也可能只需要十几年计算机就能赶上人类的计算速度。 ![计算速度](/files/sDY4nDy4fXOPhYxIKVIr) 假设计算机发展的趋势继续保持下去，在本世纪结束前计算机的处理能力/智能会比全人类加起来还多，然后人的参与会越来越少，人工超级智能会开始改造自己。 这种智能科技的失控性发展称为「奇点」(singularity)，由约翰·冯·诺伊曼 (John von Neumann, 2.1.2 节, p10 集) 在 1950 年代最早提出。距离其提出后 60 多年的今天，奇点仍然距离我们十分遥远。 \[!quote] “The accelerating progress of technology and changes in the mode of human life,give the appearance of approaching some essential singularity in the history of the race beyond which human affairs, as we know them, could not continue.” by John von Neumann “越来越快的技术发展速度和人类生活方式的改变，看起来会接近人类历史中某些重要的奇点，看起来会接近人类历史中某些重要的奇点，这个势头不会永远继续下去。” —— 约翰·冯·诺伊曼 一些专家认为，计算机的发展趋势会更加平缓一些，更趋向于 S 型而非指数型。而随着复杂度增加，进步会越来越难，微软联合创始人保罗·艾伦 (Paul Allen) 称之为「复杂度刹车」(complexity brake)。 ## 5.7.3 技术性失业 假设奇点到来、超智能计算机出现，这对人类意味着什么呢？关于这个问题由许多激烈讨论，其最直接的影响是 “技术性失业” (technological unemployment)——许多工作出于效率和成本的原因被计算机(AI 或是 robots) 替代了。 技术性失业并非新鲜事，比如 1800s 雅卡尔的织布机(Jacquard’s Loom, Episode 10) 带来的纺织工人失业导致了骚乱，1960s 的自动接线板代替了电话接线员，1980s 的机器喷漆代替了人工喷漆等等。 一方面，自动化使得一部分人们失去了工作。另一方面，大量产品被廉价生产。但与之前技术进步带来的技术性失业不同，专家认为 AI、robots 以及更广义的计算机会比这些更具有破坏性。 工作可以分为 2 个维度，4 种类型： * 重复性手工工作：可以让机器自动化，部分已经被替代，剩下的主部被替代。 * 非重复性手工型工作：如厨师、服务员、保安等，值得担心。 * 非重复性思维型型工作：如客服，收银员，银行柜员和办公室助理，同样值得担心。 * 非重复性思维型工作：如教师、艺术家、小说家、律师、医生和科学家等，暂时比较安全。 非重复性思维型工作占美国劳动力的 40%，意味着 60% 的工作易受自动化的影响。有人认为这种大规模失业会带来社会动荡和混乱，但也有人认为这是对将人类从无聊工作中解放的途径之一。 没人能预知未来，但长远来看一切终将归于平静，政界正在讨论的问题是怎么处理数百万人突然失业造成的短期经济混乱。 ## 5.7.4 未来幻想 “The Singularity will allow us to transcend (the) limitations of our biological bodies and brains. We will gain power over our fates. … We will be able to live as long as we want. We will fully understand human thinking and will vastly extend and expand its reach.” by futurist Ray Kurzweil “奇点会让我们超越肉体和大脑的局限性，我们能掌控自己的命运。可以想活多久活多久，我们能完全理解并扩展大脑思维。”——未来学家, 雷·库兹韦尔 超人类主义者 (Transhumanists) 认为会出现”改造人” (cyborgs)，人类通过和科技融合在一起来增强智力和身体，随着脑机接口的出现，再加上 Google Glass 和 微软 Hololens 这样的穿戴式计算机，这条界线正变得越来越模糊。 也有人预见到 “数字永生” (Digital Ascension) ，根据 Jaron Lanier 的说法，其是指 “人类的肉体死去，意识上传到计算机” (would involve people dying in the flesh and being uploaded into a computer and remaining conscious )。这种从生物体变成数字体的过程，可能是下一次进化跨越。 而其他人则预测人类大体会保持原样，但超智能电脑会照顾我们以便让我们好好享受生活。但也有人反对，为什么超级人工智能会费时间照顾我们？人类不也没照顾蚂蚁吗？ 我们无法预测未来，但关于未来的讨论非常多。等这些技术出现后，我们可以更好地进行计划。不论你把计算机视为未来的朋友或敌人，更有可能的是它们的存在时间会超过人类。 许多未来学家和科幻作家猜测，机器人会去太空殖民，无视时间、辐射以及一些其他让人类难以长时间太空旅行的因素。亿万年后太阳燃尽 地球成为星尘，也许我们的机器人孩子会继续努力探索宇宙每一个角落，以纪念它们的父母，同时让宇宙变得更好。 与此同时，计算机还有很长的路要走，计算机科学家们在努力推进过去 40 集谈到的话题。 在接下来的十几年，我们可以预想：VR/AR、无人驾驶车、无人机、可穿戴计算机和服务型机器人 会变得主流；互联网会继续诞生新服务；在线流媒体会用新方式连接人们；新的编程语言和范例会不断出现，帮助创造令人惊叹的新软件；新硬件能让神经网络和 3D 图形等复杂运算快如闪电；个人电脑也会创新，由过去 40 年的桌面电脑变为无处不在的虚拟助手。 我们在这个系列还有很多话题没有讨论，比如加密货币，无线通讯，3D打印，生物信息学和量子计算。 我们正处于计算机的黄金时代，全部总结是绝无可能的。但最重要的是你可以学习计算机成为这个惊人转型的一部分，把世界变得更好。