《重新了解计算机基础》- Crash Course Computer Science（计算机科学速成课）笔记15-21

1. 阿兰 图灵（1912生于伦敦）没太看懂这章

2. 相关问题

3. 可判断性问题

4. Lambdo算子

5. 图灵机：

6. 纸带、读写头、状态变量、一组规则

7. 一个强大的计算模型

8. 图灵证明了图灵机可以完成任何计算

Turing 完备是指在可计算性理论中, 运算规则系统的集合（例如指令集、编程语言或细胞自动机）能够模拟单带图灵机的行为。

5. 图灵机的停机问题

6. 如何证明无法实现：

一台机器：这台机器负责判定输入程序是否会终止运行。若能终止运行，则继续执行当前操作；若无法终止，则会停止执行自身操作。

假设输入的程序即为此机器自身编写的程序，则当该程序运行至停机时（即完成任务并停止执行），若返回结果为yes，则表示任务已完成；若返回结果为no，则表示任务未完成。

然而所得结果自相矛盾（涉及罗素悖论及理发师悖论），因而导致该方案不可行。无法实现其设想。

4. 事实证明，不是所有事情都可以用计算来完成

5. 丘奇图灵论题：可计算性理论

图灵测验即指测试者与被测者分别处于隔离状态下的情景，在此环境下使用键盘等装置向被测者发出问题。在经过多轮实验后若机器使参与者的平均误判率高于30%则判定该机器具备人类智能

1. 现代的延伸图灵测试：验证码

2. 软件工程：预防程序错误

面向对象编程作为一种编程范式，在软件开发中被广泛采用。其核心思想在于通过将相似的功能整合到层次结构中来提升效率和可维护性。

1. 核心：隐藏复杂度，选择性公布功能

2. API：程序编程接口，实现不同对象之间的连接与交互

3. 对象权限举例

4. public:其他对象都可以调用

5. private:只有同一对象内的其他函数可以调用

6. 集成开发工具：IDE,idea、eclipse等。

7. 程序文档：为了帮助开发者理解代码提高代码的复用性

8. 常用方式

9. 文档

10. 注释

11. 源代码管理：版本控制，代码仓库。例如GIT、SVN等。

源码测试：通过自动化质量保证测试确保系统稳定运行；在完成代码编写后进行；发现并修复潜在问题相当于进入预发布版本阶段。

3. 集成电路和摩尔定律（了解完软件发展之后又回归硬件发展）

4. 电子计算机时代(1940-1960):

5. 计算机由不同的分立元件（只有一个电路元件的组件）用线连接而成

分立元件：仅由一个电路元件构成的组件

ENICA：世界上第一台电子数字计算机（EDC），拥有17284个晶体管、约7 \times 1e4个电阻、约9 \times 1e3个二极管以及5 \times 1e6个焊接点

数字暴政：指的是为了提升计算机性能而必须配备的复杂部件组合。

2. 计算机2.0时代（1950年）（晶体管商业化）：

3. IC集成电路（多个组件封装在一起）：芯片的核心

4. 出现的契机：数字暴政，复杂繁多的分立元件，无法更高效利用发展计算机。

5. 现代集成电路之父：1954年Robert Noyce在其职业生涯初期即被视为"仙童半导体"：硅材料（Si）使集成电路成为现实并开启了电子技术的新纪元，并催生了硅谷这一全球科技中心。

6. IC发展

7. 1960初期集成电路只能容纳五个左右晶体管

8. 1960中期IC可容纳100个左右晶体管

9. 1971年的Intel 4004 可容纳2300个晶体管

10. 1980年可容纳3万个晶体管

11. 1990年可容纳100万个晶体管

12. 2000年可容纳3000万个晶体管

13. 2010年可容纳10亿个晶体管

14. 摩尔定理（趋势）：

集成电路中所支持的晶体管数量每隔约18至24个月的时间段内会翻一番。

2. 然而近些年

3. PCB印刷电路板：时刻金属线

集成电路在将组件封装之后，并非能够避免连接电路所需的大量插线。这也导致了计算机必须采用复杂的布线系统来完成任务。

2. 印刷电路板通过蚀刻金属线来连接线路，有效的解决了布线问题

3. 光刻:用光把图案印在材料上，例如半导体材料

出现契机：印刷电路板和集成电路在显著地扩大组件尺寸的同时，在芯片集成度方面仍有提升空间；尽管如此，在单块集成电路上实现5个晶体管以上的布局仍然具有挑战性。

2. 光刻原理（举例为晶体管，其他分立元件也可以通过类似的蚀刻制造）：

依次在一块晶圆(半导体硅)上涂覆一层氧化层保护膜，并在其表面涂覆一层光刻胶；然后将不需要曝光的部分用光刻胶进行覆盖。

