CS-Crash Course笔记

本文是B站上的视频计算机科学速成课的学习笔记，在极短的时间内能有一个对CS的概览

2023.07.20Update：结束了整个系列的观看，最大的后悔是应该在早一年的暑假中看完，不过人为时不晚
亿万年后太阳燃尽，地球成为星辰，也许我们的机器人孩子，会继续探索宇宙的每一个角落

1.计算机早期历史

信息时代：大规模使用计算机

计算设备历史

• 算盘
• 步进计算机（一连串的齿轮驱动）
  • 加法、减法（将乘除分解为连续的加减进行）
• 差分机（对多项式进行计算）
• 分析机：自动进行连续的任务（计算机的雏形）
• 美国人口普查的打孔卡片

2.电子计算机

继电器：用电控制的机械开关（通电时导通），有质量因而无法迅速开关，限制了速率

真空管：通过电子控制电路的导通，从机电到电子

降低成本和大小，提高速度和可靠性：晶体管

晶体管

半导体物理，控制导通或否

如今计算机中的晶体管小于50nm

3.布尔逻辑与逻辑门

二进制：只用真假/01代表信息

状态越多，越难区分信号

布尔代数：and、not、or

基础的逻辑元件（完全集）：与门、非门

4.二进制

1字节=8位

5.算术逻辑单元

ALU：算术逻辑单元（算数：Arithmetic，逻辑：Logic）

• 算数单元
• 逻辑单元

算数单元

逻辑门：and、or、not、xor

加法单元

由两个逻辑单元组成：xor和and

在不进位的条件下，0+0=0,1+0=1,0+1=1，与xor的运算机制一致

考虑进位，当两个输入都是1时，可以用and表示进位

不考虑进位：半加器

考虑进位：全加器

8种基本ALU

1. 加法
2. 戴进位的加法
3. 带借位的减法
4. 相反树
5. 增量+1
6. 减量-1
7. 不改变

基本组成

1. 输入A
2. 输入B
3. 操作码
4. 状态（是否进行）

6.寄存器&内存

RAM：随机存储器

Memory：持久存储

存储一位的元件

• AND可以用来存储0
• OR可以用来存储1
• 通过将输出连回输入（反馈），达到了储存特定信号的效果
• 

结合AND和OR可以做出能够储存一位的AND-OR锁存器：当设置和复位都是1，能够输出最后输入的信息

门锁

存储器的抽象结果，有数据输入和允许写入线

寄存器：一组锁存器称为寄存器，只能存放一个数字，数字的位数叫做位宽

减少寄存器中的导线及复杂度：使用矩阵结构进行构造

多路复用器：处理存储信息的地址（16位只要4位就能存储地址）

矩阵层层嵌套，来储存大量信息

7.中央处理器（CPU）

CPU负责执行程序：指令（前4位表示操作，后4位表示地址）

CPU的组成：寄存器、ALU、指令地址寄存器（存当前指令的地址）、指令寄存器（存当前的指令）

ALU

ALU（算术逻辑单元）和CPU（中央处理器）是紧密相关的两个概念。

CPU是计算机的核心部件，负责执行指令、控制计算机的运行和处理数据。它由多个功能模块组成，其中一个重要的模块就是ALU。

ALU是CPU中的一个子模块，主要负责执行计算和逻辑操作。它可以执行加法、减法、乘法、除法等算术运算，还可以执行与、或、非、异或等逻辑运算。ALU通过接收来自其他部件的指令和数据，进行运算操作，并将结果返回给其他部件或存储器。

简而言之，ALU是CPU中负责执行计算和逻辑运算的部分，而CPU是由多个功能模块组成的整体，其中之一就是ALU。

指令表

为了让CPU进行对应操作，会有对应的指令，为四位操作码，后4为表示数据从哪里来

工作流程

基本的流程为：取指令->解码->执行

