计算机科学速成课 Crash Course Computer Science 笔记（摘要形式）

计算机早期历史

1.公认最早的计算设备是算盘，发明于美索不达米亚平原。存储当前的计算状态，类似于现在的硬盘。

2.computer最早是指计算的人。

3.1694年莱布尼茨制作步进计算器，计算部分由齿轮构成。可以完成四则运算，流行了三个世纪。

4.20世纪以前普通大众中流行计算表，并流行于军队。

5.历史学家制作差分机，有了自动计算机的概念，预示了计算机的诞生。

6.hollerith将机械计算器电动，IBM成立。

电子计算器

1.早期计算设备有特定的用途，例如制表机。

2.最大的机电计算机哈佛马克一号，大脑为继电器。

3.继电器为用电控制的机械开关。

有控制线路，上面有电磁铁，可以吸引导线，用来控制电路是开还是关。

缺点：机械臂有重量，不能迅速开关，难以处理复杂问题。速度慢有齿轮磨损。继电器越多故障越多。

4.1904年，约翰安布罗斯弗莱明开发"热电子管"。电子单向流动是二极管。

1906年，发明了第三个控制电极。

5.三极真空管成为了无线电，长途电话等的基础。

6.计算机由机电转向了电子。

7."巨人一号"大规模使用真空管，可以编程了，编程的方法是把几百根电线插入插板，需要配置。

8.1946年埃尼阿克诞生，第一个真正的电子计算机。也是真空管计算机。

9.1947年发明晶体管，新的计算机时代诞生了。导致产生了更小的计算机，如1957年的IBM 608。

布尔逻辑和逻辑门

1.机械计算机是10进制，晶体管计算机2进制。

2.电路通是真，断是假。

3.一些早期计算机是三进制，五进制。状态越多越难区分。

4.”与“门是两个晶体管串联，“或”门是两个晶体管并联。

5.“异或”简称“XOR”，两个输入一真一假才能输出真。

二进制

1.二进制中一个“1”或“0”叫一个位bit。

2.8位为一个字节Byte，八位机就是计算机里大部分操作都是8位8位这样处理的。

3.1Byte=8bit，还有kb千字节，mb兆字节，gb千兆字节。

4.现在多为三十二位机和六十二位机。

5.32位浮点数中，第一位表示数字的正负，接下来的八位存指数，剩下来的存有效数字。

6.ASCII美国信息交换标准代码，ASCII是七位代码，可以存128个不同值，其中包含有换行符，大小写字母数字和标点符号。是比较早的通用标准。缺点是为了英语设计的。

7.为了解决不同语言的问题，每个国家都发明了多字编码方案，但是每种都不兼容。会遇到乱码（mojibake）。

8.1992年，Unicode诞生，有十六位，超过一百万个位置。所有语言的字符都够用了，甚至有emoji。

算术逻辑单元

1.算术操作由计算机“算术逻辑单元”处理，简称ALU。

2.ALU有两个单元，一个算术单元，一个逻辑单元。

3.算术单元负责所有数字操作。

4.可以把XOR用作1位加法器。

5.半加器

6.全加器

7.计算八位二进制的全加器叫做“8位行波进位加法器”。如果相加进位至第九位，则溢出（overflow）。

寄存器&内存

1.锁存器可以存一位，之所以叫“锁存”，是因为它“锁定”了一个值。

2.放入数据叫“写入”，拿出数据叫“读取”。

3.GATED LATCH门锁连接允许写入线，可以控制是否允许输入。允许写入线输入1时，输出数据与输入数据一致，允许写入线为0时，输出数据不再改变。

4.寄存器（register）可以存一个数字，数字的位数叫做“位宽”。

5.寄存器中用一根线连接所有的“允许输入线”。

6.寄存器位宽足够大时，使用门锁矩阵。

7.“多路复用器”可以把地址转成行和列。

8.可以将内存不断打包到更大的规模。

9.RAM随机存取存储器，记录短期记忆。

10.SRAM静态随机存取存储器。

CPU

1.CPU负责执行程序。

2.高层次视角叫“微体系构架”。

3.寄存器用来临时存数据和操作数据。

4.“指令地址寄存器”追踪程序运行到哪里了，存当前指令的内存地址。

5.“指令寄存器”存当前指令。

6.CPU的第一阶段“取指令阶段”，首先“指令地址寄存器”连到RAM，RAM返回该地址的值，并复制到“指令寄存器”里。

7.不同的指令由不同的逻辑电路解码。

例如执行LOAD_A指令：

首先“指令地址寄存器”连到RAM，RAM返回该地址的值，并复制到“指令寄存器”里。

进入解码阶段，前四位是LOAD_A指令，后四位是RAM的地址。

指令由控制单元解码。

检查是否为LOAD_A指令的电路，启用寄存器A的”允许写入线。

