计算机科学概论（第10版） 阅读笔记

第0章 绪论

• 概念的认识：

  算法（algorithm）：就是一系列的步骤，规定如何完成一项任务。
  程序（program）：某一个算法的表示称作一个程序。
  程序设计（programming）：采用与机器兼容的形式进行编码并将其输入到机器中的过程。
  软件（software）：程序及其所表示的算法总称。
  硬件（hardware）：机器设备本身。
  

• 计算机科学：

   早期的计算机所能处理的算法复杂性低，随着局限性的消除，机器已经可以执行越来越艰巨复杂的任务。人们企图用算法表达这些任务的构成，但却感到思维能力上的不足，于是越来越多的工作上转向算法和程序设计过程的研究，在这种情况下，数学家的理论研究开始有回报，由此孕育出了被称作计算机科学的这门学科。
  

第1章 数据存储

• 布尔运算：真 / 假的运算。
• 3中基本布尔运算：AND（与）、OR（或）、XOR（异或）。
• 特殊的布尔运算：NOT（非），它只有一个输入，输出就是输入值的相反值。

• 门：门（gate）指的是一种设备，给出一种布尔运算输入值时，可以得出该布尔运算的输出值。

  门：可以通过很多种技术制造出来，如，齿轮、继电器和光学设备。门经常是通过微电子电路来实现的。
  

• 触发器：触发器（flip-flop）是一个可以产生0或1输出值的电路，它的值会一直保持不变，除非其他电路过来的临时脉冲使其改变成另一个值。（输出值是在外界的刺激下，两个值之间相互转换的）

• 记录信息：触发器可以被设置为具有0或1的输出值，其他电路可以通过发送脉冲到触发器的输入端调整这个值，还有其他一些电路可以用触发器的输出来对存储值进行相应，这样，许多触发器被构成非常小的电子电路，可以用在计算机内作为记录信息的一种方法，这些信息被编码成0和1的模式。

• 超大规集成：（Very Large-scale integration）VLSI技术支持几千个电子元件被构造在一个晶片（芯片chip）上，在某些情况下，VLSI被用来在单块芯片上创建整个计算机系统。

• 流：一些位组成位串，一个长的位串被称为流（stream）。

• 主存储器：每一个电路能够存储单独的一个位，这样的位存储就叫做主存储器（main memory）。

• 存储单元：典型的存储单元容量是8位。（一个8位的串称为一个字节byte）

• 存储单元结构：通常假设存储单元的位是排成一行的，该行的左端称为高位端，右端称为低位端，高位端最左以为称为最高有效位。

• 存储地址： 为了区分计算机主存储器中各个存储单元，每一个存储单元都有一个唯一的“名字”，称为地址（address）；

• 随机存取器：主存储器有单个的、可编址的存储单元组成，所以这些存储单元可以根据需要独立存取。为了反映 用任何顺序存储单元的能力，计算机的主存储器常被称为随机存储区（random access memory RAM）。

• 动态存储器：许多技术可以存储快速消散的微小电子，因此，这些设备可以属性电路，可以在1s内反复补充电子很多次，这种就称为动态存储器（dynamic memory DRAM）。

• 存储器容量：使用2的幂来设计存储单元，会很方便，因此早期的计算机存储器的大小通常以1024（2^10）个存储单元为度量单位。

  因为接近于1000，所以术语千字节（kilobyte  KB）用来表示1024字节。
  千字节      KB(kilo byte)
  兆字节      MB(mega byte)
  吉字节      GB(giga byte)
  

• 海量存储器：也就是所谓的附加存储设备，包括磁盘，CD盘，DVD盘，磁带，闪存驱动器。

  与主存储器的区别：
  优点：
      稳定、容量大、价格低、可轻易从电脑上取下。
  缺点：
      需要机械运动，而主存储器都是电子器实现的，所以读写的速度相对慢。
  

• 磁盘存储：盘片表面有磁介质的涂层用以存储数据，读/写的磁头安装在盘片的上面或下面。一个磁盘存储系统包含若干个安装在同一根轴上的盘片，中间留有空隙，一遍磁头的读写操作。

