计算机科学速成课

计算机早期历史 Early Computing

公认最早的计算设备的算盘，注意不是中国的，而是美索不达米亚文明的，它没有计算的功能，只是用于记录数据。

最早使用计算机 computer 一词的文献是 1613 年的一本书，指的是一种职业，即负责计算的人，他们有时也会使用机器辅助计算，所以渐渐地“计算机”也代指机器。

步进计算器：由莱布尼兹发明，像汽车的里程表

• 加法：由多个齿轮组成，每当一个齿轮转过 9，它会转回 0，同时让旁边的齿轮前进一个齿

• 减法：反向旋转

• 乘除：本质上是加法或减法的叠加

• 所以它是第一台能做“加减乘除”的机器

计算表：预先算好，也就是早期的打表法，类似与字典之类的工具书，但不够灵活。

Charles Babbage 提出了“差分机”，能近似多项式，但最终没做出来，后来有人历史学家按照它的设计图做了出来，发现确实可以做到。

在做这台机器的过程中，这个人提出了一种“分析机”的概念，是“通用计算机”，和后来的冯诺依曼结构是一种东西，但实在是太超前了，当时仅存在于概念上。

此人被认为是“计算之父”

Ada Lovelace 给分析机写了假想的程序，被认为世上第一位程序员。

美国政府在 1890 年的人口普查，Herman Hollerith 发明了打孔卡片制表机，

• 打孔卡是一种纸卡，上面有网格，用打孔来表示数据。答题卡的雏形

• 当卡插入机器时，小金属针会到卡片上，如果有个地方打孔了，针会穿过孔，连通电路，电路驱动电机，给相应的齿轮+1

这人成立了制表机器公司，后来与其它机械制造商合并，成立了 IBM

电子计算机 Electronic Computing

20 世纪人口的高速增长创造了对大量计算的需求。

最大的机电计算机之一是哈佛马克一号 Harvard Mark I

大脑是继电器——用电控制的机械开关，当电流流过线圈，线圈产生电磁场，吸引金属臂，闭合电路

这个控制电路可以连接其它电路，比如马达，让齿轮+1

缺陷：

• 速度慢
• 齿轮磨损
• 继电器数量多，故障多

操作员从故障继电器中拔出一只死虫，成了 bug 的由来

热电子管：

• 把两个电极装在一个气密的玻璃灯泡里，其中一个电极加热发出电子，另一个电极吸引电子，形成电流
• 电流只能单向流动，这种电子部件叫二极管 diode
• 有人加入了第三个控制电极，就可以断开和闭合电路了

相比继电器的优点：没有会动的组件

• 磨损降低
• 开闭速度快

第一个大规模使用真空管的计算机是“巨人一号”，是第一个可编程的电子计算机，方法是把几百根电线插入插板

ENIAC 是史上第一个真正的通用、可编程、电子计算机

贝尔实验室发明了晶体管 transistor，涉及量子力学，类似于之前讲的真空管

晶体管是固态的，可以远远小于真空管，导致了更小更便宜的计算机

硅谷由此诞生，William Shockley 成立了“肖克利半导体”，里面的员工后来成立了仙童半导体 Fairchild Semiconductor，再后来成立了 Intel

布尔逻辑和逻辑门 Boolean Logic & Logic Gates

抽象 abstraction：不用管底层细节，把精力用来构建更复杂的系统

只用开/关表达信息，也就是二进制 binary

也可以使用其它的进制，如苏联搞过三进制计算机，但状态越多，越难以区分信号

布尔代数的三种基本运算方法：与、或、非

抽象：不管电路内部结构，用符号表示三种门

除此之外，异或 Xor 也很有用

二进制 Representing Numbers and Letters with Binary

以 2 为基

二进制的加法类似于竖式计算

一个 0 或 1 叫一位 bit，8 位叫做字节 Byte

KB 指的是千字节，Kb 是千比特

32 位或 64 位的计算机意思是一块块处理数据，每块是 32 位或 64 位

且计算机必须给内存中每一个位置标记上地址 address，64 位的内存地址能控制更大的内存空间

浮点数：IEEE 754 标准，类似科学记数法

表示文字：ASCII，8 位

• 以前只使用 0-128，剩下的字符是保留给各个国家自己使用的，但有些文字不够（汉字）
• 后来 128-256 作为 Extended ASCII 使用

每个国家都发明了多字节编码方案，但这些互不兼容，因而经常出现乱码，所以 Unicode 诞生了——统一所有编码的标准。

算术逻辑单元 How Computers Calculate – the ALU

计算由**算术逻辑单元 Arithmetic and Logic Unit (ALU)**处理

算术单元：