最后，将指令地址寄存器+1，“执行阶段”结束。

8.“指令寄存器”，“指令地址寄存器”，解码电路共同构成了“控制单元”，控制单元“指挥”CPU的所有组件。

9.0010为LOAD_A指令，0001为LOAD_B指令

10.1000为ADD指令，后面两位不是RAM地址而是分别代表两个寄存器，相加结束后，控制单元用一个寄存器暂时保存结果，关闭ALU后，把值存入正确的寄存器。

11.0100是STORE_A指令，把寄存器A的值放入内存，让寄存器允许读取，RAM允许写入。

12.时钟以精确的间隔，触发电信号，控制单元用这个信号，推进CPU的内部操作。

13.赫兹用来表示频率，1赫兹表示一秒1个周期。

14.计算机超频是通过修改时钟速度，加快CPU的速度。

15.芯片制造商往往会给CPU留一点余地，让CPU超频，过多超频会让CPU过热，或者产生乱码，因为信号跟不上时钟。

16.降频可以省电。

17.RAM独立于CPU之外，用“地址线”，“数据线”和“允许读写线”连接。

指令和程序

1.CPU是可编程的。

2.执行ADD指令时，寄存器的顺序很重要，决定结果放在哪里。

3.SUB减法指令

4.JUMP跳转指令，可以改变指令顺序，跳过一些指令。

5.JUMP_NEG只在ALU的“负数标志”为真时，进行JUMP。就是结果是负数时跳过。

条件跳转还有JUMP IF EQUAL和JUMP IF GREATER。

6.HALT，能区分指令和数据。

7.现在指令长度不断增加。

8.还有一种解决方法是“可变指令长度”。

高级CPU设计

1.早期计算机的提速方法是减少晶体管的切换时间。

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

3.CPU和RAM传递数据的线叫做“总线”。

4.解决CPU读取RAM信息延迟的方法给CPU是加一点RAM，叫缓存（cache）。缓存一般只有kb或mb。

5.缓存离CPU近，一个时钟周期就能给数据。

6.CPU想要的数据已经在缓存，叫“缓存命中（cache hit）”。不在缓存，叫“缓存未命中（cathe miss）”。

7.缓存可以存中间值。方便存储方便进一步读取计算。

8.缓存中的每块空间，都有一个特殊标记，叫”脏位“（DIRTY RIT）。

9.清理缓存时，先检查”脏位“。如果”脏“，把数据写入RAM。

10.”指令流水线“，取值—解码—执行，让每一个步骤同时进行来提高效率。

11.”指令流水线“有一定的问题

例1：读取某个数据时，正在执行的指令会修改这个数据。所以必要时会停止流水。

例2：条件跳转会改变顺序。

遇到JUMP也会暂停流水，直到JUMP出来结果，继续流水。

高端CPU会猜测哪种可能性更大，然后提前放入指令，进行”推测执行“。如果猜错，清空流水线。

还有”分支预测“，可以减少猜错。

12.同时运行多个指令流也可以提供性能。增加CPU的核数，或者增加CPU数量。用大量的CPU可以做超级计算机。

早期的编程方式

1.早期汇总机不能编程。

2改良的汇总机用插线板编程。

3.”存储程序计算机“，可以存储程序。

4.”冯诺依曼结构“的程序和数据都存在一个地方，早期冯诺依曼结构计算机用穿孔卡片编程。

5.1980年代以前，面板编程比较常见。

编程语言发展史

1.机器语言

2.对程序的高层次描述是“伪代码”。

3.1940-1950年，使用助记符，“助记符”后面紧跟数据，形成完整指令。

4.通过写二进制程序使电脑可以读懂文字指令，自动转成二进制指令，这种程序是“汇编器”。可以读取汇编语言。

5.汇编语言不用固定跳转地址，而是插入了可跳转的标签。

6.汇编语言只是修饰了机器语言，一般来说，一条汇编指令对应一条机器指令。程序员需要思考用什么寄存器和内存地址。

7.“算术语言版本0”，简称“A-0”。

8.高级语言不用管寄存器和内存地址。

9.“FORTRAN”主宰来早期编程。

10.数据系统语言委员会开发了“普通面向商业语言”，简称COBOL。

11.60年代，有ALGOL，LISP，BASIC等语言。

12.70年代有Pascal，C和Smalltalk。

13.80年代有C++，Objective-C和Perl。

14.90年代有Phthon，Java和Ruby。

15.新千年Swift，C#，Go在崛起。

编程原理-语句和函数

1.控制语句流。

2.可以把代码打包成函数。

算法入门

1.记载最多的算法是排序sorting

例如冒泡排序

2.算法复杂度用大O表示法。

冒泡排序的复杂度高，不适合处理大量数据

3.归并排序

4.图搜索改进后复杂度为O(nlog n+l)，n为节点数目，l是线条数目。导航找最佳路线用到图搜索。

