Crash Course Computer Science（21-30）

P21 压缩

前面提到，位图文件存储的是RGB数据，有时候一张图片很大，而我们想更快地把它发给朋友，这时候就需要用到 压缩（compression），一种简单的压缩方法是游程编码，例如连续7个像素点都是黄色，与其用7个一样的RGB数据，不如在前面加个7代表7个，再接1个RGB数据即可。这种压缩方法适合经常出现相同值的文件，并且可以轻易地复原，叫做 无损压缩。1950年代，麻省理工学院学生哈夫曼发明了一种高效编码方式，叫做 哈夫曼树（Huffman Tree），将出现频率高的块用短编码，频率低的用长编码，用树结构和字典来映射。

可以看到，上面两种方法的思路分别是消除冗余和用更紧凑的表示方法。几乎所有的无损压缩都用了这两种方法，如 gif、png、pdf、zip

然而，并不是所有的数据都需要无损。像音频文件，有些超声波部分完全可以抛弃，因为人类听不到，图像和视频也是，有时候我们并不追求超清画质，只要能看到图片是什么就够了。这时候太过细致的细节会被模糊化处理，这就是 有损压缩 。著名的例子是 mp3 和 jpeg 。

P22 命令行界面

早期计算机都是通过纸带和插线板一次性获取输入数据，计算完成后一次性输出到纸带。到了1950年代开始，小型机开始出现，大型机也慢慢有了多任务和分时系统的概念，于是 交互式 产生了。当时人们就借助了键盘来输入数据，通过电传，计算机能很快接收到键盘的输入然后显示，再根据输入的内容做出文字反馈，这种人类与计算机交流的方式叫做 命令行，用于交互的键盘和屏幕叫做 终端。

虽然命令行只能显示文字，十分原始，但由于其性能高，即便是在今天，也有很多程序员喜欢用命令行，尤其是访问远程计算机时。

P23 屏幕&2D 图形显示

屏幕显示技术最早最有影响力的是 阴极射线管（CRT），原理是把带电粒子发射到涂层上，通过磁场来控制方向。在屏幕上显示清晰的点叫做 像素（pixel），液晶显示器就是通过改变每个像素的颜色来显示图像的。

前面提到 ASCII 码通过把二进制数字映射成英文符号显示在屏幕上，映射的过程是由 字符生成器 来完成的，基本上算是第一代显卡。为了让屏幕可以显示任意画面，而不仅仅是字符，同时为了节省内存，人们用矢量画图的方式来绘制图形，屏幕上所有的一切都是由线组成。

1960年代，出现了真正内存中的一个位对应一个像素的图形界面，叫 位图显示。图形就是一个巨大的像素值矩阵，计算机把像素数据存在特殊的区域，叫做 帧缓冲区，一开始缓冲区在内存里，后来存在 高速视频缓冲（VRAM） 里，VRAM在显卡里面，而不是内存，这样访问更快。程序员预先写好了一些例如画直线、画圆、文字等函数，然后再在此基础上调用，从而绘制出丰富的图形界面。

P24 冷战和消费主义

1940年代，美国和苏联开始冷战，科技成了不可小觑的力量，而计算机是科技的中流砥柱，但由于其高成本，只有政府才负担得起。当时两个美苏都在争第一，所以在计算机研发上投入了大量的资金和人力，这促进了计算机科学的发展。之后，由于苏联宇航员抢先登上太空，不甘落后的美国发起了“阿波罗登月计划”，阿波罗的导航是首次使用集成电路的典例，且这个计划投入了40万人力，计算机技术借此得以飞跃发展。1950年代美国成立了国家科学基金会，该机构至今都在给美国科学研究提供政府资金，美国的科技之所以领先，主要原因之一就是这个机构。