小于 2 的两个二进制数加法可以一些门表示为和与进位

抽象为一个元件：

全加器接收前一个半加器的进位：

又抽象出一个元件：

把这些元件连起来，得到：

注意到最后一位可能会溢出 overflow

现代计算机使用的加法电路为超前进位加法器 carry-look-ahead adder

当然，类似的，也可以实现减法

但是乘法和除法在嵌入式芯片中没有实现，而是依靠加减模拟，但在高端芯片中有专门的电路实现。

逻辑单元：

我们可以进一步得到 ALU 的抽象表达了：

flags 可以用来检查溢出、判断两个数是否相等、比较两个数大小

寄存器 & 内存 Registers and RAM

随机存取存储器 Random Access Memory(RAM)

通过循环电路得到能记录 0 和 1 的电路：

两者结合，得到 AND-OR 锁存器 Gated Latch：

但是复位的操作实在太让人迷惑了，我们需要控制其能否输入

太复杂了，提升一级抽象：

但是保存的数据太小了，所以需要把多个这样的锁存器合并起来，成为寄存器 register，一个寄存器能存的数字位数叫做位宽 width

如果简单地把锁存器并排放置，需要的线太多了，例如如果存 256 位要 513 条线，用矩阵可以减小线的数量

所以行和列确定了一个锁存器的位置，并控制其开关。

对于 256 位的存储来说，只要 35 条线，1 条数据线，1 条允许写入线，1 条允许读取线，16 + 16 条用于选择行列的线

某个地址的表示：几个二进制位，前面一半表示行，后面一半表示列，需要多路复用器 multiplexer转换

可以抽象了：

多个内存排列形成大内存：

抽象封装成一个整体的可寻址的内存：

内存的重要特性是：可以随时访问任何位置，所以才叫随机存取

我们做的是静态随机存取存储器 SRAM，还有其它类型的 RAM，如 DRAM，闪存，NVRAM，区别在于存单个位的电路不同，但根本上，这些技术都是矩阵层层嵌套得到的

中央处理器 The Central Processing Unit

CPU 需要一些指令去执行任务，例如有这样一份指令：

指令	描述	4 位操作码	地址或寄存器
LOAD_A	从 RAM 中读取到寄存器 A 中	0010	4 位 RAM 地址
LOAD_B	从 RAM 中读取到寄存器 B 中	0001	4 位 RAM 地址
STORE_A	将数据从寄存器 A 中写入内存	0100	4 位 RAM 地址
ADD	将两个寄存器相加，把得到的结果存到第二个寄存器中	1000	2 位寄存器 ID，2 位寄存器 ID

CPU 分为三个阶段：

• 取指令阶段 fetch phase
• 解码阶段 decode phase
• 执行阶段 execute phase

又可以抽象了：

CPU 使用时钟 clock 来管理 CPU 的节奏，所以 CPU “取指令-解码-执行”的速度叫做时钟速度 clock speed，我们平时说的 CPU 超频超的就是这个时钟的频率。

注意内存是独立在 CPU 之外的

指令和程序 Instructions & Programs

之前说的指令存在内存中，CPU 顺序读取内存中的数据并执行

其它程序可以调用已有的程序，这也是一层抽象

我们的 CPU 指令都是 8 位，内存地址比较小，所以现代计算机有两种策略解决这个问题：

• 用更多为来代表指令，比如 32 位或 64 位
• 可变指令长度，例如 HALT 不需要额外数据，可以马上执行；而 JUMP 需要位置值，这个值紧挨着 JUMP，叫做立即值 immediate value

高级 CPU 设计 Advanced CPU Designs

早期计算机的提速方式：减少晶体管的切换时间

现代 CPU 在硬件层面设计了除法，这是复杂度与速度的平衡

现代处理器有专门电路来处理图形操作、解码压缩视频、加密文档等

指令集也越来越大

CPU 速度增加了，但相应的内存速度也要增加，解决延迟的方法是：给 CPU 加一点 RAM，叫缓存 cache，这意味着 CPU 从 RAM 处拿数据时，RAM 不用一次传一个，而是传一批。cache 离 CPU 很近，速度也很快

如果想要的数据已经在缓存中，叫缓存命中 cache hit；反之，叫缓存未命中 cache miss

当 CPU 完成计算时，会将结果存在缓存中，但这样的话缓存和 RAM 不一致了，这种不一致要记录下来，后面必须同步。因此缓存里每块空间有一个特殊标记，叫脏位 dirty bit，在清理缓存腾出空间之前，会先检查脏位并返回。

指令流水线 instruction pipelining：工作并行 Parallelize 处理

但有时数据是依赖 dependent 的，所以现代 CPU 会动态排序有依赖关系的指令，叫乱序执行 out-of-order execution