数据结构

1.基本的一种数据结构：数组（ARRAYS），在有些编程语言里也叫列表（list）或者（Vector）。

2.下标（index），下标从零开始。

3.字符串（string）。

4.数组以NULL结尾。

5.strcat连接两个数组。

6.数组可以有多个下标

7.多个变量打包在一起叫结构体。

8.一种结构体叫节点（node），存一个变量一个指针。

9.用节点可以做链表，链表是一种灵活的数据结构，可以存很多节点（node）。每一个节点指向下一个节点。

10.链表可以是循环列表，也可以不循环，最后一个值是0。

11.链表很容易重新排序，两端缩减，分割，倒序。

12.复杂的数据结构用链表，例如队列(queue)和栈(stack)。

13.结构体中放一个变量，两个指针构成了变量类型“树”。有根节点和子节点。“树'是单向的。

14.如果要随意连接，就构成了“图”（chart）。

15.还有“红黑树”和“堆”更多的类型。

艾伦图灵

1.图灵机(Turing Machines)是一台理论计算设备。

2.“图灵完备”（Turing Complete），微波炉和恒温器的小电脑都是“图灵完备”。

黑客与攻击

1.“NANA镜像”，物理接触到电脑，往内存上接几根线，复制整个内存。

2.常见的漏洞利用叫“缓存区溢出”。用“边界检查”可以解决。

4.可以在缓存区留一些位置，跟踪里面的值，看是否发生变化，来识别是否有入侵者。这些内存空间就做“金丝雀”(CANARIRS),因为以前金丝雀下矿会警告危险。

5.另一种手段叫“代码注入”常用于攻击用数据库的网站。

6.软件制造者不知道的新漏洞叫“零日漏洞”。

7.有足够多的电脑有漏洞，让恶意程序在电脑间互相传播，叫“蠕虫“。

8.黑客攻下足够多的电脑，可以组成“僵尸网络”。可以发起“拒绝服务攻击”简称DDoS，攻击服务器。

加密

1.系统架构师会部署“多层防御”（defense in depth）。

2.计算机安全中常见的防御形式是密码学（cryptography）。

3.“加密”和“解密”。

4.“替换加密”，缺点是不会改变数据的频率信息。熟练的密码破译师可以从统计数据中发现规律，进而破译密码。

5.“移位加密”

6.2001年出了：高级加密标准（AES）。

7.防止密钥被截获，解决办法是“密钥交换”。

编程语言发展史

1.机器语言

2.对程序的高层次描述是“伪代码”。

3.1940-1950年，使用助记符，“助记符”后面紧跟数据，形成完整指令。

4.通过写二进制程序使电脑可以读懂文字指令，自动转成二进制指令，这种程序是“汇编器”。可以读取汇编语言。

5.汇编语言不用固定跳转地址，而是插入了可跳转的标签。

6.汇编语言只是修饰了机器语言，一般来说，一条汇编指令对应一条机器指令。程序员需要思考用什么寄存器和内存地址。

7.“算术语言版本0”，简称“A-0”。

8.高级语言不用管寄存器和内存地址。

9.“FORTRAN”主宰来早期编程。

10.数据系统语言委员会开发了“普通面向商业语言”，简称COBOL。

11.60年代，有ALGOL，LISP，BASIC等语言。

12.70年代有Pascal，C和Smalltalk。

13.80年代有C++，Objective-C和Perl。

14.90年代有Phthon，Java和Ruby。

15.新千年Swift，C#，Go在崛起。

编程原理-语句和函数

1.控制语句流。

2.可以把代码打包成函数。

算法入门

1.记载最多的算法是排序sorting

例如冒泡排序

2.算法复杂度用大O表示法。

冒泡排序的复杂度高，不适合处理大量数据

3.归并排序

4.图搜索改进后复杂度为O(nlog n+l)，n为节点数目，l是线条数目。导航找最佳路线用到图搜索。

数据结构

1.基本的一种数据结构：数组（ARRAYS），在有些编程语言里也叫列表（list）或者（Vector）。

2.下标（index），下标从零开始。

3.字符串（string）。

4.数组以NULL结尾。

5.strcat连接两个数组。

6.数组可以有多个下标

7.多个变量打包在一起叫结构体。

8.一种结构体叫节点（node），存一个变量一个指针。

9.用节点可以做链表，链表是一种灵活的数据结构，可以存很多节点（node）。每一个节点指向下一个节点。

10.链表可以是循环列表，也可以不循环，最后一个值是0。

11.链表很容易重新排序，两端缩减，分割，倒序。

12.复杂的数据结构用链表，例如队列(queue)和栈(stack)。

13.结构体中放一个变量，两个指针构成了变量类型“树”。有根节点和子节点。“树'是单向的。

