计算机的实质：简单的组件 + 层层抽象
电子计算机发展
继电器→真空管→晶体管
布尔代数在计算机中的实现
- 变量：没有常数，仅 True 和 False这两个变量。
- 三个基本操作：与或非。
- 为什么称为“门”：控制电流流过的路径
异或
整数、浮点数的表示
- 整数：（有符号类型为例）1符号+31/63数字
- 浮点数：例如 IEEE 754 标准
算术逻辑单元
简称 ALU，Arithmetic&Logic Unit
有 2 个单元，1 个算术单元和 1 个逻辑单元
- 作用：计算机中负责运算的组件，处理数字/逻辑运算的最基本单元
算术单元
- 由半加器、全加器组成，底层是 与/或/非/异或 门
半加器
.png)
用于计算一位数字加减。输入A，B，输出：SUM当前位的和，CARRY进位
全加器
同时进行多位加法，本质是半加器串起来，将进位变成下一位的输入
例如：实现基本的多位加法器：除了个位是半加器，高位都是全加器
——又叫行波进位加法器，成波状逐级计算，效率明显不行
超前进位加法器（更先进更高效）
发现位之间的数量关系，直接得到每一位的算式，输入数字后并行计算，不用等后一位结果
推导式
$$C_{i+1}=G_i+P_iC_i$$
现代的加法器是超前进位加法器的变种
类似的，算术单元也可以实现减法、自加/自减计算
逻辑单元
执行 与 或 非 等逻辑操作，和简单的数值测试
ALU 的抽象
- 输入 A，B
- 输出
- 标志：溢出、零、负数
.png)
寄存器与内存
- 锁存器：用逻辑门存储 1 位数字
- 寄存器：1 排锁存器
- 矩阵：n*n锁存器的矩阵（每个锁存器有地址）
- RAM：一系列矩阵+电路，根据地址读写数据
锁存器
利用输入和输出的或门保存 1，将复位的非门接入与门保存 0
门锁（升级版锁存器）
.png)
寄存器
.png)
锁矩阵
注意点：单个矩阵每次只能读写其中的一格，如果要存储 8 位数字，需要 8 个矩阵，读写时取每个矩阵中的相同位址（用到多路复用器）
内存
略
CPU
- CPU通常由寄存器/控制单元/ALU/时钟组成
- 与 RAM 配合，用“地址线”、“数据线”和“允许读/写线”进行通信
- 指令：多条指令组成程序，如数学、内存指令
- 时钟：以精确节奏触发电信号，让控制单元推动 CPU 内部操作
- 时钟速度：取指令 → 解码 → 执行 每步的速度，单位Hz
时钟速度大，CPU速度快，耗电up，故超频/降频
工作原理
- 指令表：给 CPU 支持的所有指令分配 ID
- 控制单元：指挥部，控制指令有序读取、运行、写入
- 指令地址寄存器：按顺序通报地址，RAM 将指令交给指令寄存器
- 指令寄存器：存储具体指令
- 取指令：指令地址寄存器让RAM到指定地址取指令，给指令寄存器
- 解码：指令寄存器发送指令给控制单元 → 控制单元解码（有逻辑门确认）
- 执行：涉及计算时，调用指定的寄存器（有很多种），传操作码给 ALU，调用内存，结果存回指令寄存器
指令和程序
- 指令：指示计算机要做什么的代码（机器码），多条指令共同组成程序。如数学指令，内存指令
- 注:指令和数据都是存在同一个内存里的
- 指令集：记录指令名称、用法、操作码以及所需 RAM 地址位数的表格
指令的执行
- 原则：
- RAM 每一个地址都放了 0 或 1
- 数字可以表示值，其中特定组合表示指令
传送指令：- 读写各种存储中数据
计算指令：- 算术、逻辑、比较（算术减法）、移位
跳转指令：- 用于条件、循环
- 此外还有用于函数调用的地址跳转
指令长度
由于早期计算机每个字只有 8 位，指令只占 4 位，意味着只能有 16 个指令，这远远不够
现代计算机有两种方式解决指令不够用的问题：
最直接的是用更多位来表示指令，如 32 位或 64 位
采用“可变指令长度”，令不同的指令的长度不同，尽量节约位数
假设 1 个字为 16 位，如果某指令不需要操作内存，则可以省去寻址的位数
该情况下，部分指令后面需要跟数据，如 JUMP，称为立即值
高级 CPU 设计
- 缓存：CPU 中的小块 RAM，用于存储批量指令
- 缓存命中：想要的数据已经在缓存里
- 缓存未命中：想要的数据不在缓存里
- 脏位：缓存每块空间有特殊标记，检测缓存数据是否与 RAM 一致
如何提升性能
早期通过加快晶体管速度，来提升 CPU 速度。但很快该方法到达了极限
后来给 CPU 设计了专门除法电路+其他电路来做复杂操作：如游戏，视频解码
缓存
在 CPU 内部设置一小块内存，称为缓存
- RAM 可以一次传一批数据进来，让 CPU 不会闲着（因为本身就有传输延迟）
- 缓存可以当临时空间，存复杂运算的中间值
缓存同步
缓存已满但 CPU 仍需往缓存内输入数据时，优先将脏位数据传回 RAM 腾出位置，防止数据覆盖而丢失
指令流水线
让 取址→解码→执行 同时进行，且能并行执行指令
理论上让平均执行时间缩短为三分之一
设计难点：数据具有依赖性 跳转程序
数据依赖性解决方法：
乱序运行、预测分支（高端 CPU）
多核 CPU
多核 CPU 可以独立处理，也能共享资源
超级计算机—— ∞核CPU
现代计算机基础结构——冯诺依曼计算机
一个处理器(有算术逻辑单元)+数据寄存器+指令寄存器+指令地址寄存器+内存
编程语言发展史——从后往前
语言run的过程
高级编程语言——编译器——汇编码/机器码
语言发展时间轴
60 年代：LGOL LISP BASIC
70 年代：Pascal C Smalltalk
80 年代：C++ Objective-C Perl
90 年代：Python Ruby Java
PS：安全漏洞&补丁由来
打孔纸带时代，程序出现问题和物理修补的方式
阿兰图灵——可判定性问题
是否存在一种算法，输入正式逻辑语句 输出准确的"是"或"否"答案？
-
阿隆佐邱奇，Lambda算子
美国数学家 阿隆佐·丘奇，开发了一个叫"Lambda 算子"的数学表达系统，证明其不存在。 -
图灵机
只要有足够的规则，状态和纸带，图灵机可以解决一切计算问题。和图灵机一样完备，叫做图灵完备。（后来，停机问题证明了，图灵机不能解决所有问题） -
图灵测试
集成电路与摩尔定律（硬件发展
摩尔定律的瓶颈
1、光的波长限制
2、量子隧穿效应
操作系统
-
操作系统(OS)
操作系统也是一种程序，不过它有操作硬件的特殊权限，可以运行和管理其他程序。 -
批处理
一个程序运行后会自动运行下一个程序。 -
外部设备
和计算机连着的其他设备，如打印机。 -
设备驱动程序
为了使所写程序和不同类型的电脑兼容，我们需要操作系统充当软件和硬件之间的媒介，更具体地说，操作系统提供程序编程接口(API)来抽象硬件,叫“设备驱动程序”。程序员可以用标准化机制，和输入输出硬件（I/O）交互， -
多任务处理
操作系统能使多个程序在单个CPU上同时进行的能力，叫做“多任务处理” -
虚拟内存
多程序处理带来了一个程序所占用内存可能不连续的问题，导致程序员难以追踪一个程序，为了解决这个问题操作系统会把内存地址虚拟化，这叫“虚拟内存”。 -
动态内存分配
虚拟内存的机制使程序的内存大小可以灵活增减，叫做“动态内存分配”，对程序来说，内存看上去是连续的。 -
内存保护
给每个程序分配单独的内存，那当这个程序出现混乱时，它不会影响到其他程序的内存，同时也能有效地防止恶意程序篡改其他程序，这叫做内存保护。 -
多用户分时操作系统（Multics）
用来处理多用户同时使用一台计算机的情况，即每个用户只能用一小部分处理器，内存等， -
Unix
把操作系统分成两个部分，一个是操作系统的核心部分，如内存管理，多任务和输入/输出处理，这叫做“内核”，第二部分是一堆有用的工具，比如程序和运行库。
内存和储存介质（存储技术的发展）
在计算机中，高速昂贵和低速便宜的内存混合使用以取得一个平衡
-
早期存储介质
-
磁带、磁鼓、硬盘
-
软盘
软的 -
光盘
光的不同反射被光学传感器捕获，解码为 1 和 0 -
SSD 硬盘
里面是集成电路
文件系统
按格式存的目的是方便
-
TXT 文本文件
用ASCII解码 -
WAV 音频文件
记录的是振幅 -
BMP 图片文件：
记录每个像素的红绿蓝 RGB 值 -
目录文件：
用来解决多文件问题，存其他文件的信息，比如开头，结尾，创建时间等 -
平面文件系统 - Flat File System
文件都在同一个层次，早期空间小，只有十几个文件，平面系统够用 -
解决文件紧密的排序造成的问题
-
把空间划分成一块块
-
文件拆分存在多个块里
-
-
碎片整理
文件的增删改查会不可避免的造成文件散落在各个块里，如果是磁带这样的存储介质就会造成 问题，所以需要碎片整理——计算机把文件内容调换位置 -
分层文件系统 - Hierarchical File System：
有不同文件夹，文件夹可以层层嵌套
压缩
能存更多文件，传输也更快
-
游程编码 Run-Length Encoding
适合经常出现相同值的文件，比如用统一的（颜色-长度）格式压缩图片（脸黑的话文件会变大 -
无损压缩 Lossless compression
没有损失任何数据的压缩。 -
霍夫曼树 Huffman Tree和字典编码 Dictionary coders
一种高效的编码模式，如果是压缩图片，可以将图片数据分组，按重复频率编码 -
感知编码 Perceptual coding和有损压缩 jpeg 格式
删掉人类无法感知的数据的有损压缩方法，叫做“感知编码”，如音频文件，人类听不到超声波，所以可以舍去，MP3就是音频的一种压缩形式。
- 有损压缩的一个例子就是jpeg模式，相邻的相似像素可以融为一体。
- 时间冗余 Temporal redundancy
视频很多帧的背景一样，构成了时间冗余。因此可以只存变化的部分。进阶的视频压缩模式会找到帧与帧的相似性，然后打补丁，MPEG-4 是视频压缩的常见标准。
屏幕与 2D 图形显示
PDP-1 计算机、键盘和显示器分开，屏幕显示临时值
阴极射线管 Cathode Ray Tube (CRT)
CRT 有两种绘图方式：
- 矢量扫描 Vector Scanning
- 光栅扫描 Raster Scanning
液晶显示器 Liquid Crystal Displays (LCD)，像素 (Pixel)
随着显示技术的发展，出现了LCD，LCD 也用光栅扫描。在屏幕上显示的清晰的点，叫"像素"
字符生成器 Character generator，
相比于像素，为了减少内存，人们更喜欢使用字符，计算机需要额外硬件，来从内存读取字符，转换成光栅图形 \N 这样才能显示到屏幕上个硬件叫 "字符生成器"，基本算是第一代显卡。它内部有一小块只读存储器，简称 ROM，存着每个字符的图形，叫"点阵图案"
屏幕缓冲区 Screen buffer
为了显示，"字符生成器" 会访问内存中一块特殊区域 这块区域专为图形保留，叫 屏幕缓冲区，程序想显示文字时，修改这块区域里的值就行。
图形用户界面 (GUI)
1981年 Xerox Star system(施乐之星系统)
1983年 Apple Lisa
1985年 Windows 1.0
3D 图形
线框渲染 Wireframe Rendering
有图形算法 负责把3D坐标"拍平"显示到2D屏幕上，这叫3D投影(包括正交投影和透视投影)，所有的点都从3D转成2D后，就可以用画2D线段的函数来连接这些点，这叫线框渲染
网格 Mesh
如果我们需要画比立方体复杂的图形，三角形比线段更好，在3D图形学中我们叫三角形"多边形"(Polygons)，一堆多边形的集合叫 网格，网格越密，表面越光滑，细节越多，
三角形更常用因为能定义唯一的平面
扫描线渲染 Scanline Rendering——填充图形的经典算法
抗锯齿——边缘羽化，如果像素在内部，就直接涂颜色，如果像素经过边缘，颜色浅一些
遮挡 Occlusion
用排序算法，从远到近排列，然后从远到近渲染，这叫画家算法
深度缓冲 Z Buffering
另一种画遮挡的方法，简而言之，Z-buffering 算法会记录场景中每个像素和摄像机的距离，在内存里存一个数字矩阵，首先，每个像素的距离被初始化为"无限大"，然后 Z-buffering 从列表里第一个多边形开始处理，也就是A，它和扫描线算法逻辑相同，但不是给像素填充颜色，而是把多边形的距离和 Z-Buffer 里的距离进行对比，它总是记录更低的值，因为没对多边形排序，所以后处理的多边形并不总会覆盖前面的
概念
Z Fighting 错误
平面上表示第三个维度，上下层产生的冲突
背面剔除 Back Face Culling
表面法线 Surface Normal
平面着色 Flat Shading
高洛德着色 Gouraud shading, 冯氏着色 Phong Shading
纹理映射 Texture Mapping
GPU 的出现——图像的并行处理
计算机网络——原理和技术
局域网 Local Area Networks - LAN
如以太网
媒体访问控制地址 Media Access Control address - MAC
用于确认局域网和WiFi传输的对象
载波侦听多路访问 Carrier Sense Multiple Access - CSMA
多台电脑共享一个传输媒介，叫做载波侦听多路访问，共享媒介又称载体，如WiFi的载体是空气，以太网的载体是电线。载体传输数据的速度叫带宽
指数退避 Exponential Backoff
当多台计算机同时想要传输数据时，就会发生冲突，当计算机检测到冲突 就会在重传之前等待一小段时间，这一段时间包括固定时间+随机时间，再次堵塞时固定时间将会指数级增加
冲突域 Collision Domain
载体和其中的设备总称为“冲突域”，为了避免冲突，可以用交换器
报文交换 Message Switching
报文的具体格式简称IP，每一个电脑都会有一个IP地址
好处，可以用不同路由，通信更可靠也更能容错。
坏处，当报文比较大的时候，会堵塞线路。解决方法是 将大报文分成很多小块，叫"数据包"，来进行运输，这叫“分组交换”。路由器会平衡与其他路由器之间的负载 以确保传输可以快速可靠，这叫"阻塞控制"
消息沿着路由跳转的次数 叫"跳数"(hop count)，看到哪条线路的跳数很高，说明出了故障，这叫跳数限制。
互联网
电脑连接互联网的过程
你所用的电脑首先要连接到局域网，家里WiFi路由器连着的所有设备，组成了局域网，局域网再连到广域网（WAN），广域网的路由器一般属于你的互联网服务提供商（ISP），再连更大的WAN，往复几次，最后连到互联网主干。
IP - 互联网协议 - Internet Protocol
IP负责把数据包送到正确的计算机
UDP - 用户数据报协议 - User Datagram Protocol
UDP负责把数据包传送到正确的程序，有端口号（哪个程序），校验和（数据是否损坏）
校验和 - Checksum
UDP校验和只有16位，超过这个数，弃高位。
TCP - 传输控制协议 - Transmission Control Protocol
如果要控制所有数据必须到达，就用传输控制协议
- 特点
1 控制发送的文件按顺序到达
2 要求接收方确认无误后发送确认码（ACK），确认码的成功率和来回时间可以用来推测网络的拥堵程度，TCP可以根据这个调整传输率。由于这个特点，TCP对时间要求高的程序不适用
DNS - 域名系统 - Domain Name System
记 IP 和端口很难，DNS 用来把域名和IP地址一一对应，是树状结构
开放式系统互联通信参考模型
加密和解密
-
移位加密等固定加密规则
如凯撒加密 -
对称加密
有公钥，交流的双方各持一份私钥，加密后对方可以解密，双向
至于公钥和私钥的配合方式，有多种算法
特点是效率高，但是因为是双向交流，为了保证安全，密钥的保存和保密反而繁琐
- 非对称加密 - Asymmetric encryption
公开公钥，自己保存私钥。可以用公钥加密信息，用私钥解密，或者反过来
可以理解为单向行为，所以可以直接建立很多独立的连接，不会被密钥烦到
最有名的非对称加密算法是RSA
人工智能与未来
机器学习
- 分类识别——给定分类特征，写分类算法
- 先给一些训练数据，由统计学得到基本的决策边界
- 多给点数据，量化识别准确度，最终得到决策树
- 支持向量机——区分不同数据的最好的决策边界
即此边界和不同数据之间的距离都为最远
设一个边界为一个 =0 的方程，通过取适当参数，可以得到与两端数据相交的平行面的 =±1 的方程。取数据交点的坐标为向量，两方程相减可以得到一个点积为 2 的式子。再在边界上取两点，可以得到一个点积为 0 的式子，由于系数相同，点乘中涉及的另一个向量相同，即与边界向量垂直，因为积一定，要使两边数据点的距离尽可能远，我们还要求此固定向量的最小值。后面的部分是高数问题
- 深度学习——神经网络：模拟人类学习过程，自行建立输出逻辑以增加正确性，隐藏过程
- 强化学习
计算机视觉
颜色跟踪算法——跟踪一个像素
检测垂直边缘的算法
要识别边缘，可以判断其两边像素的颜色差异程度
核/过滤器 kernel or filter
核沿像素移动，逐步处理图像数据，这其中可以发现图像的一些特征
卷积 convolution
把核应用于像素块
卷积神经网络 Convolutional Neural Networks
用一层层不同的核来识别复杂场景，用脸来举例，先识别边缘，然后形状，器官...直至某一层把所有特征堆积在一起，识别出脸之后，可以进一步用其他算法定位面部标志，如眼睛和眉毛具体位置，从而判断心情等信息
自然语言处理 NLP
通过词性 Parts of speech 和短语结构规则 Phrase structure rules 构建分析树 Parse tree
并结合语言模型 Language Model 来实现语音识别 Speech recognition
实现原理
快速傅立叶变换 Fast Fourier Transform，把波形转换成频率
音素 Phonemes
构成单词的声音片段
语音合成 Speech Synthesis
机器人控制的回路
负反馈回路 negative feedback loop
比例-积分-导数控制器 Proportional–Integral–Derivative controller PID
通过控制三个值，比例值——实际值和理想值差多少，积分值——一段时间误差的总和，前两者用来修正错误：导数值（微分值）——期望值和实际值之间的变化率，用来避免未来的错误，这也叫预期控制，来控制进程。