用强烈光照照射未被遮盖的光刻胶后会引发化学反应导致其溶解并显示出氧化层的存在

3. 再用一种特定的酸洗掉露出的氧化层。在用特殊化学品将光刻胶洗掉。

4. 通过“掺杂”修改硅的露出部分，提高导电性

5. 用高温气体磷掺杂

6. 渗透进暴露的硅，改变其电学性质

7. 重复上述第一步及之后的操作，通过另一种掺杂吗，转化硅的另一种性质。

8. 在氧化层上通过光掩模、光刻胶蚀刻出新的小通道，用于连接其他晶体管。

9. 在最上方再放一层金属铝或铜。

10. 在金属层上再放一层光掩模、光刻胶，蚀刻光刻胶和金属层。

11. 优点：

12. 晶体管越小，移动电荷量越小，状态切换越快，耗电量更小

13. 电路紧凑，信号延迟更低、时钟速度更快

14. 摩尔定理（趋势）：

集成电路上可容纳的晶体管数量每隔18至24个月就会翻一番。

然而近年来，在微小规模下由于晶体管尺寸减小导致电子间距缩短至仅隔几个原子的距离的现象——即量子隧道效应的影响下，并且光波长度及精度已经达到现有技术极限的前提下，在维持现有技术框架的情况下无法进一步提高集成度；因此需要探索利用波长更短、光源更小的新型光源系统来突破现有技术瓶颈并实现芯片容量的持续提升。

4. 系统（具备对硬件的操作权限，并能够执行并管理其他应用程序，并支持多任务处理）

5. OS的发展

在20世纪40至50年代期间, 计算机仅能以串行方式执行程序, 即每次完成一条指令后, 必须由操作人员将下一条指令的卡片依次放入机器中才能继续运行.然而随着科技的进步, 计算机处理速度显著提升, 此时单个程序的处理速度已超越逐个插入卡片所需的时间间隔.为实现更高效率与机器性能的有效结合, 操作系统（OS）应运而生.

2. 第一台超级计算机系统的最初的超级计算机系统命名为 Atlas，并于1974年10月正式投入运行。其最初的操作系统命名为 Atlas Supervisor，在全球范围内处于领先地位，并成功实现了虚拟内存和动态保护机制

3. 实现了自动加载程序：

4. 批处理：多个程序连续自动执行

5. 多任务处理：程序调度

6. 实现单个CPU同时运行多个程序

7. 程序同时运行需要解决以下问题：

8. 在切换程序时，如何保证之前的程序数据不会丢失

解决方法：为每个程序单独分配一块专有内存区域，在获得许可的情况下将为该程序分配一组非连续的内存区域。这种情况下，输出显示这两部分地址之间存在明显的断层。为了隐藏潜在的地址断裂问题，操作系统的实现方式如下所示：

1. 操作系统将内存虚拟化：虚拟内存

2. 这样就很好的实现了动态内存分配

3. 也实现了内存保护，不会让一块程序错乱影响到另一块。

4. OS支持了外部设备的API抽象：其中一种实现方式是采用标准对话机制，并通过输入/输出硬件I/O交互完成

5. 分时操作系统：实现了多用户可以通过终端（键盘加屏幕）同时访问

为了避免单一用户占据全部的处理器和内存资源：分时操作系统通过将处理器和内存资源划分为若干份来实现对不同用户的公平分配

2. Multics多任务信息与计算操作系统：

3. 早期最著名的分时操作系统

4. 第一个在设计时考虑安全的系统

但是由于考虑到各种安全问题所导致的系统复杂性上升后

4. UNIX操作系统

5. 将OS分为两块

6. 内核：多任务、输入输出处理 、内存管理

7. 工具：程序、运行库等

8. 内核恐慌：当程序错误，循环弹出“恐慌”

微软在1985年的早期版本中缺乏内存保护功能，在这种情况下程序崩溃将引发特定错误代码并导致系统出现蓝色屏幕现象

6. 现代操作系统还有

7. Mac OS X

8. Windows11

9. Linux

10. Android

11. 内存和存储介质

12. 内存：易失性存储器

13. 存储器：非易失性

14. 最早的存储介质：打孔纸卡打孔纸带

15. 美国空军SAGE计算机主程序有62500张打孔纸卡

16. 打孔纸卡便宜、耐用，但读取慢，且只能读取一次

17. 延迟线存储器

充满液体的管道两侧分别安装了扬声器和麦克风，并通过导线将两端连接起来。利用扬声器每次发出的压力波变化，在两端形成高低电平信号。每个时间点只记录一位二进制数值（0或1），因此这种特性也使该装置被命名为顺序循环移位寄存器。

2. EDVAC计算机中用到了128位延迟线存储器，一条存352位数据，总共存45000位

3. 仍然需要解决的问题

4. 内存密度

5. 随机存储

6. 磁致伸缩延迟存储器：通过金属线震动来代表数据