14.如果要随意连接，就构成了“图”（chart）。

15.还有“红黑树”和“堆”更多的类型。

艾伦图灵

1.图灵机(Turing Machines)是一台理论计算设备。

2.图灵机是一台理论计算设备

3.组成：无限长的纸带（纸带可以存储符号），读写头，状态变量（保存当前状态），一组规则

4.规则是根据 当前状态+读写头看到的符号，决定机器做什么（在纸带上写入一个字符，或者读写头移动一格，或者都执行）

5.“图灵完备”（Turing Complete），微波炉和恒温器的小电脑都是“图灵完备”。

6.有足够的时间和内存，图灵机可以执行任何计算

7.停机问题是无法解决的

8.丘奇和图灵证明了计算机的能力有极限，无论有多少时间和内存，有些问题是计算机无法解决的

起步了可计算性理论——“丘奇-图灵论题”

9.“图灵测试”是智能测试的基础

软件工程

1.把大项目分解成小函数，可以让多人同时工作，不用关心整个项目

2.把函数打包成层级，把相关代码都放在一起，打包成对象（objects）

3.把函数打包成对象的思想叫“面向对象编程”

4.需要制作文档，以及定义好的“程序编程接口”，简称API

可以帮助不同程序员合作，不用知道具体细节

5.面向对象的编程语言可以指定函数是public或private，来设置权限

6.“面向对象编程”的核心是隐藏复杂度，选择性公布功能

7.集成开发环境IDE，提供实时检查，可以编译和运行代码

8.程序员需要给代码写文档，存在一个叫READER的文档里

9.文档可以提高复用性，其他程序员可以用代码解决自己的问题

10.源代码管理，也叫“版本控制”，把代码放在中心服务器上

源代码管理可以跟踪所有变化，发现bug，可以回滚到之前的稳定版

11.测试统称为“质量保证测试”,简称QA

12.beta版本是软件基本完成，但没有100%通过，有些公司将这个版本向公众发布

13.alpha版本是错误很多的粗糙的版本

集成电路&摩尔定律

1.1940年代~1960年代中期，计算机由独立部件组成，叫“分立元件”

问题：“数字暴政”

2.晶体管是分立元件，晶体管标志着“计算2.0时代”到来

3.集成电路IC，思路是封装复杂性，采用了半导体

4.印刷电路板PCB，通过蚀刻金属线的方式

5.IC和PCB结合使用，可以大幅减少独立组件和电线

6.光刻技术（用光把复杂图案印到材料上），

7.在硅片顶部加一层氧化层，作为保护层，

上面再加一层“光刻胶”（被光照射后变得可溶，可以用特殊化学药剂洗掉）

上面加一层“光掩膜”

8.用光照射，使氧化层被溶解，再用一种化学物质，洗掉氧化层露出的部分，蚀刻到硅层，再洗掉光刻胶

9.改变硅露出来的部分，用化学过程改变，叫“掺杂”，用高温气体来做，渗透进硅，改变电学性质

10.摩尔定律：每两年左右，材料和制造技术发展，同样大的空间，能塞进两倍数量的晶体管

11.晶体管越小，耗电越少，信号延迟越小

12.1970年，VLSI来自动生成芯片设计

13.用“逻辑综合”技术，可以放一整个高级组件，比如内存缓存

14.摩尔定律会终结

光掩模把图案弄到晶圆上，由于光的波长，精度已达极限

量子隧穿效应

操作系统

1.“操作系统”是为了让计算机自动运作

2.“操作系统”也是程序，有操作硬件的特殊权限，可以操作管理其他程序，开机第一个启动的程序

3.“批处理”

4.计算机连接其他”外部设备“

5.操作系统提供软件和硬件的媒介，操作系统提供API来抽象硬件，叫“设备驱动程序”

6.Atlas让多个程序同时进行，操作系统的这种能力叫“多任务处理”

需要给每个程序分配内存

7.“虚拟内存”，隐藏物理内存

8.“动态内存分配”使得内存大小可以灵活增减

9.内存保护

10.分时操作系统

11.Unix首先是操作系统的核心功能，叫内存管理，多任务的输入/输出处理，这叫“内核”，第二部分是有用的工具

12.“内核恐慌”

内存&存储介质

1.写入存储器（Storage）的数据，数据会一直存着，断电也不会丢失

2.最早的内存是打孔纸带

3.延迟线存储器，也叫“顺序存储器”或“循环存储器”

等待一个特定的bit，需要等待它从循环中出现

4.“磁致伸缩延迟存储器”

5.“磁芯存储器”

每个磁芯收到电流磁化，电流不同，磁化方向不同，可以存储1和0。

一个磁芯存1位，列成矩阵可以存大量数据。

可以访问任意一位。

6.磁带，用电流磁带每部分磁化方向不同，在不破坏地读取磁性