1950年代，消费者开始购买晶体管设备。此时战后的日本开始寻找新的工业机会，日本公司很快取得了晶体管的授权，开始振兴日本的半导体和电子行业，其中就包括收音机，日本设备以低利润为特点开始大量售出，而美国企业一开始就是跟政府签订高利润的合同，忽略了消费者市场，因此在消费者领域人们更愿意购买便宜好用的日本产品。

到了1970年代，冷战和太空竞赛褪去，美国企业失去了高利润的政府合同，变得更难竞争了，这导致了美国公司规模的缩小、裁员，甚至倒闭，其中就包括英特尔1974年大裁员，1979年仙童半导体濒临倒闭而被收购。美国公司的无力最终导致了日本公司如夏普、卡西欧等的崛起，以至于1970年代随处可见日本的电子产品。

在消费的刺激下，集成电路的成本越来越低，出现了各种各样的产品，电视、街机、手持计算器，最终催生了家用个人计算机。

P25 个人计算机革命

计算机成本的下降和性能的提升，让个人计算机成为可能。第一台取得成功的商业个人计算机是 MITS 公司的 Altair 8800 ，需要自己组装，而且编写的是机器码。彼时19岁的比尔盖茨和22岁的艾伦保罗向 MITS 公司提议在 8800 上运行 BASIC 程序，并答应为其编写 BASIC 的 **解释器(Interpreter)**，解释器是一种将 BASIC 语言转换成机器码的程序，解释器跟编译器的区别是，前者是在程序运行时转换，而后者是在运行前。后来他们真的做出来了，于是 Altair BASIC 成了微软公司的第一款产品。

Altair 8800的问世聚集了很多计算机爱好者的聚会，一次聚会上24岁的斯蒂夫·沃兹尼亚克突发奇想说要设计自己的计算机，它的设想是把计算机连接到电视显示并提供文本界面，沃兹的大学朋友斯蒂夫·乔布斯建议说不如直接出售组装好的主板，于是，Apple-I 问世了。

个人计算机的发展引起了行业大佬IBM的注意，IBM让十二名精干的工程师从零设计了 IBM PC，立马获得了成功。它提供了开放式架构，叫做 IBM Compatible （IBM兼容），使得第三方可以提供硬件或外设，包括显卡、声卡、硬盘等。很快，康柏和戴尔也开始卖PC了，而且采用的就是 IBM 兼容的架构，微软也很乐意给他们提供 MS-DOS 操作系统，IBM硬件+微软软件 的生态很快建立起来。

然而，苹果还是坚持采用封闭式架构，自己做机器，自己做系统，甚至卖得还不错。为了在IBM+微软的夹攻中体现竞争力，1984年，Macintosh 问世了，这是第一款采用了图形界面的个人计算机！

P26 图形用户界面

尽管第一台消费者可以购买到的图形界面个人计算机 Macintosh 是 1984 年才发布的，但图形界面的研究1960年代就开始了。恩格尔巴特算是对图形界面贡献比较大的人，尽管他的尝试在商业上失败了，但还是获得1997年的图灵奖。他在施乐公司工作，他们的研发团队将2D屏幕当作桌面，就像今天我们在用的一样，每一个程序都有一个窗口，窗口和窗口之间可以堆叠。然后用鼠标操作指针移动，用键盘输入内容。程序窗口有许多可复用的元素，文本框、按钮、滑动条、标签页等，GUI程序就是由这些小组件构成，而且是 事件响应驱动 的，并非顺序执行。

1979年，乔布斯参访了施乐公司，看到了他们如此酷的设计，决定跟施乐合作，后来他说，就像拨开了眼前的一层迷纱，我可以看到计算机产业的未来。之后，乔布斯回到苹果，开始图形界面的开发，并在1984年的 Macintosh 上大获成功。但没过多久，其他个人计算机的图形界面也赶了上来，加上当时苹果公司内部的混乱，乔布斯被赶出了苹果公司，给微软有机可乘，微软随即发布了 Windows 1.0，并在10年的时间里吃掉了95%的个人计算机的操作系统份额，其中就包括微软的第一个图形操作系统 Windows 95。

