计算机科学概论

参考文档：
计算机科学概论

（一）基础篇

1. 计算系统分层（洋葱）

• 信息层
• 硬件层
• 程序设计层
• 操作系统层
• 应用程序层
• 通信层

2. 计算硬件简史

• 第一代（1951-1959）：真空管，磁鼓，读卡机，磁带驱动器.
• 第二代（1959-1965）：晶体管，磁芯，磁盘，电路板.
• 第三代（1965-1971）：集成电路，终端（键盘，屏幕）
• 第四代（1971至今）：大规模集成化，PC，网络.

3. 计算软件简史

• 第一代：汇编语言，汇编器.
• 第二代：Fortran，Cobol，Lisp，编译器.
• 第三代：操作系统，装入器，连接器，SPSS.
• 第四代（1971-1989）：结构化程序设计（Pascal，Modula-2，C，C++），Unix系统，PC-DOS和MS-DOS系统，Macintosh机操作系统（引入鼠标概念和点击式图形界面）
• 第五代（1989至今）：微软崛起，面向对象程序设计（Java），万维网普及.

（二）信息层

1. 二进制计数系统

• 现代计算机中的数字都以二进制形式表示.
• 每个存储二进制数字的单元称为比特位（bit），每8个比特构成一个字节（byte），一个字（word）包含一个或多个字节.
• 二进制可与八进制和十六进制进行快速转换.
  • 给定2进制数字，从右至左，每3位组字是8进制，每4位组字是16进制.
  • 给定8进制或16进制数，将每一位按3位和4比特展开，即为对应的2进制数.
• 十进制转二进制（20.25）：20 = 2 * 10+0，10 = 2 * 5 +0，5 = 2 * 2+1，2 = 2 * 1+0，1 = 2 * 0+1，20 = (10100)2，0.25 * 2 ＝0.50，0.50 * 2 = 1.00，20.25 = (10100.01)2.
• 数据表示法
  • 计算机以数字形式表示信息（区别于模拟信号形式）.
  • 数字表示
    • 负整数以二进制补码形式存放，即将对应正整数的二进制每位取反后再加1.
    • 实数以浮点形式表示，包括符号位，尾数和指数（指示小数点位置），如 -120.01 = -12001 * 10 ^(-2).
  • 文本表示
    • 字符集：Unicode（16位）是对ASCII（7或8位）的扩展.
    • 文本压缩方式
      • 关键码编码（代替）
      • 行程长度编码（AAAAA = *A5）
      • Huffman编码（字符编码按频率变长）
  • 音频表示
    • 对音频信号进行周期性采样.
    • CD（激光唱片）表面有凹点，激光照射后反射强度不同，以此表示二进制数字，这是信号被数字化后的电压值，将此信号重现后发送给扬声器.
  • 图像表示
    • 颜色用RGB值表示（红绿蓝），每种成份取值在0-255之间.
    • 数字化一幅图像成一个点集，里面的点称为像素，每个像素由一种颜色构成，像素个数称为分辨率.
    • 图像表示法有位图（只保存像素）和矢量图（线段和几何形状），矢量图一般较小.
  • 视频表示
    视频被分割成了一系列静态图像（帧），可以根据连续帧之间的差别来压缩视频（时间压缩法），也可以通过删除一个帧中的冗余信息，将差别不大的像素聚集成块来压缩（空间压缩法）.

（三）硬件层

1. 门和电路

• 门是电信号执行基本运算的设备，接受一个或多个输入信号，生成一个输出信号，由晶体管实现；基本运算有与、或、非，表示法有Bool式、逻辑图和真值表.
• 电路是门的组合，分成组合电路和时序电路.
• 加法器：分为半加器和全加器（考虑进位输入）.
• 多路复用器：实现选择控制合成函数.
• CPU芯片是一种集成电路.

2. 计算部件

• 冯诺伊曼体系结构
  • 内存单元：每个存储单元都有唯一的物理地址.
  • 输入／输出单元
  • 算术逻辑单元（ALU）：ALU一般有少量存储单元（寄存器）.
  • 控制单元：掌管“读取－执行”周期，包含指令寄存器 IR(存放正在执行的指令)和程序计数器PC(存放下一条要执行的指令的地址). 控制单元和ALU合称为CPU.
