1.早期的计算

1).本系列会了解到位(bit)、字节(byte)、晶体管(transistors)与逻辑门(logic gates)，一直到操作系统(Operation Systems)、虚拟现实(Vitual Reality)与机器人(Robots)。

2).计算器历程：

• 算盘: 早期手动计算器，可加减可存储结果数据
• 机械计算器: 手动转动，齿轮咬合
• 电动机械打卡机: 此机器的速度是人工的10倍，使得美国人口普查统计得以更快完成，节省数百万美元（人们开始意识到计算机器巨大市场潜力）

2.电子运算

1).继电器(relays): 用电控制的机械开关，缺点是开关速度慢，易磨损。小虫子引发继电器故障(bug一词来源于此)。

2).真空管(vacuum tubes)或者电子管: 密闭灯泡里放2个电极，其中一电极可被加热 发射电子(thermionic emission)，另一电极吸引电子从而形成电流，这是全球第一个真空管。通过加入控制电极控制真空管的开与闭。
真空管内没有活动部件，速度更快，磨损更小。

任何只允许电流单向流动的电子部件都叫做二极管(diode)。

3).晶体管(transistors): 1947年贝尔实验室John Bardeen等人发明了晶体管。它由两电极由导电材料隔开，这些材料有时候导电有时候不导电，即半导体(semiconductor)，通过控制这些材料的电荷让其导电或不导电。
晶体管是固态组件，体积可以大幅缩小，速度更快，磨损更小。
上面提到的“导电材料”常见是用的硅来制造，所以有了硅谷。

3.布尔逻辑与逻辑电路

早期有人使用三进制、五进制等，后来发现电源电压不稳导致不能正确表达，所以统一成了二进制。
开关 等于 二进制(Binary)。
使用二进制还有个原因是: 英国数学家George Boole的布尔代数(Boolean Algebra)解决了所有的运算和法则，基于布尔代数实现了逻辑电路NOT门、AND门、OR门、XOR门。

4.二进制

这里讨论的是计算机是怎么存储和表示数字的。用二进制实现常规代数的运算。
二进制中的每个“0”或者“1”叫一个比特(bit)或者位。由于8-bit比较常见，所以称为一个字节(byte)。千字节(kilobyte) = 2的10次方个字节 = 1024个字节，兆字节(megabyte)，千兆字节(gigabyte)，TB(terabyte)。

32位(32-bit)二进制最大可表示常规代数的”0 ~ 43亿多“ 或者 ”+20亿 ~ -20亿“(第一个bit表示正负)。为了表示更多数据所以有了64位系统。接着用科学计数法表示浮点数，即正负 + 存指数 + 存有效数。

接着通过对字母进行编号来表示字母，1963年产生了基于7-bit的ASCII(American Standard Code for Information Interchange 美国信息交换标准代码)使得不同公司的计算机可以交换数据。由于ASCII针对英文字母设计的，其他自然语言如中文、土耳其文拥有的数千个字符甚至无法用1 字节（8-bit）表示，1992年有了16-bit的Unicode，统一编码方案。

计算机必须在内存中定位到某个位置，叫做地址(address)，用以存取数据。

5.算术逻辑单元ALU(Arithmetic Logic Unit)

ALU = 算术计算(如半加器、全加器) + 逻辑控制(如OR门和AND门组成的全0检测，通过检测让Flags位被标记)

操作码会告诉ALU执行什么操作

6.寄存器&内存

ALU算出来的结果得找个地方存起来，所以就有了计算机内存(Memory)。
RAM(Random Access Memory，随机存取存储器)只有通电时才能存；另一种是持久存储，断电也能保留数据。

• 记录0和1的电路

  
  

• 锁存器(And-Or Latch)，存住1-bit数据的理论电路

  
  

• 门锁(Gated Latch)电路 ，一个能存单个bit的盒子，完整电路

  
  

• 寄存器(register)，并排放8个门锁，就构成了8位寄存器，存多少个bit叫“位宽(width)”。当今计算机都有64位宽的寄存器了。寄存器是指“能存一个值的小内存块”。

  
  

• 多路复用器(multiplexer)，因为并排会很耗材、占地方、消耗更多钱财等，于是有了矩阵放置 、内存地址(Memory Address)的概念 ，如：12行8列(8位寻址 = 4bit行 + 4bit列)存了1bit的数据。 抽象一下，然后做一个256个字节的内存，然后进一步抽象成可寻址内存。

  
  
  
  
  
  
• 内存的一个重要特性就是可以随时访问任何位置，所以叫RAM。
• 上面说的制成的是SRAM(Static Random-Access Memory，静态随机存取存储器)，还有其他类型的RAM，如DRAM、闪存(Flash Memory)、NVRAM，不同之处在于用不同的电路存单个bit。

7.CPU & 时钟频率

计算机之所以能做事儿是因为有指令(instruction)去指示计算机干活儿。如果是计算指令，CPU会跟ALU通信进行计算加减，如果是内存指令，CPU会跟内存通信进行读写。

CPU运行示例之”加载数据A“：
1).取指令(fetch phase)
2).解码指令(decode phase)
3).执行指令(execute phase)
此例中8-bit RAM里前4-bit指定操作码，后4-bit指定地址或寄存器。
不同指令由不同逻辑电路解码，例如“7.1-CPU执行「LOAD_A指令」.png”图中所示的加载数据A的解码电路。把上面这些”控制单元“抽象出来。