1. 取指令
   1. 从指令地址寄存器中取出当前指令的地址
   2. 访问RAM中对应的地址，将指令存入指令寄存器中
2. 解码
   • 指令为8位，前4位位操作码，后四位为地址（RAM的地址）：
   • 00101110为传入的地址，则操作码为0010，解码为LOAD A，地址为1110，即为14，为RAM中位置为14处的地址
   • 如果指令为ADD操作，如10000100，1000表示ADD，0100代表了两个地址（两位可以表示4个值），表示将01的值加到00中（将寄存器B的值加到寄存器A中）
     • 由ALU进相加
     • 控制单元需要传入ALU的操作指令
     • 将值暂存在控制单元内部的寄存器中，再存入寄存器A中
   • 解码操作由控制单元进行解码
3. 执行
   1. 打开RAM的允许读取线，传入地址14，读取到值3
   2. 打开寄存器A的允许写入线，写入对应值3
   3. 将指令地址寄存器的地址+1

时钟

时钟以精准的周期，触发电信号，控制单元以这个电信号，推动CPU工作的进行。

CPU的时钟速度：“取指令、解码、执行”的速度。单位为Hz（1s进行几个周期）

CPU可以适当地超频和降频

8.指令和程序

CPU是可编程的

Jump指令：覆写指令地址寄存器中的地址，从而改变进行的指令的顺序

Halt指令：控制程序停止

通过不同指令的组合，实现程序功能

指令的数量

8位指令操作有4位，最多16条操作，同样最多16个地址，远远不够

现代CPU增加指令数的方法：

1. 增加位数（指令长度）
2. 可变指令长度（有的地址位不需要用到）

9.高级CPU设计

提高计算机速度：复杂度VS速度

现代CPU有专门的电路来进行特定操作，如果用标准操作实现，需要多个时钟周期。

额外电路进行特定操作

缓存：快速传数据给CPU

总线（BUS）：CPU和RAM之间传输数据的线

缓存（CACHE）：给CPU增加RAM。

可以由RAM一次传一批数据到CPU中，存在缓存中

• 从缓存中取数据的速度极快，CPU不用空等
• CACHE HIT：想要的数据已经在缓存中
• CACHE MISS：不在缓存中

缓存和内存中的数据可能不同，存在特殊位置，后续同步

指令流水线

用并行处理，充分利用闲置：取指令、解码、执行使用的是CPU的不同部分，可以进行并行处理，用上CPU的所有部分

弊端：

1. 上一步的解码可能在修改这一步读取的数据，流水线操作造成冲突，必要时需要停止流水线
2. 条件Jump指令会改变程序的执行流造成空等
   • 高级CPU进行分支预测提前执行可能的Jump后的指令
   • Jump指令可以视作分支路，预测分支后的结果

超标量流水线

一次性进行多条指令：增加几个相同的电路进行高频操作

多核处理器

一个CPU中有多个处理单元，共享一些单元如缓存

10.早期的编程方式

最初的编程为插线板编程，通过接线编写不同的程序

冯诺依曼结构：（程序和数据都存在一个地方）

• 1个处理器（有ALU）
• 数据寄存器
• 指令寄存器
• 指令地址寄存器
• 内存（存储数据和指令）

面板编程：开关，和打孔的效果等价，但体积更小

11.编程语言发展史

CPU能处理二进制：机器语言、机器码

汇编器：分析指令转换为二进制。一条汇编对应一条机器码

汇编和机器码是意义对应的（处理地址、值等等）

编译器：把高级语言转换为汇编或机器码

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

语法：规定句子结构的规则

控制语句：if-else、while

13.算法入门

算法：解决问题的具体步骤

归并排序能够直观体现$O(NlogN)$

14.数据结构

栈、队、树、图

选择不同的数据结构有不同的效果

15.阿兰·图灵

图灵机：理论计算设备

规定起始状态+规则则可运行

16.软件工程

解决方法：把函数打包成层级，把相关代码都放在一起，打包成对象

