2 计算机科学导论笔记要点

计算机科学导论1绪论图灵模型是一个可编程的数据处理器，在图灵模型中，输出数据依赖于两方面因素的结合作用：输入数据和程序。通用图灵机是对现代计算机的首次描述，该机器只要提供了了合适的程序就能做任何运算。基于冯・诺依曼模型建造的计算机分为4个子系统：存储器、算术运算单元(ALU)、控制单元和输入/输出单元。存储器用来存储数据和程序；算术运算单元进行计算和逻辑运算；输入/输出单元负责从计算机外部接收数据和程序，并把计算机的处理结果输出到计算机外部，控制单元是对其他子系统进行控制操作。冯・诺依曼模型中的程序和指令在计算机中都以二进制比特存储，在计算机中，指令按顺序执行。计算机由3大部分组成：计算机硬件、数据和计算机软件。硬件基于冯・诺依曼模型，且包含四部分。数据以0/1比特进行存储。图灵和冯・诺依曼模型的主要特征是程序的概念。程序被存储在计算机的存储器中，且必须是有序的指令集。指令集的作用实现重用。算法是按步骤解决问题的办法，计算机语言可以提高编程的效率，软件工程是指结构化程序的设计和编写，它不仅包括要完成某一任务的应用程序，还包括程序设计要严格遵循的原理和规则。而操作系统的诞生，是有一系列指令对所有程序来说是公用的，因此它是程序访问计算机部分提供方便的一种管理程序。2数字系统在将十进制数转换到其他底的数值时，分为两部分，整数部分是进行连除，余数作为本位的数值，商进行下一步计算；小数部分是进行连乘，整数值作为本位的数值，小数值进行下一步计算。3数据存储数据类型分为5种：数字、文本、音频、图像和视频。所有的数据类型都转换为称作位模式的统一表现形式。数字在存储到计算机内存中之前被转换成二进制系统。有多种方法来处理符号。有两种方法来处理小数点：定点和浮点。整数可以被当作小数点位置固定的数字。无符号整数是永远不会为负的整数。存储有符号整数的方法之一是符号加绝对值格式。这种格式中，最左边用于显示符号且其余位定义绝对值。符号和绝对值互相分开。几乎所有的计算机都使用*二进制补码表示法*来存储位于n位存储单元中的有符号整数。在该方法中，无符号整数有有效范围被分为两个相等的子范围。每一个子范围用来表示非负整数，每二个子范围用来表示负整数。在二进制补码表示法中，最左边决定整数的符号。但符号和绝对值互相分开。实数是带有整数部分和小数部分的数字。实数使用浮点表示法存储在计算机中。在浮点表示法中数字由3部分组成：符号、位移量和定点数。文本的片断是用来表示该语言中某个意思的一系列符号。我们可用位模式来表示每一个符号。不同的位模式集合被设计用于表示文本符号。硬件和软件制造商联合进来共同设计了一种名为Unicode的代码，这种代码使用32位表示一个符号。总督表示声音或音乐。音频是模拟数据，我们不能够在一段时间记录无限数量的值，我们只能记录一些样本。样本数依赖于模拟信号中变化的最大数量。从每个样本测量得到的值是真实的数字。量化指的是将样本的值截取为最接近的整数值的一种过程。存储在计算机中的图像使用两种不同的技术：光栅图或适量图。当我们需要存储模拟图像（如照片）时，就用到了光栅图。图像被扫描（采样）然后存储像素。用矢量图方法，图像被分解成几何图形的组合，诸如线段、矩形或圆形。每个几何形状由数学公式表达。视频是图像（称为帧）在时间上的表示。一部电影就是一系列的帧逐个播放而形成运动的图像。换言之，视频是随空间（单个图像）和时间（一系列图像）变化的信息表现。需要注意的地方是：符号加绝对值的表示方法有两个0，分别是+0和-0，而二进制补码的表示法只有一个0。因此范围也不一样。科学户数法中的规范化表示存储该数的3部分信息：符号、指数和尾数。小数点左边的1并没有存储，它们是隐含的。尾数是带符号的小数部分，像以符号加绝对值表示法存储的整数那样对待。在余码系统中，正的和负的都以无符号数存储，将正整数添加到每个数字中，，统一按偏移量把数向右移。在IEEE标准中，单精度数用32位来存储，符号1位、指数8位（偏移量为127）、尾数为23位，也称为余127码。双精度数彩共64位来存储，符号1位、指数11位（偏移量为1023）、尾数使用52位，也称为余1023码。图像的表示中对像素的编码使用的是RGB数，共24位，称为真彩色，每个8位表示0~256之间的一个数；除了真彩色之外，另一种方法是用索引色，通常只有256个索引，只用8位来存储同样的像素。JPEG格式使用的是真彩色模式，但压缩了图像，gif格式使用的是索引色模式。4数据运算数据运算分成三大类：逻辑运算、移位运算和算术运算。NOT运算符的唯一应用是求反，AND运算符的一个应用是对指定位进行置位(置0)，OR运算符的一个应用是对指定位置位(置1)，XOR运算符可以对指定位进行翻转。移位运算分为逻辑移位和算术移位，逻辑移位应用于不表示为符号数的模式，移动的空缺补0，其中循环移位会将移出的位补到空缺位。；算术移位假定模式为二进制补码的符号整数，向右移符号位保留，向左移符号位删除，空位补0。计算机中对整数的加减法使用的是二进制补码进行运算，减法转化为补码的加法进行运算，而用符号加绝对值的形式非常复杂，要考虑8种情况。浮点数的实数的加减法简化为小数点对齐后的以符号加绝对值柳芽存储的两整数的加减法。5计算机组成计算机的组成分成三大类（或子系统）：CPU、主存和输入/输出子系统。中央处理单元（CPU）执行数据上的操作，它有三部分：算术运算单元（ALU）、控制单元和一系列寄存器。算术逻辑单元（ALU）负责算术、移位和逻辑运算。寄存器是快速独立的存储设备，它可暂时地保留数据。控制单元控制CPU中每个部分的操作。主存是存储单元的集合。每一个单元有一个称为地址的标识符。数据被传输到内存或从内存取出是以称为字的二进制位组的方式。内存中唯一可标识的单元总数称为地址空间。有两种内存可用：随机存取存储器（RAM）和只读存储器（ROM）。输入输出（I/O）子系统的设备集合允许计算机与外界交流，存储程序和数据，即使在计算机已关机时也可以。输入/输出设备分成两大类：非存储设备和存储设备。非存储设备允许CPU/内存与外界通信；存储设备可以存储以后被检索的大量信息。存储设备被分成磁的和光的。计算机中三个子系统的连接起重要的作为，因为在这些子系统间需要进行信息的通信。CPU和内存通常被三个连接连在一起（每个称为总线）：数据总线、地址总线和控制总线。输入/输出设备通过输入/输出控制器或接口与总线相连，使用的控制器有多种，如今最常见的有：SCSI、火线和USB。有两种方法输入/输出设备的寻址：I/O独立寻址和I/O存储器映射寻址。在I/O独立寻址方法中，用来从内存读/写的指令完全不同于用来从输入/输出设备的读写指令。在I/O存储器映射寻址方法中，CPU把I/O控制器中的每个寄存器看成是内存中的字。如今，通用计算机使用称为程序的一组指令来处理数据。计算机执行程序，从输入数据创建输出数据。程序和数据都存储在内存中，CPU使用重复的机器周期一条接一条，从头到尾执行程序中的指令。简化的周期由三阶段组成：取指令、译码和执行。有三种使CPU和输入/输出设备同步的方法：程序控制输入/输出、中断控制输入/输出和直接存储器存取(DMA)。在最近向十年中，计算机的体系结构和组织经历了许多变化。计算机体系结构分成两大类：CISC（复杂指令集计算机）和RISC（精简指令集计算机）。现代计算机使用流水线技术来提高吞吐量。这个理念允许控制单元同时执行两个或三个阶段，这意味着下一条指令的处理可以在前一条结束前开始。计算机传统上有一个控制单元、一个算术逻辑单元和一个内存单元。并行处理通过使用多指令流处理多数据流来改善吞吐量。6计算机网络计算机网络是把数据从一个地方传送到另一个地方的硬件和软件的组合。网络的标准中最重要的是性能、可靠性和安全。网络中有种连接：点对点连接和多点连接。有四种常见的拓扑结构：网状型、星型、总线型和环型。其中最常用的是星型。网络可以分为三大类：局域网（LAN）、广域网（WAN）和城域网（MAN）。互联网是能够互相通信的两个或多个网络，因特网是所有网络的总和。控制因特网的协议集合称为TCP/IP协议族，由五层组成：应用层、传输层、网络层、数据链路层和物理层。路由器只使用下三层。应用层负责向用户提供服务。应用层的地址是特定于应用程序的。传输层负责整个消息的进程到进程的分发，意味着传输层的客户端与服务器间创建了一种逻辑连接。传输层中用端口号来标识进程。传输层的一个职责是多路复用和解多路复用。服务器使用众所周知的端口号，计算机使用传输层分配的临时端口号。另外，传输层负责拥塞控制、流量控制与差错控制。在TCP/IP协议族的发展历程中，有三种传输层协议：UDP、TCP和SCTP。UDP不提供属于单个消息的数据包间的逻辑连接，因此属于无连接协议。TCP支持传输层所有职责的协议，也被称为面向连接的协议。UDP速度最快，TCP速度最慢，不适合实时传输。SCTP适合于实时传输。网络层负责单个数据包从源主机到目的主机的发送，网络层有一个特殊的职责——路由选择。网络层的协议主要是IP协议，另外还有辅助协议如ICMP、IGMP。IP协议提供的是尽力而为服务，差错控制等功能由上层协议完成。数据链路层负责数据帧的节点到节点的发送。数据链路层还负责跳之间的差错控制和流量控制。它使用物理或MAC地址来标识节点。物理层完成在物理设备上的二进制比特的传输。TCP/IP层从上到下进行封装，每一层都会在上一层的数据基础上加上头或尾。因此实际上物理层传输的数据会远远多于应用层的数据。电子邮件（E-mail）使用的主要协议是简单邮件传输协议（STMP）。电子邮件使用的其他协议是POP和IMAP。文件传输协议（FTP）是因特网上最常见任务的标准机制，用于计算机的文件传输。FTP与其他客户/服务器应用的不同之处在于，它建立了两个连接：一个用于数据传输，另一个用于控制命令的交换。TELNET是允许用户访问远程计算机上任何应用程序的通用客户/服务器程序。换言之，它允许用户登录到远程的计算机上。登录后，用户可以使用远程计算机上可用的服务，并把结果传回本地计算机上。万维网（）是分页在全球并连在一起的信息存储库。为了使用，我们需要三个组件：浏览器、Web服务器和超文本传输协议（HTTP）。上的文档可以分成三大类：静态、动态和活动。静态文档是内容固定的文档，客户端只能得到文档的副本。动态文档是浏览器请求文档时由Web服务器创建的。通用网关接口（CGI）是创建和处理动态文档的技术。活动文档是运行在客户端的一个程序。7操作系统计算机系统由部分组成：硬件和软件。软件分成两大类：操作系统和应用程序。操作系统是计算机硬件和用户（程序和人）和人一个接口，它便利其他程序更加方便有效地运行，并能方便地对计算机硬件和软件资源进行访问。操作系统的两个主要设计目标是硬件的高效使用和资源的使用方便。操作系统的载入是一个自举过程，自举程序放在ROM中，开机之后载入ROM，然后把操作系统载入RAM内存。操作系统经历了一处长期的演化历史：批处理操作系统、分时操作系统、单用户操作系统、并行系统和分页式系统。现代操作系统至少有四个功能区域：内存管理器、进程管理器、设备管理器、文件管理器。操作系统还提供与用户交互的功能，称为图形界面或者命令解释程序。现代操作系统的第一职责是内存管理。内存必须由操作系统控制，以避免内存溢出。内存管理技术可以分为两类：单道程序和多道程序。在单道程序中，内存的大部分容量都为一个程序独享。在多道程序中，多个程序同时在内存中。现代操作系统的第二职责是进程管理。进行是运行的程序。进程管理使用调度器和队列来管理进程。进程管理涉及具有不同资源的不同进程间的同步问题。这可能潜在地造成死锁和饿死。死锁是指一个进程由于其他进程无限制地使用资源导致无法运行的情况。饿死是指一个进程由于资源分配限制太多而不能执行的情况。现代操作系统的第三职责是设备或I/O管理。在计算机系统中，输入/输出设备在数目和速度上都有限制。因为这些设备与CPU和内存相比，速度