磁带是连续的，必须倒带或者快进才能到特定位置

7.“磁鼓存储器”

8.磁盘，寻道时间较短

9.软盘

10.激光盘

11.光盘，光盘表面有很多小坑，造成光的不同反射，光学传感器捕获解码为1和0

12.硬盘，U盘里面是集成电路

文件系统

1.“文件格式”

txt 文本文件

wave文件，读取数据前需要知道码率，单声道还是立体声

Bitmap 后缀.bmp，用来存图片

2.关于数据的数据叫“元数据”，存在文件开头，在实际数据前面，叫文件头Header

3.文件连续存储，目录文件存在开头，目录文件还存文件信息

属于“平面文件系统”

4.现代文件系统把空间分成一块块，导致一些“预留空间”方便改动

5.删除文件只是删除了记录，在写入其他文件数据前原来数据还存在

6.增删减文件会导致碎片，不可避免

7.碎片整理，可以清理碎片

8.所有文件和目录都在根目录下

压缩

1.压缩会让文件更小，用更少的位来表示数据

2.减少重复信息，最简单的方法是游程编码（Run-Length Encoding）

3.另一种方法是“用更紧凑的表示方法”

“霍夫曼树”，每次选频率最低的两个，放在一起，并记录总频率

属性：按频率排列

每个分支用0和1表示

可以制作字典，将数据按字典中的二进制保存

4.游程编码和字典编码都是无损压缩，压缩时不会丢失信息，解压后，数据和之前完全一样

5.有些文件丢掉一些数据没关系，大多数有损压缩技术都用到了这点

比如声音文件中的超声波

6.删掉人类无法感知的数据的方法，叫“感知编码”

7.时间冗余，找出帧和帧之间相似的补丁，用简单的效果实现，比如移动和旋转，变亮和变暗

命令行界面

1.“人机交互”学科

2.大型计算机能同时支持多个程序和多个用户，叫做“多任务”和“分时系统”

3.QWERTY键盘布局不是通用的，法国AZERTY布局，中欧常见QWERTZ布局

4.十字打字，“十指盲打”，专业打字员每分钟100字以上

5.电传打字机

6.电传交互界面在1960~1970很常见，输入一个命令，按下回车，然后计算机会输出来，这叫“命令行界面”

7.1970年，屏幕代替电传打字机

8.交互文字游戏 Zork

压缩

1.压缩会让文件更小，用更少的位来表示数据

2.减少重复信息，最简单的方法是游程编码（Run-Length Encoding）

3.另一种方法是“用更紧凑的表示方法”

“霍夫曼树”，每次选频率最低的两个，放在一起，并记录总频率

属性：按频率排列

每个分支用0和1表示

可以制作字典，将数据按字典中的二进制保存

4.游程编码和字典编码都是无损压缩，压缩时不会丢失信息，解压后，数据和之前完全一样

5.有些文件丢掉一些数据没关系，大多数有损压缩技术都用到了这点

比如声音文件中的超声波

6.删掉人类无法感知的数据的方法，叫“感知编码”

7.时间冗余，找出帧和帧之间相似的补丁，用简单的效果实现，比如移动和旋转，变亮和变暗

命令行界面

1.“人机交互”学科

2.大型计算机能同时支持多个程序和多个用户，叫做“多任务”和“分时系统”

3.QWERTY键盘布局不是通用的，法国AZERTY布局，中欧常见QWERTZ布局

4.十字打字，“十指盲打”，专业打字员每分钟100字以上

5.电传打字机

6.电传交互界面在1960~1970很常见，输入一个命令，按下回车，然后计算机会输出来，这叫“命令行界面”

7.1970年，屏幕代替电传打字机

8.交互文字游戏 Zork

屏幕&2D图形显示

1.文本图形和文字图形最早是分开的，屏幕不清晰

2.早期屏幕的典型用途：跟踪程序的运行情况（比如寄存器的值）

3.阴极二极管，电子路径由磁场控制，将电子变换方向打在屏幕上

引导电子束描绘形状，叫“矢量扫描”

按固定路径来，一行一行来，从上向下，从左到右，不断重复，叫“光栅扫描”

4.屏幕上显示清晰的点叫“像素”

5.液晶显示器LCD，采用光栅扫描

6.早期计算机不用像素，像素占太多内存

7.早期计算机不存像素存字符

8.“字符生成器”从内存读取字符，转换成光栅图形

9.ROM只读存储器，存着每个字符的图形，叫“点阵图案”

10.“字符显示器”会访问屏幕缓冲区

11.有人用字符模仿图形界面

12.可以用“矢量指令”画“矢量图形”

13.Sketchpad是一个交互式图形界面，用途是计算机辅助设计CAD

用了输入设备光笔

可以让线条完美平行，长度相同，完美垂直90度，动态缩放

是人机交互的转折点

