计算机科学

Posted by Bibooo on 07-26,2022

这文章记录一些关于计算机的知识,我觉得程序员应该可以看看,大部分都是抽象,我们在写代码或者在做程序的时候,不用在乎底层知识,我们只需要写,编译器会帮我们处理成想要的样子,我觉得硬件底层是很复杂的一个东西,它不仅仅是编程的逻辑判断,还有物理知识,电的知识,这篇文章是一个个抽象来理解计算机,所以我们不用关心底层什么 ALU,或者 计算等等。

视频

这篇文章不只是记录,也写包括我的理解,可能不是很对,有错误请给提 issues。

感谢CrashCourse 字幕组 以及 Crash Course 你们很棒

计算机早期历史(起源)

  • 算盘
  • 时钟(算日出,潮汐,天体的位置,或纯粹拿来计时)
  • 星盘(让船只可以在海上计算维度)
  • 计算尺(帮助计算乘法和除法)

这些设备让原先很费力的事变得更快,更简单,更精确。

最早计算机 ”Computer“ 指负责计算的人是一门职业。(减低计算工作量)

工业时代出现了 步进计算器 (第一台能做到 加减乘除全部四种运算的计算器)(制作成本大,效率不行)

电子计算机

早期计算设备都针对特定用途,比如 制表机 大大推进了政府和企业 它们帮助,甚至代替了人工,然而人类社会的规模在以前所未有的速度增长。

20世纪上半叶,世界人口几乎翻倍,一战动员7千万人,二战1亿多人全球贸易和运输更加紧密工程和科学的复杂度也达到新高。我们甚至开始考虑登陆其他行星复杂度的增高导致数据量暴增人们需要更多自动化 更强的计算能力,很快,柜子大小的计算机变成房间大小,维护费用高 而且容易出错。

哈佛马克一号 (通过继电器)控制电子。当电流流过线圈,线圈产生电磁场吸引金属臂,从而闭合电路 这个电路可以连接到马达让计算齿轮 +1 . (继电器内的机械表有质量因此无法快速开关)因为是齿轮磨损任何会动的机械都会随时间磨损。

因为这些原因出现了真空管 向"控制"电极施加正电荷,它会允许电子流动,但如果施加负电荷它会阻止电子流动。

因此通过控制线路,可以断开或闭合电路和继电器的功能一样,但真空管里面没用机械组件这意味着更少的磨损。

这些“三级真空管” 成为了无线电,长途电话以及其他电子设备的基础,持续了接近半个世纪。

这标志着计算机从机电转向电子

巨人 被认为是第一个可编程的电子计算机

编程的方法是把几百根电线插入插板有点像老电话交换机这是为了让计算机执行正确操作,虽然“可编程”,但还是要配置它

电子数值积分计算机 “ENIAC”

几年后在 1946 年,在“宾夕法尼亚大学”完成建造 这是世上第一个真正的通用,可编程,电子计算机

ENIAC 每秒可执行 5000次十位数加减法比前辈快了很多倍。ENIAC 运行半天左右就会出一次故障。

晶体管

晶体管的出现,一个全新的计算机时代诞生了。晶体管的物理学相当复杂,牵扯到量子力学。

它是一个开关,可以用控制线路来控制开或关。晶体管有两个电极,电极之间有一种材料隔开它们。这种材料有时候导电,电极之间有一种材料隔开它们,这种材料有时候导电,有时候不导电 。这叫 “半导体”。

布尔逻辑和逻辑门

只用 开/关 两张状态也可以代表信息这叫二进制 意思是“用两种状态表示”

电路闭合,电流流过,代表 “真”电路断开,无电流流过,代表 “假”

二进制也可以写成 1 和 0 而不是 true 和 false 只是不同的表单方式罢了。

晶体管的确可以不只是 开/关,还可以让不同大小的电流通过,一些早期电子计算机是三进制的,有三种状态甚至五进制,五种状态问题是,状态越多,越难区别信息。

计算机用二进制的另一个原因是有一整个数学分支存在,专门处理 “真” 和 “假”它已经解决了所有法则和运算 叫 “布尔代数”

布尔代数中有三个基本操作:NOT,AND,OR

计算机如何存储和表示数字