• 扇区：因为一个道可以包含的数据通常比我们每一次要处理的数据多，所以每个道划分若干个小弧区，称为扇区（sector）。

  磁盘上所有的扇区包含相同数目的二进制位。
  每一个到分为相同数目的扇区。
  外边缘的道位的密度要高于内边缘道的位的密度。
  但是外边缘道的数量要远多于内边缘的道数量。（所以外边缘的利用率高）
  

• 硬盘系统： 小的磁盘容量仅有几MB，但大的可达到几GB，它可能有5~10个刚硬的盘片。由于这种磁盘系统所用的盘片是刚硬的，所以称为硬盘系统。

  硬盘每分钟几千转，软盘每分钟固定300转。
  为了使盘片更快的旋转，硬盘系统的磁头不直接接触盘片的表面。
  而是“浮”在上面，之间的空隙非常小，以至于一颗灰尘都会阻塞。
  造成破坏的现象称为滑道，因此硬盘系统出厂前已经被密封在盒子里。
  

• 磁盘性能评估：

  ①：寻道时间(seek time)：磁头从一个道移动到另一个道的时间。
  ②：旋转延迟(rotation delay)：磁头准备完毕，盘片需要旋转到指定数据的扇区，所需的时间。
  ③：存取时间(access time)：也就是寻道时间和等待时间之和。
  ④：传输速率(transfer rate)：读写的速率，这个速率受，内/外边缘的影响。
  

• 磁带：磁带的一个主要缺点是卷轴之间移动的带子很长，比如从开头一下跳到结尾，可能需要很长时间，而磁盘的仅仅调整磁头位置，旋转盘片到指定扇区即可。

• 光盘：光学技术，由涂着保护层的反射材料制成。通过在反射层上创建偏差的方法在光盘上面记录信息。激光束通过监视CD快速旋转时反射层的不规则反射偏差来读取信息。（Compact CD）。

• 闪存驱动器：用电子信号将二进制直接送到存储介质中，该介质中，电子信息号使得二氧化硅的微小晶格截获电子，从而转换微电子电路的性质。因为可以保持截获很多年，所以闪存技术适合存储脱机数据。

  优点：
      ①：不需要像磁学光学，那样通过物理运动来存储读取信息。
      ②：适合存储脱机数据。
      ③：存取速度快。
      ④：对物理震动不敏感，他在便携应用中的潜力是诱人的。
  缺点：
      ①：反复的擦写会逐渐损坏二氧化硅的晶格，不适合主存储器应用。
      ②：当涉及真正长期应用时，它们不如光学盘片可靠。
  

• 文件：海量存储系统中的信息一般被分为组为较大的单元，称为文件。

• 缓冲区：缓冲器通常是用于一个设备向另一个设备传输的过程中临时存储数据的区域。

• 用位模式表示信息：

• 文本的表示：通常由一种代码表示，每一个不同的符号均赋予其相应的唯一的位模式。

  ASCII码表，Unicode 码表
  

• 数值的表示：当信息只有数值时，如果还用编码形式去表示那就有点浪费，比如表示 37的话，就需要使用 16个二进制位（两个字节），而且以这种方式存储，用两个字节的16个二进制位存储的最大数是99。所以这个时候使用 二进制计数法。16个二进制位可以存储0~65535范围内的任何一个整数。

• 图像的表示：图像表示为一组点，每一个点成为一个像素（pixel），每个像素的显示被编码，整个图像就表示成这些已编码像素的集合，这些集合被称为位图（bitmap）。

  黑白照片：很长的位串表示每一行像素，每一位的取值0/1表示像素黑/白。
  黑白照片(精致)：每个像素用一组位(通常是8个)表示，可以表示出阴影。
  彩色图像：
                RGB编码：每个像素表示3中颜色成分(红绿蓝)，一个字节通常用来表示每一个颜色成分的亮度。一个像素占3个字节。例如 # 2AF 
  

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：

• ****：