对象可以包含其他对象、函数、变量

面向对象

面向对象编程：通过封装组件隐藏复杂度

private：同一对象内部的其他函数才能调用

public：其他函数都可调用

IDE：集成开发环境

maybe vim

文档

注释、文档

版本控制

代码仓库：从中央服务器中获取pull，改动后commit

源代码管理可以跟踪改动记录

17.集成电路&摩尔电路

晶体管标志着计算时代2.0

PCB：印刷电路板：更小、更便宜、更可靠

晶体管：更高密度、更高性能

集成电路：计算时代3.0

18.操作系统

OS：本质还是软件，但有操作硬件的权限、运行和管理其他程序，其他程序由OS启动

充当软件和硬件之间的媒介

最大限度利用性能：在单个CPU上运行几个程序

将内存地址虚拟化：操作系统隐藏和抽象实际物理地址，OS自动处理映射关系

动态内存规划：让程序认为运行在连续内存上

Unix

将操作系统分为两部分

• 内核
  • 内存管理、多任务、输入/输出处理
• 有用的工具
  • 程序、运行库

19.内存&存储介质

内存：非永久性

利用磁性的正负表示01信息

光盘：表面有凹凸，反射光的属性不同，解码为01信息

20.文件系统

文件在底层都是长串的二进制码

文本格式

一长串的二进制值

利用ASCII码进行解码

元文件&文件头

关于数据的数据：元数据。存放在文件开头，在实际数据前面：文件头

在WAV文件开头储存波形的储存码率等，BMP文件存储图片的高度宽度等等

存储文件的位置

最简单存储的方式是连续存储，但OS不知道文件的其实位置

目录文件通常存储在最开头吧，方便查找，记录其他文件的名字和格式及相关信息

增删文件：修改文件目录

删除：修改文件目录，实际地址上依然存储信息，但是可以被覆写

文件夹

目录文件不仅需要指向文件，还需要指向目录：额外数据来区分

目录文件

存储其他文件的名字、扩展名、元数据（修改时间，文件所有者，文件的起始位置）

文件系统：专门管理文件

1. 将空间划分为一块一块
   • 有预留空间方便修改
   • 方便管理
2. 拆分文件在不同块中
3. 目录文件记录文件所在的多个块中
   • 删除文件：标记删除，但实际位置上的文件还在

碎片：文件在不同的块中，且顺序是乱的

• 增删文件导致，不可避免
• 文件系统会进行碎片整理

分层文件系统

有了文件夹的概念：目录不止要指向文件，还要指向目录

根目录：在最顶层的文件夹，存储文件和目录

移动文件只需要修改目录中的信息即可

21.压缩

简单性意味着效率不高

游程编码

适用于有大量重复信息的内容

用标签标记是实际数据还是数量：[标记0/1]Data

字典编码

Huffman编码

有损压缩

如音乐文件中去除超声波部分：用不同精度编码不同频率

感知编码：删除了人无法感知的信息

22.命令行界面

命令行界面：

• 用户输入各种命令
• 加入各种参数，由计算机输出

23.屏幕&2D图形显示

减少内存消耗：

1. 储存固定的ASCII码，由特定硬件负责输出到显示器
2. 利用线段绘制图像

24.冷战和消费主义

起初用作军事用途

计算机能够增强人的智力：记忆力、计算速度等等

阿波罗导航计算机：第一次使用集成电路

政府和消费者推动了计算机的发展

25.个人计算机革命

单芯片CPU的出现：强大+便宜+体积小

解释器：将BASIC语言转换为机器码

解释器运行时转换，编译器提前转换

开放式架构：有文档，可以外接其他设备

26.图形用户界面

图形用户（GUI）界面是革命性变化

用计算机辅助工作来增强工作

让计算机易用：

1. 多窗口（可重叠等等）
2. 桌面组件
3. 可复用的基本元素（勾选等等）

创建一个界面