128 64 32 16 8 4 2 1
1 1 1 1 1 1 1 1

128 + 64 + 32 +16 +8 +4 + 2 + 1 = 255

最大数是 255,8位都是 1 能表示 256个不同的值,2的 8次方 0 - 256

你可以听说过 8 位机,8 位图像,8位音乐意思是计算机里大部分操作都是 8位这样处理的,但 256个值不算多,意味着 8位游戏只能用 256种颜色 8位是如此常见,以至于有专门的名字:字节

1 字节 = 8位

1 bytes = 8bits

如果有 10个 bytes ,意味着有 80 位。

你听过 千字节(kb)兆字节(mb)千兆字节(gb)不同前缀代表不同数量级

计算机必须给内存中每一个位置,做一个“标记”这个标记叫“位址”目的是为了方便存取数据

除了负数和正数,计算机也要处理非整数,比如 12.7 和 3.14,因为小数点可以在数字间浮动。有很多种方法表示浮点数

IEEE 754标准

652.9可以写成 0.6259 x 10 ^3

.6259 叫 “有效位数”,3 是指数。 在 32 位浮点数中第一位表示数字的正负,接下来 8位存指数,剩下 23 位存有效位数

计算机可以用数字表示字母

最直接的方法是给字母编号:A是 1,B是 2,C是 3,以此类推曾用 5位序列 来编码英文的 26个字母。

ASCII,美国信息交换标准代码,发明与 1963年,ASCII是 7 位代码,足够存 128 个不同值。

很多国家语言不一样,中文,日文,所以为了统一,Unicode 诞生了统一所有编码的标准。设计与 1992 年,解决了不同国家不同标准的问题。

Unicode 用一个统一编码方案。

算术逻辑单元(ALU)

ALU 是计算机的数学大脑 ALU 就是计算机里负责运算的组件,基本其他所有部件都用到了它。

ALU 有 2个单元,1个算术单元和 1个逻辑单元

算术单元

它负责计算机里的所有数字操作。

现代计算机用的加法电路有点不同, “超前进位加法器”

逻辑单元

逻辑单元执行逻辑操作比如之前讨论过的 AND,OR 和 NOT操作它也能做简单的数值测试比如一个数字是不是负数。

计算机内存

我们知道可以用 ALU计算那么结果我们要保存可能下次运算或者再次运算。

如果你在玩困难磨模式的 “扫雷”,然后狗跑过来,被电源线绊倒,把插头拔了出来,你知道失去进度的痛苦。你损失数据的原因是:

电脑用的是随机存取存储器 简称 “RAM”它只能在有电的情况下存储东西,比如游戏状态。

另一种存储(memory)叫持久存储,电源关闭时数据也不会丢失它用来存其他东西。

锁存器通过允许写入跟ALU逻辑门来存储数据,一组这样的锁存器叫“寄存器”寄存器能存一个数字,这个数字有多少位,叫“位宽”。早期电脑用 8 位寄存器,然后是 16 位,32 位。如今许多计算机都有 64 位宽的寄存器。

写入寄存器前,要先启用里面所有锁存器。

64位寄存器要64根数据线,64根连到输出端。幸运的是,我们只要 1 根线启用所有锁存器但加起来也有 129条线了。如果存 256 位要513条线!解决办法就是 ”矩阵

矩阵 黑客帝国 yyds

在 矩阵 中,我们不并列排放锁存器而是做成网格。存 256 位,我们用 16x16 网格的锁存器,有 16行 16列要启用某个锁存器,就打开相应的 行线和列线。

所以对于 256位的存储。只要 35 条线,1 条 ”数据线“ 1 条 ”允许写入线“ 1条 ”允许读取线“ 还有16行 16列的线用于选择锁存器 (16+16=32,32+3=35)

RAM 有很多类型,DRAM,闪存,和 NVRAM,它们在功能上与 SRAM 相似。但用不同的电路存单个位。比如用不同的逻辑门,电容器,电荷陷阱,或忆阻器。**但根本上 这些技术都是矩阵层层嵌套,来存储大量信息。就像计算机中的很多事情,底层其实都很简单。**让人难以理解的,是一层层精妙的抽象,像一个越来越小的俄罗斯套娃。