当执行到”ADD“指令时，就要用到ALU了。

8.指令和程序

实现”11-5=1“更多的指令。

为了让CPU干更多的事，处理更多指令：
方法一、升级硬件(即修改指令长度)。如换上64位CPU。
方法二、可变指令长度(即将指令和数据拆开，指令相邻下一个存放数据值的内存地址，这个地址叫”立即值“)。如 Intel 4004芯片 的指令集支持46个指令，它就是用8-bit的”立即值“处理的。

9.高级CPU设计

电子计算 早期的提速是通过减小“晶体管转换开关”的时间，现在则是越来越多地为特定计算设计特定的指令电路。例如早期的除法指令是由循环多次减法指令实现的，乘法是由循环多次加法实现的，现在为除法单独设计了电路和ALU结构。现代电脑处理器有专门的电路处理图形操作、解码视频、文档加密等。所以有了各种对特定领域的处理器，如GPU。

至今，高速而厉害的指令引起了另一个问题：数据的高速读写(RAM)。数据是通过总线传输的。

RAM需要时间查找地址、取得数据，另外一个指令可能需要多个时钟周期 而在此期间CPU是闲着的。所以后面在CPU中加入小的RAM，叫高速缓存(Cache)，读取数据时不再是单个传值，而是一批数据，更快提供数据(cacha hit、cache miss)，而且可以存储复杂运算的中间值等等，用以提高CPU的处理速度。通过脏位(dirty bit，页面重写标志位)标识，在RAM和Cache同步时，RAM中的旧数据得以被更新。

另一个提升CPU性能的方法：指令流水线(instruction pipelining)。

多核CPU，不同于多个CPU，前者会共享同样的资源，如缓存。

当多核还不够时，可以构建拥有多个CPU的计算机。甚至是超级计算机，用以计算航空航天、模拟宇宙等等超级变态的计算。

10.编程史话

将机器程序化的需求在计算机发展前就已经存在，毕竟不是美国人口普查汇总数据这么简单。

为了程序化控制，人们设计了控制插板，通过电线传递信号，执行不同计算。

为了节省人力提高效率，有了穿孔卡片。穿孔卡片形成对织布机(何时更改织线颜色)或者计算机(一个孔对应汇总值加1)的连续指令，40年代末随着电子内存的普及，将整个程序存储在计算机内存中成为可能，使得程序易于修改、易于被CPU快速读取。穿孔卡片不仅可以向计算机传递数据，也可以通过给卡片打孔存储数据。

程序和数据在一个共享的内存中的结构被成为冯洛伊曼结构(Von Neumann Architecture)，冯诺依曼计算机的特征，有包含算术逻辑单元的处理器、数据寄存器、指令寄存器、指令地址寄存器、存储数据和指令的内存。

11.程序语言

计算机只能处理二进制指令，这些二进制叫机器语言(machine language)或机器码(machine code)。在计算机早期阶段，人们必须用机器码写程序，具体操作是先用英语描述(伪代码，pseudo-code)写在纸上，然后通过操作码表转换为二进制机器码，最后导入计算机开始运行。

1940~1950年代人们开发了更可读更高层的语言，他们给每个操作码分配一个名字，称为助记符(mnemonics)，如LOAD_A 14，通过可重用的二进制帮助程序(汇编器(assembler))，自动转换成二进制机器码。LOAD_A 14就是一条汇编指令。汇编与机器指令往往是一一对应的。

程序员可以创建内存地址的抽象表示，叫变量(variables)。

A = 3
B = 5
C = A + B
# 这个例子在底层操作中，编译器可能把变量A存在寄存器A里，亦或是寄存器B里，但这些底层逻辑我们不用关心了

为了远离每种CPU特有的汇编代码和机器码，从底层细节中脱离出来，编程语言应运而生，一次编写多种执行。在1960年代，我们有了ALGOL、LISP、BASIC等语言，70年代有了Pascal、C等。80年代有了C++、Objective-C 和 Perl。90年代有了Python、Ruby、Java。在新世纪里有了C#、Swift、Go。

12.编程原理：语句和函数

语句表达独立而完整的思想。赋值语句、IF语句、WHILE循环、FOR循环等。

代码越来越复杂冗长，为了隔开并隐藏繁琐的东西，编程语言可以把一段代码打包，放入函数（某些编程语言中也可以叫方法、子程序），变成使用函数模块化地编程，也方便团队作战。

现代编程语言有许多提前写好的函数，叫库(Libraries)。它们由专业人员编写，效率高，检验充分，可提供给每个人使用。

13.算法初步

解决一个计算问题往往有多种不同的解决方案，这些不同方案间的区别就是“算法”，算法就是完成计算的具体步骤。

各种算法中，被用到最多的就是“排序”(sorting)。

算法的输入大小 和 运行步骤之间的关系，代表了算法的复杂度，表示算法运行速度大致是个什么量级。选择排序(Selection Sort)复杂度为O(n^2)；归并排序(Merge Sort)的是O(n log n) ；图搜索(Graph search)里的Dijkstra算法了解一下。

14.数据结构

楼上的算法处理的数据是如何存储在计算机内存中的呢？答案是数据结构(Data Structures)

