计算机科学速成课（三）
2022.12.29
20. 文件系统-Files & File Systems
文件（比如txt、wav、bmp）在底层全是一样的，一长串二进制，为了知道文件是什么，文件格式至关重要。
元数据 meta data，就是数据头header，写数据的一些信息、属性，比如文件有多长。
为了存多个文件（为了知道不同文件的开头和结尾在哪里，因为存储器只是存大量的bit，没有文件概念），需要一个特殊文件，记录其他文件的位置，这个特殊文件叫“目录文件”。
目录文件会存每个文件的信息，比如创造时间、开始位置、结束位置。
增加某文件内存可能会影响后面文件，因此现代文件系统会做两件事：1.把空间分成一块块，有一些“预留空间” slack space 可以方便改动、方便管理。因此目录文件还要记录文件在哪些块里；2.拆分文件，存在多个块里，因此只要分配块，文件可以轻松增大缩小。
文件在不同块block里，叫做“碎片” framentation。碎片整理。
21. 压缩-Compression
压缩来减少文件的字节数。
无损压缩：没有丢失任何数据，解压缩后，数据和压缩前的完全一样。无损压缩的格式有：GIF，PNG，PDF，ZIP。游程编码、字典编码。
压缩方法：
- 游程编码 run-length encoding 减少重复信息，适合经常出现相同值的文件。消除冗余。
- 字典编码 dictionary encoding 。霍夫曼树 huffman tree。选频率最低的两个，放在一起，记录总频率，再重复上述操作。用更紧凑的表示方法。
按频率排列，频率高的在上面。这种编码不会冲突，因为树的每条路径唯一，也就是不会出现某个编码是另一个编码的前缀的情况，称为“无前缀” prefix-free。
压缩：
原本是：
变成：
有损压缩 lossy compression 丢掉那些人类区分不出的数据。
音频压缩，用不同精度编码不同频段。感知编码 perceptual coding。
图片压缩，人类对物体边缘、尖锐对比敏感，对颜色细微变化不敏感。JPEG
视频压缩，时间冗余 temporal redundancy 视频中不用每一帧都存这些像素，可以只存变化的部分。这是利用了帧和帧之间的相似性 inter-frame similarity。进一步地，可以找出帧和帧之间相似地补丁，通过比如移动和旋转、变亮和变暗，就也不需要保存像素，只需要对之前帧做操作。MPEG-4。
但视频中有时会出现补丁错了：这是因为压缩太严重，没有足够容量更新补丁内的像素。
22. 命令行界面-Keyboards & Command Line Interfaces
人类和计算机交互，早期是电传打字机。命令行交互。后来屏幕代替电传打字机。
23. 屏幕&2D 图形显示-Screens&2D Graphics
CRT：阴极射线显像管，原理基于电子打到磷上会发光，然后磁可以控制电子走向，于是可以控制达到屏幕的图案，再通过光栅扫描（沿着行、列，一行行扫描，在某些地方有电子，有些地方没电子），持续重复扫描，图案就可以持续显示在屏幕上。
字符生成器。早期屏幕上不用像素来呈像，而是只显示字符，这样省内存。
后来出现 CRT上的“矢量模型”。认为所有图形都由线条组成。
Sketchpad ，一个交互式图形界面，用途是计算机辅助设计 (CAD)。
光笔，就是一个有线连着电脑的触控笔，有了它们，用户可以画出很完美的线条并进行缩放等操作。
像素：内存中的位（bit）对应屏幕中的像素，这叫“位图显示”。把图形想成一个巨大的像素值矩阵。计算机把像素数据会缓存起来，存在“帧缓存区”，在显卡上，因此访问速度快。
24. 冷战和消费主义-The Cold War and Consumerism
25. 个人计算机革命-The Personal Computer Revolution
microcomputer。
personal computer 。个人计算机。
解释器 interpreter。解释器和编译器很像，区别是解释器运行时转换（把某种代码转换成可执行机器码），编译器提前转换。
26. 图形用户界面-Graphical User Interfaces
GUI是“事件驱动编程” event-driver programming ，代码可以在任意时间执行以响应事件。
27. 3D 图形-3D Graphics
3D投影 projection：图形算法把3D坐标“拍平”显示到2D屏幕上，就是把所有点从3D转成2D，然后用画2D线段的函数来连接这些点，这叫“线框渲染” wireframe rendering。
3D投影有好多种：正交投影 orthographic projection，各个边在投影钟互相平行；透视投影 perspective projection 平行线段在远处收敛于一点。
在3D图形学中把三角形称为“多边形”polygons。由多边形组成的茶壶：
一堆多边形的集合叫“网格”mesh。
用三角形的原因是空间中三个点定义一个平面，只要给3个3D坐标点，就可以画出一个平面。
3D图像需要填充，填充图形的经典算法叫“扫描线渲染”scanline rendering。填充就是要把多边形转成一块填满像素的区域。
扫描线渲染的原理：先铺一层像素网格，找到多边形的三个点的最大和最小的Y值，只在这两点间工作，算法从上往下，一次处理一行，计算每行和多边形相交的两个点（然后因为是三角形，如果相交一条边，必然相交另一条边），扫描线算法会填满2个相交点之间的像素。
填充速率叫fillrate。
但是这样边缘会有锯齿，一种减轻锯齿的方法叫“抗锯齿”anti-aliasing。通过判断多边形切过像素的程度，来调整颜色。如果像素在多边形内部，就直接涂颜色；如果多边形划过像素，颜色就浅一些。这种边缘羽化的效果，看着更舒服。
遮挡 occlusion：在3D场景中，由于距离远近不同，多边形往往只有一部分能看见，因为其它的被挡住了。
实现遮挡的方法：1. 画家算法 painter’s algorithm ，排序算法，从远到近排列，然后从远到近渲染。和画家画画一样，画家也是先画背景，然后再画更近的东西。
- 深度缓冲 Z-buffering。事先生成一个“缓冲区”网格，里面距离都是无穷远，然后并不排序，依次把三角形填充，发现三角形的距离比缓冲区更小时，缓冲区变成该距离，如果某些地方没有比缓冲区里的值小，则不填充。
3D游戏中有个优化叫“背面剔除”back-face culling，因为平面是有两面的，正面和背面，有些物体只需要渲染一面，另一面不渲染，节省处理时间。
灯光，也叫“明暗处理” shading。3D场景中，物体表面应该有明暗变化。三角形面对的方向叫“表面法线”surface normal，这个方向是垂直于表面的。根据灯光和法线的关系，进行着色。
纹理 texture 在图形学中指的是“外观”（而不是手感），各种花哨效果。纹理映射 texture mapping。就是把多边形坐标和纹理坐标对应起来，扫描线算法填充颜色时，纹理算法会查询纹理，从响应区域取平均颜色，并填充多边形。
再大的场景，过程都是一遍又一遍地处理所有多边形。扫描线填充，抗锯齿，光照，纹理化。
加速渲染：1.用专门的硬件来加速运算；2.把3D场景分成多个小部分，并行渲染。GPU 图形处理单元，GPU在显卡上，周围有专用的RAM（保存网格和纹理），让GPU的多个核心可以高速访问。
28. 计算机网络-Computer Networks
局域网 LAN ，以太网。以太网的原理：很多台电脑都用电缆连接（一条以太网电线能连接到彼此各个电脑），当一台电脑要传数据给另一台电脑时，以电信号形式将数据传入电缆，最早因为电缆是共享的，连在同一个网络里的其他计算机也能看见数据，后来以太网需要每台计算机都有唯一的媒体访问控制地址（MAC地址），这个唯一的地址放在头部，作为数据的前缀发送到网络中，所以计算机只需要监听以太网电缆，只有看见自己的MAC地址，才处理数据。
以太网、无线网络（WIFI）都用的这个机制。
多台电脑共享一个传输媒介，很多计算机同时侦听载体，这种方法叫“载波侦听多路访问”，carrier sense multiple access，CSMA，载体（carrier）指运输数据的共享媒介，以太网的“载体”是铜线（电缆），WiFi的“载体”是传播无线电波的空气。载体传输数据的速度叫“带宽” bandwidth。
冲突 collision，多台计算机同时传输数据，会在载体里产生冲突，网络阻塞。解决的方法是遇到冲突，计算机会等待1秒+随机数，也就是1点多秒，然后再看看载体是不是空的，如果是空的就传输，如果不是空的，就等2s，再不是空的就等4s，…，8s，…，这种指数级增加等待时间的方法叫“指数退避” exponential backoff。
同一个载体连接的设备叫“冲突域”collision domain（可能发生冲突的范围）。为了减少冲突，可以通过“交换机”把一个冲突域拆成两个冲突域。交换机会记录一个列表，写着哪个mac地址在哪边网络（哪个域）。
计算机网络从一个地点到另一个地点之间通常有多条线路，叫“路由”routing。两个地点之间是专有线路。
传输数据的另一种方法叫“报文交换”message switching。消息会经过好几个站点。报文交换的好处是 可以用不同路由，使通信更可靠更能容错falut-tolerant。
消息沿着路由跳转的次数，叫“跳数”hop count。通过检测跳数，可以看出报文传输正不正常。
很大的报文传输会阻塞网络，使得后面的报文传输很慢（因为要等前面的大报文传完，或者选择效率低的路由路线），解决方法是将大报文分成很多小块，叫“数据包”packet。
报文的具体格式由“互联网协议“（IP）定义。
同一个报文的数据包可能会经过不同线路，因此到达目的地的顺序不同。TCP/IP可以解决乱序问题。
分组交换 packet switching：将数据包拆分成多个小数据包，然后通过灵活的路由传递。
29. 互联网-The Internet
个人计算机和一个巨大的分布式网络连在一起（互联网）。网络传输的过程是这样的，比如手机或电脑要看一个视频，首先要连接到局域网（LAN）上，家庭路由器连着的所有设备，组成了局域网。局域网再连到广域网（WAN），WAN的路由器一般属于在互联网服务提供商（ISP），比如电信联通，广域网里，先连到一个区域路由器，比如覆盖一个街区的路由器，然后连到更大的路由器，比如覆盖一个城市，可能再跳几次，达到互联网主干，沿着主干到达视频文件的服务器，比如youtube的服务器。（可以用traceroute来看数据包传输过程中跳了几次）。
IP是底层协议，只记录了地址，数据传到某地址的计算机之后，不知道要传给哪个程序用，因此还有上层协议，比如”用户数据报协议“UDP。UDP的头header里有端口号信息。每个想访问网络的程序都要向操作系统申请一个端口号。
- IP负责把数据包送到正确的计算机；
- UDP负责把数据包送到正确的程序；
UDP的header里还有校验和。但是UDP也不会修复数据包，也不会让数据重发，接收方遇到数据损坏一般只是扔掉。UDP无法得知数据包是否到达目的地，发送方发了数据之后，无法得知数据包是否到达目的地。适用于比如视频通话，速度快，简单。
TCP，传输控制协议，所有数据必须到达，适合发邮件等不能缺失数据的场景。
TCP/IP。
TCP的数据包有序号，因此接收方即使收到的数据包的到达时间不同，也可以根据序号把数据包排成正确的顺序；
TCP要求接收方的电脑收到数据包，并且校验和检查无误后（数据没有损坏），给发送方发一个确认码 ACK，代表收到了。得知上一个数据包成功抵达后，发送方会发下一个数据包。
TCP可以处理乱序和丢失数据包，丢了就重发，还可以根据拥挤程度自动调整传输速率。
互联网有个服务，负责把域名和IP地址一一对应，就像互联网的电话簿，叫”域名系统“，DNS，比如输入某个IP+端口号能访问谷歌网址，输入google.com也能访问谷歌。
域名结构用树形表示：
物理层 physical layer：线路里的电信号，无线网络里的无线信号，这些叫”物理层“ physical layer。
数据链路层 data link layer：媒体访问控制地址（MAC)，冲突检测，指数退避，以及底层协议。 ”数据链路层“负责操控”物理层“。
网络层 network layer ：负责各种报文交换和路由。
传输层 transport layer：比如UDP和TCP协议，负责在计算机之间进行点到点的传输，还会检测和修复错误。
会话层 session layer：会话层会使用TCP和UDP来创建连接，传递信息，然后关掉连接。这一整套叫”会话“。
OSI：
上面还有”表示层“ presentation layer和”应用程序层“ application layer。