CPU (“中央处理单元”)

CPU 负责执行程序,程序由一个又一个操作组成,这些操作叫 “指令”因为它们“指示”计算机要做什么。如果是数学指令,比如 加/减 CPU 会让 ALU 进行数学运算。也可能是内存指令,CPU会和内存通信,然后读写值。

我们已经知道数据 是以二进制值存在内存里,程序也可以存在内存中。

我们给 CPU 支持的所有指令,分配一个 id

指令(INSTRUCTION) 描述(DESCRIRTION) 4位操作码(4-BIT OPCODE) 地址或寄存器(ADDRESS OR REGISTERS)
LOAD_A Read RAM location into register A 0010 4-bit RAM address
LOAD_B Read RAM location into register B 0001 4-bit RAM address
ADD Add two registers,store result into second register 1000 2-bit register ID,2-bit register ID

假设 前四位存 “操作代码”后四位 可以是寄存器或内存地址。

CPU 有 “指令地址寄存器”存当前指令的内存地址。另一个寄存器存当前指令,叫 “指令寄存器”。

不同指令由不同逻辑电路解码,这些逻辑电路会配置 CPU 内的组件来执行对应 操作。

人工切换 CPU 的状态 “取指令-解码-执行”。

当然不是每台电脑里都有一个 “精灵”来切换或控制 CPU 状态,其实是 “时钟" 来负责管理 CPU 的节奏。

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

CPU ‘“取指令->解码->执行”’ 的速度叫 ”时钟速度“,单位是 赫兹 赫兹是用来表示频率的单位

如今电脑手机基本上都有几千兆赫兹 一兆赫兹是 1秒 一百万个时钟周期。

你可能听说过有人会把计算机超频,意思是修改时钟速度,加快 CPU 的速度

RAM 是在 CPU 外面的独立组件。CPU 和 RAM 之间用”地址线“ ”数据线“ 和 “允许读/写线” 进行通信

CPU之所以强大,是因为它是可编程的,如果写入不同指令,就会执行不同任务。
CPU是一块硬件,可以被软件控制!

现代计算机随着功能增加 指令也不断增加。现代 CPU 用两种策略

1.最直接的方法是用更多位来代表指令,比如 32 位或 64位 这叫 指令长度

2.第二个策略是 “可变指令长度” 举个例子,比如某个 CPU 用 8 位长度的操作码 如果看到 HALT 指令,HALT 不需要额外数据 那么会马上执行,如果看到 JUMP,它得知道位置值,这个值在 JUMP 的后面。这叫 “立即值”这样设计,指令可以是任意长度,但会让读取阶段复杂一点点。

