Crash Course Computer Science

标签：Crash -- RAM Course Computer 指令 memory CPU 内存

【计算机科学速成课】[40集全/精校] - Crash Course Computer Science

ep1. Early Computing

• Charles Babbage

  • English mathematician and inventor

  • conceived the first automatic digital computer

• Ada Lovelace

  • English mathematician
  • the first computer programmer

ep2. Electronic Computing

继电器

应用：Harvard Mark 1--one of the largest electro-mechanical computers

特点：

• 速度慢：1秒能做3次加减运算，1次乘法6秒，除法15秒

• 齿轮磨损：需要频繁地检查并更换故障继电器

真空管--改进继电器

热电子管——替代继电器的新电子组件：一极可加热并发射电子，另一极（正极）吸收电子，形成电流

二极管：电流只能单向流动

三极真空管：二极管+开关（控制电路正负电荷）

• 更少的磨损+更快的开关速度

应用：Colossus MK 1--the 1st large-scale use of vacuum tubes for computing

designed by Tommy Flowers

completed in 1943

晶体管--new era!!!

Bell Laboratory, 1947

John Bardeen, Walter Brattain, William Shockley

一个开关，用控制电路来控制开或关

半导体

如今计算机中的晶体管小于50nm（纸的厚度为10w nm）

ep3. Boolean Logic & Logic Gates

George Boole: self-taught English mathematician

NOT gate

input: true output: false

input: false output: true

AND gate

需要两个晶体管串联

OR gate

需要两个晶体管并联

重要补充--XOR异或

ep4. Representing Numbers and Letters with Binary

位与字节

二进制中，一个 0 或 1 ，叫一位 (bit)

8 bits非常常见，以至它有专门的名字——字节 (byte)，缩写为B

1KB=1024B

32-bit / 64-bit的计算机：一块块处理数据，每块是32位或64位

浮点数

用科学计数法表示

例如32位计算机：

字符串

用ASCII码表示字符，7-bit

1个字节有8位，128～255就留给各个国家的语言

Unicode：统一编码标准，解决了不同语言编码不兼容的问题

ep5. How Computers Calculate--the ALU 算术逻辑单元

计算的大脑：ALU = Arithmetic and Logic Unit 算术逻辑单元

算术单元 (Arithmetic Unit)

半加器 Half Adder

实现一位的A+B计算，carry表示进位

全加器 Full Adder

实现一位A+B+C计算

8位加法器

现代计算机的改进：超前进位加法器 (carry-look-ahead adder)

逻辑单元 (Logic Unit)

进行一些判断

Finally, 搭建出整个ALU!!!

ep6. Registers and RAM 寄存器和内存

RAM：Random Access Memory 随机存取存储器，只能在有电时存储

Memory：persistent memory，断电时亦可存储

制作1位的存储器

理解存储：不断地输出同一个值

OR能存储 1，AND能存储 0

解释：当B为1，output为1，流回来的B总是1，无论A如何取值，output永远为1

AND-OR Latch (AND-OR锁存器)：结合二者

• reset=0，即不启用重置功能，所存循环=set输入
• reset=1，即启用重置功能，无论set为何，储存循环初始化为0

Gated Latch门锁

锁存器的抽象结果

寄存器

并排放多个锁存器能存更多东西。一组锁存器称为寄存器，能存一个数字，数字的位数叫做位宽

现在的很多计算机使用64-bits wide register

工作原理

1根允许写入线连接所有，每个锁存器都有1根线控制状态

矩阵优化

1根允许写入线，16*2根控制状态的线

理解：要在某个锁存器上存01，允许写入线置1，相应“横纵坐标”置1，结束时都置0；要存多个，重复以上操作

多路复用器

我们想定位 (12行,8列) 的锁存器，需要使用到多路复用器

转为二进制 (1100,1000) ，row 1100 通过多路复用器（橙色的梯形）会定位到第12行，column 1000 通过另一个多路复用器会定位到第8列

Memory

抽象：4 bit代表行，4 bit代表列

扩大规模

8个memory存8-bit的数字

每一个memory里面有256个位置，每个位置只能输出输入1或0，八个memory并排，输出输入的数据是八位的二进制数

一个256memory尽管存储空间有256个1位数字，但只能同时读取一个1位数字，所以需要8个256memory来同时存取8位数字的所有位数