14.真正像素的计算机和显示器出现在1960年代末，用内存中的位对应屏幕上的像 素，叫位图显示，早期存在“帧缓存区”，早期时，这些数据存在高速视频内存 里，简称VRAM

冷战和消费主义

1.二战促进了计算机发展

2.美国国家科学基金会负责给研究提供资金

3.贝尔获得了晶体管的授权

4.苏联计算机发展比较落后

5.真空管和晶体管无法适应太空环境，NASA采用了集成电路

6.军事洲际导弹推动了集成电路大规模生产

7.日本半导体在60年代靠低利润率占领了消费者市场，导致美国公司倒闭

8.英特尔把精力转向处理器

9.廉价的微处理器催生了新的产品，不如街机游戏

个人计算机革命

1.单芯片CPU强大，体积小，便宜

2.成本小，性能提高导致个人电脑出现

3.解释器

4.Altair8800有Basic解释器，催生了更多的计算机爱好者

5.苹果公司选择了“封闭架构”，自己设计一切，用户无法加新硬件到计算机中

图形用户界面

1.早期的交互式图形程序是一次性项目，没有良好的体验

2.施乐奥托有图形界面

3.Alto团队用窗口，图标，菜单和指针来做，叫WIMP界面

4.GUI是“事件驱动编程”，不是自上而下执行，代码可以在任意事件执行，以影响事件

5.1981年发布了施乐之星系统

6.Windows 95有“多任务”和‘’受保护内存“

7.Microsoft Bob页面不够简洁，失败

3D图形

1.图形算法负责把3D坐标拍平显示到2D屏幕上，叫3D投影

2.正交投影

透视投影

3.填充图形的经典算法叫扫描线渲染，进行填充像素

4.减轻锯齿的方法是抗锯齿，多边形里面的像素直接填充，边上的填充浅颜色的

5.3D中存在遮挡

从远到近排序，先填远的

深度缓冲：将多边形的距离对比，记录小的，如果距离一样，结果不可预测

6.背面剔除：忽略多边形背边，减少一半运算

7.明暗处理：考虑多边形面对的方向，他们面对的方向叫“表面法线“，根据其余光源的关系确定明暗

8.纹理

纹理映射：查询纹理，取平均颜色，并填充多边形

9.图形的专门处理器GPU“图形处理单元”，在显卡上，周围有RAM，有多个核心

计算机网络

1.第一个网络在1950~1960年诞生，“球鞋网络”

可以共享存储器和硬件设备

2.1970年前计算机大多是单独工作的

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

最成功的是“以太网”

以太网需要计算机有唯一的媒体访问控制地址，简称MAC地址

这个唯一的地址放在头部，作为数据的前缀发送到网络中

计算机只需要监听以太网电缆

多台电脑共享一个传输媒介，这种方法叫“载波侦听多路访问”，简称“CSMA”

载体传输数据的速度叫“带宽”

4.计算机能够监听电线中的信号检测冲突，停止传送信息

但是很多计算机都会抢停顿间隔，导致越来越多的冲突

可以分配不同的等待时间，并进行指数退避

5.载体和其中设备总称“冲突域”collision domain

6.可以拆分冲突域，交换机位于两个更小的网络之间，必要时才在两个网络间传数据

7.把电路连接到正确的目的地叫“电路交换”。

8.路由"报文交换"，消息会经过多个站点。可以用不同路由，使通信更可靠更能容错

9.消息沿着路由跳转的次数叫“跳数”hop count

跳数可以记录是否出错，如果某条消息跳数很高，就知道路由肯定哪里出错了，这叫“跳数限制”

10.报文交换的缺点之一是报文有时比较大，会堵塞网络

解决办法是将大报文分成很多小块，叫“数据包”，每个数据包都有目标地址

报文的具体格式由“互联网协议”定义，简称IP

11.每台电脑需要一个IP地址

12.路由器会平衡与其他路由器之间的负载，叫“阻塞控制”

13.IP上的TCP/IP可以解决乱序问题

14.“分组交换”

互联网

1.计算机首先要连接到局域网LAN

局域网再连接到广域网WAN，WAN的路由器一般属于你的“互联网服务提供商”简称ISP

2.用Windows，Mac OS Linux系统，可以用traceroute来看跳了几次

3.IP是基础的协议，数据包的头部只有目标地址，头部存“关于数据的数据”，也叫元数据

4.需要更高级的协议，最简单的叫“用户数据报协议”简称UDP，头部包括有用的信息，信息之一是端口号，每个想访问网络的程序，都要向操作系统申请一个端口号

还包括“校验和”，会将数据加起来，超过16位时，舍弃低位

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

6.所有数据必须到达，就要用“传输控制协议”，简称TCP，TCP有“端口号”和“校验和”

TCP数据包有序号，所以可以解决乱序问题