CPU

  • 早期是加快晶体管切换速度,来提升 CPU 速度

    但这种提速方法最终会碰到瓶颈,所以处理器厂商发明各种新技术来提升性能,不但让简单指令运行更快。也让它能进行更复杂的运算。

    现代 CPU 直接在硬件层面设计了除法可以直接给 ALU 除法指令,这让 ALU 更大也更复杂一些。

    复杂度 vs 速度 的平衡在计算机发展史上经常出现

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

    CPU ‘“取指令->解码->执行”’ 的速度叫 ”时钟速度“,单位是 赫兹 赫兹是用来表示频率的单位

    我们上次说了时钟,超高的时钟速度带来另一个问题,那就是如何快速传递数据给 CPU。

    就像 蒸汽机,但无法快速加煤。

    RAM 成了瓶颈

    RAM 数据要用线来传递,叫 “总线”总线可能只有几厘米,别忘了电信号的传输接近光速,但 CPU 每秒可以处理上亿条指令很少的延迟也会造成问题 RAM 还需要时间找地址,取数据,配置,输出数据。一条 “从内存读数据”的指令可能要多个时钟周期。

    1.解决延迟的方法之一是

    **给 CPU 加一点 RAM 叫 “缓存”**因为处理器里空间不大,所以缓存一般只有 KB 或 MB.而 RAM 都是 GB 起步 缓存提高了速度,CPU 从 RAM 拿数据时,RAM 不用传一个,可以传一批,虽然花的时间久一点,但数据可以存在缓存。

    缓存也可以当临时空间,存一些中间值,适合长/复杂的运算

    当我们做运算时,计算出的值是新的值以后可能还会作出运算,这时 缓存 和 RAM 不一致了,这种不一致必须要记录下来,之后要同步,因此缓存里每块空间,有一个特殊标记 叫 “脏位”

    同步一般发生在 当缓存满了而 CPU 又要缓存时在清理缓存腾出空间之前,会先检查 **“脏位”**如果是 “脏的”,在加载新内容之前,会把数据写回 RAM。


    2.另一种提升性能的方法叫 “指令流水线”

    我们上次说了 CPU 执行是取指令=>解码=>执行 这种设计,三个时钟周期执行 1 条指令,但因为每个阶段 用的是 CPU 的不同部分,意味着可以并行处理! “执行”一个指令时,同时 “解码”下一个指令,同时 "读取"下一个指令。

    不同任务重叠进行,同时用上 CPU 里所有部分。这样的流水线,每个时钟周期执行1个指令。

    这种方法也会带来一些问题,跟缓存一样:指令之间的依赖关系,可能你在读取某个数据,而同时执行的指令正在改这个数据。

    因此流水线处理器 要弄清数据依赖性,必要时停止流水线,避免出问题

    高端 CPU ,比如笔记本和手机里那种会更进一步,动态排序,有依赖关系的指令最小化流水线的停工时间,这叫 “乱序执行” 这种电路非常复杂,但因为非常高效,几乎所有现代处理器都有流水线。

    第二个是 一些 JUMP 指令 这些指令会改变执行顺序。简单的流水线处理器,看到 JUMP 指令会停一会儿,等待条件值确定下来,一旦 JUMP 的结果出了,处理器就继续流水线,因为空等会造成延迟,所以高端处理器会用一些技巧。

    因为空等会造成延迟,所以高端处理器会用一些技巧,可以把 JUMP 想成是 “岔路口”高端 CPU 会猜哪条路的可能性大一些,然后提前把指令放进流水线,这叫 “推测执行” 当 JUMP 的结果出了,如果 CPU 猜对了,流水线已经塞满正确指令,可以马上运行,如果 CPU 猜错了,就要清空流水线就像走错路掉头

    为了尽可能减少清空流水线的次数,CPU 厂商开发了复杂的方法来猜测哪条分支更有可能,叫 “分支预测”

    现代 CPU 的正确率超过 90% 理想情况下,流水线一个时钟周期完成 1 个指令,然后 “超标量处理器” 出现了,一个时钟周期完成多个指令即便有流水线设计,在指令执行阶段处理器里有些区域还是可能会空闲。比如,执行一个 “从内存取值”指令期间 ALU 会闲置,所以一次性处理多条指令(取指令 + 解码)会更好

    如果多条指令要 CPU 的不同部分,就多条同时执行,我们可以再进一步,加多几个相同的电路执行出现频次很高的指令。目前说的方法,都是优化 1 个指令流的吞吐量

    另一个提升性能的方法是 同时运行多个指令流 用多核处理器,你应该听过 双核或四核处理器,意思是一个 CPU 芯片里,有多个独立处理单元,很像是有多个独立 CPU,但因为它们整合紧密,可以共享一些资源,比如缓存,使得多核可以合作运算,但多核不够时,可以用多个 CPU.高端计算机,比如现在给你传视频的 Youtube 服务器需要更多马力,让上百人能同时流畅观看

  • 给 CPU 专门的除法电路 + 其他电路来做复杂操作,比如游戏,视频解码

  • 给 CPU 加缓存,提高数据存取速度,更快喂给 CPU。

CPU 就介绍到这里了,我觉得其实跟程序一样,我说的只是形象化,比如最开始 CPU可能只能进行简单的计算,后来有了 ALU ,有了指令,更多的指令,让功能很多,问题也随着而来,比如优化 取指令->解码->执行,同时取指令->解码->执行,多核处理器。都是一步步而来的,一个问题,我们可以拆分成一个又一个组件或者是模块,来一起完成它。编程是,生活也是。

早期的编程方式

插孔编程

