benben's Blog

1、分立元件与数字暴政

一开始，计算机都有独立组件构成，叫"分立元件"，然后不同组件再用线连在一起，这会导致计算机的构成很复杂，这个问题就叫做"数字暴政"。

2、集成电路与仙童半导体

封装复杂性：与其把多个独立部件用电线连在一起，拼装出计算机，不如把多个组件包在一起，变成一个新的独立组件。这种新的独立组件就叫集成电路(IC)，仙童半导体(用硅做成)让继承电路变成了现实。为了不用焊接或用一大堆线，发明了印刷电路板(PCB)，他通过用蚀刻金属线的方式把零件连接在一起。

3、光刻

即用光把复杂图案印到材料上。我们把一片薄片状的硅叫做晶圆，通过一系列生产步骤，将晶圆表面播磨的特定部分除去的工艺叫做光刻。
光刻组件示意图

光刻成品示意图

4、摩尔定律

每两年左右，得益于材料和制造技术的，同样大小的空间，能塞进两倍数量的晶体管。

5、进一步小型化会碰到的问题

1. 由于光的波长限制，精度已达到极限。
2. 量子隧穿效应：当晶体管非常小，电极之间可能只距离几个原子，电子会跳过间隙，会产生漏电问题。

1、对象

当任务庞大，函数太多，我们需要把函数打包成层级，把相关代码都放一起，打包成对象。对象可以包括其他对象、函数和变量。把函数打包成对象的思想叫做"面向对象编程"，面向对象的核心是隐藏复杂度，选择性的公布功能。

2、面向对象编程

把函数打包成对象的思想叫"面向对象编程"。

3、API

当团队接收到子团队编写的对象时，需要文档和程序编程家口(API)来帮助合作。API控制哪些函数和数据让外部访问，哪些仅供内部。

4、集成开发环境(IDE)

程序员用来专门写代码的工具。

5、调式(debug)

IDE帮你检查错误，并提供信息，帮你解决问题，这个过程叫调试。

6、文档与注释

文档一般放在一个叫做README的文件里，文档也可以直接写成"注释"，放在源代码里，注释是标记过的一段文字，编译代码时，注释会被忽略。注释的唯一作用是帮助开发者理解代码。

7、版本控制

版本控制，又称源代码管理。大型软件公司会把代码放在一个中心服务器上，叫"代码仓库"，程序员可以把想修改的代码借出，修改后再提交回代码仓库。版本控制可以跟踪所有变化，如果发现bug，全部或部分代码，可以"回滚"到之前的稳定版。

8、质量控制

测试可以统称"质量保证测试"(QA)，作用是找bug

9、beta alpha

beta版软件，即是软件接近完成，但没有完全被测试过，公司有时会向公众发布beta版，以帮助发现问题。alpha是beta前的版本，一般很粗糙，只能在内部测试。

0、可判断性问题

是否存在一种算法，输入正式逻辑语句 输出正确的"是"或"否"答案？

1、阿隆佐邱奇，Lambda算子

美国数学家 阿隆佐·丘奇，开发了一个叫"Lambda 算子"的数学表达系统，证明其不存在。

2、图灵机

只要有足够的规则，状态和纸带，图灵机可以解决一切计算问题。和图灵机一样完备，叫做图灵完备。

3、停机问题

证明图灵机不能解决所有问题。

4、图灵测试

向人和机器同时发消息，收到的回答无法判断哪个是人，哪个是计算机，则计算机达到了只能程度。

1、数组 下标

数组(Array)，也叫列表(list)或向量(Vector)，是一种数据结构。为了拿出数组中某个值，我们要指定一个下标(index)，大多数编程语言里，数组下标都从0开始，用方括号[]代表访问数组。注意：很容易混淆"数组中第5个数"和"数组下标为5的数"，数组下标为5的数是数组里面的第6个数。

2、字符串

即字母、数组、标点等组成的数组，字符串在内存里以0结尾。

3、矩阵

可以把矩阵看成数组的数组。

4、结构体

把几个有关系的变量存在一起叫做结构体。

5、指针

指针是一种特殊变量，指向一个内存地址，因此得名。

6、节点

以指针为变量的结构体叫节点。

7、链表

用节点可以做链表，链表是一种灵活数据结构，能存很多个节点(node)，灵活性是通过每个节点 指向 下一个节点实现的。链表可以是循环的也可以是非循环的，非循环的最后一个指针是0.

8、队列

"队列"就像邮局排队，谁先来就排前面，这叫先进先出(FIFO--first in first out)，可以把"栈"想成一堆松饼，做好一个新松饼，就堆在之前上面，吃的时候，是从最上面开始。

9、栈

栈是后进先出(LIFO)。

10、树