P27 3D图形

投影和多边形

将 3D 的物体通过投射的方式，显示在 2D 的屏幕上，就是 3D 投影。如果正方体各个边在投影中也互相平行，叫做 正交投影，如果会在远处收敛于一点，则叫做 透视投影。在复杂的场景中，通常用三角形来绘制图案，三角形在图形学中称为 多边形，一堆多边形的集合叫做 网格。网格数量和精细度呈正比。

渲染

线框绘制好后需要填充，经典的填充算法是 扫描性渲染，它会找到三角形最大和最小的Y值，然后从上往下逐行填充颜色，如果像素不高，就会产生很多锯齿。一种解决办法是 抗锯齿，原理很简单，即边缘部分用较浅的颜色来渲染。

在 3D 场景中，经常有画面堆叠的情况。这叫 遮挡。常用 画家算法 来计算遮挡。先画远的，再画近的。再用扫描性渲染来填充。但是这种算法需要先对多边形的远近进行排序。

还有一种算法叫 深度缓冲（Z-buffering），是通过数值来记录多边形的远近，如果更远的部分被更近的遮挡，就不渲染。这种算法因为不用排序，所以会更快。但是这种算法有个有趣的现象，如果两个多边形距离一样，谁画在上面？而且浮点数计算往往不够准确，导致结果不可预测，因此在一些 3D 游戏中，经常出现 Z-Fighting 现象，同一个地方画面颜色变来变去。此外，在一些 3D 游戏中，往往会忽略多边形背面的渲染，来加快渲染速度，但坏处是如果遇到bug进入了多边形内部，会看到消失的画面。

在 3D 场景中，同样也需要明暗处理，最简单的是用 平面着色 照明算法，后来又开发了其他优化算法。此外，3D 中还需要 纹理化 让网格得到特殊外观。此处就不展开讲了。

GPU

总而言之，在 3D 渲染中需要用到大量的计算，CPU不是专门为此设计的，因此工程师们做了专门的处理器—— GPU ，图形处理单元，放在显卡上面，能够进行大规模并行计算，现代GPU每秒能处理上亿个多边形！

P28 计算机网络

局域网

计算机网络的诞生是为了方便信息交换和共享物理资源。计算机近距离构成的小型网络称为 局域网（LAN），最广泛使用的局域网技术是 以太网，用一条电缆连接多台电脑，用电信号传输，由于以太网不会区分信号是要传给谁的，大家都能接收到相同的信号，所以需要每台计算机都有一个物理地址（mac），只监控传给自己的电信号。像共享电缆这样，多台电脑共享一个传输媒介，称为 载波侦听多路访问（CSMA），以太网的载体是铜线，Wi-Fi的载体是空气。载体传输数据的速度叫做 带宽（bandwidth）。共享载体带来的一个弊端是容易冲突，大家都有数据要发，产生信号混乱，解决办法是 指数退避，当有冲突时按指数时间递增延迟发送。即便如此，在较大的局域网中还是很容易产生冲突，于是人们使用 交换机 来减少冲突域。

路由和IP协议

在大型局域网中，计算机之间的通路可能有多条，这就产生了 路由（routing）。两台相隔较远的计算机通信，最开始是使用专用电路线路，叫做 电路交换，缺点是价格昂贵且不灵活。另一种方法是 报文交换，途中会经过好几个站点，就像邮局送信一样，好处是可以使用不同的路由，提升容错且更可靠，坏处是如果报文过大会阻塞路由。于是人们把将大的报文分成多个小块，叫做 数据包（packets），这种方法称为 分组交换。报文和分组的格式由互联网协议（Internet Protocol，IP）定义，每台联网的计算机都需要一个 IP 地址。路由器 会平衡与其他路由器的负载，叫做 拥塞控制。同一个报文的不同数据包，可能会经过不同的路由线路，最后到达目的地后再按顺序拼接起来，顺序问题由 TCP/IP 协议来解决。分组交换的好处是它是去中心化的，没有中心权威机构，也没有单点失败问题。