条件跳转，例如 JUMP NEGETIVE，会改变程序的执行流，需要等待出结果。所以高端 CPU 会推测执行 speculative execution 接下来会走哪条路，现代 CPU 的猜测成功率超过 99%

执行取值阶段时，ALU 会闲置，所以一次性处理多条指令会更好，并增加 ALU 数量

目前所说的方法都是优化 1 个指令流的方法，可以通过多核心 Core 来同时运行多个指令流

超级计算机：很多频率很低的处理器核心

早期的编程方式 Early Programming

给机器编程的需求在计算机出现之前就有了，来自纺织业，玛丽纺织机，每一行的图案由穿孔纸卡决定

1890 年的人口普查

控制面板有很多小插孔，程序员插电线来控制程序，因此也叫插线板 plug board

后来控制面板变成了可插拔

内存价格的下降让可存储计算机成为了可能，程序和数据都存在一个地方，叫冯诺依曼结构 Von Neumann Architecture

第一台冯诺依曼结构的计算机是“宝宝”

即使如此，数据和程序还是需要纸卡才能输入计算机，但纸卡数量太多了，容易打乱，所以会在卡片侧面画对角线。

用纸卡的最大程序是美国空军的 SAGE 防空系统没错，用纸片防空

穿孔纸卡的亲戚是纸带

另一种编程方式：大量的开关控制

编程语言发展史 The First Programming Languages

程序员想要一种更通用，更软的方式编程

计算机只能理解二进制，也就是机器语言 machine language，所以人们先在纸上写“高层次的”代码，叫做伪代码 Pseudo-Code，再用操作码表把伪代码转成二进制机器码

程序员给每个操作码分配一个简单的名字，叫做助记符，其后紧跟数据，形成完整指令

二进制程序可以读懂文字指令，自动转成二进制指令，汇编语言 Assembly Language 诞生，这种程序叫汇编器 Assembler

若新增了一条指令，其后所有 JUMP 后面的地址都要改变，但汇编器会自动帮你处理这种问题，程序员可以不用管底层细节，提升了抽象维度

程序写在打孔纸带上，如果程序有漏洞物理上的，需要用胶带打补丁也是物理上的

Grace Hopper 设计了第一个高级编程语言，叫算术语言版本 0，并创造了第一个编译器 Compiler

变量 variables 是内存地址的抽象

Fortran 公式翻译 formula transformation

但最初的该语言只能跑在 IBM 计算机上，所以开发了一门通用的高级编程语言——COBOL

从此，计算机科学从深奥学科，变成了大众化工具

• 1960 年代：ALGOL, LISP, BASIC
• 1970 年代：Pascal, C, Smalltalk
• 1980 年代：C++, Objective-C, Perl
• 1990 年代：Python, Ruby, Java

编程原理——语句和函数 Programming Basics – Statements & Functions

变量，赋值语句

if 判断

while 循环

for 循环

把代码打包成函数，又一层抽象

预先写好的函数集合——库 libraries

算法入门 Intro to Algorithms

选择排序

大 O 表示法

归并排序

Dijkstra 算法

数据结构 Data Structures

数组 Array，字符串 String，矩阵 Matrix，结构体 Struct，指针 Pointer，节点 Node，链表 Linked List，队列 Queue，栈 Stack，树 Tree，二叉树 Binary Tree，图 Graph

阿兰·图灵 Alan Turing

可判定性问题：是否存在一种算法，输入正式逻辑语句，输出准确的“是”或“否”答案？

• 阿隆佐·丘奇提出Lambda 演算证明了这样的算法不存在，但较难以理解
• 图灵提出了图灵机 Turing Machine，图灵机可以实现任何计算

停机问题 Halting Problem，证明了有些问题是无法被计算的

两者结合，丘奇和图灵证明了计算是有极限的，起步了可计算性理论，现在叫丘奇-图灵论题

图灵设计了一个机电计算机，叫 Bombe，用于破解德军密码

他最有名的战后贡献是人工智能 Artificial Intelligence，并提出了图灵测试 Turing Test

图灵后来被指控为同性恋，靠药物治疗，最终服毒自杀

图灵奖：计算机界的最高奖项

软件工程 Software Engineering

这个词由 Margaret Hamilton 创造

对象 Object

面向对象编程 Object Oriented Programming

API Application Programming Interface

public, private

集成开发环境 IDE - Integrated Development Environments

调试 debugging

文档和注释 readme, comment

版本控制 Version control

质量控制 Quality Assurance testing, QA

Beta, Alpha

集成电路 & 摩尔定律 Integrated Circuits & Moore's Law