如何实现？同时给8个memory同样的address，每个memory存一个01（应该有address与锁存器的映射），因为有256个锁存器，也就有256种状态，可以接收256个不同地址，所以一共能存256个字节

address把矩阵打开

每个寄存器里有256个锁存器，也就是256位，然后现在又有8个寄存器，每个储存一位，8位等于一个字节，所以加起来就是256个字节

继续抽象：256 addresses, each address can read or write an 8-bit value

RAM

Access memory location at any time, in a random order

就是我们平常说的内存

ep7. The Central Processing Unit 中央处理器

CPU：处理程序

元器件

以上图的RAM为例（只有16 memory locations，each containing 8 bits）

4个8-bit registers，记为 A, B, C, D

instruction address register：追踪程序运行到哪里了，称为“指令地址寄存器”，存储当前指令的memory address

instruction register：存当前指令，称为“指令寄存器”

CPU's operation

p1--fetch phase 取指令阶段

instruction address register 连到 RAM module，寄存器的值为0，所以RAM返回地址0的值，00101110 会复制到 instruction register 中（理解：指令地址 \(\Rightarrow\) 定位 RAM \(\Rightarrow\) 取相应指令）

p2--decode phase 解码阶段

前四位opcode为 0010 ，是指令 LOAD_A（解码主要看对应哪个指令，例如：看 LOAD_A ，检查编码是不是 0010 就可以了）；后四位 1110 是 RAM 的地址，该指令的作用是 read RAM location into register A

p3--execute phase 执行阶段

打开 RAM 的 read enable line ，把地址 1110 传过去；RAM 拿到本地址的值，即 00000011 ；把 RAM 的 data wire 连到4个寄存器，启用 LOAD_A check circuit 去启用寄存器A的 write enable line ，然后A就得到了data，即 00000011

执行完成✅，把 instruction address register 的值+1，重复 p1

CPU 可以指挥哪些寄存器工作，作为 ALU 的输入

ps. control unit 用一个自己的寄存器保存运算结果，关闭 ALU 后在写入 相应的寄存器

循环结果

从内存中加载两个值，相加，再把结果放回内存 RAM

控制循环：例子中人为地+1，实际用 cock 来使 CPU ticking

ep8. Instructions & Programs

CPU is programmable

指令

新增指令：

Jump原理：用指令后4位（代表内存地址的值）覆盖 address register 的值

Halt指令：结束程序

相除取余程序

ep9. Advanced CPU Designs

complexity-for-speed

给 ALU 增加更多的运算功能（相应地，电路复杂度增加）减少时钟 tick 次数

新问题：如何将数据快速传递给CPU？

RAM 与 CPU 的数据传输

时间消耗

• RAM 与 CPU 相独立，数据用线 (bus) 来传输

• RAM 自身找地址、取数据、输出数据（CPU 在等）

提升性能

方法一：缓存 cache

CPU 空间不大，所以缓存 KB、MB 级，而 RAM GB级。CPU 一次从 RAM 处取到很多数据

方法二：指令流水线 instruction pipelining

像银行分三年存三年定期

原理：执行一个指令的同时，解码下一个指令，读取下下个指令，让所有器件都运行

弊端：

• 上一步的解码可能在修改这一步读取的数据，流水线操作造成冲突，必要时需要停止流水线

• Jump 指令会改变程序的执行流

  • 高级 CPU 预测 (speculative execution)，将可能执行的指令放进流水线

超标量处理器 (superscaler processor)：一个时钟周期处理多个指令

方法三：多核处理器 multi-core processor

同时运行多个指令流（在一个 CPU 里，有多个独立处理单元）

ep10. Early Programming

program加载进内存

冯诺伊曼结构：

• a processor with ALU
• data registers
• instruction register
• instruction address register
• memory

ep11. The First Programming Languages

Here comes Software!!!

汇编程序 Assembler

read in text-based instructions, and assemble them into the binary instructions

汇编程序与机器指令是一一对应的

编译器 compiler

把高级语言“翻译”为较为低级的语言

ep12. Programming Basics--Statements & Functions

模块化编程，函数封装很重要

超过100行代码的函数很少见

There're libraries for everything--including networking, graphics, sound

ep13. Algorithms

改进后的 Dijkstra ，O(nlogn + l)

ep14. Data Structures

数组array/list/vector