1. 调用GUI-API创建一个窗口指定窗口的大小
2. 添加组件、文字等等

GUI：事件驱动型

通过用户触发的事件来决定执行哪段代码

27.3D图形

图形算法：将3D图形转换为2D显示

渲染

3D投影：

1. 正交投影：各边在投影中相互平行
2. 透视投影：各边收敛到一点

在3D图形处理中，将三角形称为多边形

网格：多边形的集合

网格越密，精度越高，表面越光滑

填充

扫描线渲染

将多边形转换为有填充的区域：

1. 建立坐标系X-Y，将三角形放入
2. 得到最高和最低的y坐标，扫描在这个区间之间进行
3. 从上到下，一次处理一行，必然有两点相交
4. 将一行内在两边范围内的填充

边缘锯齿比较多，尤其低像素

抗锯齿：多边形划过的像素填充较浅的颜色

遮挡

多边形的处理关系

画家算法：利用排序先处理远的多边形（背景），再填充近的元素

深度缓冲：

1. 算法记录每个像素和屏幕的距离
2. 然后利用扫描线算法进行填充

计算浮点数有误差：哪个元素在前后有误差

阴暗处理

物体表面的多边形朝向：表面向法（法向量）

平面着色：利用距离和朝向队明暗进行处理

纹理映射

纹理指表面而不是手感

将多边形坐标和相应区域的纹理数据进行映射，在扫描线渲染时进行填充相应的纹理

GPU

图形处理单元，进行大规模并行处理：大量相似的简单任务

28.计算机网络

局域网：靠近计算机组成的小型网络

载体：共享数据的载体媒介

带宽：载体传输数据的速度

冲突

以太网：通过一条以太电线连接数台计算机

媒体访问控制地址：MAC地址

传输数据时在信息前加上目标的MAC地址

冲突：当网络流量上升，两台计算机想要同时写入的概率上升

解决方法

停止传输：有可能其他计算机也停止，冲突概率上升

等待一段时间：

1. 等待固定时间+随机时间
2. 如果再次冲突，登台固定时间指数倍+随机时间（指数退避）

冲突域

减少统一载体中设备的数量

冲突域：载体和其中设备的总称

利用交换机将冲突域拆分为两个更小的冲突域

传输数据

通过结点传输（报文交换）或专用线路

跳数：消息沿路由跳转的次数

跳数过多时肯定有地方出现了故障

IP地址

传输大文件：拆分为小文件进行传输，通过灵活的路由进行传输

IP协议：互联网传输协议

计算机地址：IP地址

路由器会平衡和其他路由器之间的负载，保证线路的稳定

29.互联网

传输方式

互联网：分布式巨大网络

LAN：局域网

广域网：WAN

家中所有设备->路由->小型WAN->大型WAN

传输协议

IP

将数据包拆分为一个个数据包进行传输

传输的目标地址：IP地址

UDP

UDP：用户数据协议，在元数据中存储相应数据

1. 端口号：每个想访问网络的程序向OS申请一个端口号
   • IP负责将数据包送到正确的计算机，UDP负责把数据包送到正确的程序
2. 校验和：检查数据是否正确
   • 将数据加起来，得到一个总数，发送作为校验，接受时检验和是否一致
   • 如果收到数据坏了，一般直接丢掉
   • 如果数据丢了，无法解决

TCP

控制传输协议：TCP：所有数据必须到达

为什么叫TCP-IP：和IP地址一样数据存在头部

1. 序号
   • 数据包的编号，到达后TCP可以将乱序的数据排序
2. 确认码
   • TCP要求接收方的电脑数据接收到数据后且校验和检查无误后给发送方发一个确认码
   • 接收方得到确认码后才会发送下一个数据
   • 如果没收到，再发送一遍
   • 一次会发送多个数据
   • 
   • 确认码的成功率和到达时间可以判断网络拥挤程度，TCP动态调控

域名系统