早期计算机由很多分立元件 Discrete components 组成，导致计算机太复杂了，这个问题叫做数字暴政 Tyranny of Numbers

晶体管比电子管更小更快更可靠，所以 IBM 把计算机从电子管换成晶体管

把多个组件包在一起，变成一个新的独立组件，叫做集成电路 Integrated Circuits(IC)

仙童半导体让 IC 成为现实，Noyce 被公认为现代集成电路之父

但 IC 还是需要连起来，所以发明了印刷电路板 printed circuit board(PCB)，通过蚀刻金属线的方式，把零件连接到一起

为了实现更复杂的设计，光刻 Photolithography 登场

摩尔定律：每 18 个月相同空间能塞下的晶体管数量翻倍

VLSI 软件，用来自动生成芯片设计

进一步小型化的 2 个大问题：

• 光的波长不足以制作更精细的设计
• 量子隧穿效应

操作系统 Operating Systems

放程序的时间太长，需要一种方式让计算机自动运作，于是操作系统 Operating Systems诞生了。

操作系统也是程序，但它有操作硬件的特殊权限，可以运行和管理其它程序，一般是开机第一个启动的程序，其它所有程序由 OS 启动

第一个操作系统加强了程序加载方式，可以一次多个，当运行完一个程序时，会自动运行下一个

计算机的配置不同，程序员需要考虑和早期的外部设备交互，而程序员无法拿到所有的设备，所以那时只能“祈祷程序能运行”现在不也是吗？

操作系统充当软件和硬件的媒介，提供 API 来抽象硬件，叫设备驱动程序 device drivers，程序员和**输入输出硬件(I/O)**交互

电脑速度快，而打印机之类较慢，所以处理器经常闲着。Atlas Supervisor 操作系统还能在单个 CPU 上同时运行几个程序，即多任务处理 multitasking。

每个程序都会占一些内存，操作系统会把内存地址虚拟化，叫做虚拟内存 Virtual Memory，程序可以假定内存总是从地址 0 开始，而实际物理位置被操作系统抽象了。从程序的角度看，它获取的内存是连续的，而实际上是不连续的。这种机制使得程序的内存大小可以灵活增减，叫动态内存分配 dynamic memory allocation。同时，如果一个程序出错，不会影响其它程序，叫内存保护 memory protection

计算机不仅能同时运行多个程序，还能让多用户同时访问，多个用户用终端 terminal访问计算机，每个用户只能使用一小部分处理器、内存等，成为服务器的雏形。

多用户分时操作系统 Multics 从设计时就考虑安全，但被认为过度设计了，功能太多了。所以有人打造了 Unix，把操作系统分成两部分：

• 核心功能，叫内核 kernel
• 程序和运行库

如果有错误发生，就让内核恐慌 panic，机器崩溃，是蓝屏的起源

内存 & 存储介质 Memory & Storage

存储器 Storage 中的数据断电不会丢失

最早的存储介质是打孔纸卡和打孔纸带

延迟线存储器 Delay Line Memory：

缺点：

• 想访问一个特定的 bit，必须等待它从循环中出现，所以又叫顺序存储器 sequential 或循环存储器 cyclic-access memory

• 增强内存密度困难

磁致伸缩延迟存储器 magneto strictive delay lines 用金属线的振动来代表数据

磁芯存储器 magnetic core memory：如果给磁芯绕上电线，并施加电流，可以将磁化在一个方向，磁芯排列成网格。

磁带 tape

虽然磁带驱动器很贵，但磁带很便宜，因此磁带至今仍用于存档

缺点：访问速度慢，是连续的

类似的有磁鼓存储器 Magnetic Drum Memory：金属圆筒，盖满了磁性材料，滚动读取数据

磁盘 disk：和前者类似，一个读/写磁头会上下移动，直到找到正确的磁盘，磁盘也会高速旋转，花费的时间叫做寻道时间 seek time

软盘，除了是软的，和硬盘没什么区别

光学存储器，光盘 CD 和 DVD，光盘表面有很多小坑，造成光的不同反射，光学传感器捕获到并解码为 0 和 1

固态 solid state：没有机械活动部件，里面是集成电路，称为 SSD

文件系统 Files & File Systems

文件格式：可以随便存文件数据，但按格式存会更方便

TXT 文本文件：ASCII

WAV 音频文件：

• 在读取数据前，有关于数据的数据——元数据 meta data，在文件开头，所以也叫文件头 Header

• 元数据中包括码率 bit rate，单声道或双声道等

• 每秒上千次的音频采样数字

BMP 图片文件：

• 元数据有图片宽度、高度、色深

• 像素的红绿蓝 RGB 值