数据结构包括：数组(Array)、字符串(String)、矩阵(Matrix)、结构体(Struct)、指针(Pointer)、节点(Node)、链表(Linked List)、队列(Queue)、栈(Stack)、树(Tree)、二叉树(Binary Tree)、图(Graph)。不同数据结构适用于不同计算场景。

链表比数组更灵活，它不像数组大小固定，而是可动态增减的，且更容易重新排序、两端缩减、分割等，所以许多复杂数据结构都基于链表。如队列和栈。

Node稍微变一下，改成有2个指针，就变成了Tree。很多算法在用树这种结构。树的重要特性是从根节点到叶子节点的路径是单向的。如果数据随意连接，那可以用Graph来表示了。

不同数据结构适用于不同的计算场景，选择正确的数据结构会让工作更加简单。所以大多数编程语言都自带了很多做好的数据结构，如C++的“标准模板库”，让程序员专注更多其他的事情。

15.阿兰.图灵

图灵机(Turing machine)是一台理论计算模型，输入+规则可以得到输出。

16.软件工程(Software Engineering)

把函数打包成层级分明的体系(hierarchies)，将相关代码合并为对象(objects)。

由于不同的人或不同的团队写的函数，需要文档(documentation)帮助了解代码和应用程序接口(application programming interface，即API)。

模块A对模块B一无所知，让B的一切暴露给A调用会出乱子，API可以控制哪些函数和数据可以让外部访问，哪些仅供内部使用。有选择性的暴露一部分功能是 面向对象编程(Object Oriented Programming) 的本质。用这种方式处理大型复杂项目非常有效。

现代软件开发者会用特定的应用来编程，它集成了很多工具来编写、编译和测试代码，这些应用又叫集成开发环境(Integrated Development Environments，即IDE)。除了IDE，还有个牛逼的软件可以帮助团队协作大项目，那就是源代码管理(Source Control)，也叫版本控制(Revision Control)。这些代码被放置在服务器上叫代码仓库。然后有了质量保证测试(Quality Assurance testing)，即QA。

17.集成电路、摩尔定律

软件日益精巧，从卡片打孔的机器语言到如今的集成环境中的面向对象编程语言，这些进步依赖于硬件的不断改进。

早期组成计算机的部件由很多不同的分立的元件组成，再将它们用线缆连接到一起。随着计算机性能需求的提升，需要用更多分立的元件（元件倒是从继电器 → 电子管 → 晶体管，体积缩小，造价降低）制作出更强计算能力的计算机。但是随着线缆数量增多，复杂程度和成本也上去了。突破发生在1958年，改为将许多组件集成于一个单独的电子部件内，这就是集成电路(Integrated Circuits，IC)，用以制作计算机部件。然后又有了印刷电路板(Printed circuit boards, PCB)。然后又有了光刻法(Photolithography)这种全新的制造工艺，即使用光将复杂的图案转移到材料（如半导体）上。如今的光刻分辨率已达几纳米。