访问网络时：需要IP和端口号，DNS将网址和域名系统对应

1. 如果域名存在，返回IP地址
2. 如果错误，DNS错误

DNS存储以树形式存在

网络的分层

• 传输层：负责计算机之间点到点之间的传输
• 会话层：创建连接，传输数据
• 

30.万维网

万维网在互联网之上运行

互联网是传输数据的管道

超链接

万维网的最基本单位是页面，通过超链接在不同页面之间跳转

通过超链接构成网络

网页需要唯一地址：URL

点击URL时，计算机做DNS查找，返回对应的IP地址

HTTP

找到服务器后，请求对应的网页：GET/pages

超文本传输协议：HTTP

服务器接受到GET指令后，返回对应网址的网页，由计算机中浏览器进行渲染

HTTP协议可以返回对应的状态

HTML

超文本标记语言，用于构建网页

利用标签来构建网页，可以加入CSS和Javascript

搜索

搜索引擎：

1. 爬虫：跟着连接到处跑的软件
2. 索引：记录访问过的文件上出现的词
3. 搜索算法

指向该页面的超链接的数量代表了网页的质量

31.计算机安全

计算机安全：保护系统和数据：保密性、完整性、可用性

保密性：只有有权限的人才能读取系统的数据和系统

完整性：只有有权限的人才能修改系统的数据和系统

可用性：有权限的人可以随时修改读取系统的数据和系统

威胁模型分析

威胁模型分析：从抽象层面想象敌人

攻击矢量：攻击手段

威胁分析需要针对能力进行分析

在给定模型下提供解决方案

身份验证

权限和能力

身份认证

1. 你知道什么
   • 只有用户和计算机知道：密码等
     • 破解密码：暴力破解等
     • 增加密码长度或字母组合
2. 你有什么
   • 验证方式：某种“钥匙”：避免了被猜中的问题
   • 钥匙可以被复制
3. 你是什么
   • 将生物数据进行验证
   • 密码和钥匙是确定性的验证，但生物性验证有不确定性
     • 传感器的数据不确定等有不确定性
     • 环境、生物变化等等
   • 生物识别可有被复制：拿到指纹或虹膜数据

访问控制

访问控制列表：读、写、执行权限

按等级区分文件的密级：公开、机密、绝密

不能：

1. 读上
   • 有高密级的权限可以读低密级的文件
   • 更高文件的密级不会被读取
2. 写下
   • 有绝密权限可以写绝密，但不能写更低权限的文件
   • 绝密的数据不会向下泄露

入侵

安全内核：决定内核有什么

隔离：当程序被攻击后，如何限制损害，控制损害的最大程度

沙盒：OS将程序放到特定内存中，不能访问其他内存

32.黑客&攻击

1. 网络钓鱼：通过发送邮件等引诱点击链接，安装程序记录输入的用户名和密码
2. 假托：加班IT部门的人，引诱将电脑配置地易于攻击
3. 木马：伪装为无害的恶意软件
4. 暴力破解、
   • 现代系统通过加长等待时间等待
   • 黑客复制整个内存进行尝试，再将原内存复制
5. 缓冲区溢出
   • 利用溢出注入黑客需要的有用信息
   • 边界检查：复制前检查数据长度
   • 在缓冲区后留一些空间
6. 通过SQL语言注入指令
   • 用户名-密码利用SQL在数据库中进行查询
   • 在用户名中嵌入SQL指令

33.加密

多层防御：多层不同的安全机制进行防御

加密算法：将明文转换为密文

1. 替换加密：将字母进行替换
2. 移位加密：更改读的列行顺序

加密算法

AES加密标准

利用密钥进行解密

传递密钥

密钥交换：不发送密钥，依然让两台计算机在密钥上达成共识

将密钥比作颜色：混合不可逆