TCP要求接收方的电脑收到数据包并且校验和检查无误后，给对方发一个确认码ACK，代表收到了，一定时间没有收到确认码，会再发一次

收件方可以删除重复数据包

TCP可以调整同时发包数量，解决拥堵

问题

7.“域名系统”，简称DNS，顶级域名在最顶部，比如.com，下一层是二级域名，比如google.com，再下一层是子域名

万维网（WORLD WIDE WEB）

1.传输数据最多的程序是万维网

2.万维网的最基本单位是单个页面

页面有内容，也有去往其他页面的链接，这些链接叫“超链接”

3.文字超链接也叫“超文本”

超文本指向的通常是另一个网页

4，为了使网页能够互相连接，每个网页需要一个唯一的地址，这个地址叫“统一资源定位器”URL

5.“超文本传输协议”HTTP

6.超文本标记语言HTML，有18种HTML指令

7.层叠样式表(CSS)和JavaScript

8.搜索引擎

有三个部分

爬虫，一个跟着链接到处跑的软件，每当看到新链接，就加进自己的列表里

不断扩张的索引，记录访问过的网页上，出现过哪些词

查询索引的搜索算法

9.网络中立性

应该平等对待所有的数据包

计算机安全

1.需要网络安全减少虚拟世界中的犯罪

2.计算机安全可以看成是保护系统和数据的：保密性，完整性和可用性

3.保密性是只有有权限的人才能读取计算机系统和数据

4.完整性是只有有权限的人才能使用和修改系统和数据

5.可用性是有权限的人应该随时可以访问系统和数据

6.DDOS（拒绝访问攻击）是黑客发大量的假请求到服务器，让网络很慢或者挂掉，这是攻击可用性

7.安全专家会从抽象层面想象“敌人”可能是谁，这叫“威胁模型分析”

8.安全问题可以总结为两个问题：

1.你是谁？

2.你能访问什么？

9.为了区分谁是谁，我们用“身份认证”（authentication）

1.你知道什么

2.你有什么

3.你是什么

10.暴力攻击（brute force attack）：试遍一切可能

一般系统会限制次数

但是利用僵尸网络控制很多电脑可以多次尝试

11.“双因素”或“多因素”认证

12.身份验证后，来到了“访问控制”，访问权限通过”权限或“访问控制列表（ACL）来实现

13.只能向上读，不能向下写的方法叫Bell-LaPadula模型

14.系统级安全“安全内核”

构建安全内核的挑战在于：决定内核应该有什么，代码越少越好

15.“独立安全检查和质量验证”

16“隔离”减少攻破后的损失

黑客与攻击

1.“NANA镜像”，物理接触到电脑，往内存上接几根线，复制整个内存。

2.常见的漏洞利用叫“缓存区溢出”。用“边界检查”可以解决。

4.可以在缓存区留一些位置，跟踪里面的值，看是否发生变化，来识别是否有入侵者。这些内存空间就做“金丝雀”(CANARIRS),因为以前金丝雀下矿会警告危险。

5.另一种手段叫“代码注入”常用于攻击用数据库的网站。

6.软件制造者不知道的新漏洞叫“零日漏洞”。

7.有足够多的电脑有漏洞，让恶意程序在电脑间互相传播，叫“蠕虫“。

8.黑客攻下足够多的电脑，可以组成“僵尸网络”。可以发起“拒绝服务攻击”简称DDoS，攻击服务器。

加密

1.系统架构师会部署“多层防御”（defense in depth）。

2.计算机安全中常见的防御形式是密码学（cryptography）。

3.“加密”和“解密”。

4.“替换加密”，缺点是不会改变数据的频率信息。熟练的密码破译师可以从统计数据中发现规律，进而破译密码。

5.“移位加密”

6.2001年出了：高级加密标准（AES）。

7.防止密钥被截获，解决办法是“密钥交换”。

机器学习&人工智能

1.机器学习算法让计算机可以从数据中学习，然后自行做出预测和决定

2.大多数计算机科学家会说，机器学习是为了实现人工智能这个更宏大目标的技术之一

3.做分类算法的算法叫“分类器”

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

为了做出更好的判断，需要“训练数据”

4.“决策边界”

5.“混淆矩阵”可以记录正确数和错误数

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

7.“决策树”，生成决策树的机器学习算法需要选择用什么特征来分类

8.“支持向量机”

9.机器学习面临的问题：特征增多时，上千维度的决策空间，给超平面找出一个方程

10.“支持向量机”和“决策树”来源于统计学

11.人工神经网络，计算机模拟时不用化学信号电信号，而是利用数字。两个神经元最兴奋的是分类结果

12.有输入层，输出层和隐藏层

隐藏层负责把输入变成输出干分类这个重活

13.神经元有激活函数，也叫传递函数，应用于输出，对结果执行最后一次数学修改