1965年，Gordon Moore总结了：大约每过两年，得益于材料和制造技术的发展，同样大小的空间里可以布置的晶体管数量将翻倍。这就是摩尔定律(Moore's Law)。人们用这个定律表达一种趋势。

CPU不是唯一受益的元件，还有内存显卡固态硬盘等。从19世纪70年代开始，用超大规模集成电路技术来实现自动生成芯片设计。

为了突破摩尔定律，需要解决：①光波长的问题，波长更短，投射的图形越小。②量子隧道贯穿问题，晶体管越小，电极所在的地方可能只间隔数个原子，电子可以越过这些间隔。

18.操作系统

卡片打孔时期，人们手动把程序放入读卡器花的时间大于程序运行时间，人们需要一种让计算机自动运作的的方式，于是操作系统(Operation System)诞生了，管理并启动其他程序。

计算机变便宜，开始变多，有不同硬件配置，操作系统充当软件和硬件之间的媒介。操作系统提供API来抽象硬件，叫设备驱动程序(device drivers)，使程序可以用标准化输入输出硬件(I/O)。

通过调度使得多个程序同时运行，在单个CPU上共享时间，操作系统的这种能力叫多任务处理(multitasking)。

程序可能会分配到非连续的内存块，为了隐藏这种复杂性，操作系统会虚拟化内存位置，程序就可以假定内存总是从地址0开始并且是连续的。操作系统和CPU会自动处理虚拟内存和物理内存之间的映射。

多任务时，当切换到另一个程序时，程序不能丢失数据，所以为每个程序分配专属内存块。这样一来如果程序出错，写入错误数据，则只能影响到自己，这个功能叫内存保护(Memory Protection)。

1970年代，大学可以买电脑给学生用，计算机不仅能同时快速运行多个程序，也能让多个用户同时访问。就设计了多用户的分时操作系统(time-sharing Operation System)，通过终端(Terminal)，终端只是一个键盘+屏幕 连接到主计算机，让多用户可以同时访问计算机。早起最有影响力的分时操作系统是1969年发布的Multics(多任务信息与计算系统)，该系统非常复杂，操作系统占用一半的内存。

由于Multics过于复杂，贝尔实验室的Dennis和Ken Thompson联手打造了新的操作系统，叫Unix，把系统分为内核(即系统核心功能，如内存管理、I/O) 和 工具集(程序和运行库)。简单化的Unix可以在更便宜和更多样化的硬件上运行。

1980年代早期，电脑的成本降到个人可以负担，叫个人或家庭电脑(Personal or Home Computer，PC)。PC机比大学、企业、政府的大型主机简单多了。1981年微软为PC发布的MS-DOS(微软磁盘操作系统，Microsoft's Disk Operation System)就是更简单的操作系统，很受PC市场欢迎，即便是缺少多任务和内存保护这样的功能。

19.内存&存储介质

纸卡、纸带
延迟线存储器
磁芯存储器
磁带
磁鼓存储器
硬盘
内存层次结构
软盘
CD/DVD，即光盘
固态硬盘SSD，没有活动部件，访问时间一般低于1/1000秒

存储器(Storage)和内存(Memory)不同，前者数据会一直存着，断点不会丢失。

20.文件系统

文件就是按照一定的格式排列的一长串二进制。元数据存储在文件的开头和实际数据之间，也叫文件头(Header)。

.wave文件举例：①麦克风每秒上千次地采集声音；②每次采集到的振幅用一个数字表示，这些数字存储在wave文件中；③播放这个文件时，音频程序启动计算机扬声器发射波形。
位图(bitmap)，.bmp文件：计算机上图片由称为像素(pixel)的小方块组成，每个像素是红、绿、蓝的组合。

存储器（可能是磁带、磁盘、硬盘等）没有文件的概念，只能存储大量的bit，为了存储多个文件，有种特殊的文件用来记录其他文件的位置大小等，称为目录文件(Directory file)。通常目录文件存在存储器的开头位置。

现代文件系统将文件存在块(Blocks，统一块级大小方便管理)中，并将文件拆分为多个部分存储在不同块中。

随着存储容量和文件数量的增长，所有文件都存在同一个层次（只有一个文件目录）变得效率低下，将相关文件夹放到同一个文件夹里，变成分层文件系统(Hierarchical File System)。如root目录下有music目录、photoes目录：

21.文件压缩技术

我们希望文件能尽量小一些，可以存大量文件，传输也更快一些。解决方法就是压缩(Compression)，用更少的bit编码数据。

游程编码(Run-length Encoding)，「消除冗余」，利用文件中存在相同的值进行压缩，插入一个额外字节进行长度说明，并删除重复数据。。注意：少数情况下（文件中没有重复数据却插入了一些数据），经过压缩后数据反而变多了。

字典编码(dictionary coder)，「使用更紧凑的表示」，先将数据进行编码，即code与data的对应关系，然后用code来表示文件数据。

游程编码 和 字典编码 是无损压缩技术(lossless compression techniques)，很多无损压缩文件格式都用到了它们，如gif、png、pdf、zip等。

大多数有损压缩技术(lossy compression techniques)的基础是：删除掉一下人类看不出什么区别的数据，这种根据人类感知来删除数据的做法叫感知编码(Perceptual coding)。比如声音，人类听觉只能识别特定频率的声波，我们给音乐录音时，超声波的数据都可以扔掉。有损音频压缩就会用不同精度编码不同频段。这就是手机中和现实中听起来的不一样的原因之一。如 MP3音频文件比 未压缩的音频格式wav或flac往往小10倍。

22.命令行界面

1868年Christopher Latham Sholes发明了打字机。打字机设计之初的目的是为了文件的易读性和标准化。1874年打字机用了QWERTY键盘布局，并开始流行。1880年Elizabeth Longley开始推广十指打字(ten-finger typing)法。

打字机出现后有了电传打字机(teletype machines)。电传打字机有了电子接口，然后有了电传电脑界面，用户输入一个命令按回车然后计算机会打印输出，这就形成了后来的命令行界面(Command Line Interfaces)。

到1970年代，用屏幕加键盘代替电传打字机变得实惠。这些虚拟的电传打字机被叫做终端(Terminal)。

早期一个著名文字游戏叫Zork，后来从纯文字进化成多人游戏，简称MUDs(Multi-User Dungeons)。

23.屏幕 & 2D图形显示

出现了显示技术：
阴极射线管(Cathode Ray Tubes，CRT)，其原理是把电子发射到有磷光体图层的屏幕上，当电子撞击涂层时会发光几分之一秒。由于电子是带电粒子 其路径可以被磁场控制。绘制图形有2种方式：①矢量扫描(Vector Scanning)，即引导电子束描绘出形状，然后足够快地重复这条路径。 ②光栅扫描(Raster Scanning)，即从上向下从左到右逐行扫描但只在特定的点打开电子束来描绘，然后不断重复这个过程。

屏幕上显示的这些清晰的点，也称为像素(pixel)。如今用的液晶显示器(Liquid Crystal Display，LCD)也是用的光栅扫描技术，每秒多次更新像素里红绿蓝的颜色。

史上第一代显卡是被称为字符生成器(Character generator)的硬件，它从内存中读取字符然后转换成光栅图形 显示在屏幕上。它内部有一小块只读存储器ROM(Read-only Memory)，存储点阵图案(matrix pattern) 或像素矩阵。。和一块专门为图形保留的屏幕缓冲区(Screen Buffer)，当程序想显示文字时，操作这块区域的值即可。

字符生成器由于字符集有限，没办法绘制出任意形状。于是想出用CRT的矢量扫描模式来描绘，用线来组成图形。。程序更新内存中的矢量设定指令值，让图形随时间变化--动画(Animation)。1962年代发明的Sketchpad 和 光笔 是人机交互方式的转折点。 。

内存中的bit可以直接一一对应到屏幕上的像素，被称为位图显示(bitmapped displays)。可以把图形想象成一个巨大的像素矩阵，计算机把像素数据存在帧缓冲区(frame buffer)，早期这些数据存在内存RAM里，之后存储在特殊的被称为VRAM(Video RAM)的高速显存中，它位于显卡上。。

24.冷战和消费主义

由于美国和前苏联的太空竞争，导致对计算机的需求倍增，促使阿波罗计划使用了造价不菲的像集成电路这样的高新技术，也反过来促进了计算机的发展。冷战结束后，大部分需求变成了公司和消费者，让计算机普及、走向市场并最终获得良性发展。

25.个人计算机革命

普通计算机是公司或大学里面的那些大家伙，然后有了微型计算机(Microcomputer)，后面变成了PC。1970年代个人电脑变得可行。

比尔盖茨和保罗艾伦写了个BASIC解释器(Interpreter)，这样就不用写晦涩难懂的机器代码了，拿去卖钱。解释器与编译器(Compiler)不同，前者是程序开始运行时进行转换，而后者是提前全部转换成机器码后再执行。

乔布斯提议卖组装好的电脑，Apple-I、Apple-II诞生。IBM意识到了个人电脑的市场，其PC就采用开放架构IBM Compatible(IBM兼容)，兼容更多软硬件。而苹果选择封闭架构，更好的用户体验。

1979年火爆的电子表格程序VisiCalc，是微软Excel和谷歌Google Sheets的鼻祖。

26.图形用户界面(Graphical User Interfaces，GUI)

1973年施乐公司发布的XEROX ALTO是第一台GUI电脑，它的WIMP（即窗口Window、图标Icon、菜单Menu、和指针Pointer）的启发下，1984年苹果发布的Macintosh，这是普通人可以买到的第一台带图形用户界面的电脑。相比命令行，图形界面是个革命性进展，用户可以不必记住命令，图形界面就告诉用户可以做什么，用户只需在屏幕上找选项就行了。。

GUI程序就是由一些小组件(滑块、按钮、打钩框等)组成的。GUI用的是事件驱动编程(Event-driven programming)。

早先微软的Windos操作系统都是基于DOS的，而DOS设计时就没想过运行图形界面，但从Windows3.1（对外是Windows 95）开始微软开发了面向消费者的GUI操作系统。Windows 95还提供了Mac OS没有的高级功能如多任务和内存保护等。

27. 3D图形

线框渲染(Wireframe Rendering)：可以理解为显示的线段。
把3D坐标拍平显示到2D屏幕上，这个过程叫“3D投影(3D Projection)”。
正交投影(Orthographic Projection)：立方体的各个边，在投影中是互相平行的。。
透视投射(Perspective Projection)：平行线段会在远处收敛于一点。。
网格(Mesh)：一堆多边形的集合。。
三角形在3D图形学中被称为是“多边形(Polygons)”，三角形更常用的原因是能定义唯一的平面。
扫描线渲染(Scaline Rendering)：多边形转换成填满的像素。因为3D图像不是线框渲染，需要被填充。。电脑填充的速度叫“填充速率(fillrate)”。这种处理方式简单粗暴，边缘充满锯齿。有种解决技术叫“抗锯齿(Anti-aliasing)”。原理是：判断多边形切过像素的程度来使用浅一点颜色进行填充。。
遮挡(Occlusion)：在3D场景中，有的多边形被另外一些多边形挡住。解决方法就是楼下的“画家算法” 和 “深度缓冲”，二者也都会基于扫描线渲染技术。
画家算法(Painter's Algorithm)：先排序 然后从远到近渲染。。
深度缓冲(Z-buffering)：记录场景中多边形每个像素和摄像机的距离，保留数值小的值，再进行填充渲染。。
Z-fighting错误：如果场景中出现多边形A和B距离都是20，哪个被渲染在上面变得不确定。。
背面剔除(Back-face Culling)：如游戏里面人物角色，你只能看到朝摄影机的那一面，为了节省处理时间和计算量，渲染中经常忽略角色的背面。这就导致一个BUG，当进到角色内部时，角色会消失。就像CF里面卡BUG，掉进地底以后看不到地面了。。
光靠扫描线渲染技术是没有立体感的。。 所以就加点灯光效果，提高真实度。
光照/明暗处理(Shading)：就是灯光效果。
表面法线(Surface Normal)：多边形物体的单个多边形的垂直线。。
平面着色(Flat Shading)：根据表面法线，距离光源的角度就不同，反光效果也就不同（越反光越用更亮的颜色填充）。。 平面着色会使得多边形物体边界非常明显，不光滑，这导致更多其他算法被开发出来，楼下的”高诺德着色“和”冯氏着色“。
高诺德着色(Gouraud Shading) 和 冯氏着色(Phong Shading)：不是只用一种颜色给多边形物体上色，用过渡色让物体看起来更真实。。
纹理(Textures)：纹理在图形学中指外观，而不是手感。
纹理映射(Texture Mapping)：把 多边形坐标 和 内存中纹理图像 的坐标一一对应，从纹理的相应区域取平均色去填充多边形。 这样才会得到一个精美的小茶壶。。。
一遍又一遍地处理多边形：扫描线填充，抗锯齿，光照，纹理化等，在3D场景中，这样的计算是巨大的。一方面可以为这些特定的运算添加特定的硬件来加快速度，另一方面把3D场景分解成多个更小的部分并行渲染。GPU应运而生。
图形处理单元(Graphics Processing Unit，GPU)：GPU就在显卡上，它周围有专用的RAM，所有网格和纹理都可以存里面，让GPU的多个核心可以高速访问。

28.计算机网络

LAN局域网(Local Area Networks): 计算机近距离构成的小型网络。LAN技术有很多，其中最成功的是以太网(Ethernet)，开发于1970年代施乐公司。。
MAC地址(Media Access Control address): 以太网中电缆是共享的，每天联网计算机都看得到数据但是不知道数据到底是给谁的，所以有了媒体访问控制地址，即MAC地址。这个唯一的地址放头部作为数据的前缀发送到网络中，只有看到是自己的MAC地址才处理数据。
载波监听多路访问(Carrier Sense Multiple Access，CSMA): 多台电脑共享一个传输媒介的方法叫“载波监听多路访问”。如以太网的载体是铜线、WIFI的载体是传播无线电波的空气。载体传输数据的速度叫带宽(Bandwidth)。
指数退避(Exponential Backoff): 当2台主机向以太网内同时发送数据时会发生冲突，数据全乱掉了。一种解决方案是等待网络空闲再重试，然后再在重传之前等待一段时间 = 呈指数级增长的等待时间 + 随机时间，这就叫指数退避。以太网和WIFI都用了这种方法，很多其他传输协议也用。
冲突域(Collision Damain): 如果主机数量进一步增加，指数退避也不好使，所以需要减少同一载体中的设备数量。载体和其中的设备统称为冲突域。为了减少冲突，可以用交换机(Switch)把网络拆成两个冲突域。交换机里有个路由表记录MAC地址在哪边。 。
最大的网络就是因特网(Internet)。
电路交换(Circuit Switching): A和B有5条专用通信线路，如果都被占用，要等其中一条线路空闲出来才能使用，这就是电路交换。
消息交换/报文交换(Message Switching): 除了在A和B之间建立专用通信线路，还可以让 报文/消息 在AB间好几个站点之间路由传递。消息沿着路由跳转的次数叫跳数(hop count)。如果一个报文很大，传输时会阻塞整个链路很长时间，所以要将大报文分成很多小块，叫数据包(packets)。每个数据包都有目标地址，所以路由器知道该发到哪里。数据包的具体格式由互联网协议(Internet Protocol，IP)定义，这个标准创建于1970年代。路由器会不断平衡与其他路由器之间的负载，这叫“阻塞控制(congestion control)”。有时同一报文的多个数据包会经过不同线路导致到达的顺序不一致，所以在IP之上还有其他协议，如TCP/IP，可以解决乱序问题。
分组交换(Packet Switching): 将数据报文拆分成多个小数据包，然后通过灵活的路由传递，这种路由方法叫分组交换。题外话：冷战期间有核攻击的威胁，所以创造了分组交换，实现去中心化，一个站点死掉，还可以走其他站点路由传递。世界上第一个分组交换网络和现代互联网的祖先是ARPANET。
物联网(Internet of things): 如今越来越多的智能设备联网，形成了物联网。

29.互联网

计算机想要获取YouTube上的视频：

• 首先要连接到局域网LAN(Local Area Network)。你家WIFI路由器连接着的所有设备组成了局域网。
• 局域网再连接到广域网WAN(Wide Area Network)。WAN的路由器一般属于你的互联网服务提供商，ISP(Internet Service Provider)，广域网里先连接到一个覆盖街区的区域性路由器，然后路由器再连接到一个覆盖整个城市的更大的WAN。
• 广域网连接到互联网主干上。互联网主干由一群超大型超高带宽的路由器组成。
• 再沿着主干到达有对应视频文件的YouTube服务器，获得数据。可以用traceroute来看数据包中转了几次

数据包想要在互联网上传输，要符合互联网协议(Internet Protocol，IP)标准。就像物品需要满足邮寄的限制条件才能被邮寄，如起始地址、大小重量。

IP是非常底层的协议，数据包的头部只有目标地址，使得数据包到达后，操作系统并不知道该把数据交给哪个程序。因此需要在IP之上开发更高级的协议，如UDP(User Datagram Protocol)。

UDP也有它自己的头部数据，在自己的头部数据中放了端口号、校验和等重要信息。UDP会把自己的DATA部分全加在一起，计算出校验和放入头部，以便确认传输过程中是否出了差错，不过可惜UDP没有数据修复和数据重传的功能，UDP也无法知道数据包是否到达目的地。但是UDP简单速度快。

如果是邮件这种数据，就要求所有数据必须到达，不能出差错，那就用 传输控制协议(Transmission Control Protocol，TCP)。
TCP结构与UDP类似，不过有更高级的功能：1、TCP数据包有序号。2、TCP要求接收方“校验和”确认无误后返回给发送方一个确认码(ACK)。发送方超时未收到ACK会重发。收件方也能通过序号去重。通过ACK成功率和花费的时间可以推算出网络拥堵请求，自动调整传输率（同时发包的数量）。

TCP由于ACK，把要传输的数据包数量翻了一倍，所以传输速度不如UDP。

总结：IP负责把数据包送到正确的计算器；UDP、TCP负责把数据包送到正确的程序。

由于IP地址（172.217.7.238）不好记，所以有了域名系统(Domain Name System，DNS)，负责吧域名和IP地址一一对应。域名的数量太多，所以不是一个地方统一管理，而是成树状结构。

开放式系统互联通信(Open System Interconnection，OSI)网络模型：

1. 物理层(Physical Layer)：线路里的电信号、WIFI的信号
2. 数据链路层(Data Link Layer)：负责操控物理层。有MAC、碰撞检测、指数退避
3. 网络层(Network Layer)：负责各种报文交换和路由
4. 传输层(Transport Layer)：UDP、TCP，负责点对点传输
5. 会话层(Session Layer)：使用UDP、TCP来创建连接，传输，关掉连接
6. 表示层(Presentation Layer)：信息语法语义关联。加密解密、压缩解压缩
7. 应用层(Application Layer)：由应用层服务组成。SMTP邮件传输协议、HTTP超文本传输协议、FTP文件传输协议
   分层后有利于改进和维护

30.万维网（World Wide Web）

万维网不等于互联网，它是在互联网之上运行的。万维网的基本单位是一个网页，网页上有无数的超链接(hyperlink)、超文本hypertext，把更多的网页连接在一起，形成了万维网。

这就需要每个网页有唯一的地址，叫统一资源定位器(Uniform Resource Locator，URL)。网络服务器的标准端口为 80 端口，使用超文本传输协议(Hypertext Transfer Protocol，HTTP)进行数据传递，1991 年有了 HTTP 第一个标准，即 HTTP 0.9，它当时只有一个 Get 指令。

光有超文本也不行，别人不知道哪些文本是超链接哪些不是。然后人们开发出了超文本标记语言(Hypertext Markup Launguage，HTML)，1990 年有了第一个版本，即 HTML 0.8。最新的 HTML5 有100 多种标签，还有其他相关技术，如层叠样式表(Cascading Style Sheets, CSS) 和 JavaScript 加进 HTML 做一些更复杂的事情。

Web浏览器(Web Browsers) 跟网页服务器沟通，浏览器从网页服务器获取网页和媒体，浏览器复杂渲染显示。这个架构于 1990 年 Tim Berners-Lee制作，同时制定了URL、HTML、HTTP，整套架构于 1991 年发布。万维网就此诞生。由于这些标准都是公开的，所以有了多家浏览器，如 Internet Explorer、Mozilla、Chrome。

慢慢的万维网里有了越来越多的网站，其中一些成为了巨头，如亚马逊。然后又有了门户网站，做一个目录，专门帮人归类记录其他网站的，如 Yahoo。然后有了搜索引擎，Google。

搜索引擎由 3 部分组成：爬虫(web crawler，抓取新超链接) + 索引(index，记录爬过的网页) + 搜索算法(search algorithm，查询索引)

网络中立(network neutrality)是指 应不应该平等对待所有数据包，让它们以相同的速度和优先级传递。如果不网络中立，某些巨头就可以垄断排挤其他竞争对手让对手的数据包传递得很差。

今天为什么我们说 HTTP 是无连接、无状态的：无连接是因为每个请求都不用保持连接，避免服务端占用资源。无状态是因为每个请求独立执行，一个请求不知道其他请求的信息，服务端不用跟踪状态占用资源。

31.网络安全(Cybersecurity)

网络安全可以分为三个方向：

• 保密性(secrecy)：只有被授权的人才能读取计算机系统和数据
• 完整性(integrity)：只有被授权的人才能读写系统和数据
• 可用性(availability)：只有被授权的人才能总是访问系统和数据

威胁模型分析(threat model)，在特定情境下做的保护措施。

要有身份认证(authentication)：①what you know，如用户名密码 ②what you have，如果是一把锁那么你需要有钥匙 ③what you are，如指纹识别虹膜识别。

暴力攻击(brute force attack)，把所有可能都试一遍。

多因素认证(multi-factor authentication)，同时使用 2 中或以上的认证方式。如苹果的密码和验证码同步验证。

过了身份认证以后，还需要有 “访问控制(Access Control)”，即 Permissions、Access Control Lists。 美国国防部多层安全政策的Bell-Lapadula模型，即“不能向上读，不能向下写”。

隔离，是种把损害降到最低的思想。比如“沙盒(sandbox)”。

32.黑客&网络攻击

黑客(Hacker)有好有坏，好的是为了查找漏洞及时修复，坏的是恶意破坏牟利。前者是White Hats，后者是Black Hats。

• 社会工程学(Social Engineering)，不是技术手段，而是欺骗别人让人泄密。
• 钓鱼(Phishing)，长得跟真的一样的假网站。
• 假托(Pretexting)，假装是内部人员，欺骗泄密。
• 木马(Trojan Horses)，偷数据、加密文件让你交赎金等。
• NAND镜像(NAND Mirroring)，通过物理接触往内存里面接几根线，复制内存，重置内存，暴力破解。此方法破解过iPhone 5C。
• 漏洞利用(Exploit)，利用系统漏洞获取某些能力和访问权限。一种常见的Exploit就是缓冲区溢出(Buffer Overflow)，缓冲区是一种概称，指预留的一块内存空间，超长溢出部分的数据会覆盖相邻的数据，导致系统出错或非法修改内存中的数据。应对措施有边界检查(Bounds Checking)、随机存放变量在内存中的位置、在缓冲区后面留点不用的内存空间（金丝雀，canaries）去跟踪检查。
• 代码注入(Code Injection)，常用来攻击用数据库的网站。对此，首先不让输入特殊字符，然后服务器再筛查一遍，最后放入数据库查。
• 零日漏洞(Zero Day Vulnerability)，即软件制造者不知道软件有新漏洞被发现。
• 计算机蠕虫(Worms)，有足够多的电脑有漏洞，让黑客把恶意程序自动在电脑间相互传播。这样黑客拿下了大量电脑，这些电脑组成了”僵尸网络(Botnet)“。”拒绝服务攻击(DDoS)“就是僵尸网络里的所有电脑发一大堆垃圾信息堵塞服务器。

33.密码学

• 多层防御(Defence in depth)，没有永远安全的系统或程序，那就设置多层防御。
• 加密(Encryption)、解密(Decryption)，把明文通过加密算法转为密文就叫加密，反之为解密。没有密码得到的就是一堆乱码。
• 早期还没有计算机的时候就已经有人加密私人信件，一类是替换加密(Substitution cipher)，凯撒加密(Caesar chipher)是这类替换加密中的一种，把字母A变成D等。另一类是移位加密(Permutation cipher)，列位移加密(Columnar transpostion cipher)是这类中的一种，用一小网格利用读取方向和网格大小来解密。
• 德国纳粹Enigma加密机，到了1990年代，人们用密码学做了加密机器。Enigma不仅是简单的替换加密，转子每输入一个字母会转动一格，就意味着AAA可能变为CDK。2台初始设置相同的Enigma配合使用就可以做到加解密。
• 1997年的”数据加密标准“(Data Encryption Standard，DES)，最初用56-bit二进制密钥。
• 2001年的”高级加密标准“(Advanced Encryption Standard，AES)，用更长128/192/256-bit。AES将数据切成小块，每块16个字节，然后用密钥进行一系列替换加密和移位加密以及其他操作，每块数据重复这个过程10次或以上。为啥选用这些长度bit，为啥只重复10次？权衡安全和性能。
• 密钥交换(key exchange)，早期人们靠口头约定或密码本，而现在要在互联网上公开传递密钥。密钥交换是一种不发送密钥但依然让2台计算机在密钥上达成共识的算法。用单向函数实现。
• 单向函数(one-way functions) 和 密钥加密 原理，单向函数是一种数学操作，很容易算出结果，却很难逆向得到输入，如颜色混合，很难知道混了什么颜色。
• 迪菲-赫尔曼 密钥交换(Diffie-Hellman Key Exchange)，在Diffie-Hellman中，单向函数是模幂运算，那一个数当基数一个数当指数做幂运算再除以第三个数得到余数，只给余数和基数很难的值指数是多少。
• 非对称加密(Asymmetric encryption)，加密和解密不是同一个密钥。目前最流行的非对称加密算法是RSA。

密码学里常常会用到质数，质数是指大于1的自然数中，除了1和自身以外不能被其他自然数整除的自然数。

34.机器学习&人工智能

机器学习(machine Learning, ML)是为实现人工智能(Artificial Intelligence, AI)的技术之一。
机器学习算法的目的是为了最大化正确率和最小化错误率。
很多机器学习使用了统计学算法，如通过特征生成决策树(decision tree)；但也有其他方法，如人工神经网络(artificial neural networks)。

35.计算机视觉

计算机视觉(computer vision)，目标是让计算机理解图像和视频。

36.自然语言处理

人类希望计算机也能像人类一样有处理自然语言的能力，自然语言处理(Natural Language Processing,NLP)。
自然语言不同于机器语言，机器语言词汇量少、高度结构化，而人类自然语言词汇量大、有口音、一词多义等等。

英语单词的九种基本词性：名词(nouns)、代词(pronouns)、冠词(articles)、动词(verbs)、形容词(adjectives)、副词(adverbs)、介词(prepositions)、连词(conjunctions)、感叹词(interjections)

早期聊天机器人和对话系统用无数个手动写的“规则匹配”（可能说的话）来实现。

计算机从声音中提取词汇，即语音识别(speech recognition)，通过谱图（不同频率振幅）定位重读元音，利用深度神经网络识别出人类语音。

通过语音合成（speech synthesis），让计算机输出语音。

37.机器人

1940年代有了CNC机器（Computer Numerical Control，计算机数控），可以执行一连串程序指定的操作，做一些非常精细的加工，这在之前生产中是很难做到的。CNC机器大大推进了制造业。

利用控制回路和反馈机制的PID控制器（Proportional integral derivative controller），让机器人的属性变成期望值。

把各种技术（人工智能、计算机视觉、自然语言处理等）结合起来，让机器人越来越像人。机器人可以接受命令并高效执行，有智力并且可以杀人的机器人叫“致命自主武器(lethal autonomous weapons)”

38.计算机心理学

我们需要了解人类心理学，做出更好的计算机。比如人类对颜色的感知，用颜色强度表示连续的数据、用不同颜色表示没有顺序的分类数据等等会非常有效。

界面设计中有个重点概念，直观功能(affordances)，直观功能为如何操作物体提供线索。如旋钮用来转，插槽用来插东西。the user knows what to do just by looking.

与直观功能相关的一个心理学概念是“认出与回想(recognition vs recall)”，这就是为什么选择题比填空题更容易。用感觉来出发记忆会容易得多。

人机交互(human robot interaction, HRI)是一个研究人类和机器人交互的领域。

原文地址：
(b站)10分钟速成课：计算机科学
(Youtube)Computer Science