为了存多个文件，需要一个特殊文件记录其它文件的位置，叫做目录文件 directory file，经常在开头，如果修改或增删了文件，必须修改目录文件内容

存的内容：

• 该目录下所有文件的文件名 + 扩展名
• 文件的元数据，如创建时间、最后修改时间、文件所有者、读写权限
• 文件的起始位置和长度

平面文件系统 flat file system，文件都在同一个层次

把文件前后排在一起，前面文件增添会覆盖后面文件

现代文件系统会：

• 把空间划分成一块块，有一些预留空间可以移动

• 拆分文件，存在多个块中

• 像删掉某个文件，只需要在目录文件中删掉那条记录，没有擦除在磁盘上的记录，所以有时数据可以恢复

• 一个文件存在多个块中，有很多碎片 fragmentation，碎片较多影响机械硬盘速度，所以需要定期碎片整理 defragmentation

• 目录可以嵌套，在同一个根目录 root 下的文件移动只要修改目录内容就行了

文件系统提供了一层抽象，使我们不必关心文件在磁盘的具体位置

压缩 Compression

优点：能存更多文件，传输更快

游程编码 Run-Length Encoding：把 00000 视为 5 个 0

无损压缩 Lossless compression：有些时候不希望文件内容改变，例如文本文件

哈夫曼树 Huffman Tree

有损压缩：有一些人类无法感知的数据，删掉这些数据的方法叫感知编码 perceptual coding，如 jpeg

因为视频前后画面往往差距不大（时间冗余 temporal redundancy），往往通过比较帧之间的差异来压缩，但压缩太严重会导致花屏

命令行界面 Keyboards & Command Line Interfaces

计算机早期同时输入程序和数据（用纸卡/纸带），尽可能迁就机器，对人类好不好用是其次，“翻译”的负担就落到了程序员身上。

程序运行开始直到结束，中间没有人类进行操作，因为计算机很贵，不能等人类慢慢输入，执行完的结果打印在纸上。

数据录入机制：键盘

• 肖尔斯 QWERTY 布局

• 十指打字和盲打的发明

电传打字机 teletype machine：可以用电报线发送和接收文本，有电子接口，可以适用于计算机

输入一个命令，敲回车，计算机会输回路，叫命令行界面 command line interfaces

后来屏幕的价格下降，但直接沿用了以前的方法，把屏幕视为无限大的纸

最早的纯文字的 galgame

屏幕 & 2D 图形显示 Screens & 2D Graphics

早期计算机键盘和屏幕是分开的，因为屏幕无法显示清晰的文字，数据往往打印到纸上，屏幕的用途是跟踪程序的运行情况

阴极射线管 CRT，描绘图形的方法：

• 引导电子束描绘出形状，叫矢量扫描 vector scanning
• 按固定路径，一行行来，从上到下，从左到右，不断重复

可以在屏幕上显示清晰的点，叫像素 pixels

液晶显示器 LCD 也用光栅扫描，多次更新

早期计算机不用像素，因为内存不够，所以存符号，需要一种硬件从内存读取字符，转换成光栅图形，显示在屏幕上，叫字符生成器，是第一代显卡。它内部有一小块只读存储器 ROM 存着每个字符的图形，叫点阵图案。字符生成器会访问内存中一块特殊区域，该区域专为图形保留，叫屏幕缓冲区 screen buffer，想显示文字时，修改这块区域里的值就行。

出现了字符画

矢量模式：所有形状都由线条组成。矢量指令（一组画图的程序）存在内存中，通过矢量图形卡画到屏幕上。程序可以更新这些值，让图形随时间变化——动画。

Sketchpad 一个交互式图形界面，用途是计算机辅助设计 CAD，第一个完整的图形程序

输入设备：光笔——笔尖用光线传感器检测显示器的刷新，通过判断刷新时间，电脑可以知道笔的位置，可以画形状了

位图显示。计算机把像素数据存在内存中一个特殊区域，叫帧缓冲区 frame buffer，后来存在高速视频内存 VRAM 里，VRAM 在显卡上

很多早期的显示器不能显示白色，更像绿色

程序员调用预先写好的绘图函数，画直线、曲线、图形、文字等，一层抽象

冷战和消费主义 The Cold War and Consumerism

冷战导致美国往计算机领域投入大量资源

范内瓦·布什预见了计算机的潜力，提出假象机器 Memex，帮助建立国家科学基金会，给科学研究提供资金

1950 年代消费者开始买晶体管设备，收音机大卖

日本取得晶体管的授权后，索尼做了晶体管收音机，为日本半导体行业崛起埋下种子

苏联 1961 年把宇航员加加林送上太空，导致美国提出登月

NASA 预算大大增加，用集成电路来制作登月计算机