11、图

如果数据随意连接，有循环，我们称之为图

0、基本概念

算法：解决问题的基本步骤

1、选择排序：

数组：一组数据
选择排序的复杂度为O(n²)

2、大O表示法

大O表示法(算法)的复杂度：算法的输入大小和运行步骤之间的关系，来表示运行速度的量级。

3、归并排序

归并排序的算法复杂度为O(n*log n)，n是需要比较+合并的次数，和数组大小成正比，log n是合并步骤所需的次数，归并排序比选择排序更有效率。

4、Dijkstra算法

一开始复杂度为O(n²)，后来复杂度为O(nlog n + l)，n表示节点数，l表示有多少条线。

1、计算机技术的影响——进入信息时代

• 出现自动化农业设备与医疗设备
• 全球通信和全球教育机会变得普遍
• 出现意想不到的虚拟现实/无人驾驶/人工智能等新领域

2、计算机的实质：

极其简单的组件，通过一层层的抽象，来做出复杂的操作。计算机中的很多东西，底层其实都很简单，让人难以理解的，是一层层精妙的抽象。像一个越来越小的俄罗斯套娃。

3、关于计算的历史：

1. 公元前 2500 年，算盘出现，为十进制，功能类似一个计数器。
2. 公元前 2500 年-公元 1500 年：星盘、计算尺等依靠机械运动的计算设备出现
3. 公元 1613 年：computer 的概念出现，当时指的是专门做计算的职业，
4. 1694 年：步进计算器出现，是世界上第一台能自动完成加减乘除的计算器。
5. 1694-1900 年：计算表兴起，类似于字典，可用于查找各种庞大的计算值。
6. 1823 年：差分机的设想出现，可以做函数计算，但计划最后失败。
7. 19 世纪中期：分析机的设想出现，设想存在可计算一切的通用计算机。
8. 1890 年：打孔卡片制表机。原理：在纸上打孔→孔穿过针→针泡入汞→电路连通→齿轮使计数+1。

1、电子计算机元器件变化：

继电器→真空管→晶体管

2、计算机的出现背景：

20世纪人口暴增，科学与工程进步迅速，航天计划成形。以上导致数据的复杂度急剧上升、计算量暴增，对于计算的自动化、高速有迫切的需求。

3、电子计算机的发展：

• 1945年 哈佛马克1：使用继电器，用电磁效应，控制机械开关，缺点为有磨损和延迟。
  最早还因为有虫子飞进去导致故障，引申出 bug=故障的意思。
• 1943年 巨人1号：使用真空管（三极管），制造出世界上第一个可编程的计算机。
• 1946年 ENIAC：第一个电子通用数值积分计算机。
• 1947年 晶体管出现，使用的是固态的半导体材料，相对真空管更可靠。
• 1950年 空军ANFSQ-7：真空管到达计算极限。
• 1957年 IBM608：第一个消费者可购买的晶体管计算机出现。

1、计算机为什么使用二进制：

1.计算机的元器件晶体管只有2种状态，通电(1)&断电(0)，用二进制可直接根据元器件的状态来设计计算机。
2.而且，数学中的“布尔代数”分支，可以用True和False(可用1代表True，0代表False)进行逻辑运算，代替实数进行计算。
3.计算的状态越多，信号越容易混淆，影响计算。对于当时每秒运算百万次以上的晶体管，信号混淆是特别让人头疼的。

2、布尔代数&布尔代数在计算机中的实现

1.变量：没有常数，仅True和False这两个变量。
2.三个基本操作：NOT/AND/OR。
3.为什么称之为“门”：控制电流流过的路径。

1)NOT操作：

1. 命名：称为NOT门/非门。
2. 作用：将输入布尔值反转。输入的True或False，输出的为False或True。
3. 晶体管的实现方式：
   
   • 半导体通电True，则线路接地，无输出电流，为False。
   • 半导体不通电False，则输出电流从右边输出，为True。
     

2)AND操作

1. 命名：AND门/与门
2. 作用：由2个输入控制输出，仅当2个输入input1和input2都为True时，输出才为True，2个输入的其余情况，输出均为False。可以理解为，2句话(输入)完全没有假的，整件事(输出)才是真的。
   
3. 用晶体管实现的方式：
   串联两个晶体管，仅当2个晶体管都通电，输出才有电流(True)
   

3)OR操作

1. 命名：OR门/或门
2. 作用：由2个输入控制输出，只要其中一个输入为True，则输出True。
   
3. 用晶体管实现的方式：
   使用2个晶体管，将它们并联到电路中，只要一个晶体管通电，则输出有电流(True)。
   

3、特殊的逻辑运算——异或