如今，不仅仅是PC、手机接入计算机网络世界，形成互联网，一些智能家电也有了网络功能，构成了 物联网。

P29 互联网

UDP

互联网是一个巨型分布式网络，大数据会被拆分成一个一个数据包传输。数据包的格式遵循IP协议，即在数据包的头部加上元数据注明要发给谁，但如果只有IP协议，对方不知道这是哪个应用程序需要的数据，于是人们在IP协议之上开发了更高级的协议。例如 用户数据报协议（UDP） 在数据前加UDP头，指明了端口号，端口号是应用程序访问网络时，需要向操作系统申请的识别号。总而言之，IP协议负责把数据包发给正确的计算机，UDP协议负责发给正确的应用。

TCP

UDP头里还有 checksum 检验和，用来检查数据是否正确，如果不正确，UDP通常会把数据包丢弃，加之UDP并不能确认对方已经收到数据包，所以它其实并不太可靠。但是由于其简单性，一些应用并不在乎丢失数据，例如视频通话最多也就是丢帧，影响不大，所以UDP的使用还是非常广泛的。不过到了邮件发送，文件传输等场景，要求所有数据必须准确无误地送达，就不得不使用 传输控制协议（TCP） 了，其原理跟UDP一样，但提供了更高级的功能，如数据包排序、确认码（ACK）、超时重传、滑窗、拥塞控制，从而保证数据完整无误地传输。

DNS

应用程序想从网络上的另一台计算机上的应用程序获取数据，需要知道对方的IP地址和端口号，事实上，因为 172.217.7.238 是谷歌服务的ip地址，而80是其端口号，我们在浏览器上输入 http://172.217.7.238:80 即可直接访问谷歌。但记下一串数字总归是很烦的，我们还是喜欢输入 www.google.com 的方式，这叫做域名。互联网上有一种专门的服务，负责把域名和ip地址对应起来，这种服务就是 域名系统（Domain Name System，DNS）。

OSI七层模型

线路里的电信号或者Wi-Fi里的无线信号，这些是物理层。mac地址，碰撞检测，指数退避等用来操控物理层的方法叫做数据链路层，IP协议等负责各种报文交换和路由转发的叫做网络层，TCP和UDP负责如何点到点传输的叫做传输层，操纵TCP、UDP进行连接、传递信息、关闭连接的叫做会话层，例如socket，最后像浏览器、Skype、微信等具体的应用程序如何展现数据，就是展示层和应用层了。

P30 万维网（world wide web）

万维网建立在互联网之上，通常我们用浏览器访问一个页面，会输入如 www.bilibili.com/video/av21376839 这样的链接，前缀www就是万维网的缩写。其最基本的单位是单个页面，页面上会有跳转到其他页面的链接，叫做 超链接，每个页面都需要一个唯一的地址，叫做 统一资源定位符（URL）。当我们输入一个 URL，DNS首先会找到域名 www.bilibili.com 对应的ip地址，然后我们的计算机会向对方（通常是web服务器，默认80端口）发起一个 tcp 连接，连接建立后，会继续向服务器请求对应的页面 /video/av21376839，这里面用到的协议是 超文本传输协议（HTTP）。服务器返回的内容为了更好地展示，如标题、内容、列表，通常会用 超文本标记语言（HTML） 来显示，如今最新的 HTML5 标准，加上 CSS、JavaScript 可以做出丰富多彩的网页效果。

如果我们知道一个域名，可以直接输入，但如果我们事先不知道呢？最开始网页服务还比较少的时候，人们可以维护一个黄页目录，有专门提供这种服务的网站，例如 Yahoo，后来随着万维网的网站越来越多，人工维护变得困难起来，于是又出现了搜索引擎，如Google。