7. 增加了存储密度

8. 磁芯存储器：通过将慈心上缠绕电线。并施加电流，来存储数据

9. 可以通过磁芯排列网络来增加内存密度

10. 第一次大规模使用磁芯存储器：

11. 1953年 的Whirlwindl:一块上磁芯排列32x32，用了316块，存16000位

12. 磁带存储器

13. 需要使用到磁带存储器

UNIVAC于[公式]年推出了一系列技术成果，并在其中推出了存储磁带系统。该系统采用高密度存储方案，在设计上实现了以下特点：单个磁带卷可储存约[公式]的信息内容，并通过高效的数据排列方式实现了整体空间利用率的最大化。

3. 问题：访问速度慢：访问数据需要前进或回退磁盘很多位。才能定位。

4. 磁鼓存储器

5. 一个高速运转的铁桶，每分钟上千转。

6. 1953年，可以存80000位(10KB)，1970年停产。

7. 硬盘

8. 1956年IBM第一台存储计算机 RAMAC 305，50张24英寸的磁盘存5MB左右

9. 寻道时间：磁盘访问一位数据的时间

10. 现代磁盘可以存100万MB数据，平均寻到时间低语1/100秒

11. 软盘：相较于磁盘是软的，已淘汰

12. 光学存储器

13. 1972年出现，12英寸激光盘

14. 通过凹槽光反射来存储0/1

15. 包括光盘CD和DVD

16. 机械硬盘（电磁存储）

17. 固态硬盘SSD（使用集成电路半导体存储），寻道速度为1/1000秒

18. 第一个RAM集成电路出现于1972

19. 文件系统（用于存储一整块文件）

20. 文件格式：按格式排列文件

21. 简单的文件格式列举

22. 文本文件（TXT）:

23. 用于文字数据

24. 使用ASCLL解码

25. 波形文件（WAV）：

26. 用于存储音频数据

27. 文件的文件头用来保存元数据（文件数据的数据）

28. 码率

29. 单声道、立体声道

30. 元数据之后的数据为

31. 每秒捕获多次的声音振幅

32. 振幅越大、声压越大、数字越大

33. 每秒可达上千次

34. 位图（bmp）

35. 用来存图片数据

36. 文件的文件头存放元数据：图宽、图高

37. 后面存储颜色深度（24位）

38. 8位RED(0-255)

39. 8位GREEN(0-255)

40. 8位BLUE(0-255)

41. 文件系统

42. 平面文件系统

43. 文件连续存储在内存块内

44. 目录文件，记录其他文件的目录，包括:

45. 文件名+.+扩展名

46. 创建时间

47. 最后修改时间

48. 文件所有者

49. 读写权限

50. 文件起始位置

51. 块地址

52. 当文件增加数据时，出现的溢出该如何解决

53. 在每块数据中预留数据

54. 拆分文件，存入多个块中

55. 文件删除：

56. 当删除文件，不需要删源文件，只需要删除目录信息

57. 新文件可直接覆盖数据

58. 碎片

59. 当文件进行增删改查之后，文件数据隔开，且每块的顺序也被打乱

60. 解决方法：

61. 碎片整理：将数据来回移动，排列出正确顺序

62. 分层文件系统

63. 出现契机：内存容量的发展以及数据暴增，存在一个目录，查找麻烦

与平面文件系统的区别在于，在目录文件的文件信息中增加了是否为目录的标记

1. 用元数据分开文件和目录

2. 目录里还可以包括目录

3. 压缩(把数据占用空间尽可能压到最小，用更少的位表示数据)

4. 压缩方式

5. 无损压缩（基本采用两种方式：消除冗余和更紧凑的表示方式）

6. 行程编码

7. 给所有数据前都标上长度，多次重复的数据只保留一位即可

8. 字典编码：DFTBA

9. 用符号来表示数据

10. 用到哈夫曼树：

11. 1950年 大卫 哈夫曼 发明的高效编码方式

12. 通过列出数据出现频率，每轮列出两个最低频率，按频率排序

13. 例如 黑黄 出现一次 ，黑白 出现一次 ， 白黄 出现两次 黄黄出现四次

14. 按哈夫曼树排列

15. 最后压缩的结果为：字典加上数据对应符号

2. 有损压缩

3. 感知编码：依赖人类感知模型

4. 音频压缩：用不同精度编码不用频段

5. 删掉人类听不到的超声波等

6. 完整保留人类敏感的人声

7. 图片压缩：通过降低分辨率来压缩

8. 如使用8x8像素，将相似颜色统一成一个颜色

9. 经典格式：JPEG

10. 视频压缩：

11. 时间冗余：视频中不动的像素

12. 找出帧与帧之间的相似不定，用简单的效果来实现移动、旋转等效果

13. 经典格式：MPEG-4