1. 命名：XOR门/异或门
2. 作用：2个输入控制一个输出。当2个输入均为True时，输出False，其余情况与OR门相同。
   
3. 图示：
   先用一个OR门，将其与AND门并联，AND门与NOT门串联，最后让NOT与AND门并联，获得输出。
   

4、逻辑门的符号表示

1. 作用：将逻辑门简化，将逻辑门用于构建更大的组件，而不至于太复杂。
2. 图示：
   
   • 非门：用三

1、二进制的原理，存储单元MB/GB/TB解释

1. 计算机中的二进制表示：

单个数字1或0,1位二进制数字命名为位(bit)，也称1比特。

2. 字节(byte)的概念：

1byte=8bit，即1byte代表8位数字。最早期的电脑为八位的，即以八位为单位处理数据。为了方便，将八位数字命名为1字节(1byte)。

3. 十进制与二进制的区别：

• 十进制有10个数字，0-9，逢10进1(不存在10这个数字)，则每向左进一位，数字大10倍。
• 二进制有2个数字，0-1，逢2进1，(不存在2这个数字)，则每向左进一位，数字大2倍。

4. 如何进行二进制与十进制联系起来：

• 将十进制与二进制的位数提取出来，编上单位：
  eg.二进制的 1011=1*2^0 + 1*2^1 + 0*2^2 + 1*2^3= 11（从右往左数）
  eg.十进制的 1045= 1*10^3 + 0*10^2 + 4*10^1 + 5*10^0

5. 十进制与二进制的图示：

十进制的263

二进制的10110111

6. 二进制的运算：

相同的位数相加，逢2进1

7. byte在电脑中的单位置换：

1byte=8bit
1KB=1024byte
1TB=1000GB
1GB=十亿字节=1000MB=10^6KB

2、正数、负数、整数、浮点数的表示

1. 整数：

表示方法：

• 第1位：表示正负。1是负，0是正（补码）
• 其余31位/63位：表示实数

2. 浮点数（Floating Point Numbers）：

定义：小数点可在数字间浮动的数（非整数）
表示方法：IEEE 754 标准下

用类似科学计数法的方式，存储十进制数值

• 浮点数=有效位数*指数
• 32 位数字中：第 1 位表示正负，第 2-9 位存指数。剩下 23 位存有效位数
• eg.625.9=0.6259（有效位数）*10^3（指数）

3、美国信息交换标准代码-ASCⅡ，用来表示字符

1. 全称：美国信息交换标准代码
2. 作用：用数字给英文字母及符号编号
3. 内容：7位代码，可存放128个不同的值
4. 图示

1、什么是算术逻辑单元

1. 命名：简称ALU，Arithmetic&Logic Unit
2. 组成：ALU有2个单元，1个算术单元和一个逻辑单元(Arithmetic Unit和Logic Unit)
3. 作用：计算机中负责运算的组件，处理数字/逻辑运算的最基本单元。

2、算术单元

1. 基本组件：
   
   • 由半加器、全加器组成
     
     • 半加器、全加器由AND、OR、NOT、XOR门组成
2. 加法运算
   
   1. 组件：AND、OR、NOT、XOR门
   2. 元素：输入A，输入B，输出(均为1个bit，即0或1)
3. 半加器
   
   • 作用：用于计算个位的数字加减。
     
     • 输入：A,B
     • 输出：总和，进位
       
       抽象：
       
       sum:总和 carry：进位
4. 全加器：
   
   • 作用用于计算超过1位的加法(ex: 1+1+1)，由于涉及进位，因此有3个输入(C充当进位)。
     
     原理图示：
     

3、如何用半加器与全加器做8位数的加法

说明：以8位行波加法器为例
1. 用半加器处理第1位数(个位)的加法，得到的和为结果的第一位。
2. 将输出的进位，输入到第2位用的全加器的输入C中。
3. 将第2位的2个数用全加器计算，得到的和为结果的第2位(sum)。
4. 将第2位计算的进位连接到百位的全加器输入C中。
5. 在第3-8位上，循环第3-4步的操作。
现在电脑上使用的加法器叫“超前进位加法器”

4、算术单元支持的其他运算

5、溢出的概念

内容：在有限的空间内，无法存储位数过大的数，则称为溢出。
说明：第8位的进位如果为1，则无法存储，此时容易引发错误，所以应该尽量避免溢出。

6、逻辑单元

作用：执行逻辑操作，如NOT、AND、OR等操作，以及做简单的数值测试。

7、ALU的抽象

1. 作用：ALU的抽象让工程师不再考虑逻辑门层面的组成，简化工作。
2. 图示：
   像一个大"V"。
   
3. 说明：
   图示内容包括：
   
   • 输入A,B
   • 输出
   • 标志：溢出、零、负数