矩阵可以表示任何维度

ep15. Alan Turing

希尔伯特可判定性问题

Is there an algorithm that takes, as input, a statement written in formal logic, and produces a "yes" or "no" answer that's always accurate?

图灵机

模型

无限长 memory tape：存储 symbol

读写头：read, write or modify symbols on tape

状态变量：保存当前状态

规则：描述机器做什么

图灵证明：如果有足够的时间和内存，图灵机可以执行任何计算

Halting Problem 停机问题

Is there an algorithm that can determine, given a description of a turing machine and the input from its tape, whether the machine will run forever or halt?

假设存在图灵机H，可以解决停机问题。如果H说会停机，那么新机器B会不停；如果H说不会停机，那么新机器B停下。

把H和B组合，如果H说B会停机，则B不停，说明H无法判定。

图灵机无法解决停机问题！

Church & Turing: 计算是有极限的

ep16. Software Engineering

Object Oriented Programming

package functions into hierarchies, pulling related code into "objects"（把大型软件拆分成小的单元）

团队协作

Documentation

团队需要文档，理解代码在做什么

README file

Comment

Application Programming Interface (API)

好的接口

public/private function: 其他objects是否可以调用

Integrated Development Environments (IDE)

vim是最棒的编辑器

Source Control / Version Control / Revision Control

把代码放到中心服务器上，叫code repository；程序员想修改部分源码，check out；改完后放回原文档，commit

代码的master version（主版本）应该尽量少错

Quality Assurance (QA) 质量保证测试

找bug

Beta software: 接近完成但没有测试过的软件，让用户来 QA

ep17. Integrated Circuits & Moore's Law

Integrated Circuits

避免电脑中错综复杂的电线交织

an electronic part -- wherein all the components of the electronic circuit are completely integrated

Robert Noyce

co-inventor of the integrated circuit

Fairchild Semiconductor founder

Printed Circuit Boards (PCB) 印刷电路板

Photolithography 光刻

Use light to transfer complex patterns to a material, like a semiconductor

在硅上雕刻，形成晶体管、电阻、电容

其他受益元件

CPU, RAM, graphics cards显卡, solid state hard drives固态硬盘, camera sensors

ep18. Operating Systems

Operating Systems

本质也是程序，与硬件交互，可以管理运行其他程序

batch processing 批处理：计算机运行完一个程序，自动运行下一个

软硬件媒介

操作系统充当硬件和软件的媒介：提供API来抽象软件，叫做 device drivers

allow programmers to talk to common input and output hardware (I/O)

加速进程

processor常常要等I/O慢慢地运行

在一个CPU上运行多个程序--multitasking

比如一个程序打印，另一个计算

给每个程序分配专属内存块，并把内存地址虚拟化，隐藏实际物理位置，用 [0, 999] 代替 [1000, 1999]。对程序自身而言，觉得内存是连续的

内存保护：一个程序崩溃不会影响其他

多用户同时访问

Time-Sharing分时操作系统：每个用户只能用一小块处理器、内存等

Unix

OS分为两部分

• kernel内核：memory management, multitasking, deal with I/O

• 有用的工具：程序, 库

ep19. Memory & Storage

内存：非永久性

存储器：数据一直存下

ep20. Files & File Systems

WAV

存音频

元数据 (meta data / header)

关于数据的数据（像哈夫曼编码的开头）

• bit rate

• 单声道 or 立体声

BMP

存图片--像素

文件系统

Flat File Systems--文件都在一个目录内

文件大多连续存储，需要知道每个文件的起始和终止位置--目录文件

预留空间 (slack space) 成块便于修改文件

文件在存储中被分散，变为碎片 (fragmentation) ，计算机会移动块，碎片管理

Hierarchical File System--分层，现代

目录文件可以存储目录

ep21. Compression 压缩

Run-Length Encoding 游程编码

思想：减少重复信息，把 2+2+2 变为 2*3

没有丢失数据，是无损压缩

Dictionary Encoding 字典编码

思想：用更紧凑的表示方法

a directory stores the mapping from codes to data

无损压缩

有损压缩

音频中的超声波完全可以忽略，因为我们不能分辨

MP3, JPEG 有损，通话

视频文件可以运用图片的压缩方法，除此之外，视频中连着几帧可能变化不大，有 temporal redundancy，可以只存有变化的部分