集成电路的发展实际上是由军事应用大大推进的，美国造超级计算机进一步推进集成电路

美国半导体行业一开始靠政府高利润合同活着，忽略消费者市场，1970 年代冷战渐消，行业开始衰败，很多公司倒闭，英特尔转型处理器

总结：政府和消费者推动了计算机的发展

• 早期靠政府资金，让技术发展到足够商用
• 然后消费者购买商用产品继续推动产品发展

个人计算机革命 The Personal Computer Revolution

1970 年代初成本下降，个人计算机变得可行

Altair 8800

比尔·盖茨和保罗·艾伦写 BASIC 解释器

乔布斯提议卖组装好的计算机，Apple-I 诞生也奠定了苹果以后卖的产品很贵的路线

1977 年出现 3 款开箱即用的计算机

IBM 意识到个人计算机市场，IBM PC 发布，采用开放架构，兼容的机器都叫 IBM Compatible（IBM 兼容）

生态系统产生雪球效应：

• 因为用户多，软硬件开发人员更愿意花精力在这个平台
• 因为软硬件多，用户也更乐意买“IBM 兼容”的计算机

苹果选择封闭架构，一切都自己来，只有苹果在非“IBM 兼容”下保持了足够的市场份额

图形用户界面 Graphical User Interfaces

图形界面先驱：道格拉斯·恩格尔巴特，创造了第一个鼠标，演示了视频会议、实时协作编辑文件等当然，就像所有超前太多的技术一样，失败了

施乐公司将 2D 屏幕当作桌面，用户可以打开多个程序，每个程序在一个框里，叫窗口，桌面配件可以移动

设计界面：窗口、图标、菜单、指针——WIMP 界面

GUI 是事件驱动编程 event-driven programming，代码可以在任意时间执行以响应事件

施乐之星系统发布

• 扩展了“桌面隐喻”，文件看起来像一张纸，还可以存在文件夹里，这些都可以放桌面上，或数字文件柜里，从用户的角度看，是一层新抽象

• 剪切、复制、粘贴的术语来自编辑打印机文件物理意义上的剪——粘

• 无论你在计算机上做什么，文件打印出来应该长得一样，所见即所得

当然最终失败了

乔布斯参观了施乐公司

• 发布 Apple Lisa，第一款有图形界面和鼠标的产品，但太贵了，果然失败了
• Macintosh 较便宜，大卖

3D 图形 3D Graphics

3D 投影：把所有的点从 3D 转成 2D。

• 正交投影
• 透视投影

可以用画 2D 线段的函数连接这些点，叫线框渲染 Wireframe Rendering

如果想画立方体这种简单的图形，直线就够了，但更复杂的图形，三角形更好，因为三点确定一条直线。在 3D 图形学中，称三角形为多边形 Polygons

平衡角色的真实度和多边形数量

填充图形的算法：扫描线渲染 Scanline Rendering

减轻边缘锯齿的方法：抗锯齿 Antialiasing，判断多边形切过像素的程度来调整颜色

多边形到处都是，有些被遮挡 occlusion 了。

处理方法：

• 排序算法，从远到近排序，从远到近渲染，也叫画家算法
• 深度缓冲 Z-Buffering，渲染时保留最近的多边形的颜色

距离相同时会随机选择，出现 Z-fighting 效果

3D 游戏有个优化叫背面剔除 back-face culling，即不渲染永远不出现的一面，如地板的背面

明暗处理 shading：物体表面有明暗变化，表面面对的方向叫表面法线

纹理 textures：外观，将多边形坐标和纹理坐标对应起来

做专门的硬件来加速，并行渲染，该硬件叫 GPU，周围有专用的 RAM，所以的网格和纹理都在里面，可以高速访问

计算机网络 Computer Networks

球鞋网络，在公司内部

• 方便消息交换
• 共享物理资源

计算机近距离构成的小型网络叫局域网 LAN

LAN 技术：以太网 Ethernet，最简单形式为一条以太网电线连接数台计算机，以太网需要每台计算机有唯一的媒体访问地址 （MAC 地址）

多台计算机共享一个传输媒介，叫载波侦听多路访问 CSMA，载体 carrier 指传输数据的共享媒介，以太网的载体是电缆，Wi-Fi 的载体是空间

两台计算机想同时写入数据，叫冲突 collision，当计算机检测到冲突，就会在重传之前等待一段时间，若重传发现仍然冲突，则说明网络拥堵，等待时间翻倍，这种方法叫指数退避 exponential backoff

载体和其中的设备总称冲突域 collision domain，可以用交换机 switch 把它拆分成多个冲突域，其会记录哪个 MAC 地址在哪边网络，必要时在两个网络间传数据