在 1980 年代,几乎所有的计算机都有穿孔纸卡读取器可以吸入一张卡片,把卡片内容写进内存,如果放了一叠卡片,读取器会一个个写进内存,一旦程序和数据写入完毕,电脑会开始执行即便简单程序也有几百条指令,要用一叠纸卡来存。如果不小心摔倒弄撒了要花上几小时,几天,甚至几周来整理。

控制面板编程(插线板)

面板有很多小插孔,程序员可以插电线,让机器的不同部分 互相传数据和信号,因此也叫“插线板”,

不幸的是,这意味着 运行不同程序要重新接线,到 1920 年代,控制面板变成了可拔插让编程更方便。

插线板很复杂,计算机非常昂贵人们急需更快,更灵活的新方式来编程。

1940 年代晚期 1950年代初,内存变得可行价格下降,容量上升。与其把程序存在插线板存在内存变得可行。

这种程序易与修改,方便 CPU 快速读取 这类机器叫 “存储程序计算机” 如果内存足够,不仅可以存要运行的程序。包括程序运行时产生的新数据。

程序和数据都存在一个地方,叫 “冯诺依曼结构”

冯诺依曼的标志是 : 一个处理器(有算术逻辑单页)+数据寄存器+指令寄存器+指令地址寄存器+内存(负责存数据和指令)

面板编程

与其插一堆线到插线板,可以用一大堆开关和按钮,做到一样的效果,面板上有指示灯,代表各种函数的状态和内存中的值。50和60年代的计算机,一般都有这样巨大的控制台很少有人只用开关来输入一整个程序,但技术上是可行的。

早期针对计算机爱好者的家用计算机,大量使用了开关,因为大多数家庭用户负担不起昂贵的外围设备,比如穿孔纸卡读取器。

第一款取得商业成功的家用计算机是 Altair 8800 有两张版本可以买:

  1. 预先装好的整机
  2. 需要组装的组件

计算机爱好者,喜欢买组件版。

编程方式:拨动面板上的开关,输入二进制操作码,然后按 “存储键”把值存入内存,然后会到下一个内存位置,你可以再次拨开关,写下一个指令。

早期编程都是专家,不管是全职还是技术控,都要非常了解底层硬件,比如 操作码,寄存器,才能写程序所以编程很难,很烦。哪怕工程师和科学家都无法 完全发挥计算机的能力。

所以我们需要更简单的编程方式

编程语言发展史

硬件层面编程非常麻烦,所以程序员想要一种更通用的方法编程 - 一种“更软的”媒介

软件

计算机能处理二进制,二进制是处理器的 “母语”事实上,它们只能理解二进制。这叫 机器语言或机器码

在计算机早期阶段,必须用机器码写程序。

举例: “从内存取下一个销售额,然后加到天,周,年的总和,然后算税等等”

这种对程序的高层次描述,叫“伪代码”在纸上写好,用 “操作码表”把伪代码转成二进制机器码,翻译完成后,程序可以喂给计算机并运行,你可能猜到了,很快人们就厌烦了。所以在 1940-1950年代程序员开发出一种新语言,更可读,更高层次。每个操作码分配一个简单名字,叫 “阻记符”

助记符 后面紧跟数据,形成完整指令与其用 1 和 0 写代码,程序员可以写“LOAD_A 14”

CPU 不知道 LOAD_A 14 是什么它不能理解文字,只能理解二进制,所以程序员想了一个技巧,写 二进制程序来帮忙,它可以读懂文字指令,自动转成 二进制指令 这种程序叫 汇编器

汇编器读取用“汇编语言”写的程序,然后转成“机器码”,随着时间推移,汇编器有越来越多功能,让编程更容易其中一个功能是自动分析 JUMP 地址 汇编器不用固定跳转地址。而是让你插入可跳转的标签。

汇编器有这些厉害功能,比如自动跳转,汇编只是修饰了一个机器码一般来说,一条汇编指令对应一条机器指令,所以汇编码和底层硬件的连接很紧密,汇编器仍然强迫程序员思考,用什么寄存器和内存地址