ep22. Keyboards & Command Line Interfaces

Terminal: 在“终端”中执行命令和脚本来让 shell 执行相应的操作

ep23. Screen & 2D Graphics

vector scanning: 引导电子画图

raster scanning(光栅扫描): 按固定路径，一行一行，不断重复

character generator

从内存中读取字符，转换成光栅图形，才能显示在屏幕上

“第一代显卡”

ep24. The Cold War & Consumerism

Apollo Guidance Computer

• fast
• small & light
• reliable

ep25. Personal Computer Revolution

single-chip CPU

Altair 8800--first pc

• Bill Gates: 建议增加BASIC程序

Apple 1--first apple

• Steve Jobs

Apple 2--first 组装

dirty dizens created IBM PC

IBM兼容，apple不兼容（不能自己加硬件）

ep26. Graphical User Interface

Apple Macintosh

ep27. 3D Graphics

3D projection

把3D投影成2D

正交投影

平行的边仍然平行

透视投影

现实生活中看过去不平行，而是有汇聚

渲染

Wireframe rendering线框渲染

线段连接2D图

三角形

称三角形为多边形（polygons），最常用的图形

抗锯齿方法

避免边缘的方形太明显，内部之间着色，边缘弱化着色

画家算法

像油画，先画背景，再画近景

深度缓冲

先用数字填，再画像素

背面剔除

略去背面的细节

阴暗处理

加一个光源并计算每个像素的明暗程度

纹理映射

材料的纹路

ep28. Computer Networks

交换器switch，控制一些信号流动

也是互联网的工作原理，互联网的本质是多个连在一起的小网络

ep29. Internet 互联网

传输方式

获取b站某视频：

先连接 local area network (LAN) 局域网，WIFI 连着所有设备，组成局域网。局域网再连接到广域网 (WAN) ，WAN 的路由器由 Internet Service Provider (ISP) 运行，会连接一片地方。再接更大的路由器，覆盖城市。一步步跳到主干。再找b站的服务器。

传输协议

IP

我们看的视频是“文件”，“数据包” (packet)

IP：数据包在互联网上传输需要符合的标准 (Internet Protocol)

UCP

UCP：user datagram protocol

port number 端口号：每个想访问互联网的程序都要向操作系统申请一个端口号。读到端口号时，把数据包交给对应程序

checksum 校验和：检查数据是否正确，没有修复功能

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

TCP

TCP：transmission control protocol

高级功能：

1. 序号：数据包有编号，到达后 TCP 可以将乱序的数据排序
2. 确认码 ACK：TCP要求接收方的电脑收到数据包后且校验和检查无误后给发送方发一个确认码，接收方才会发送下一个数据。否则，再发送一遍。多路发送

域名系统 DNS

访问网站时，需要IP和端口号，例如 172.217.7.238:80 可以进入谷歌首页

DNS将网址和域名系统对应

DNS树状存储

网络分层

各司其职，共同完成信息传输

ep30. The World Wide Web 万维网

浏览器？万物即达

超链接 hyperlink

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

网页需要唯一地址--URL(uniform resource locator，统一资源定位器)

访问网站时：

1. 连接 xxx.com 的服务器：先做DNS查找，得到IP地址，浏览器会打开一个TCP连接到这个IP地址，运行网络服务器（标准端口是 80）
2. 向服务器请求 xxx 页面：http

HTTP

HTTP：超文本传输协议 hypertext transfer protocol

点击某个连接时，我们向服务器发送 GET/xxx 指令(纯文本)，服务器收到后，返回对应网址的网页，由浏览器进行渲染

HTML

由于网页内容实际是 ASCII ，无法区分文本和链接 \(\Rightarrow\) 用HTML标记

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

存为 .html 文件，用浏览器打开：

加入CSS(cascading style sheets，层叠样式表) 和 Javascript，丰富网页

搜索

谷歌的重要性优先排序：指向页面的超链接的数量 \(\propto\) 网页质量

ep31. Cybersecurity

计算机安全

保护系统和数据的保密性、完整性、可用性

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

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

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

威胁模型分析

想象一个“敌人”（威胁模型），模拟对计算机进行攻击

Who're u?

What should u have access to?

身份验证

让计算机知道使用者是谁

way1 你知道什么

密码

way2 你有什么

用户有特定物体，比如用钥匙开门

way3 你是什么