从一个地点到另一个地点通常有多条路线——路由 routing

A 和 B 之间有专有线路：电路交换

报文交换 message switching：消息会经过好几个站点，消息沿路由跳转的次数叫跳数 hop count，某条消息的跳数很高就出错了，叫跳数限制 hop limit

大报文分成很多小块，叫数据包 packets，报文具体格式由互联网协议 IP 定义，每台联网的机器都要 IP 地址

路由器会平衡与其他路由器之间的负载，叫阻塞控制 congestion control

去中心化，分组交换，全世界路由器协同工作

互联网 The Internet

广域网 WAN 的路由器属于互联网服务提供商 ISP

IP 数据包头部只有目标地址，所以不知道该把数据交给哪个程序

用户数据报协议 UDP 也有头部，信息之一为端口号，还有校验和 checksum，通过把数据求和来检查数据是否正确，UDP 无法确认是否正确送达，所以有时会丢包

总结：

• IP 负责把数据包送到正确的计算机
• UDP 负责把数据包送到正确的程序

传输控制协议 TCP，所有数据必须送达，相比 UDP

• 头部还有序号，保证了数据包可以正确排序

• 要求接收方的电脑检查无误后，给发送包发一个确认码，若一段时间没收到确认码，则重发

• 可以同时发多个数据包

• 确认码的成功率和来回时间可以推测网络的拥堵程度，用这个信息调整同时发包的数量，解决拥堵问题

缺点：数据包数量太多了，效率低

域名系统 DNS：将域名和 IP 地址一一对应

域名结构：

• 顶级域名：.com
• 二级域名：google.com
• 子域名：images.google.com

得到了一层新抽象

万维网 The World Wide Web

万维网运行在互联网上，通过浏览器 web browsers 访问万维网

万维网的基本单位的页面 page，页面有内容和去往其他页面的链接——超链接 hyperlinks，文字超链接叫超文本 hypertext

每个网页需要一个唯一的地址，叫统一资源定位器 URL

超文本传输协议 HTTP，HTTP 的请求前有状态码，如 404

超文本标记语言 HTML，层叠样式表 CSS，JavaScript

Tim Berners-Lee 在 CERN 工作的业余时间写了第一个浏览器，并建立了 URL，HTML，HTTP

起初人们会维护一个目录，链接到其他网站，Jerry 和 David 的万维网指南，后来改名成 Yahoo

搜索引擎使用爬虫并维护索引

谷歌的算法：看其他网站有没有链接到这个网站，即反向链接的数量代表了网站质量

网络中立性 net neutrality：应该平等对待数据包

计算机安全 Cybersecurity

• 保密性 secrecy：只有有权限的人才能读取计算机系统和数据
• 完整性 integrity：只有有权限的人才能使用和修改系统和数据
• 可用性 availability：有权限的人应该随时可以访问系统和数据

安全专家想象敌人可能是谁，叫威胁模型分析 threat model，模型想象攻击者的手段叫攻击矢量 attack vector

身份认证 authentication

• 你知道什么
• 你有什么
• 你是什么

两种或两种以上的认证方式：双因素认证 two-factor

访问控制 access control 通过权限或访问控制列表 ACL 来实现

• 读 read
• 写 write
• 执行 execute

不能向上读，不能向下写——Bell-LaPadula 模型

安全内核——代码越少越好

验证代码安全性的方法：独立安全检查和质量验证，即让一群安全行业内的软件开发者来审计代码，所以安全型代码往往是开源的

不让被攻破的程序危害到计算机上的其他东西叫隔离 isolation

沙盒 sandbox：给每个程序独有的内存块，其它程序不能动

虚拟机 virtual machine：模拟计算机，每个虚拟机在自己的沙箱里

黑客 & 攻击 Hackers & Cyber Attacks

社会工程学 social engineering：欺骗别人让人泄密信息，即电信诈骗最强的黑客总是用最原始的方法

• 钓鱼邮件 Phishing
• 假托 Pretexting：冒充工作人员
• 木马

因为密码失败次数过多会完全锁住，所以有 NAND 镜像的方法，即复制整个内存，每次尝试后重置内存，即可继续尝试密码

漏洞利用 exploit：

• 缓冲区溢出 buffer overflow：密码在内存中的 buffer 后跟着数据，黑客输入过长的密码使数据溢出，从而达到修改数据的目的，防止的方法有：
  • 边界检查
  • 随机存放变量在内存中的位置
  • 在 buffer 后留一些不用的空间，检查其中的值是否变化，这些内存空间叫金丝雀 canaries，因为以前矿工会带金丝雀下矿，金丝雀会警告危险
