计算工具的演化
计算的基本过程
- 获取并记录参与计算的数；
- 制定运算规则；
- 实施计算并输出结果。
算盘
算盘的本质是一个存储器，具体计算规则的实施是由人手动完成的。
- 算盘上可以记录数值数据；
- 算盘的运算不仅可以基于十进制，早期的算盘也有基于十六进制的；
- 算盘不只能完成加、减法运算，根据乘、除法的珠算规则，还可以进行乘除法运算。
帕斯卡加法器
帕斯卡加法器是基于十进制的。计算过程自动实施，只需要手动输入数值即可得到结果。
莱布尼茨在帕斯卡加法器的基础上改进了设计，增加了乘除运算，但机器的操作复杂。这些进步都提升了机器的灵巧性，但无一例外地没能突破手工计算的界限。
帕斯卡运算器的减法运算
在计算机的逻辑运算单元中，只有加法器。可用补数（补码）将减法运算过程转换成加法运算过程，这样就可以使用同样的硬件完成加减乘除运算。
在做减法时，借位问题往往使操作非常棘手。因此使用计算位数最大的数（如9、99、999、9999、…）作为减数参与运算。
以 31-16 为例：
解决上述问题的基本思想在于，求出除数的“补数”后，再与被减数相加，得到结果的“补数”，最后将结果转换而求解。
将减法问题转换为加法问题。
位数的补数是，数值上。
例如：
的补数是。
。巴贝奇的差分机和分析机
巴贝奇的贡献使计算机器的发展得到巨大突破，实现了从手工计算到机械自动的突破。
- 差分机提高了乘法速度、改进了对数表等数字表的精确度。
- 分析机是一种机械式通用计算机，奠定了现代数字计算机的基础。
分析机的设计非常超前，当时的制造工艺没能完成这个以齿轮为机械、以蒸汽为动力的作品。
用两个相对简单的例子理解巴贝奇的设计思想：“可编程”打孔卡片的提花织布机和八音盒。
算法是自动化计算的灵魂。
“可编程”打孔卡片的提花织布机
利用打孔的卡片控制织花的图样，工作时无需人工的干预。
提花织布机上有“可编程”的设计思想，通过设计不同打孔卡片，可以得到不同的提花图案。 提花织布机可以解读卡片上孔的含义，而由此控制各个机械部件的工作动作，类似于现代计算机的解码思想，边解读边织布的过程类似于现代计算装置的工作过程。
八音盒
图灵机
图灵机——理想计算机的数学模型。
图灵构造出一台假想的机器，该机器由以下几个部分组成：
- 一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号“▢”表示空白。纸带上的格子从左到右依次被编号为 0, 1, 2, …，纸带的右端可以无限伸展。
- 一个读写头HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
- 一套控制规则TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态，按照以下顺序告知图灵机命令：
- 写入（替换）或擦除当前符号；
- 移动 HEAD，“L”是向左，R 是向右或者 N 不移动；
- 保持当前状态或者转到另一状态
- 一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个停机状态。
因此，只要定义好了控制器规则，图灵机可以完成任何意义上的计算——一切直觉上能计算的函数都可用图灵机计算，反之亦然。
图灵从理论上证明了通用计算机存在的可能性，奠定了通用计算机的理论基础。
计算的本质
计算，归根到底是一种符号变换，是一个符号串 f 按照一定规则转换成符号串 g 的过程。
计算机的发展与摩尔定律
计算机的发展
第一代计算机——真空电子管
第二代计算机——晶体管
第三代计算机——集成电路
第四代计算机——微处理器、大规模集成电路
计算机的发展阶段通常是按计算机所采用的物理器件来划分的。
摩尔定律
集成电路上可容纳的晶体管数目，约每隔两年便会增加一倍；
经常被引用的“18个月”，是由英特尔首席执行官大卫·豪斯（David House）提出。
预计18个月会将芯片的性能提高一倍（即更多的晶体管使其更快），是一种以倍数增长的观测。
归纳起来，主要有以下 3 种版本：
- 集成电路上可容纳的晶体管数目，约每隔 18 个月便增加一倍。
- 微处理器的性能每隔 18 个月提高一倍，或价格下降一半。
-
进制
为什么要使用二进制
1945 年 6 月，冯诺依曼和歌德斯坦等人联名发布了一篇报告，此报告有 101 页，后来被称为 101 报告。
报告指出：
对进制的物理实现，需要满足以下规则： 状态简单；
- 可靠性和稳定性足够高；
- 运算规则足够简单；
- 通用性强。
十进制需要 10 个符号来表示数据，对应的物理装置必须要有 10 种足够稳定的状态。而二进制只需要 2 个符号表示数据，且对应的物理装置也只需要 2 种稳定的状态表示即可。
二进制的状态和运算规则较十进制简单、可靠性和稳定性也高，且逻辑运算中的真和假可以完美地用二进制表示、通用性足够强。
所以二进制比十进制更经济。
位模式
8 个二进制位 (bit) 表示 1 个字节 (byte)。
在任何电子机械装置上的自动计算都存在着范围和精度的问题。
二进制
二进制与十进制的转换
二进制 → 十进制
十进制 → 二进制
整数
小数
二进制的特点
基于位模式的有上限性，浮点数在计算机中的表示是有精度损失的。
爱国者导弹计算时由于“截断误差”导致对飞毛腿导弹的拦截失败，28 名军官由此丧生。
解决爱国者导弹问题的方案有：
- 每两个小时重启一次爱国者导弹系统；
- 修改24位位模式至64位；
- 修改程序，补偿误差。
示例：
>>> 0.1 * 30.30000000000000004>>> 0.3 * 30.8999999999999999
八进制 (Octal System)
0, 1, 2, 3, 4, 5, 6, 7
十六进制 (Hexadecimal)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
二进制、八进制、十六进制间的转换
把二进制数 10100101.0101111 分别转换成八进制和十六进制数。
二进制 → 八进制
从小数点分别往左往右，将二进制的 3 位作为八进制的 1 位进行计算，不足 3 位时用0补齐。
二进制 → 十六进制
从小数点分别往左往右，将二进制的 4 位作为十六进制的 1 位进行计算，不足 4 位时用0补齐。
八进制 → 二进制
从小数点分别往左往右，将八进制的 1 位作为二进制的 3 位进行计算。
十六进制 → 二进制
从小数点分别往左往右，将十六进制的 1 位作为二进制的 4 位进行计算。
码制
真值、机器数
算术运算中的数值都带有符号以表示正负。
在计算机中单独使用一个二进制位，用 0 表示正数，用 1 表示负数。由此，这样表示的数就是机器数——将数的符号数值化的表示形式（有原码、反码、补码 3 种）。
带符号位的机器数对应的带符号的数值称为机器数的真值。
以计算机字长为 8 位为例：
| 十进制 | 真值 | 机器数 |
|---|---|---|
| 3 | +0000 0011 | 0000 0011 |
| -3 | -0000 0011 | 1000 0011 |
编码方法
原码
直接将原本的数转换成 n 位二进制后的表示方法：
- 二进制最高位认为是对符号的编码；
- 剩下的 n-1 位是对数字进行的编码；
- 若数字部分不足 n-1 位，则用
0补齐； - 数值
0的原码有0…000和1…000两种形式。
优点：简单直观、易于理解。
缺点：
- 做加、减法运算较为复杂：要对符号位和数值的绝对值大小进行判断。
- 零的形式不唯一。
补码
- 符号部分的处理与补码相同（最高位为符号位，0 表示正数，1 表示负数）；
- 数字部分与它的符号位有关：
- 对于正数，补码的数字部分与原码数字部分相同；
- 对于负数，补码的数字部分由原码数字部分“按位取反，再加 1”得到。
“按位取反，再加 1”可以实现原码和补码的双向变换。
以计算机字长为 8 位为例：
| 十进制 | 源码 | 补码 |
|---|---|---|
| 3 | 0000 0011 | 0000 0011 |
| -3 | 1000 0011 | 1000 0011 → 1111 1100 → 1111 1101 |
补码的表数范围
补码的运算
加减法
补码表示法可以简化加法运算，并且可以将减法变成加法。
计算机只需要一套实现加法运算的线路，就能用补码进行减法运算。简化了计算机内部硬件电路的结构。
- 符号位也参加运算;
- 不考虑符号位的进位问题，直接截断丢弃。
乘除法
数据的表示
数值的表示
小数点位置是否固定，将数分为“定点表示”和“浮点表示”两类不同表示格式，它们由原码（和/或）补码构成。
定点数
用来表示整数和纯小数。
小数点位置固定，且隐藏。通过与计算机的约定实现，并未真正用一个二进制位存储了小数。
定点整数
定点小数
浮点数
用科学计数法将浮点数转换成一对定点数（包括定点整数部分和定点小数部分）。
M 代表尾数（纯小数，用原码或补码表示），E 代表阶码（整数，用补码表示），R 代表基数（是 2，不必占用空间）。 如：
浮点的规格化
在计算机内部，浮点数都是以规格化形式出现。如果一个非 0 浮点数的尾数最高位为 1，则称之为浮点规格化数。
如：
假设阶码用 8 位二进制表示，尾数用 16 位二进制表示，则的浮点形式是：000010010100000000100000。
IEEE 754 标准
字符的表示
声音的表示
使用时间和幅度连续变化的模拟信号，将声音的在时间方向上的波形用连续间隔采样的方式“数字化”。
数字化：将连续的模拟声音信号转换成时间和幅度都离散的数字信号。
从模拟声音信号到数字音频的过程需要经过“采样”、“量化”和“编码”。
用“采样频率”、“量化位数”和“声道数”描述数字音频的技术指标。
- 采样频率越高，表示在单位时间内的采样次数越多，可以获得更多的声音样本；
- 量化位数，即采样精度。采样精度越高，数字信号越能细腻地还原声音信息，更好地减少量化上的失真
- 声道数描述了一次采样所记录产生的声音波形的个数，双声道比单声道更具有现场感和立体感（电话常用单声道模式、CD 等多采用双声道模式）。
采样
每隔一个时间间隔在模拟声音波形上取一个幅度值（采样频率越高，数字化后得到的声音就越逼真）
量化
为采样点确定振幅值，并对振幅值进行限定和近似（线性量化：幅度划分等间隔；）
如，线性量化：
编码
量化后的幅度值用二进制数表示的过程。
量化位数（位深度）：表示量化的采样值数据的二进制位数。
PCM（脉冲编码调制, Pulse Code Modulation, PCM）编码：对模拟声音信号进行均匀采样、线性量化、四位编码的过程。
数字音频的数据量计算（无压缩）
数据率：单位时间内的数据量。
图像的表示
颜色
RGB 颜色模型：
- 三色光的基色：根据国际照明委员会 (CIE)：700nm (红); 546.1nm (绿); 435.8nm (蓝)
- 光的强度被划分为 256 个级别 (0~255)
- 每种光的颜色用一个字节表示
还可以增加一个表示透明度的
通道。
图像的数字化
图像 (Image, 位图)
由像素点组成，每个像素点表示一种颜色。适合图案不规则、颜色丰富没有规律的图。图像的分辨率越高、像素深度越深，数字化后的图像越逼真，同时图像的数据量也越大。
- 图像分辨率：数字图像的像素数目，用“像素/行×行/幅”描述，即采样点数、总像素点数；
- 像素深度：每个像素的颜色所使用的二进制位数 (bit)，也称为位深度。决定彩色图像中可以出现的最多颜色数，或黑白图像中的最大灰度等级。
按一定的空间间隔自左到右、自上而下提取画面信息，并按一定的精度进行量化的过程。
采样
对于连续图像，沿 x 方向等间隔 Δx 采样，采样点数为 n；沿 y 方向等间隔 Δy 采样，采样点数为 m。于是得到一个 m×n 的离散样本矩阵 A(m, n)。矩阵 A 中的各个点被称为像素点。
量化
把每一个离散的像素点的亮度或颜色取值用若干位数的二进制编码表示的过程。
将近似的亮度或颜色划分为同一个亮度或颜色，将他们的取值确定在有限个数范围内。
编码
使用二进制编码表示像素点的不同颜色，以行为单位存入二进制文件。
数字图像的数据量计算（无压缩）
图形 (Graphic, 矢量图)
使用指令记录图的点、线、面的位置及颜色信息，只是一种对图形的描述。
适合标志、线路图、设计图等。
视频的表示
把在时间上相互关联的图像连续起来就构成了动态图像。各个独立的图像按照特定速率连续播放，形成连续运动的画面。独立图像本身就是“帧”，是动态图像的基本单位。“帧率”反映了屏幕上每秒显示帧的数量。
视频
数字视频的数据量计算（无压缩）
动画
结构化程序设计
自顶向下，逐步求精：将问题求解由抽象逐步具体化。
模块化设计：根据模块的功能将它划分为若干个子模块，如果需要的话，可以对其再进行划分。
结构化编码：用高级语言正确实现三种基本程序结构（顺序结构、选择结构、循环结构）。
冯诺依曼计算机
最早的通用计算的思想和其体系结构的形成。
冯诺依曼计算机的体系结构针对的是计算机的硬件（裸机）部分。
布尔代数
早在 1850 年左右，英国数学家布尔 (G.Boole) 就已创立了逻辑代数（布尔代数）。逻辑代数系统采用二进制，是一个关于 0 和 1 的代数系统，用基础的逻辑符号系统描述物体和概念。是现代电子计算机的数学和逻辑基础。
香农 (Claude Shannon) 是奠定现代计算机发展的重要人物：1938 年，首次用布尔代数进行开关电路分析，并证明布尔代数的逻辑运算可以通过继电器电路实现。
香农是现代信息论的著名创始人。1948 年他发表《通信的数学理论》，标志着信息论诞生。
第 03 集：布尔逻辑和逻辑门 - Boolean Logic & Logic Gates
计算机系统
- 中央处理单元 (CPU)：算术逻辑单元（运算器）、控制单元（控制器）
- 总线：数据总线、地址总线、控制总线
- 存储器：内存、外存
- 输入设备：鼠标、键盘
- 输出设备：显示器、打印机
计算机程序与指令
程序：为完成一项特定任务而用某种语言编写的一组指令序列。
指令：对计算机进行程序控制的最小单位。
计算机的指令系统：所有指令的集合。
指令周期：取指令、分析指令、执行指令、指令计数器增 1。
机器指令格式
计算机的两个基本能力
- 能够存储程序
- 能够自动地执行程序
操作系统
操作系统（OS, Operating System）是管理计算机硬件与软件资源的计算机程序。
操作系统为用户提供了“抽象机”，隐藏了底层硬件的细节，提供应用和服务的公共接口。操作系统功能
- 管理功能
- 存储管理
- 进程管理（处理机管理）
- 文件管理
- 设备管理
- 服务功能
特征
- 动态性——有生命周期：
- 由创建产生
- 由调度执行
- 因等待暂停（等待某种资源，等待 I/O 完成）
- 因完成消亡
- 独立性——是系统进行资源分配与调度的独立单位
- 并发性：为了增强计算机处理能力和提高资源利用率，采用的同时操作技术
- 异步性（不可再现性）：每个进程都以自己独立的、不可预知的速度进展
存储管理
程序运行需要从硬盘装载到主存。
虚拟存储器管理实现了存储扩充。这一技术的实现基础是程序的运行具有局部性。虚拟存储器的实现，减小了运行的程序对内存的需求，另一方面也增加了可支持的并行进程的数量。表现出来的是原本看起来不够充足的内存也能正常运行，实际上是操作系统将不太活跃的进程存储到了外置存储器上划分的虚拟化存储空间上了。
单位时间内的程序执行只会访问部分指令、只有一部分指令处于活跃状态。因此不必将程序全部载入内存。
某存储单元被使用后，其相邻的存储单元也可能很快会被使用。最近访问过的程序代码和数据可能很快又会被访问。因此，程序在执行时可部分装入主存、主存容量越大，CPU 执行速度越快。线程 (Thread)
线程是操作系统能够进行运算调度的最小单位。大部分情况下，它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。
一个进程可以有很多线程来处理，每条线程并行执行不同的任务。如果进程要完成的任务很多，这样需很多线程，也要调用很多核心，在多核或多 CPU，或支持 Hyper-threading 的 CPU 上使用多线程程序设计的好处是显而易见的，即提高了程序的执行吞吐率。
多线程间使用“分时”思想运行并占用 CPU——并发。
并发性是指在一个系统中，拥有多个计算。这些计算有同时执行的特性，彼此有着潜在的交互。因此系统可进行的运行路径会有相当多个，而且结果可能具有不确定性。并发计算可能会在具备多核心的同一个芯片中复合运行，以优先分时线程在同一个处理器中运行，或在不同处理器中运行。\
抽象与计算
由于世界的复杂性以及求解复杂问题的困难，抽象就变得非常重要。
抽象不借助具体形象反映现实，而是以抽象表达科学的真实移除细节看主干。 忽略一个主题中与当前问题无关的方面，以便更充分地注意与当前问题有关的方面——移除细节看主干。
图灵机是计算的抽象。
冯诺依曼体系结构是计算机硬件层次的抽象。
计算机科学最本质的内容是抽象 (abstraction) 与自动化 (automation)。
- Abstraction (抽象)：给问题建立合适的 model (模型)
Automation (自动化)：使用模型，为自动求解问题找到方法。
算法的特征
算法是指从初始符号或已知符号开始，一步一步地变换符号，经过限步骤,最后得到一个满足预先规定的符号串的变换过程。
输入
- 一个算法必须有零个或零个以上输入量
- 输出
- 一个算法应有一个或一个以上输出量，输出量是算法计算的结果
- 明确性
- 算法的每个步骤都必须精确地定义，拟执行的动作的每一步都必须严格地、无歧义地描述清楚，以保证算法的实际执行结果精确而符合要求或期望
- 有限性
- 算法在有限个步骤内必须终止
- 有效性（可行性或能行性）
递归 (Recursion)
在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。表现是函数直接或间接调用自己。
- 一部分是函数知道怎么解决的问题——基本实例
- 另一部分不知道怎么解决，但它是原始问题的简化（规模小），简化的最终结果是基本实例，而基本实例又是可以解决的。
递归在程序实现上更简洁、但循环更高效。
def factorial(num):if num == 0:return 1return num * factorial(num - 1)
常用策略——分治法 (Divide and Conquer)
采取”分而治之”的思想把一个复杂的问题分成两个或更多的子问题再把子问题分成更小的子问题……直到最后子问题可以进行简单地直接求解。于是，原问题的解可以通过子问题的解的合并而得到。
问题的解决依赖于类似问题的解决，不过后者的复杂程度或规模较原来的问题更小。一旦将问题的复杂程度和规模化简到足够小时，问题的解法其实非常简单解决。
设计递归算法的思路
若有收获，就点个赞吧
0 人点赞