1. 有公开颜色，所有人能看到、
2. A将秘密颜色a和公开颜色混合，传递给B
3. B将其的秘密颜色b和公开颜色混合，传递给A
4. A、B分别将自己的秘密颜色与从对方手中得到的颜色混合
5. 这样AB得到一样的颜色

外部可以得到部分信息，但不能得到最终颜色

对称加密：双方用一样的密钥加密和解密信息

非对称加密：用公钥加密，私钥解密

34.机器学习&人工智能

机器学习：机器从数据中做决定

机器学习是为了实现人工智能的一个重要手段

分类

为了简化，将数据简化为特征

机器学习：找出最佳区分

决策边界：区分不同数据的区分边界

混淆矩阵：分类后数据在决策边界中的符合程度

决策树：类似于连续的if-else进行区分

支持向量机：利用任意曲线来区分决策空间

人工神经网络

人造神经元：接受多个数据，整合卞发出一个数据

输入层-隐藏层-输出层

1. 输入层

   • 提供需要分类的数据

2. 输出层

3. 隐藏层

   1. 将每个输入乘以一个权重，相加输入，并加减一个固定的相差值
   2. 偏差和权重就是神经网络的调参参数
   3. 激活函数对结果进行最后一次数学修改
   • 加权、求和、偏置、激活

深度学习：有多个隐藏层

强AI

非专用AI

吸收大量信息，不断进步学习

强化学习：反复试错来学习

35.计算机视觉

让计算机理解图像和视频

图像是像素网格

像素块

占多个像素的物体：一块块像素处理

左右像素差别越大，越可能是边缘

核or过滤器：用来做像素乘法，总和存储到中心

$$1 \quad 0 \quad -1\\ 1 \quad 0 \quad -1\\ 1 \quad 0 \quad -1$$

卷积：将核作用于像素块

卷积能够突出边界值，边缘的像素值很高

对不同的边缘用不同的核，可以表述简单的形状

卷积神经网络

1. 给神经元输入二维像素，就类似于进行卷积，输入权重等于核的值
2. 神经网络可以选用有用的核来进行区分
3. 单层卷积区分单个特征，多层卷积可以识别一些形象
4. 一般会有很多层来识别形状和场景

36.自然语言处理

早期问题：将句子切分为一块块

语法

用短语构造规则来代表语法规则

1. 给语言指定规则
2. 根据规则做出分析树
3. 利用分析树得到句子中单词的词性和句子的结构
4. 
5. 可以用规则来生成句子

语音识别

用机器学习从语言数据中学习

利用FTT将波形转换为频率的谱图：纵轴为频率，亮度越大，对应频率的声音响度越大

音素：构成声音的片段。计算机根据音素进行识别，本质是音素识别

语音合成

早期语音合成是音素拼接

37.机器人

机器人时代已经来临

机器人由计算机控制，自动执行一系列指令

控制

控制器负责把机器人的属性变成期望值，用反馈进行控制

负反馈控制回路：

1. 传感器
2. 控制器处理传感器得到的错误
3. 物理组件做出动作进行负反馈

PID

有控制器和反馈器：比例-积分-微分控制器，现在纯软件控制

1. 比例值：实际值和理想值差多少
2. 积分值：一段时间内误差的综合
3. 导数值：期望值与实际值之间的变化率，预期控制，解决未来可能的问题
4. 

机器人三定律

指导机器人的行为准则

38.计算机心理学

易用性以人类为优先，计算机心理学注重于更好地帮助人类实现操作

好的界面应该提供多种方法来实现

人机交互

39.教育科技

计算机带来的最大改变之一：信息的创造和传播的能力

MOOC：老师依然必不可少，学生获得反馈

贝叶斯知识追踪：将学生掌握的知识视作变量，通过测试/试探获取

40.奇点·天网·计算机的未来

计算机的深度和广度，是新时代的咒语

电气化->计算机->人工智能

智能难以量化，以处理问题的能力衡量

非重复性创造性工作，不易受自动化影响

亿万年后太阳燃尽，地球成为星辰