• 代码注入 code injection：攻击数据库，在用户名中输入命令，防止方法：
  • 禁止使用特殊字符
  • 清理输入

软件的制造者不知道软件有新漏洞被发现了，该漏洞叫零日漏洞 zero day vulnerability

拒绝服务攻击 DDos：阻塞服务器

加密 Cryptography

多层防御 defense in depth

加密 encryption，解密 decryption

替换加密 substitution ciphers：把每个字母替换成其它字母，但字母的出现频率是一样的，易被猜出来，如凯撒密码

移位加密 permutation ciphers：调整字母的排列顺序

数据加密标准 DES：56 bit 的密钥，位数太少了，现在易破解

高级加密标准 AES：128/192/256 位密钥，将数据切成一块一块，每块 16 个字节，用密钥进行一系列替换加密和移位加密，重复 10 次左右，在性能和安全性间取得平衡

传递密钥的方法：密钥交换 key exchange，例如使用单项函数，很容易算出结果，但很难从结果推算出输入

• 公钥，私钥传递
• 迪菲-赫尔曼密钥交换 Diffie-Hellman Key Exchange：模幂运算，双方用一样的密钥加密和解密消息，叫对称加密

非对称加密：用公钥加密消息，用私钥解密；或用私钥加密，公钥解密。用于服务器签名。RSA

机器学习 & 人工智能 Machine Learning & Artificial Intelligence

做分类的算法叫分类器 classifier

把数据简化为特征 features，用来帮助分类的值

机器学习算法的目的是最大化正确分类 + 最小化错误分类

• 决策边界
• 未标签数据

把决策空间切成几个盒子的方法可以用决策树 decision tree 表示

也有不用树的方法，如支持向量机 support vector machines，本质上用任意线段来切分决策空间，不一定是直线

这些算法都运用了统计学的知识，但也有用生物学的——人工神经网络 artificial neural networks

• 神经元可以接收多个输入，整合并发出一个信号
• 被分成一层层
• 每一个神经元：对每一个输入乘不同的权重，求和，最后减去一个偏差
• 激活函数：应用于输出，对结果执行最后一次数学修改

弱 AI 或窄 AI：只能做特定任务

强化学习 reinforcement learning：自我提升

计算机视觉 Computer Vision

核 kernel 或过滤器 filter

• 检测竖直边缘的核叫 Prewitt 算子
• 有的核能够锐化图片
• 核也可以匹配特定形状
• 维奥拉·琼斯人脸检测算法

卷积神经网络 convolutional neural networks：

• 给神经元输入二维像素就像卷积
• 神经网络可以学习对自己有用的核

自然语言处理 Natural Language Processing

分析树 parse tree：标了每个单词的词性和句子的结构

聊天机器人使用大量规则

语音识别 speech recognition：通过快速傅里叶变换 FFT 将波形图转化为谱图 spectrogram，不同的共振峰可以识别构成单词的声音片段——音素 phonemes

使用语言模型 language model 来提高识别的准确率

语音合成 speech synthesis：让计算机输出语音

机器人 Robots

没有电子部件的机器叫自动机 automatons

• 吃饭鸭
• 土耳其行棋傀儡

计算机数控机器 （CNC 机器）：控制精细

Unimate：把压铸机做出来的热金属提起来，然后堆起来

负反馈回路 negative feedback loop：

• 传感器
• 控制器
• 系统

比例-积分-微分控制器 （PID 控制器）：比例专注当下，积分记仇，微分看下一步

控制回路负责把机器人的属性变成期望值，这些值由更高层的软件制定

机器人三定律

计算机心理学 Psychology of Computing

易用性 Usability

• 人类擅长给颜色强度排序，所以用颜色强度作比较
• 人类不擅长颜色排序，所有颜色用于区分不同的对象

分组更好记

直观功能 Affordances：旋钮用来转，插槽用来插东西

认出和回想 recognition & Recall：图标

让机器有一定情商

用软件修正注视位置，让视频通话时看起来像盯着对方，而不是盯着下方

把机器人做的像人，恐怖谷理论

教育科技 Educational Technology

通过调速、暂停等技巧，加强学习效率

大型开放式在线课程 Massive Open Online Course(MOOC)

智能辅导系统 Intelligent Tutoring Systems

判断规则 + 选择算法：域模型，可以用来帮助学习者解决特定问题

贝叶斯知识追踪

• 学生已经学会的概率
• 瞎猜的概率
• 失误的概率
• 做题过程中学会的概率

教育数据挖掘 Educational Data Mining

奇点，天网，计算机的未来 The Singularity,Skynet and the Future of Computing

普适计算 Ubiquitous Computing

奇点

把工作分为 4 个象限

人类从生物体变成数字体最后一层抽象