1952年 Hopper 创造了第一个编译器,编译器专门把高级语言 转成低级语言比如汇编或机器码(CPU 可以直接执行机器码

FORTRAN 这门语言数年后由 IBM 在 1957 年发布主宰了早期计算机编程(因为懒,不想编程,所以写这门语言,让编程更容易)

FORTRAN 比等同的手写汇编代码短 20 倍,然后 FORTRAN 编译器会把代码转成机器码,人们怀疑性能是否比得上手写代码,但因为能让程序员写程序更快,所以成了一个更经济的选择运行速度慢一点点,编程速度大大加快。

当时 IBM 计算机在卖计算机因此最初 FORTRAN 代码只能跑在 IBM 计算机上 1950年代大多数编程语言和编译器只能运行在一种计算机上如果要升级代码,可能要重写所有代码。一层工业界,学术界,政府的计算机专家在 1959年 组建了一个联盟

数据系统语言委员会 Grace Hopper 担任顾问

开发一种通用编程语言,可以在不同机器上通用,最后诞生了一门高级,易与使用,普通面向商业语言,简称 COBOL。为了兼容不同底层硬件,每个计算架构需要一个 COBOL 编译器。最重要的是,这些编译器都可以接收相同的 COBOL 代码,不管是什么电脑这叫”一次编写,到处运行“。如今大多数编程语言都是这样,不必接触 CPU 特有的汇编码和机器码。减少了使用门槛,在高级编程语言出现之前,编程只是计算机专家和爱好者才会做的事。而且通常是主职。

感谢这些语言,让计算机科学从深奥学科 变成了大众化工具

同时,编程的抽象也让计算机专家。现在叫 ”专业程序员“制作更复杂的程序。如果用汇编写可能要上百万行。

编程语言都有的基本元素。

编程有“语句”语句表单单个完整思想。规定句子结构的一系列规则叫 语法

(会跳过一些,因为都是基础语句 if else)

如果每次想用就复制粘贴,会很麻烦,每次都要改变量名字,如果代码发现问题,要补漏洞时要把每一个复制粘贴过的地方都找出来改。

为了隐藏复杂度可以把代码打包成”函数“也叫 ”方法“或 ”子程序“有些编程语言这么叫。

模块化编程 不仅可以让单个程序员独立制作 APP也让团队协作可以写更大型的程序

现代编程语言 有很多预先写好的函数集合,叫”库“

算法入门

算法 一词来自 波斯一个学者 1000 多年前的代数之父之一。

如何想出高效算法 - 是早在计算机出现前就有的问题诞生了专门研究计算的领域。然后发展成一门现代学科 -》计算机科学

记载最多的算法是 排序 比如给名字,数字排序,排序到处都是,找最便宜的机票,按最新时间排邮件,按姓氏排联系人。

视频的代码好像是 python 实现的,我其实更偏向 JS,但是我发现关于 JS 算法的书好少。

(待续,如果你是个前端工作者,你可以点 star 我会重新写一篇文章来更新 JS的算法,包括 力扣的题门。跟我一起学)

数据结构

算法处理的数据 存在内存里的格式是什么

比如 j = STAN ROCK

在内存中会以这种格式存储的

MEMORY LOCATION VALUE
1000 S
1001 T
1002 A
1003 N
1004 (SPACE)
1005 R
1006 O
1007 C
1008 K
1009 S
1010 (zero)

字符串在内容里以 0 结尾不是 “字符0” 是 二进制值0 这叫字符 “null”表示字符串结尾

二维数组(矩阵)

可以把矩阵看成 数组的数组,一个 3x3 矩阵就是一个长度为 3 的数组

数组里每个元素都是一个长度为3的数组(任何维度都行)

有时,把几个有关系的变量存在一起,会很有用,多个变量打包在一起叫 结构体

存结构体的数组,和其他数组一样,创建时就有固定大小,不能动态增加大小,还有,数组在内存中按顺序存储,在中间插入一个值很困难,但结构体可以创造更复杂的数据结构,消除这些限制。

链表

链表是一种灵活数据结构,能存很多个节点,灵活性是通过每个节点 指向 下一个节点实现的。

链表可以是循环和非循环的,最后一个指针是 0 “null”,代表链表尽头

当程序员使用链表时,很少看指针具体指向哪里,而是用链表的抽象模型。

(听说过链表,但好像是后端接触的)

链表大小可以动态增减,可以创建一个新节点,通过改变指针值,把新节点插入链表

链表也很容易重新排序,两端缩减,分割,倒序等

因为灵活,很多复杂数据结构 都用链表。最出名的是队列(queue) 和 栈(stack)

“队列”就像邮局排队,谁先来就排前面。 这叫 “先进先出”
“栈”是后进先出 (栈就不叫 “入队”“出队”叫 “入栈”“出栈”)

计算机科学之父

阿兰~图灵 中间是英文圆圈=-=。

可判定性问题:是否存在一种算法,输入正式逻辑语句输出准确的是 “是”或 “否”答案?

图灵机是一台理论计算设备,有无限长的纸袋,纸带可以存储符号,还有一个读写头可以读取和写入纸袋上的符号,还有一个状态变量,保存当前状态,还有一组规则,描述机器做什么 规则是根据 当前状态 + 读写头看到的符号,决定机器做什么 结果可能是纸袋写入一个符号或改变状态,或把读写头移动一格,或执行这些动作的组合

软件工程

把大项目分解成小函数,可以让多人同时工作,如果你的任务是写排序算法你只需要确保高效和正确就可以了,然而把代码打包成函数 依然不够,如果只是这样,微软 Office 会有几十万个函数,虽然比 4000 万行代码要好一些,但还是太多了。解决办法是:把函数打包成层级。把相关代码都放在一起,打包成对象(objects)

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

团队需要文档 帮助理解代码都做什么,以及定义好的 “程序编程接口 简称 api api帮助不同程序员合作,不用知道具体细节,只要知道怎么使用就行了。”

面向对象编程的核心是 隐藏复杂度,选择性的公布功能,因为做大型项目很有效,所以广受欢迎

集中电路 && 摩尔定律

在大概50年 软件从纸币打孔变成面向对象编程语言,在集成开发环境中写程序,但如果没用硬件的大幅度进步,软件是不可能做到这些的

大约 1950年代~1960年代中期这段时间里计算机都由独立部件组成,叫 “分立元件” 然后不同组件再用线连在一起 如果想提升性能,就要加更多部件,这导致更多电线,更复杂。

与其把多个独立部件用电线连起来,拼装出计算机,我们把多个组件包在一起,变成一个新的独立组件

这就是 集中电路 IC

但最终还是需要连起来,创造更大更复杂的电路,比如整个计算机。所以工程师们再度创新:印刷电路板,简称 PCB

捕获

PCB 可以大规模生产,无需焊接或用一大堆线。它通过蚀刻金属线的方式,把零件连接到一起 我们把 PCB 和 IC 结合使用 可以大幅减少独立组件和电线,但做到相同的功能 而且更小,更便宜,更可靠,三赢!

许多早期 IC 都是把很小的分立部件封装成一个独立单元,例如这块 1964年的 IBM样品

许多早期 IC 都是把很小的分立元件封装成一个独立单元,例如这块 1964年的 IBM 样品,不过,即使组件很小塞五个以上的晶体管还是很困难,不过即使组件很小塞五个以上的晶体管还是很困难。为了实现更复杂的设计,需要 全新的制作工业 “光刻”登场!

在现实中,光刻法一次会做上百万个细节,芯片放大是这样的,导线上下交错,连接各个元件,尽管可以把光掩膜投影到一整片晶圆上,但光可以投射成任意大小,就像投影仪可以投满荧幕一样,我们可以把光淹膜聚焦到极小的区域,制作出非常精细的细节,一片晶圆可以做很多 IC 整块都做完后,可以切割然后包进微型芯片,微型芯片就是在电子设备中那些小长方体,记住,芯片的核心都是一小片 IC,随着光刻技术发展,晶体管变小密度变高

1960年代初。IC 很少超过 5个晶体管,因为塞不下,但 1960年代中期市场上开始出现超过 100个晶体管的 IC

1965年 戈登`摩尔看到了趋势:每两年左右,得益与材料和制作技术的发展同样大小的空间,能塞进两倍数量的晶体管!这叫 “摩尔定律”然而这个名字不太对,因为它不是定律,只是一种趋势但它是对的

晶体管越小,要移动的电荷量就越少,能更快切换状态 耗电更少,电路更紧凑还意味着信号延迟更低导致时钟速度更快

操作系统

待续 因为目前在找工作,所以复习方向在前端这块