用户的生物特征确定是谁

访问控制

系统知道你是谁后，它需要知道你能访问什么

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

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

访问控制模型之一：Bell-LaPadula模型

• 不能向上读

  • 有高密级的权限可以读低密级的文件

• 不能向下写

  • 有绝密权限可以写绝密，但不能写更低权限的文件
  • 绝密的数据不会向下泄露

ep32. Hackers & Cyber Attacks

网络钓鱼

通过发送邮件等引诱点击链接，安装程序记录输入的用户名和密码

假托 Pretexting

装成IT部门的人，引诱用户将电脑配置地易于攻击

木马

发邮件，木马会伪装成无害的东西（如照片、发票），但实际是恶意软件（malware）

暴力破解

复制内存，暴力尝试密码，直到设备让你等待，再把内存复制回去，继续试

远程攻击

漏洞利用——缓冲区溢出

利用溢出注入黑客需要的有用信息

保护方案：

• 边界检查：复制进缓冲区前先检查数据长度

• 随机存储重要信息：黑客就不知道应该覆盖的内存在哪里

• 追踪缓冲区中不用空间的值

代码注入

通过 SQL(structured query language) 语言注入指令

ep33. Cryptography 加密

移位加密

传递密钥

假设密钥是一种独特的颜色：

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

ep34. Machine Learning & Artificial Intelligence

机器学习

红蓝分别表示物种A、B，人工观察记录两个特征值，体现在横纵坐标上。但有重合部分，机器学习算法找出最佳区分。这样获取新动物可以大致判断是 A or B

人工神经网络

人造神经元：接收多个输入（是数），整合并发出一个信号

分类方法：输入层--隐藏层--输出层

• 输入层

  • 提供需要分类的数据

• 输出层

  • 隐藏层

• 隐藏层

  • 分类

  • 加权、求和、偏置、激活（例如，把值都算进 1 和 -1 之间）

深度学习(deep learning)：有多个隐藏层

AI

弱AI

针对特定任务

强AI

通用

反复试错来学习

ep35. Computer Vision 计算机视觉

像素块

块 (patch)：处理 small regions of pixels

Q：找出这幅图中的柱子

核/过滤器：数字用作像素乘法（核中数字*灰度值），总和存在中心

卷积：将核应于像素块

卷积能够突出边界值，边缘的像素值很高。上例对竖线尤为明显，不同的核可以突出不同的边界

卷积神经网络 (convolution neural network)

神经网络的加权用核，得到卷积神经网络

一般会有很多层来识别形状和场景

ep36. Natural Language Processing

语音识别

需要比手写快才有价值

快速傅立叶变换(Fast Fourier Transform)：波形到频率的转换

颜色越亮表示该频率越多

音素(phonemes)： 构成单词的声音片段

ep37. Robots

比例-积分-微分控制器(PID控制器)

Q：送餐机器人以 2m/s 的速度运动，为保持匀速，要用更复杂的控制逻辑处理摩擦、风力等的影响

控制回路+反馈机制

比例控制：根据与理想值的偏差来判断是加大还是减小马力

积分控制：算一段时间的偏差和

微分控制：预测未来的变化

ep38. Psychology of Computing

人类的认知规律

1. 擅长对颜色强度排序，所以颜色强度适合显示连续值

   

2. 不擅长排序颜色，所以不同颜色适于分类

   

3. 交流的时候喜欢凝视，所以视频通话通过算法保持眼睛“看向”摄像头

界面设计理念

直观 affordance：图标彰示用途，用户一看就知道按键的功能

CMC

computer-mediated communication 以计算机为媒介的通信

ep39. Educational Technology

Bayesian knowledge tracing

根据学生答题来判断对知识的掌握情况，记录四个概率：

• 已学会的概率
• 瞎猜的概率 probability of guess
• 失误的概率 probability of slip
• 过程中学会了的概率 probability of transit

ep40. The Singularity, Skynet, and the Future of Computing 奇点、天网、计算机的未来

奇点：智能科技的失控性发展的结点

重复性手工工作可以让机器自动进行

You can be a part of this amazing transformation and challenge, by learning about computing and taking what's arguably humanity's great invention, to make the world a better space.

标签：Crash,--,RAM,Course,Computer,指令,memory,CPU,内存
From： https://www.cnblogs.com/chasetsai/p/18287672