• “读取－执行”周期
  • 读取下一条指令：控制单元访问程序计数器中的地址，复制内容，放入指令寄存器.
  • 译解指令：指令将被译解成控制信号(指令本身被逐字地嵌入电路，CPU中的电路逻辑将决定执行什么操作).
  • 获取数据（如果需要）：某些指令可能需要额外的内存访问.
  • 执行指令：控制单元把信号发给算术逻辑单元以执行处理.
• RAM和ROM(主存通常包含一些ROM和通用的RAM)
  • RAM是随机存储器，每个单元可被直接访问并改写，断电后不再保存.
  • ROM是只读存储器，内容永久不能更改，断电后仍然保存.
• 二级存储设备(在计算机不运行的时候保存数据)
  • 磁带：常用于备份磁盘上的数据.
  • 磁盘：使用电磁质材料制成的薄磁盘存储数据，每个磁盘被划分成磁道和扇区，每个扇区放一个信息块；分为硬盘和软盘；硬盘由几个连接在主轴上的磁盘片构成，每个磁盘片都有自己的读写头.
  • 光盘（CD/DVD）：CD上没有同心磁道，而只有一个从里到外盘旋的螺旋磁道.
  • 闪存：U盘和固态磁盘（SSD）都是闪存，可写入可擦除.
• 触摸屏
  • 电阻式：两个导电层，一个水平线，一个竖直线，上下层接触后电流流通，确定触摸屏幕的位置.
  • 电容式：玻璃屏幕上附加一个层压板，可将电流导向任何方向. 当屏幕被接触后，电流将流向手指或书写笔，通过比较电流强弱确定触摸位置.
  • 红外式
  • 表面声波式
• 嵌入式系统：是为完成小范围功能而专门设计的计算机，几乎所有含有数码显示的电子设备都使用了这一系统. 其集成在单个微型处理器芯片上，程序被存储在ROM中，大多用汇编语言来写，也有用C来编写.
• 并行计算结构
  • 并行计算形式
    • 比特级
    • 指令级
    • 数据级
    • 任务级
  • 并行硬件分类
    • 多核处理器
    • 超标量处理器
    • 对称多处理器
    • 大规模并行处理器

（四）程序设计层

1. 低级程序设计语言与伪代码

• 机器语言（可用Pep/8虚拟机模拟）：是一套计算机硬件能够识别并执行的指令，用二进制编写，指令固定在硬件中.
• 汇编语言：是一种使用辅助记忆码表示的指令，程序被翻译成等价的机器语言，而后在Pep/8模拟器上执行.
• 可以使用伪代码来叙述算法，算法设计中的两种常见策略是自我提问和推迟细节.

2. 问题求解与算法设计
3. 抽象数据类型与子程序
4. 面向对象设计与高级程序设计语言

（四）操作系统层

1. 操作系统（是系统软件，区别于应用软件）

• 计算机启动时载入ROM中存储的一小组系统指令，这些指令从硬盘中载入大部分系统软件，最终将载入操作系统软件的所有关键元素，执行启动程序，提供用户界面，系统准备就绪.
• 内存管理：所有程序在执行时与其要引用的数据都存储在主存中. 操作系统必须管理内存，以控制和监管把进程载入主存中的什么位置，任何内存管理技术必须定义联编逻辑地址（虚拟）和物理地址（真实）的方法. 分为单块内存管理法和分区法.
• 进程管理：操作系统管理进程的生命状态（创建－准备完毕－运行－等待－终止）；PCB（进程控制块）存储了每个进程的必要信息.
• CPU调度：要确定下一个使用CPU的进程. 算法有先到先服务（顺序使用），最短作业优先（按时间最短），轮询法（轮流使用）.

2. 文件系统和目录

（五）应用系统层

1. 信息系统
2. 人工智能
3. 模拟，图形学，游戏和其他

（六）通信层

1. 网络
2. 万维网
3. 计算机安全

（七）总结：计算的限制