14.加权，求和，偏置，激活函数，会应用于一层中每个神经元

15.隐藏层可能不只有一层，可以有很多层，“深度学习”因此得名

16.这种AI叫“弱AI”或“窄AI“，只能做特定的任务

17.真正通用的，是像人类一样聪明的AI，叫“强AI”，目前为止没有做出来“强AI”

18.有人认为强AI不能被做出来

计算机视觉

1.图像是像素的网格，每个像素的颜色，通过三种基色定义：红蓝绿

2.记录下球的颜色，保存中心像素的RGB值，用算法检索每一帧每一个像素，最贴近的是球

3.“核”或“过滤器”

4.把核应用于像素块，这种操作叫“卷积”,“核”能锐化图像，能像饼干模具一样，匹配特定的形状

5.这两个边缘增强的核叫“Prewitt算子”

6.如今的热门算法是“卷积神经网络”，神经网络有多个神经元，神经网络可以用用来学习核来识别图像中的特征

7.“卷积神经网络”用一堆神经元处理图像数据,“卷积神经网络”一般会有很多层，来识别复杂的物体和场景

8.生物识别，跟踪标记点可以理解肢体行为

9.抽象是构建复杂系统的关键

自然语言处理

1.“自然语言处理”NLP

2.NLP的一个早期基本问题是怎么把句子切成一块块

3.“短语结构规则”

4.“分析树”

5.数据块更小更容易处理

6.“知识图谱”

7.聊天机器人甚至可以发展出自己的语言

8.“语音识别”，

9.波形到频率的转换用快速傅立叶变换FFT

10.构成单词的声音片段叫“音素”，英语有44种音素

11.语音合成

机器人-ROBOTS

1.机器人时代已经到来

2.机器人由计算机控制，可以执行一系列动作的机器

3.有时叫虚拟人物“机器人”，叫“bot”和“agent”更合适

4.来源robota（强迫劳动）斯拉夫语

5.没有电肯定没有电子部件的机器，叫“自动机”

6.“土耳其行棋傀儡”，像机械的人工智能，机器里有人控制

7.第一台计算机控制的机器出现在1940年代晚期，计算机数控的机器简称CNC

8.负反馈电路

9.实际器件可能有惯性，不能精确的随时停止

10.自然界中有外力，为了处理外力，需要更复杂的控制逻辑

11.有个使用广泛的机制，有控制回路和反馈机制，叫“比例-积分-微分控制器”，一般简称“PID控制器”，以前是机械，现在是软件

12.“比例值”，就是“实际值”和“理想值”差多少，偏差越多，越用力，是比例控制的。算积分值，就是一段时间内误差的总和，不够会继续用力，最后是“导数值”，是期望值与实际值之间的变化率，用来解决未来的变化，有时也叫“预期控制”

三个值一起用，有不同的权重

这些值由更高层次的软件而来

应用比如车里面的巡航控制

13.“无人驾驶”有智力并且能杀人的机器叫

“致命自主武器”lethal autonomous weapons

14.艾萨克阿西莫夫写了“机器人三定律”，之后又加了“定律0”

计算机心理学

1.理解人类的认知系统能帮助我们设计更好的界面

2.分块是指把信息分成更小，更有意义的块

3.人类的短期记忆能记住5到9个东西，，保守一点，分组一般是5个或更少，所以电话号一般分组

4.“直观功能”为如何操作物体提供线索

应该直观的知道怎么使用而不是加一些说明

比如看到按钮就想到点击

这是图形界面比命令行更容易用的原因之一

5.与直观功能相关的一个心理学概念是”认出与回想“

用感觉来触发记忆

6.与心理学相冲突的是“专业知识”，建立如何高效完成事情的“心理模型”

7.情绪会影响日常生活，比如学习，沟通和决策

8.得到的数据会与计算模型结合使用，模型写明人类如何表达情感

9.比起面对面交流，人们更愿意在网上透露自己的信息

10.如果想说服，讲课，引起注意，眼神注视非常重要

11.“增强凝视”，比如纠正摄像头的位置

12.人机交互HRI，研究人机交互的领域，比如人类如何感受机器人的不同形式和不同行为

13.类人机器人，这个“几乎像人类”和“真的人类”之间的小曲线，叫“恐怖谷”

教育科技

1.可以倍速暂停

2.“大型开放式在线课程”MOOC

3.缺点：没有好的反馈

4.“智能辅导系统”

5.“判断规则“加选择算法，组合在一起成为”域模型“

6.智能辅导系统负责创建和维护学生模型

7.“贝尔斯知识追踪”

奇点，天网，计算机的未来

1.“普适计算”的愿景

2.人工智能

3.智能科技失控性发展叫“奇点”

4.“复杂度刹车”，随着复杂度的增加，发展减慢

5.“技术性失业”

6.从生物体变成数字体，可能是下一次进化跨越