Coursera 计算导论与 C 语言基础，北京大学

搞竞赛的时候学的 C 语言，这门语言对我来说应该算是很亲切了。
然而竞赛涉及到的语言特征毕竟有限，较为偏向理论，与工作时需要用到的相关语言特征肯定有很大不同。遂萌生了想从零开始系统的学习一下 C 语言和面向对象编程理念的想法，那么就从 coursera 上的这门课开始吧！

第三次数学危机到图灵机

哥德尔提出了不完全性定理：

任何一个形式系统，只要包括了简单的初等数论描述，而且是自洽的，它必定包含某些系统内所允许的方法既不能证明真也不能证伪的命题。
不完全性定理使数学家们追求完美形式化数学的梦想破碎了。

然而，数学家们决定继续研究可计算问题与不可计算问题的分界。可计算问题可以简化为如下的命题：设函数 f 定义域 D，值域 R，若 存在一种算法 对 D 中任意给出的 x 都能计算出相应的 f(x)，则称该函数是可计算的。
所以，我们只需建立一个数学模型，然后证明，凡是这个计算模型能够完成的任务，就是 可计算的任务。
图灵提出的图灵机 (Turing machine)，就是这样一种解决问题的模型，亦是现在计算机的前身。

计算机为什么能计算？

计算机是由各种电子元件与电路组成的，没有人脑的复杂结构，其是如何实现“计算”这一功能的呢？

关于计算机中数的表示

以图灵机为例，很容易发现：字母表中的符号越多，读入移动次数就越少，但是程序数量就越多；反之亦然。
字母表中的符号的最优数量最中确定为 2，这也就是为什么计算机中采用二进制表示体系的原因。

关于计算机中数的计算 （以加法为例）

布尔提出的布尔代数使得加法可以转变为一系列逻辑运算，而这些简单的逻辑运算可以用电路实现。
半加器可以实现不进位的二进制加法，半加器串联构成的全加器可以实现考虑进位二进制加法
因此：

• 参与运算的数可以转变为二进制数
• 二进制数的运算可以运用基本的布尔运算实现
• 基本的布尔运算都可以由电路实现

这就使得由电路与电子元件构成的计算机能够进行 “计算”

计算机发展史

• 现代计算机：真空管 => 晶体管 => 集成电路 => 大规模集成电路
• 摩尔定律 (Moore's Law)：集成电路上可容纳的晶体管数目，约每隔两年便会增加一倍；CPU性能与成本比每18个月翻一番：摩尔定律还能坚持多久？
  摩尔定律下的计算危机：晶体管大小限制；电泄露问题；散热问题
  突破摩尔定律：全新的计算模式与计算理念 (量子计算机，生物计算机)
• 量子计算机：量子 => 同一时间可以表示多种状态，大大提高计算效率
  实现量子计算机的困境：与外界环境隔离以保持良好相干性 VS. 与外界环境耦合以控制演化并读出结果

计算机是如何计算的？、

冯诺依曼机 (Von Neumann machine)

• 早期理念：对于不同的计算问题，重新改编电路的排布
• 冯诺依曼的否定：应当采用 某种命令 来控制计算机以改变计算机的功能；这种 命令 不是临时输入的，而是 可存储的 => 存储程序式计算机/冯诺依曼式计算机 (EDVAK的问世)
• 冯诺依曼机：控制器，运算器，存储器，输入输出设备以总线相连接
  现代计算机：控制器，运算器与存储器中的高速缓存区被集成在 CPU 中；存储器还有内存，外存 (硬盘，光驱) 部分；键鼠，显示器 => 输入输出设备

存储器

• 存储空间单位：1B = 8bit.. B => KB => MB => GB => TB (8个位 Bit 组成一个字节 Byte ：字节是程序能够控制的最小内存单位)
• 构成(工作速度/价格排序)：寄存器 \(>\) 高速缓冲区(CASHE) \(>\) 内存(临时存储，断电丢失) \(>\) 外存
  CPU 由缓存到内存读取数据，若在内存中读取到，则将该数据所在数据块加载到缓存中，提高读取效率
  CPU 对数据的访问具有 局部性 ：时间局部(短时间内对同一个内存地址的多次访问)， 空间局部(使用的信息相邻)
• 静态 RAM 的六管基本存储单元：保存 0/1
• 地址与数据单元：32 位的 CPU 最多只能配备 4G 内存 => 32 位地址最多有 \(2^{32} B = 4G\)

CPU 程序执行

• CPU 电路可以进行计算，如何识别，执行程序？ => 指令集
• 指令最终表示为二进制码，包含指令码与操作数
• 程序语言(人类编写) => 机器语言 => 二进制码形式指令