第2章计算机科学的基本概念和基本知识.ppt

第二章第二章 计算机科学的基本概念和基本知识计算机科学的基本概念和基本知识2.1 2.1 计算模型与二进制计算模型与二进制 数学不等于计算，但数学确实起源于对计算的研究数学不等于计算，但数学确实起源于对计算的研究 数学、计算模型（计算方法、数学机器）、形式化与形数学、计算模型（计算方法、数学机器）、形式化与形式化方法式化方法 我们说，形式是事物的内容存在的外在方式、形状和结我们说，形式是事物的内容存在的外在方式、形状和结构的总和所谓形式化是将事物的内容与形式相分离，用事构的总和所谓形式化是将事物的内容与形式相分离，用事物的某种形式来表示事物形式化方法是在对事物描述形式物的某种形式来表示事物形式化方法是在对事物描述形式化的基础上，通过研究事物的形式变化规律来研究事物变化化的基础上，通过研究事物的形式变化规律来研究事物变化规律的全体方法的总称规律的全体方法的总称1.1.1 1.1.1 计算模型与图灵机计算模型与图灵机 所谓计算模型是刻划计算这一概念的一种抽象的形式系所谓计算模型是刻划计算这一概念的一种抽象的形式系统或数学系统，而算法是对计算过程步骤（或状态的一种刻统或数学系统，而算法是对计算过程步骤（或状态的一种刻2021/5/211划，是计算方法的一种能行实现方式。

在计算机科学中，我划，是计算方法的一种能行实现方式在计算机科学中，我们通常所说的计算模型，并不是指在其静态或动态数学描述们通常所说的计算模型，并不是指在其静态或动态数学描述基础上建立求解某一基础上建立求解某一( (类类) )问题计算方法的数学模型，而是指问题计算方法的数学模型，而是指具有状态转换特征，能够对所处理的对象的数据或信息进行具有状态转换特征，能够对所处理的对象的数据或信息进行表示、加工、变换、输出的数学机器由于观察计算的角度表示、加工、变换、输出的数学机器由于观察计算的角度不同，产生了各种不同的计算模型不同，产生了各种不同的计算模型 递归函数、递归函数、TuringTuring机等机等 (1) s(x)(1) s(x)＝＝x x＋＋1 1 （后继函数）（后继函数） (2) o(x) (2) o(x)＝＝0 0 （零函数）（零函数） (3) U (3) Uj j(n)(n)(x(x1 1，，x x2 2，，……，，x xn n) )＝＝x xj j （射影函数）（射影函数） 由由初初始始函函数数和和有有限限次次使使用用算算子子可可以以构构造造各各种种复复杂杂的的递递归归函数，或者可计算函数。

函数，或者可计算函数 图灵机的示意图图灵机的示意图2021/5/212控制器的命令可表示为：控制器的命令可表示为： （状态，符号）（状态，符号）→→（写符号，移动，状态）；（写符号，移动，状态）； ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬── ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬── │ │００││００││００││１１││１１││１１││００││１１││１１││１１│ │ ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴── ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴── ↑ ↑ ┌─┐ ┌─┐ │ │ │ │ ┌┘ └┐ ┌┘ └┐ │ │控制器控制器││ └───┘ └───┘ 一旦图灵机在运行中进入了一个状态，而且这个状态一旦图灵机在运行中进入了一个状态，而且这个状态是一个结束状态，那么，图灵机就停机，计算任务宣告完是一个结束状态，那么，图灵机就停机，计算任务宣告完成，此时带上的内容就是计算的输出结果。

成，此时带上的内容就是计算的输出结果2021/5/213 例例1 1 M M的的字字母母表表A A＝＝{0{0，，1 1，，b}b}，，b b表表示示空空格格状状态态集集Q Q＝＝{q{q1 1，，q q2 2，，q q3 3} }，其中，指定，其中，指定q q1 1是开始状态，是开始状态，q q3 3是终止状态是终止状态 M M的程序（控制器的命令）如下：的程序（控制器的命令）如下： q q1 1 0 1 R q 0 1 R q1 1；； q q1 1 1 0 R q 1 0 R q1 1；； q q1 1 b b R q b b R q2 2；； q q2 2 b b L q b b L q3 3；； q q2 2 0 0 H q 0 0 H q1 1；； q q2 2 1 1 H q 1 1 H q1 1；； 对图灵机的工作过程从不同的角度考察，可以给予不对图灵机的工作过程从不同的角度考察，可以给予不同的解释同的解释 第一第一，把图灵机看作识别器，即判断带子上最初的内，把图灵机看作识别器，即判断带子上最初的内2021/5/214容能否被图灵机所接受。

假定图灵机从左向右扫描完带子上容能否被图灵机所接受假定图灵机从左向右扫描完带子上的内容后停机则为接受，否则为不接受的内容后停机则为接受，否则为不接受 例例2 2 一台图灵机可以设计成识别下面的序列：一台图灵机可以设计成识别下面的序列： 1000110, 10011101, 010101011 1000110, 10011101, 010101011 第第二二，，把把图图灵灵机机看看作作生生成成器器，，对对给给定定的的输输入入集集合合，，考考察察输输出出集集合合，，并并研研究究输输入入输输出出集集合合性性质质之之间间的的关关系系，，这这就就研研究究了图灵机的生成能力了图灵机的生成能力 例例3 3 设设一一台台图图灵灵机机的的输输入入集集合合为为InIn＝＝{1{1n n0 0n n│n∈N}│n∈N}，，可可设设计计一一台台图图灵灵机机，，对对给给定定的的输输入入集集合合InIn，，得得到到输输出出集集合合OutOut＝＝{0{0n n1 1n n│n∈N}│n∈N}其中，N N是全体自然数的集合是全体自然数的集合 第第三三，，把把图图灵灵机机看看作作计计算算器器，，相相当当于于一一个个函函数数。

图图灵灵机机的输入是函数的自变量的值，图灵机的输出是函数的值的输入是函数的自变量的值，图灵机的输出是函数的值 例例4 4 图灵机可以计算下列函数：图灵机可以计算下列函数：2021/5/215 (1) s(x) (1) s(x)＝＝x x＋＋1 1；； (2) o(x) (2) o(x)＝＝0 0；； (3) A(0 (3) A(0，，y)y)＝＝y y＋＋1 1，， A(x A(x＋＋1 1，，0)0)＝＝A(xA(x，，1)1)，， A(x A(x＋＋1 1，，y y＋＋1)1)＝＝A(xA(x，，A(xA(x＋＋1 1，，y))y)) 第一和第二个函数读者不难从图灵机的定义出发感悟第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数，而第三个函数就比较复到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断顺便提一下，第三个函数叫做阿克曼杂，一时难于判断顺便提一下，第三个函数叫做阿克曼函数，它是阿克曼（函数，它是阿克曼（W.AckermannW.Ackermann）在研究原始递归函数和）在研究原始递归函数和递归函数的关系时给出的。

这个函数在计算理论中具有重递归函数的关系时给出的这个函数在计算理论中具有重要价值事实上，图灵机还可以计算形式上比第三个函数要价值事实上，图灵机还可以计算形式上比第三个函数更复杂的函数更复杂的函数 沿着这样一种思路，图灵机被证明具有很强的计算能沿着这样一种思路，图灵机被证明具有很强的计算能力，它与力，它与3030年代发展的递归函数论（一种能行可计算性理年代发展的递归函数论（一种能行可计算性理2021/5/216论）中一类最一般的可计算函数（部分递归函数或部分可论）中一类最一般的可计算函数（部分递归函数或部分可计算函数）在计算表达能力上是等价的然而，图灵机简计算函数）在计算表达能力上是等价的然而，图灵机简洁的构造和运行原理隐含了存储程序的原始思想，深刻地洁的构造和运行原理隐含了存储程序的原始思想，深刻地揭示了现代通用电子数字计算机最核心的内容揭示了现代通用电子数字计算机最核心的内容 图灵奖图灵奖 2.1.2 2.1.2 二进制二进制 也许是图灵机读写带上只出现两个符号启发了研究者，也许是图灵机读写带上只出现两个符号启发了研究者，在当时的技术条件下，从便于元器件的设计和制造考虑，在当时的技术条件下，从便于元器件的设计和制造考虑，计算机的研制很自然地选择了二进制。

后来的实践也证明计算机的研制很自然地选择了二进制后来的实践也证明了这种选择具有极大的优点了这种选择具有极大的优点 十进制数的表示十进制数的表示 例如，例如，1997.6301997.630这个数可以写成：这个数可以写成： 1997.630 1997.630＝＝1×101×103 3＋＋9×109×102 2＋＋9×109×101 1＋＋7×107×100 0 ＋＋6×106×10-1-1＋＋3×103×10-2-2＋＋0×100×10-3-32021/5/217 一般地，任何一个十进制数一般地，任何一个十进制数S S都可以表示为：都可以表示为： S S＝＝k kn nk kn-1n-1 … k … k0 0.… k.… k-m-m ＝＝k kn n×10×10n n＋＋k kn-1n-1×10×10n-1n-1＋＋……＋＋k k0 0×10×100 0＋＋……＋＋k k-m-m×10×10-m-m -m -m ＝＝ ∑ k ∑ ki i×10×10i i i i＝＝n n其中，其中，1010称为十进制的基数称为十进制的基数,k,ki i∈{0,1,2,3,4,5,6,7,8,9}∈{0,1,2,3,4,5,6,7,8,9}，，m m，，n n为正整数。

小数点的位置不言自明为正整数小数点的位置不言自明 二进制和十进制一样，是一种数制，它用于表示数的符二进制和十进制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值二进号（数字）由于在书写中的位置不同而具有不同的值二进制表示数的符号只有两个，即制表示数的符号只有两个，即0 0和和1 1，其数值与十进制中的，其数值与十进制中的0 0和和1 1相同此外，与十进制不同之处在于二进制数是逢二进一此外，与十进制不同之处在于二进制数是逢二进一2021/5/218 例如，十进制数与二进制数中的一些可作如下对应：例如，十进制数与二进制数中的一些可作如下对应： 十进制十进制 二进制二进制 (0) (0) (0) (0) (1) (1) (1) (1) (2) (10) (2) (10) (3) (11) (3) (11) (4) (100) (4) (100) (5) (101) (5) (101) … … … … … … (9) (1001) (9) (1001) (10) (1010) (10) (1010) … … … … … … 一般地，任何一个二进制数一般地，任何一个二进制数S S都可以表示为：都可以表示为：2021/5/219 S S＝＝k kn nk kn-1n-1 … k … k0 0. … k. … k-m-m ＝＝k kn n×2×2n n＋＋k kn-1n-1×2×2n-1n-1＋＋……＋＋k k0 0×2×20 0＋＋……＋＋k k-m-m×2×2-m-m   -m -m ＝＝ ∑ k ∑ ki i×2×2i i i i＝＝n  n  其中，其中，2 2称为二进制的基数，称为二进制的基数，k ki i∈{0,1},m,n∈{0,1},m,n为正整数。

为正整数 进一步，读者可从十进制数和二进制数的一般表示公进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，不同式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样之处只是基数不一样 二进制的运算规则比十进制的运算规则简单得多二进制的运算规则比十进制的运算规则简单得多只只要建立两种进制的数据之间的转换方法，那么，二进制将要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势具有更多的优势计算机的理论基础是逻辑和代数当二计算机的理论基础是逻辑和代数当二进制与同样只使用进制与同样只使用““真真””和和““假假””两个值的逻辑代数建立两个值的逻辑代数建立了联系后，这就为计算机的逻辑设计提供了便利的工具了联系后，这就为计算机的逻辑设计提供了便利的工具2021/5/2110 2.2 2.2 存储程序式计算机的基本结构与工作原理存储程序式计算机的基本结构与工作原理 图灵机的出现为现代计算机的发明提供了重要的思想图灵机的出现为现代计算机的发明提供了重要的思想图灵机的带子可以看成是计算机的存储设备，数据可以存图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根据需要擦去。

图灵机的命令相当于一组储在上面，也可以根据需要擦去图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，决定读事先设计、存储好了的程序，它们在控制器安排下，决定读写头的每一步操作这样一种数学机器，如果不考虑它的实写头的每一步操作这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，确实包含了存储程序的重要思想用性，就思想和原理而言，确实包含了存储程序的重要思想 程序与存储程序式计算机程序与存储程序式计算机 图灵机诞生后不到十年，在以冯图灵机诞生后不到十年，在以冯··诺依曼为代表的一批诺依曼为代表的一批科学家的努力下，现代存储程序式电子数字计算机的基本结科学家的努力下，现代存储程序式电子数字计算机的基本结构与工作原理被确定下来它主要由如下的五部分组成（见构与工作原理被确定下来它主要由如下的五部分组成（见P8P8图）：图）： 存储器，运算器，控制器，输入设备，输出设备存储器，运算器，控制器，输入设备，输出设备2021/5/2111 在学科的发展历程中，习惯上，人们将不带有软件系在学科的发展历程中，习惯上，人们将不带有软件系统的存储程序式电子数字计算机系统称为硬件裸机，将硬统的存储程序式电子数字计算机系统称为硬件裸机，将硬件裸机，参与构成硬件裸机的各类部件及其研究范畴统称件裸机，参与构成硬件裸机的各类部件及其研究范畴统称为硬件（方向）。

为硬件（方向） 2.3 2.3 数字逻辑与集成电路数字逻辑与集成电路 数数字字逻逻辑辑是是数数字字电电路路逻逻辑辑设设计计的的简简称称，，其其内内容容是是应应用用数数字字电电路路进进行行数数字字系系统统逻逻辑辑设设计计电电子子数数字字计计算算机机是是由由具具有有各各种种逻逻辑辑功功能能的的逻逻辑辑部部件件组组成成的的，，这这些些逻逻辑辑部部件件按按其其结结构构可可分分为为组组合合逻逻辑辑电电路路和和时时序序逻逻辑辑电电路路组组合合逻逻辑辑电电路路是是由由与与门门、、或或门门和和非非门门等等门门电电路路组组合合形形成成的的逻逻辑辑电电路路；；时时序序逻逻辑辑电电路路是是由由触触发发器器和和门门电电路路组组成成的的具具有有记记忆忆能能力力的的逻逻辑辑电电路路有有了了组组合合逻逻辑辑电电路路和和时时序序逻逻辑辑电电路路，，再再进进行行合合理理的的设设计计和和安安排排，，就就可可以以表表示示和和实实现现布布尔尔代代数数的的基基本本运运算算而而布尔代数只使用布尔代数只使用1 1（真）和（真）和0 0（假）两个数，这样，当二进（假）两个数，这样，当二进2021/5/2112制的加法、乘法等运算与布尔代数的运算建立了对应关系制的加法、乘法等运算与布尔代数的运算建立了对应关系后，就可以用逻辑部件来实现二进制数据的加法、乘法等后，就可以用逻辑部件来实现二进制数据的加法、乘法等各种运算。

各种运算 例例5 5 基本的基本的““与与””、、““或或””、、““非非””门电路 “ “与与””门电路一般有两个以上的输入和一个输出图门电路一般有两个以上的输入和一个输出图(a)(a)表示了一个表示了一个““与与””门电路，其输出门电路，其输出P P和输入和输入A A、、B B、、C C之间之间的逻辑关系可用下面的式子表示：的逻辑关系可用下面的式子表示： P P＝＝A·B·CA·B·C 电路设计中，用高电平信号表示电路设计中，用高电平信号表示1 1，低电平信号表示，低电平信号表示0 0，那么，，那么，““与与””门电路只有当输入门电路只有当输入A A、、B B、、C C同时为同时为1 1时，输时，输出出P P才为才为1 1，否则，，否则，P P为为0 0 “ “或或””门电路可以用图门电路可以用图(b)(b)表示一般地说，表示一般地说，““或或””门门电路是一种具有逻辑加法功能的电路，它有两个以上的输电路是一种具有逻辑加法功能的电路，它有两个以上的输入和入和2021/5/2113一个输出，其输出一个输出，其输出P P和输入和输入A A、、B B、、C C之间的逻辑关系可用下之间的逻辑关系可用下面的式子表示：面的式子表示： P P＝＝A A＋＋B B＋＋C C 在具体的电路设计中，如果我们用高电平信号表示在具体的电路设计中，如果我们用高电平信号表示1 1，，低电平信号表示低电平信号表示0 0，那么，，那么，““或或””门电路仅当输入门电路仅当输入A A、、B B、、C C中有一个为中有一个为1 1时，输出时，输出P P就为就为1 1，否则，，否则，P P为为0 0。

“ “非非””门电路可以用图门电路可以用图(c)(c)表示一般地说，表示一般地说，““非非””门门电路是一种具有逻辑取反功能的电路，它只有一个输入和电路是一种具有逻辑取反功能的电路，它只有一个输入和一个输出，其输出一个输出，其输出P P和输入和输入A A之间的逻辑关系可用下面的式之间的逻辑关系可用下面的式子表示：子表示： P P＝～＝～A A 在具体的电路设计中，如果我们用高电平信号表示在具体的电路设计中，如果我们用高电平信号表示1 1，，低电平信号表示低电平信号表示0 0，那么，，那么，““非非””门电路当输入门电路当输入A A为为0 0时，输时，输出出P P就为就为1 1，否则，当输入，否则，当输入A A为为1 1时，输出时，输出P P为为0 02021/5/2114 “与与”、、“或或”、、“非非”三种门电路示意图三种门电路示意图             P                               P                               P            ↑                             ↑                             ↑┌──┻──┓     ┌──┻──┓     ┌──┻──┓│         ·          │     │        ＋        │     │        ～        │└┳─┳─┳┛     └┳─┳─┳┛     └──┳──┛    ↑    ↑    ↑             ↑    ↑    ↑                     ↑     A     B     C               A     B     C                      A        （（a）） （（b）） （（c）） 将布尔代数和前面谈到的二进制联系起来，我们可以将布尔代数和前面谈到的二进制联系起来，我们可以看出，看出，““与与””、、““或或””、、““非非””门电路的作用与集合运算门电路的作用与集合运算““交交””、、““并并””、、““补补””是一致的。

一旦门电路中仅使用是一致的一旦门电路中仅使用两个电平信号两个电平信号0 0和和1 1，引入二进制及其运算规则，那么，用，引入二进制及其运算规则，那么，用门电路及其组门电路及其组2021/5/2115合就可以实现二进制的各种运算，而对复杂电路的计算，合就可以实现二进制的各种运算，而对复杂电路的计算，如电路的化简就有可能通过布尔代数的方法进行事实上如电路的化简就有可能通过布尔代数的方法进行事实上也正是如此也正是如此 由此可见，真正构成计算机科学基本的、核心的内容由此可见，真正构成计算机科学基本的、核心的内容是围绕计算而展开的大量带有规律性的知识，而不是具体是围绕计算而展开的大量带有规律性的知识，而不是具体的实现技术因为，在将来，我们完全可能发展一种能表的实现技术因为，在将来，我们完全可能发展一种能表示二进制数及其运算的新技术，它比今天的微电子技术精示二进制数及其运算的新技术，它比今天的微电子技术精度更高、生产价格更便宜如果真是那样，这种技术就可度更高、生产价格更便宜如果真是那样，这种技术就可能取代微电子技术在计算科学中的地位近年来科学研究能取代微电子技术在计算科学中的地位近年来科学研究的发展已显现出一些很有希望但尚不成熟的技术，如光电的发展已显现出一些很有希望但尚不成熟的技术，如光电子技术，金属表面处理技术等。

当然，程序技术在可预见子技术，金属表面处理技术等当然，程序技术在可预见的将来尚不太可能被别的技术所代替，原因是它与各种应的将来尚不太可能被别的技术所代替，原因是它与各种应用相联系，而且在形式上易于反映能行性这一本质的计算用相联系，而且在形式上易于反映能行性这一本质的计算特征，在表达形式上与通常算法的描述较为接近特征，在表达形式上与通常算法的描述较为接近, ,设计和设计和生产的成本也比较低，又不存在工业污染的问题，所以不生产的成本也比较低，又不存在工业污染的问题，所以不2021/5/2116易被取代因此，我们常说，从这个意义上讲，软件技术易被取代因此，我们常说，从这个意义上讲，软件技术比微电子技术对计算科学更重要一些比微电子技术对计算科学更重要一些 2.4 2.4 机器指令与汇编语言机器指令与汇编语言 用用计计算算机机求求解解一一个个问问题题，，必必须须事事先先编编制制好好程程序序程程序序是是由由指指令令组组成成的的每每一一台台计计算算机机都都设设计计规规定定了了一一组组指指令令集集合，称为机器指令系统合，称为机器指令系统 机器指令的格式一般分为两部分，如下所示：机器指令的格式一般分为两部分，如下所示： ┌───┬──────┐ ┌───┬──────┐ 指令格式：指令格式： │ │操作码操作码│ │ 地址部分地址部分 │ │ └───┴──────┘ └───┴──────┘其中，操作码指出运算的种类，如＋，－，其中，操作码指出运算的种类，如＋，－，××，，÷÷，跳转，跳转等，地址部分用来指示参与运算的数据保存在什么地方，等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器等。

操作码和地址部分如存储器的某个地址或某个寄存器等操作码和地址部分都用二进制代码表示都用二进制代码表示2021/5/2117 机器指令一般可根据其功能划分为以下几类：机器指令一般可根据其功能划分为以下几类：(1)(1)控制指令；控制指令；(2)(2)算术运算指令；算术运算指令；(3)(3)逻辑运算指令；逻辑运算指令；(4)(4)移位操作指令；移位操作指令；(5)(5)传送操作指令；传送操作指令；(6)(6)输入输入/ /输出指令输出指令 应当注意的是，不同的机器，其指令系统是不同的应当注意的是，不同的机器，其指令系统是不同的 指令系统的日渐增大虽然给用户的程序设计带来了方便，指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而使运算速度下降研究发现，开销的增大而使运算速度下降研究发现，指令系统存在着指令系统存在着改进的必要和可能改进的必要和可能 真正使研究人员对指令系统进行较大改进的原因是超大真正使研究人员对指令系统进行较大改进的原因是超大规模集成电路（规模集成电路（VLSIVLSI）技术的发展和采用微程序技术实现体）技术的发展和采用微程序技术实现体系结构设计思想的过程中硬件复杂性的不断增长带来的技术系结构设计思想的过程中硬件复杂性的不断增长带来的技术上的困难，使人们开始认识到在进行计算机系统设计时，应上的困难，使人们开始认识到在进行计算机系统设计时，应2021/5/2118公平对待硬件与软件的地位，使两者平衡负担整个系统的复公平对待硬件与软件的地位，使两者平衡负担整个系统的复杂性。

这一认识的转变直接导致了精简指令系统计算机杂性这一认识的转变直接导致了精简指令系统计算机（（RISCRISC）的诞生所谓）的诞生所谓RISCRISC是根据指令系统中各种指令应用是根据指令系统中各种指令应用的规律，将最常用的指令，以及一些控制较为简单的寄存器的规律，将最常用的指令，以及一些控制较为简单的寄存器－寄存器的操作与寄存器等一起直接做在－寄存器的操作与寄存器等一起直接做在VLSIVLSI芯片上，靠减芯片上，靠减少译码、存储、寻址方式和次数等开销而大大增加运算速度少译码、存储、寻址方式和次数等开销而大大增加运算速度实际上，实际上，RISCRISC主要是一种体系结构设计的思想，而不只是一主要是一种体系结构设计的思想，而不只是一种计算机产品种计算机产品RISCRISC技术由于极大地提高了计算机的运算速技术由于极大地提高了计算机的运算速度，因而它的问世被认为是计算机体系结构发展史上的一个度，因而它的问世被认为是计算机体系结构发展史上的一个里程碑 汇编语言汇编语言 汇编语言实际上是由一组汇编指令构成的语言每一条汇编语言实际上是由一组汇编指令构成的语言每一条汇编指令用某个西文字符串的缩写来表示其所代表的操作，汇编指令用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数据的二进制、八进制和十进制数字序列。

大用符号来代表数据的二进制、八进制和十进制数字序列大多数情况下，一条汇编指令对应一条机器指令，少数对应几多数情况下，一条汇编指令对应一条机器指令，少数对应几2021/5/2119条机器指令例如，下面是几条汇编指令的操作符，右边中条机器指令例如，下面是几条汇编指令的操作符，右边中文是名称文是名称 addadd 加法加法 idividiv 有符号除法有符号除法 mulmul 无符号乘法无符号乘法negneg 求补求补 xchgxchg 交换交换 testtest 逻辑比较逻辑比较 jmpjmp 无条件转移无条件转移 有了汇编语言，就得编写和设计汇编语言翻译程序（简有了汇编语言，就得编写和设计汇编语言翻译程序（简称汇编程序），专门负责把使用汇编语言书写的程序翻译成称汇编程序），专门负责把使用汇编语言书写的程序翻译成可直接执行的机器指令程序一般说来，汇编程序被看成是可直接执行的机器指令程序一般说来，汇编程序被看成是系统软件的一部分系统软件的一部分 当然，汇编语言在可读性和编写程序时仍然是不能令人当然，汇编语言在可读性和编写程序时仍然是不能令人满意的，这导致进一步发展了高级程序设计语言。

不过，由满意的，这导致进一步发展了高级程序设计语言不过，由于高级语言在使用时通常还是要通过编译程序逐步将高级语于高级语言在使用时通常还是要通过编译程序逐步将高级语言写的程序翻译成机器指令的程序，而这种翻译的结果往往言写的程序翻译成机器指令的程序，而这种翻译的结果往往不如机器指令或汇编语言写的程序效率高，所以，直到今天，不如机器指令或汇编语言写的程序效率高，所以，直到今天，不少工程师在系统软件的开发中还在使用机器指令和汇编语不少工程师在系统软件的开发中还在使用机器指令和汇编语言2021/5/2120 2.5 2.5 算法、过程与程序算法、过程与程序 求解一个给定的问题，不同的人常编写出不同的然而都求解一个给定的问题，不同的人常编写出不同的然而都是正确的程序，这是为什么呢？是正确的程序，这是为什么呢？ 这里存在两个层面的问题，一个是与计算方法密切相关这里存在两个层面的问题，一个是与计算方法密切相关的算法问题，另一个是程序设计的技术问题的算法问题，另一个是程序设计的技术问题 例例6 6 给定两个整数，求它们的最大公因数给定两个整数，求它们的最大公因数。

不失一般性，设有不全为不失一般性，设有不全为0 0的整数的整数x x、、y y，记，记gcd(xgcd(x，，y)y)为为它们的最大公因数，即同时能整除它们的最大公因数，即同时能整除x x、、y y的公因数中的最大者的公因数中的最大者显然，显然，gcd(xgcd(x，，y)y)可表示为可表示为 gcd(x gcd(x，，y)y)＝＝max{z│ z|xmax{z│ z|x，，z|y}z|y} 这个问题许多中学生都会解，最常见的有著名的欧几里这个问题许多中学生都会解，最常见的有著名的欧几里德辗转相除计算方法当然，还有许多种解法我们首先从德辗转相除计算方法当然，还有许多种解法我们首先从函数函数gcd(xgcd(x，，y)y)的性质出发来求解函数的性质出发来求解函数gcd(xgcd(x，，y)y)具有如下具有如下性质：性质： (1) gcd(a (1) gcd(a，，b)b)＝＝gcd(bgcd(b，，a)a)2021/5/2121 (2) gcd(a (2) gcd(a，，b)b)＝＝gcd(―agcd(―a，，b)b) (3) gcd(a (3) gcd(a，，0)0)＝＝|a||a| (4) gcd(a (4) gcd(a，，b)b)＝＝gcd(bgcd(b，，a mod b)a mod b)，，0≤a mod b0≤a mod b＜＜b b（欧几里德辗转相除计算方法）（欧几里德辗转相除计算方法） 根据以上性质，我们可以设计如下算法：根据以上性质，我们可以设计如下算法： 算法算法A A（计算函数（计算函数gcd(xgcd(x，，y)y)）） A A1 1. . 输入输入x x，，y y；；z z是辅助变量；是辅助变量； A A2 2. . 重复执行如下操作步骤：重复执行如下操作步骤： (1) (1) 若若y y＝＝0 0，则输出，则输出|x||x|，算法停止．，算法停止． (2) (2) 若若y≠0y≠0，则，则z←x mod yz←x mod y，，x←yx←y，，y←zy←z；； 有了计算函数有了计算函数gcd(xgcd(x，，y)y)的算法，用程序设计语言很容的算法，用程序设计语言很容易写出可在计算机上执行的程序。

算法易写出可在计算机上执行的程序算法A A的核心是利用了函的核心是利用了函数数gcd(xgcd(x，，y)y)的上述第四条性质倘若我们使用的不是第四的上述第四条性质倘若我们使用的不是第四2021/5/2122条性质，那么，算法就会发生改变条性质，那么，算法就会发生改变 不难想象，不同的求解方法将产生出不同的算法，不不难想象，不同的求解方法将产生出不同的算法，不同的算法将使我们设计出不同的程序，而决定这个程序功同的算法将使我们设计出不同的程序，而决定这个程序功能能的的本本质质是是计计算算方方法法及及其其算算法法一一般般地地说说，，对对不不同同计计算算方方法法过过程程的的抽抽象象描描述述就就产产生生了了相相应应的的不不同同算算法法，，但但同同一一算算法法由不同的人来写程序则完全可能设计出差别很大的程序由不同的人来写程序则完全可能设计出差别很大的程序 凭直觉想象给出的算法往往不是最好的算法凭直觉想象给出的算法往往不是最好的算法 例例7 7 用程序变换技术设计的计算函数用程序变换技术设计的计算函数gcd(x,y)gcd(x,y)的程序的程序 利利用用一一种种叫叫做做程程序序变变换换技技术术的的程程序序设设计计方方法法，，可可以以产产生计算函数生计算函数gcd(x,y)gcd(x,y)的如下递归过程性程序：的如下递归过程性程序： Procedure gcd(x Procedure gcd(x，，y:inty:int，，var z:int)var z:int)；； begin if x begin if x＝＝0 then z:0 then z:＝＝y y；； x≤y & x≠0 then gcd(x x≤y & x≠0 then gcd(x，，y y－－x x，，z)z)；；2021/5/2123 x x＞＞y & x≠0 then gcd(yy & x≠0 then gcd(y，，x x，，z)z) endif endif end end；； 显然，这个程序要一眼看出其功能是困难的。

实际上，显然，这个程序要一眼看出其功能是困难的实际上，这个反映辗转相除计算方法程序经过程序变换，形式上已这个反映辗转相除计算方法程序经过程序变换，形式上已发生了很大变化发生了很大变化 这两个例子进一步引发我们的一些思考：如何确保算这两个例子进一步引发我们的一些思考：如何确保算法和程序的正确性？既然求解同一个问题可以有不同的方法和程序的正确性？既然求解同一个问题可以有不同的方法，不同的算法，不同的程序，那么，怎么来判断算法和法，不同的算法，不同的程序，那么，怎么来判断算法和程序的好坏呢？程序变换是否改变算法呢？程序的好坏呢？程序变换是否改变算法呢？ 上面两个例子初步表明算法、程序与数学之间存在着上面两个例子初步表明算法、程序与数学之间存在着密切的联系要解决上面的问题，没有数学和计算科学理密切的联系要解决上面的问题，没有数学和计算科学理论的支持恐怕不行多年来大学计算机科学本科教学的实论的支持恐怕不行多年来大学计算机科学本科教学的实践已反复证明，实际情况正是如此践已反复证明，实际情况正是如此 在计算机科学研究中，事实上存在在计算机科学研究中，事实上存在一条规律：一条规律：一个问一个问2021/5/2124题，当它的描述及其求解方法或求解过程可以用构造性数学题，当它的描述及其求解方法或求解过程可以用构造性数学描述，而且该问题所涉及的论域为有穷，或虽为无穷但存在描述，而且该问题所涉及的论域为有穷，或虽为无穷但存在有穷表示时，那么，这个问题一定能用计算机来求解；有穷表示时，那么，这个问题一定能用计算机来求解；反过来，凡是能用计算机求解的问题，也一定能对该问题的反过来，凡是能用计算机求解的问题，也一定能对该问题的求解过程数学化，而且这种数学化是构造性的。

求解过程数学化，而且这种数学化是构造性的 当当一一个个问问题题的的求求解解获获得得了了计计算算方方法法和和算算法法时时，，并并不不等等于于万万事事大大吉吉了了在在许许多多情情况况下下，，找找到到求求解解一一个个问问题题的的算算法法只只是是走走完完了了第第一一步步至至于于现现实实是是否否可可以以计计算算，，则则取取决决于于算算法法的的存存在在性性和和计计算算的的复复杂杂性性，，即即取取决决于于该该问问题题是是否否存存在在求求解解算算法法，，算算法法所所需需要要的的时时间间和和空空间间在在数数量量级级上上能能否否被被接接受受要要注注意意的的是是，，有有的的问问题题虽虽然然存存在在求求解解问问题题的的计计算算方方法法，，但但是是，，不不存存在在算算法法原原因因有有两两种种可可能能：：一一是是计计算算方方法法可可能能不不是是构构造造性性的的；；二二是是虽虽为为构构造造性性的的，，但但计计算算方方法法不不能能保保证证计计算算过过程程在在任任何何初初值的情况下都能结束值的情况下都能结束2021/5/2125 算法复杂性算法复杂性 什么是算法的复杂性呢？什么是算法的复杂性呢？ 使用计算机计算各种问题，需要存储空间、计算时间。

使用计算机计算各种问题，需要存储空间、计算时间不同的算法计算所需要的时间和空间是不同的所谓算法不同的算法计算所需要的时间和空间是不同的所谓算法的复杂性就是对算法计算所需要的时间和空间的一种度量的复杂性就是对算法计算所需要的时间和空间的一种度量由于不同的计算机千差万别，运算速度和字长可以相差很大，由于不同的计算机千差万别，运算速度和字长可以相差很大，因此，不可能用算法在某一台计算机上计算所需要的实际的因此，不可能用算法在某一台计算机上计算所需要的实际的时间和存储单元（空间）去衡量这个算法的复杂性那么，时间和存储单元（空间）去衡量这个算法的复杂性那么，怎样才能准确刻划算法的计算复杂性呢？怎样才能准确刻划算法的计算复杂性呢？ 引入引入渐近增长率渐近增长率的概念来刻划算法的计算复杂性渐进的概念来刻划算法的计算复杂性渐进增长率用复杂性度量函数表示，该函数表示了算法随问题规增长率用复杂性度量函数表示，该函数表示了算法随问题规模大小变化引起的算法中抽象的基本运算执行的次数或存储模大小变化引起的算法中抽象的基本运算执行的次数或存储空间量的变化规律如某个计算问题当输入规模分别为空间量的变化规律。

如某个计算问题当输入规模分别为1 1，，2 2，，3 3，，……，，n n时，经分析算法中抽象的基本运算次数分别为时，经分析算法中抽象的基本运算次数分别为1 1，，4 4，，9 9，，……，，n n2 2，那么，就可以用函数，那么，就可以用函数n n2 2来刻划这个算法的来刻划这个算法的时间复杂性，并称这个算法的时间复杂性度量为时间复杂性，并称这个算法的时间复杂性度量为 (n(n2 2) )级2021/5/2126有了复杂性度量函数，一旦选定具体计算机，可以根据这台有了复杂性度量函数，一旦选定具体计算机，可以根据这台计算机对某个计算机对某个n n值的实际运算速度比较准确地估算出对其他值的实际运算速度比较准确地估算出对其他的的n n值完成计算所需要的时间于是，对各种算法的复杂值完成计算所需要的时间于是，对各种算法的复杂性进行分析的关键是要设法去找出这样的函数，它涉及到与性进行分析的关键是要设法去找出这样的函数，它涉及到与数学密切相关的算法的设计原理、思想和方法，算法分析是数学密切相关的算法的设计原理、思想和方法，算法分析是具有智力挑战性的研究课题具有智力挑战性的研究课题 证比求易算法证比求易算法（本书上的三个中国人算法）（本书上的三个中国人算法） 在算法计算复杂性的研究中，一个算法如果存在图灵机在算法计算复杂性的研究中，一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将这个算法归入可计算的多项式时间计算复杂性算法，就将这个算法归入P P类，如果存在非确定性图灵机可计算的多项式时间计算复杂类，如果存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入性算法，就将其归入NPNP类。

对大多数实际问题来说，找到一类对大多数实际问题来说，找到一个解可能很难，检验一个解常常比较容易，所以都属于个解可能很难，检验一个解常常比较容易，所以都属于NPNP类现在，计算科学研究中一个悬而未决的重要问题是：现在，计算科学研究中一个悬而未决的重要问题是： P P＝＝NPNP？2021/5/2127P P＝＝NPNP？？ 这个问题不仅具有理论上的价值，而且具有重大实这个问题不仅具有理论上的价值，而且具有重大实用价值因为到目前为止，已经发现了一批可计算但有相当用价值因为到目前为止，已经发现了一批可计算但有相当难度的问题是属于难度的问题是属于NPNP类的，并且常通过证明一个问题与已知类的，并且常通过证明一个问题与已知属于属于NPNP类中的某个问题（如可满足性问题，简称类中的某个问题（如可满足性问题，简称SATSAT问题）问题）等价将其归入等价将其归入NPNP类不过，该问题是否属于类不过，该问题是否属于 P P类，即是否能类，即是否能找到多项式时间计算复杂性算法求解该问题，或证明该问题找到多项式时间计算复杂性算法求解该问题，或证明该问题不存在多项式时间计算复杂性算法求解，至今尚未解决。

现不存在多项式时间计算复杂性算法求解，至今尚未解决现在，很多人都猜测秋碧贞楠的看法是对的：求解一个问题总在，很多人都猜测秋碧贞楠的看法是对的：求解一个问题总是比验证一个问题的解要难，用公式表示也就是是比验证一个问题的解要难，用公式表示也就是P≠NPP≠NP7070年代初，库克（年代初，库克（S. A. CookS. A. Cook）和卡尔普（）和卡尔普（R. M. KarpR. M. Karp）指出，）指出，NPNP类中有一小类问题具有以下性质：迄今为止，这些问题多类中有一小类问题具有以下性质：迄今为止，这些问题多数经过深思熟虑还没有人找到多项式时间计算复杂性算法数经过深思熟虑还没有人找到多项式时间计算复杂性算法但是，一旦其中的一个问题找到了多项式时间计算复杂性算但是，一旦其中的一个问题找到了多项式时间计算复杂性算法，这个类中的其它问题也能找到多项式时间计算复杂性算法，这个类中的其它问题也能找到多项式时间计算复杂性算法，那么就可以断定法，那么就可以断定P P＝＝NPNP换句话说，如果确属这个换句话说，如果确属这个2021/5/2128类中的某个问题被证明不存在多项式时间计算复杂性算法，类中的某个问题被证明不存在多项式时间计算复杂性算法，那么，就等于证明了那么，就等于证明了P≠NPP≠NP。

通常，将这类问题称为通常，将这类问题称为NPNP完全完全性问题正正是是由由于于这这些些原原因因，，算算法法被被认认为为是是计计算算科科学学的的核核心心问问题题之之一 定定义义1 1（（算算法法）） 给给定定问问题题和和设设备备，，一一个个算算法法是是用用该该设设备备可可理理解解的的语语言言表表示示的的，，解解决决这这个个问问题题的的一一种种方方法法的的精精确确刻刻划特别，算法具有下列特征属性：划特别，算法具有下列特征属性： (1) (1) 算算法法应应用用于于一一个个具具体体的的输输入入集集合合或或问问题题描描述述将将在在有有穷穷步动作序列之后得到结果；步动作序列之后得到结果； (2) (2) 该序列有一个唯一的初始动作；该序列有一个唯一的初始动作； (3) (3) 该序列中的每一个动作有一个唯一的后继动作；该序列中的每一个动作有一个唯一的后继动作； (4) (4) 该该序序列列终终止止时时或或者者得得到到这这个个问问题题的的解解，，或或者者因因该该问问题题不可解而获得不可解说明不可解而获得不可解说明2021/5/2129 定义定义1 1是一种百科全书式的定义，在专业上似乎不够严是一种百科全书式的定义，在专业上似乎不够严谨，而且也不适应于不确定性算法和分布式、并行算法。

谨，而且也不适应于不确定性算法和分布式、并行算法 Knuth Knuth的算法定义的算法定义 定义定义2 2（（KnuthKnuth算法定义）算法定义） 一个算法，就是一个有穷规则一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的的集合，其中之规则确定了一个解决某一特定类型问题的运算序列此外，算法的规则序列须满足如下五个重要条运算序列此外，算法的规则序列须满足如下五个重要条件（特性）：件（特性）： (1) (1) 有穷性算法必须总是在执行有穷步之后结束；有穷性算法必须总是在执行有穷步之后结束； (2) (2) 确定性算法的每一个步骤必须是确切地定义的；确定性算法的每一个步骤必须是确切地定义的； (3) (3) 输入算法有零个或多个输入；输入算法有零个或多个输入； (4) (4) 输出算法有一个或多个输出，即与输入有某个特定输出算法有一个或多个输出，即与输入有某个特定关系的量；关系的量； (5) (5) 能行性算法中有待执行的运算和操作必须是相当基能行性算法中有待执行的运算和操作必须是相当基本的，即是说，本的，即是说， 它们原则上都是能够精确地进行的，而且它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。

用笔和纸做有穷次就可以完成2021/5/2130 有穷性和能行性是算法最重要的两个特征对有些问题有穷性和能行性是算法最重要的两个特征对有些问题来说，如果我们给出了一个类似于算法的有穷运算序列，而来说，如果我们给出了一个类似于算法的有穷运算序列，而它对某些输入可能不停机，那么，我们就称这样的运算它对某些输入可能不停机，那么，我们就称这样的运算序列为一个过程算法和过程都满足能行性和确定性，唯一序列为一个过程算法和过程都满足能行性和确定性，唯一的本质区别是算法的执行必须终止，而过程则不然，它可以的本质区别是算法的执行必须终止，而过程则不然，它可以永不停止需要指出的是，高级程序设计语言中也有过程的永不停止需要指出的是，高级程序设计语言中也有过程的概念，但与这里所讲的过程不同，那里实际上指的是一种子概念，但与这里所讲的过程不同，那里实际上指的是一种子程序 1960 1960年代，克努特把计算机科学定义为是研究算法的学年代，克努特把计算机科学定义为是研究算法的学问不过，由于问不过，由于19801980年代计算机科学中并行与分布式算法的年代计算机科学中并行与分布式算法的发展与计算机体系结构密切相关，以及学科研究中发展多种发展与计算机体系结构密切相关，以及学科研究中发展多种不同层面计算模型的需要，包括发展非图灵－冯不同层面计算模型的需要，包括发展非图灵－冯··诺依曼型诺依曼型计算模型，使许多人认识到研究计算模型与体系结构具有与计算模型，使许多人认识到研究计算模型与体系结构具有与研究算法同等的重要性，从而使今天学术界对计算科学下的研究算法同等的重要性，从而使今天学术界对计算科学下的定义变得比过去更为准确。

见第二章）定义变得比过去更为准确见第二章）2021/5/2131 一般地说，对任何一个问题，如果有了解决该问题的算一般地说，对任何一个问题，如果有了解决该问题的算法，就可以编制相应的程序所谓法，就可以编制相应的程序所谓程序，是一种事先编制好程序，是一种事先编制好了具有特殊功能的指令序列了具有特殊功能的指令序列其中，指令既可以是机器指其中，指令既可以是机器指令，汇编语言指令，也可以是高级语言的语句命令，甚至还令，汇编语言指令，也可以是高级语言的语句命令，甚至还可以是用自然语言描述的运算、操作命令当然，用自然语可以是用自然语言描述的运算、操作命令当然，用自然语言编写程序是计算机科学进入非常高级的阶段的标志之一，言编写程序是计算机科学进入非常高级的阶段的标志之一，有赖于自然语言理解取得重大突破，目前看来还是一个十分有赖于自然语言理解取得重大突破，目前看来还是一个十分遥远的设想遥远的设想 程序这一概念的出现，得益于人类长期的生活实践，程程序这一概念的出现，得益于人类长期的生活实践，程序设计也不神秘但是，程序设计是一种高智力的活动，不序设计也不神秘但是，程序设计是一种高智力的活动，不同的人对同一事物的处理可以设计出完全不同的程序。

我们同的人对同一事物的处理可以设计出完全不同的程序我们每一个人的生活经历已经告诉自己，知识和阅历（经验）是每一个人的生活经历已经告诉自己，知识和阅历（经验）是处事（设计程序）的基础正因为如此，在计算机发展的早处事（设计程序）的基础正因为如此，在计算机发展的早期，程序设计被认为是一个与个人经历、思想和技艺相联系期，程序设计被认为是一个与个人经历、思想和技艺相联系的一种技艺和技巧后来，软件开发规模的扩大和开发方式的一种技艺和技巧后来，软件开发规模的扩大和开发方式2021/5/2132的变化，程序设计才开始被当成一门科学来对待的变化，程序设计才开始被当成一门科学来对待 既然程序如此重要，又为人类经常使用，就有必要对程既然程序如此重要，又为人类经常使用，就有必要对程序及其运行的规律进行深入的研究于是，对程序各种性质序及其运行的规律进行深入的研究于是，对程序各种性质如程序的结构、程序的正确性、程序的运行效率等的研究产如程序的结构、程序的正确性、程序的运行效率等的研究产生了计算机科学十分重要的一个方向生了计算机科学十分重要的一个方向────程序理论程序理论 有一种程序的定义，用公式给出：有一种程序的定义，用公式给出： 程序＝数据结构＋算法；程序＝数据结构＋算法； 定义初看起来有新意，它从程序的特征入手，高度抽象定义初看起来有新意，它从程序的特征入手，高度抽象和概括。

然而，仅有学术上的辅助参考价值，不能作为科学和概括然而，仅有学术上的辅助参考价值，不能作为科学的定义因为，按照定义，一旦数据结构和算法的定义被确的定义因为，按照定义，一旦数据结构和算法的定义被确定下来，程序的概念应该被随之确定，而实际上，程序的概定下来，程序的概念应该被随之确定，而实际上，程序的概念比数据结构加算法的涵义更广考虑到我们前面给出的算念比数据结构加算法的涵义更广考虑到我们前面给出的算法定义都明确要求满足终止性的属性，而程序可以不停机，法定义都明确要求满足终止性的属性，而程序可以不停机，甚至采用非常高级的程序设计语言设计的程序可以没有任何甚至采用非常高级的程序设计语言设计的程序可以没有任何2021/5/2133数据结构，有的程序中看不到算法（如数据结构，有的程序中看不到算法（如PrologProlog程序中一些程序中一些推理计算的过程）所以，我们还是只取前一种程序的定推理计算的过程）所以，我们还是只取前一种程序的定义更合适一些义更合适一些 2.6 2.6 高级语言与程序设计技术和方法高级语言与程序设计技术和方法 所谓高级程序设计语言（简称高级语言）是指用于描所谓高级程序设计语言（简称高级语言）是指用于描述计算机程序的类自然语言。

这种语言只是自然语言的一述计算机程序的类自然语言这种语言只是自然语言的一个很小的子集，在语法结构上比较简单而且规范，在语义个很小的子集，在语法结构上比较简单而且规范，在语义上较少二义性，能够以比较准确、易读的形式描述各种计上较少二义性，能够以比较准确、易读的形式描述各种计算机程序例如，人们常见的算机程序例如，人们常见的FortranFortran语言、语言、PascalPascal语言、语言、C C语言，语言，LISPLISP语言，语言，AdaAda语言，语言，PrologProlog语言，等等语言，等等 高级程序设计语言是程序设计发展的产物高级程序设计语言是程序设计发展的产物  19501950年代年代: Fortran: Fortran语言、语言、BasicBasic、、AlgolAlgol；； 19601960年代：年代：PL/1PL/1、、APLAPL、、COBOLCOBOL、、SNOBOLSNOBOL、、Algol-68Algol-68、、 Pascal Pascal、、SIMULASIMULA、、LISPLISP、、C C、、 19701970年代年代: Prolog: Prolog、、SmalltalkSmalltalk、、AdaAda、、XYZXYZ、、BetaBeta、、 2021/5/2134 随着计算机应用领域的不断拓展，针对各个应用领域的随着计算机应用领域的不断拓展，针对各个应用领域的不同特点和程序设计的经验，科研人员设计和发展了一批高不同特点和程序设计的经验，科研人员设计和发展了一批高级程序设计语言。

级程序设计语言 对于一个已经有了计算该问题算法的待解问题，不同的对于一个已经有了计算该问题算法的待解问题，不同的人根据同一算法可能编出完全不同然而都是正确的程序这人根据同一算法可能编出完全不同然而都是正确的程序这种不同除了程序的书写形式有区别外，重要的是这些程序的种不同除了程序的书写形式有区别外，重要的是这些程序的结构反映在程序设计的构思和易读性方面有差别，程序运行结构反映在程序设计的构思和易读性方面有差别，程序运行的效率（主要指速度）不一样，有时相去甚远这是为什么的效率（主要指速度）不一样，有时相去甚远这是为什么呢？呢？ 程序设计语言是一门科学程序设计语言是一门科学 对程序结构本质的深入研究促进了对程序质量的认识对程序结构本质的深入研究促进了对程序质量的认识 开发程序的效率和质量取决于程序设计方法和技术开发程序的效率和质量取决于程序设计方法和技术 多年的研究发展了许多程序设计方法和技术如自顶向多年的研究发展了许多程序设计方法和技术如自顶向下逐步求精的程序设计方法、自底向上的程序设计方法、程下逐步求精的程序设计方法、自底向上的程序设计方法、程2021/5/2135序推导的设计方法、程序变换的设计方法、函数式程序设计序推导的设计方法、程序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计技术、程序技术、逻辑程序设计技术、面向对象的程序设计技术、程序验证技术、约束程序设计技术、并发程序设计技术等。

验证技术、约束程序设计技术、并发程序设计技术等 例如，对于许多问题的计算，可以用类似于计算函数的例如，对于许多问题的计算，可以用类似于计算函数的方法来进行，也可以用表（一种数据结构）处理的方法来进方法来进行，也可以用表（一种数据结构）处理的方法来进行，甚至还可以用逻辑公式演绎推导的方法进行，在实现技行，甚至还可以用逻辑公式演绎推导的方法进行，在实现技术上，既可以用递归技术计算，也可以用迭代技术或其它技术上，既可以用递归技术计算，也可以用迭代技术或其它技术进行计算术进行计算 作为一门科学，高级语言和程序设计确实对学科的发展作为一门科学，高级语言和程序设计确实对学科的发展产生了巨大的影响程序设计方法和技术在各个时期的发展产生了巨大的影响程序设计方法和技术在各个时期的发展不仅直接导致了一大批风格各异的高级语言的诞生，而且许不仅直接导致了一大批风格各异的高级语言的诞生，而且许多新思想、新概念、新方法和新技术不仅在语言中得到体现，多新思想、新概念、新方法和新技术不仅在语言中得到体现，同时渗透到了计算机科学的各个方向，从理论、硬件、软件同时渗透到了计算机科学的各个方向，从理论、硬件、软件到应用等多方面深刻影响了学科的发展。

到应用等多方面深刻影响了学科的发展对高级语言和程序对高级语言和程序设计的掌握是计算机科学专业的基本功之一设计的掌握是计算机科学专业的基本功之一2021/5/2136 2.7 2.7 系统软件与应用软件系统软件与应用软件 从计算机（硬件裸机）到计算机系统从计算机（硬件裸机）到计算机系统 从计算机系统到计算机体系结构从计算机系统到计算机体系结构 软件是一个发展的概念，早期软件和程序几乎是同义词软件是一个发展的概念，早期软件和程序几乎是同义词后来，软件的概念在程序的基础上得到了延伸后来，软件的概念在程序的基础上得到了延伸19831983年，年，IEEEIEEE对软件给出了一个较为新颖的定义，指出：对软件给出了一个较为新颖的定义，指出：软件是计算软件是计算机程序、方法、规范及其相应的文稿以及在计算机上运行时机程序、方法、规范及其相应的文稿以及在计算机上运行时所必须的数据所必须的数据 在软件的发展过程中，人们将各种软件分成两大类一在软件的发展过程中，人们将各种软件分成两大类一类称为类称为系统软件系统软件，一类叫做，一类叫做应用软件应用软件。

所谓系统软件是指那所谓系统软件是指那些参与构成计算机系统，提供给计算机用户使用，用于扩展些参与构成计算机系统，提供给计算机用户使用，用于扩展计算机硬件功能、维护整个计算机硬件和软件系统，平滑用计算机硬件功能、维护整个计算机硬件和软件系统，平滑用户思维方式、操作习惯与计算机硬件设备之间沟坎的软件户思维方式、操作习惯与计算机硬件设备之间沟坎的软件应用软件是相对于系统软件而言的，它是对用户在计算机系应用软件是相对于系统软件而言的，它是对用户在计算机系统上针对各种具体的应用问题开发的一类专用程序或软件的统上针对各种具体的应用问题开发的一类专用程序或软件的2021/5/2137总称一般地说，操作系统、汇编程序、编译系统、数据库总称一般地说，操作系统、汇编程序、编译系统、数据库管理系统、软硬件故障诊断程序、子程序库、各种软件开发管理系统、软硬件故障诊断程序、子程序库、各种软件开发工具和软件包及其说明文件等属于系统软件，其它由用户开工具和软件包及其说明文件等属于系统软件，其它由用户开发发的的各各种种形形形形色色色色的的应应用用程程序序及及其其说说明明文文件件或或应应用用软软件件系系统统被称为应用软件。

被称为应用软件 操作系统操作系统------一种系统软件，它负责管理计算机系统中一种系统软件，它负责管理计算机系统中的各种资源并控制各类程序的运行它通过接受来自用户的的各种资源并控制各类程序的运行它通过接受来自用户的操作命令，按照用户的要求对计算机的工作进行控制计算操作命令，按照用户的要求对计算机的工作进行控制计算机配上操作系统之后，能够提高效率，便于使用机配上操作系统之后，能够提高效率，便于使用 系统软件和应用软件迄今并没有严格的定义系统软件和应用软件迄今并没有严格的定义 2.8 2.8 计算机组织与体系结构计算机组织与体系结构 从从计计算算机机系系统统的的逐逐个个设设计计、、制制造造到到计计算算机机的的系系列列化化和和软软件的兼容性件的兼容性2021/5/2138 IBM 360 IBM 360系统标志着计算机体系结构（系统标志着计算机体系结构（ArchitectureArchitecture））研究的开端（研究的开端（19641964年）计算机体系结构是使用机器语言编计算机体系结构是使用机器语言编写程序的用户可以看到的一个机器的抽象结构，而对这一结写程序的用户可以看到的一个机器的抽象结构，而对这一结构实现的硬件组成属于计算机组成原理研究的范畴。

构实现的硬件组成属于计算机组成原理研究的范畴 随着大规模和超大规模集成电路（随着大规模和超大规模集成电路（LSI/VLSILSI/VLSI）技术的成）技术的成熟，一方面器件速度和可靠性在不断提高，目前已逼近极限，熟，一方面器件速度和可靠性在不断提高，目前已逼近极限，另一方面器件的体积和价格在持续下降，这极大地增强了计另一方面器件的体积和价格在持续下降，这极大地增强了计算机的性能然而，算机的性能然而，高质量的器件不是产生高性能计算机的高质量的器件不是产生高性能计算机的唯一因素唯一因素虽然，今日大多数计算机都是图灵－冯虽然，今日大多数计算机都是图灵－冯··诺依曼诺依曼型存储程序式电子数字计算机，但人们早已认识到计算机不型存储程序式电子数字计算机，但人们早已认识到计算机不仅仅是一个硬件组织的问题一个现代的计算机系统一般被仅仅是一个硬件组织的问题一个现代的计算机系统一般被认为是由存储器、处理器、功能部件、互联网络、汇编程序、认为是由存储器、处理器、功能部件、互联网络、汇编程序、编译程序、操作系统、外部设备、通信通道等内容组合而成编译程序、操作系统、外部设备、通信通道等内容组合而成的。

的2021/5/2139 早期计算机系统研究与开发的两个基本特点：早期计算机系统研究与开发的两个基本特点：（（1 1）硬件和软件的研究与开发基本上是独立进行的；）硬件和软件的研究与开发基本上是独立进行的；（（2 2）硬件的研究与开发更多的是从计算机组成原理上去关）硬件的研究与开发更多的是从计算机组成原理上去关心各部件中分离元器件及其相互之间的联接关系，关心各心各部件中分离元器件及其相互之间的联接关系，关心各部件的内部构造和外部特性；部件的内部构造和外部特性； 集成电路的发展改变了专业人员的认识集成电路的发展改变了专业人员的认识 计算机计算机CPUCPU的速度和存储器的容量成倍增长，各种多功的速度和存储器的容量成倍增长，各种多功能部件不断引入，如何设计和配置计算机系统使其具有更能部件不断引入，如何设计和配置计算机系统使其具有更高的性能价格比，适应不同用户的要求，成为亟待解决的高的性能价格比，适应不同用户的要求，成为亟待解决的问题集成电路的发展也使许多专业人员可以不再关心各问题集成电路的发展也使许多专业人员可以不再关心各部件的内部细节，而只须考虑如何以一种统一的观点从硬部件的内部细节，而只须考虑如何以一种统一的观点从硬件器件和一些软件系统出发，通过组合配置，设计功能更件器件和一些软件系统出发，通过组合配置，设计功能更强、性能价格比更高、更可靠的计算机系统。

于是，计算强、性能价格比更高、更可靠的计算机系统于是，计算机体系结构应运而生机体系结构应运而生2021/5/2140 典型的、有助于常人理解计算机体系结构的方向是所谓典型的、有助于常人理解计算机体系结构的方向是所谓的网络计算机系统用户面对网络计算机系统进行开发是十的网络计算机系统用户面对网络计算机系统进行开发是十分困难的，因为，他不可能熟悉网上每一种通信资源）的配分困难的，因为，他不可能熟悉网上每一种通信资源）的配置情况，而且也不了解每一种通信资源的基本操作方法，更置情况，而且也不了解每一种通信资源的基本操作方法，更不可能考虑通信出错的情况以及如何纠错显然，对于用户不可能考虑通信出错的情况以及如何纠错显然，对于用户来说，需要有一种能够屏蔽计算机硬件系统技术细节，仅对来说，需要有一种能够屏蔽计算机硬件系统技术细节，仅对用户提供功能透明的系统层，使用户看到的和实际使用的是用户提供功能透明的系统层，使用户看到的和实际使用的是一个与使用者思想方式、使用习惯比较接近，无须具体关心一个与使用者思想方式、使用习惯比较接近，无须具体关心网络计算机通信时一些十分繁琐的技术细节的分布式计算机网络计算机通信时一些十分繁琐的技术细节的分布式计算机系统。

系统 硬件的互联结构和软件结构及相互关系形成的计算机系硬件的互联结构和软件结构及相互关系形成的计算机系统的总体结构，支持这种结构的基本算法，还有以总体结构统的总体结构，支持这种结构的基本算法，还有以总体结构为基础的面向用户的程序设计语言等内容构成了计算机体系为基础的面向用户的程序设计语言等内容构成了计算机体系结构的技术范畴结构的技术范畴2021/5/2141 2 2．．9 9 并行计算机、通道与并行计算并行计算机、通道与并行计算 单单CPUCPU计算机计算机 –– 多功能部件多寄存器计算机多功能部件多寄存器计算机 –– 流水线流水线向量计算机向量计算机 –– 阵列式计算机阵列式计算机 –– 多处理器并行计算机多处理器并行计算机 –– 多多处理机并行计算机处理机并行计算机 –– 多计算机网络并行计算机系统多计算机网络并行计算机系统 并行处理要求在计算机上并行地运行许多程序根据使并行处理要求在计算机上并行地运行许多程序根据使用的计算机系统的不同，我们可以在四个程序的级别上提出用的计算机系统的不同，我们可以在四个程序的级别上提出并行处理的问题：并行处理的问题： 作业或程序级并行作业或程序级并行 任务或过程级并行任务或过程级并行 指令级并行指令级并行 指令内部级并行指令内部级并行 不同的并行处理思想和技术，产生了不同的并行计算机不同的并行处理思想和技术，产生了不同的并行计算机系统。

从使用方便的角度考虑，用户更希望看到的是系统提系统从使用方便的角度考虑，用户更希望看到的是系统提供作业或程序级并行，这样用户可以不必考虑实现并行的细供作业或程序级并行，这样用户可以不必考虑实现并行的细2021/5/2142节而从实际计算提高效率的角度考虑，用户更希望系统节而从实际计算提高效率的角度考虑，用户更希望系统已经实现了指令级并行或指令内部级并行那么，面对众已经实现了指令级并行或指令内部级并行那么，面对众多的并行计算机系统，我们应该怎么来认识和区别它们的多的并行计算机系统，我们应该怎么来认识和区别它们的系统结构呢？系统结构呢？ 注意到了程序在计算机上的执行实际上是指令在数据注意到了程序在计算机上的执行实际上是指令在数据集上的一个操作序列这样一个基本的事实，集上的一个操作序列这样一个基本的事实，M. J. FlynnM. J. Flynn在在19661966年提出了一种著名的、也是现今比较常用的系统结年提出了一种著名的、也是现今比较常用的系统结构分类方法他将计算机系统的系统结构分为四类，分别构分类方法他将计算机系统的系统结构分为四类，分别是：单指令流单数据流计算机（是：单指令流单数据流计算机（SISDSISD）、单指令流多数据）、单指令流多数据流计算机（流计算机（SIMDSIMD）、多指令流单数据流计算机（）、多指令流单数据流计算机（MISDMISD）、）、多指令流多数据流计算机（多指令流多数据流计算机（MIMDMIMD）。

由多机系统技术的扩展及网络互连与通信技术的引入，由多机系统技术的扩展及网络互连与通信技术的引入，发展了分布式网络计算机系统，提出了分布式计算机体系发展了分布式网络计算机系统，提出了分布式计算机体系结构、分布式算法与分布式并行处理的概念等结构、分布式算法与分布式并行处理的概念等2021/5/2143 并行计算机系统的出现，带来了信息并行化处理的概并行计算机系统的出现，带来了信息并行化处理的概念并行处理是信息处理的一种有效形式，它着重于发掘念并行处理是信息处理的一种有效形式，它着重于发掘计算过程中的并发事件并发性包含宏观上的并行性，包计算过程中的并发事件并发性包含宏观上的并行性，包含同时性以及微观上的流水线处理并行事件可在同一时含同时性以及微观上的流水线处理并行事件可在同一时间间隔内在多个资源（如多个处理器）里发生；同时事件间间隔内在多个资源（如多个处理器）里发生；同时事件可在同一时刻上发生，流水线事件可在部分重叠的时间内可在同一时刻上发生，流水线事件可在部分重叠的时间内于一个（或多个）资源里出现并发通常是指宏观上一个于一个（或多个）资源里出现并发通常是指宏观上一个资源里并行发生了两个或两个以上的事件，但在微观上是资源里并行发生了两个或两个以上的事件，但在微观上是顺序发生的，而并行通常是指多个资源里微观上同时发生顺序发生的，而并行通常是指多个资源里微观上同时发生了两个或两个以上事件。

显然，一组事件是并行的也是并了两个或两个以上事件显然，一组事件是并行的也是并发的，但一组事件是并发的却不一定是并行的发的，但一组事件是并发的却不一定是并行的 通道通道 - - 通道是数据或信息传送的通路通道是数据或信息传送的通路 利利用用并并行行计计算算机机系系统统进进行行数数据据与与信信息息的的并并行行处处理理称称为为并并行行计计算算从从处处理理对对象象的的角角度度划划分分，，并并行行计计算算分分为为数数值值并并行计算和非数值并行计算与顺序计算类似，并行计算也行计算和非数值并行计算与顺序计算类似，并行计算也2021/5/2144分成几个步骤：研究并行计算方法，研究并行算法，设计分成几个步骤：研究并行计算方法，研究并行算法，设计并行程序，调试与运行，分析结果由于许多问题的计算并行程序，调试与运行，分析结果由于许多问题的计算已经有了计算方法，而这些计算方法中隐含了大量的并行已经有了计算方法，而这些计算方法中隐含了大量的并行性，稍作变化就可支持并行算法和并行程序设计，而且，性，稍作变化就可支持并行算法和并行程序设计，而且，由于各种并行计算机的系统结构不同，各处理器和各多功由于各种并行计算机的系统结构不同，各处理器和各多功能部件之间在体现算法时的相互作用不同，算法不能通用。

能部件之间在体现算法时的相互作用不同，算法不能通用因此，除了并行计算机体系结构的研究外，当前和今后相因此，除了并行计算机体系结构的研究外，当前和今后相当长的一个时期内并行处理的一个工作重点将是研究各种当长的一个时期内并行处理的一个工作重点将是研究各种并行与分布式计算机系统上的并行算法或分布式算法并行与分布式计算机系统上的并行算法或分布式算法 2.10 2.10 计算机网络与通信计算机网络与通信 随着计算科学及其应用的高速发展，用户对软硬件和随着计算科学及其应用的高速发展，用户对软硬件和信息资源共享的需求和一大类问题本身具有地域上分布的信息资源共享的需求和一大类问题本身具有地域上分布的特点，促进了计算机网络的发展特点，促进了计算机网络的发展2021/5/2145 所谓所谓计算机网络计算机网络是使用通信设备和通信线路将一组地理是使用通信设备和通信线路将一组地理上分布的相同（称为同质）或不同（称为异质）的计算机、上分布的相同（称为同质）或不同（称为异质）的计算机、终端及其附属设备按照某种方式互联起来得到的一个计算机终端及其附属设备按照某种方式互联起来得到的一个计算机硬件系统，也叫网络计算机。

在这种计算机硬件系统的基础硬件系统，也叫网络计算机在这种计算机硬件系统的基础上，通过开发能协调各台计算机系统工作的通信系统或更进上，通过开发能协调各台计算机系统工作的通信系统或更进一步的网络操作系统，就能使一组计算机实现软硬件资源共一步的网络操作系统，就能使一组计算机实现软硬件资源共享、协同计算，合作求解一个问题由这种通信系统或网络享、协同计算，合作求解一个问题由这种通信系统或网络操作系统连同网络计算机一起，就形成了网络计算机系统操作系统连同网络计算机一起，就形成了网络计算机系统 按照数据传输范围和实现技术的不同，计算机网络存在按照数据传输范围和实现技术的不同，计算机网络存在局域计算机网络局域计算机网络和和广域计算机网络广域计算机网络之分局域计算机网络局域计算机网络是是一个数据通信系统，其传输范围在中等地理区域，使用中等一个数据通信系统，其传输范围在中等地理区域，使用中等或高速数据传输速率，使用专用数据通信线或总线进行通信，或高速数据传输速率，使用专用数据通信线或总线进行通信，可联接大量独立设备，在物理通信通道上互相通信可联接大量独立设备，在物理通信通道上互相通信 广域计算机网络广域计算机网络把不同城市、不同国家中的计算机或计把不同城市、不同国家中的计算机或计2021/5/2146算机系统通过分级互联技术联接起来，其传输范围可达到算机系统通过分级互联技术联接起来，其传输范围可达到相当远的距离。

目前最常见的是使用公用或专用线通相当远的距离目前最常见的是使用公用或专用线通信，主干网和一些局域网使用可进行数字通信的光纤光缆信，主干网和一些局域网使用可进行数字通信的光纤光缆数据通信专用线数据通信专用线 网络互联的拓扑结构是计算机网络的重要特性网络网络互联的拓扑结构是计算机网络的重要特性网络的拓扑结构是一种抽象的由点和线组成的图网络上的每的拓扑结构是一种抽象的由点和线组成的图网络上的每台计算机用一个结点表示，机器与机器之间的链路用线和台计算机用一个结点表示，机器与机器之间的链路用线和路径表示，于是，图论构成了网络计算机体系结构中一些路径表示，于是，图论构成了网络计算机体系结构中一些基本算法研究中数学描述的理论基础基本算法研究中数学描述的理论基础 支持计算机网络的重要技术是通信，即实现计算机之支持计算机网络的重要技术是通信，即实现计算机之间信息传输的一种技术方式网络通信的核心内容是通信间信息传输的一种技术方式网络通信的核心内容是通信协议所谓通信协议是网络通信中一组约定的集合，由它协议所谓通信协议是网络通信中一组约定的集合，由它确定了经由通信网络传输的信息或存储在报文和数据库中确定了经由通信网络传输的信息或存储在报文和数据库中2021/5/2147的信息的格式和控制方式。

研究通信协议主要是为了在网络的信息的格式和控制方式研究通信协议主要是为了在网络计算机系统中实现可靠的、高效的数据交换，差错控制，信计算机系统中实现可靠的、高效的数据交换，差错控制，信息编码，线路利用，同步，使通信数据具有透明性息编码，线路利用，同步，使通信数据具有透明性 网络上连接着大量的计算机系统，每一台计算机系统上网络上连接着大量的计算机系统，每一台计算机系统上可能有多个用户在同时使用计算机与其它网上用户进行通信，可能有多个用户在同时使用计算机与其它网上用户进行通信，而网络的通信线路通常设计成公用资源，这样，网络通信为而网络的通信线路通常设计成公用资源，这样，网络通信为了实现可靠的数据交换，因需要做许多具体的操作运算而变了实现可靠的数据交换，因需要做许多具体的操作运算而变得十分复杂由于从用户发送或接收可以识别的符号信息到得十分复杂由于从用户发送或接收可以识别的符号信息到实际在正确的通信线路上传递物理信息之间存在转换、线路实际在正确的通信线路上传递物理信息之间存在转换、线路利用、分组交换、差错纠正等一系列的操作，为了便于协议利用、分组交换、差错纠正等一系列的操作，为了便于协议的有效实现和对不同的用户开放，最大限度地实现线路的有的有效实现和对不同的用户开放，最大限度地实现线路的有效利用，有必要对网络计算机系统进行通信结构分层。

于是效利用，有必要对网络计算机系统进行通信结构分层于是产生了网络协议层每一层包含一组通信功能和相应的层间产生了网络协议层每一层包含一组通信功能和相应的层间通信协议，支持通信双方在不同的层间进行通信，并提供了通信协议，支持通信双方在不同的层间进行通信，并提供了实现通信的具体思想和方法实现通信的具体思想和方法2021/5/2148 按照按照ISOISO的建议，网络结构模型是开放系统互连模型的建议，网络结构模型是开放系统互连模型OSIOSI（七层协议），包括物理层，数据链路层，网络层，传（七层协议），包括物理层，数据链路层，网络层，传输层，会话层，表示层，应用层共七层，产生了七层协议输层，会话层，表示层，应用层共七层，产生了七层协议 开放系统开放系统A A 开放系统开放系统B B ┌─────┐ ┌─────┐ 应用层协议应用层协议 ┌─────┐ ┌─────┐ │ │ 应用层应用层 ├ ├－－－－－－－－－－－－－－－－－－－－－－－－－－－－┤ ┤ 应用层应用层 │ │ ├─────┤ ├─────┤ 表示层协议表示层协议 ├─────┤ ├─────┤ │ │ 表示层表示层 ├ ├－－－－－－－－－－－－－－－－－－－－－－－－－－－－┤ ┤ 表示层表示层 │ │ ├─────┤ ├─────┤ 会话层协议会话层协议 ├─────┤ ├─────┤ │ │ 会话层会话层 ├ ├－－－－－－－－－－－－－－－－－－－－－－－－－－－－┤ ┤ 会话层会话层 │ │ ├─────┤ ├─────┤ 传输层协议传输层协议 ├─────┤ ├─────┤ │ │ 传输层传输层 ├ ├－－－－－－－－－－－－－－－－－－－－－－－－－－－－┤ ┤ 传输层传输层 │ │ ├─────┤ ├─────┤ 网络层协议网络层协议 ├─────┤ ├─────┤ │ │ 网络层网络层 ├ ├－－－－－－－－－－－－－－－－－－－－－－－－－－－－┤ ┤ 网络层网络层 │ │ ├─────┤ ├─────┤ 数据链路层协议数据链路层协议 ├─────┤ ├─────┤ │ │数据链路层数据链路层├├－－－－－－－－－－－－－－－－－－－－－－－－－－－－┤┤数据链路层数据链路层││ ├─────┤ ├─────┤ 物理层协议物理层协议 ├─────┤ ├─────┤ │ │ 物理层物理层 ├ ├－－－－－－－－－－－－－－－－－－－－－－－－－－－－┤ ┤ 物理层物理层 │ │┌┴─────┴──────────────┴─────┴┐┌┴─────┴──────────────┴─────┴┐│ │ 物理传输介质物理传输介质 │ │└────────────────────────────┘└────────────────────────────┘2021/5/2149 物物理理层层协协议议实实现现物物理理上上互互连连系系统统间间位位流流信信息息的的透透明明传传输输，，即即实实现现了了一一位位（（组组））数数据据在在两两个个通通信信实实体体之之间间的的可可靠靠传传送送通通信，它描述了经通信介质在数据链路实体之间建立、维信，它描述了经通信介质在数据链路实体之间建立、维护和拆除物理连接。

护和拆除物理连接 数数据据链链路路层层协协议议主主要要是是对对高高层层屏屏蔽蔽传传输输介介质质的的特特性性，，为为网网络络通通信信实实体体之之间间提提供供建建立立、、维维护护和和释释放放数数据据链链路路连连接接的的功功能和手段，实现无差错的数据以帧为单位的可靠传送能和手段，实现无差错的数据以帧为单位的可靠传送 网网络络层层协协议议主主要要是是为为通通信信子子网网与与高高层层结结构构之之间间提提供供界界面面连连接接，，其其主主要要任任务务是是对对通通信信子子网网实实现现路路径径选选择择，，实实现现通通信信实实体体之之间间端端- -端端的的透透明明的的数数据据传传送送，，对对高高层层屏屏蔽蔽了了数数据据传传送送经经过过的路径 传传输输层层协协议议也也称称为为主主机机- -主主机机层层协协议议，，它它为为会会话话层层的的通通信信实实体体之之间间提提供供透透明明的的数数据据传传送送，，其其主主要要任任务务是是接接收收会会话话实实体体送送来来的的数数据据，，根根据据需需要要把把它它们们分分成成若若干干比比较较小小的的单单元元，，保保证证所有数据单元经下面三层正确地到达另一个会话实体。

所有数据单元经下面三层正确地到达另一个会话实体2021/5/2150 会会话话层层协协议议也也称称进进程程- -进进程程层层协协议议，，它它通通过过协协议议提提供供的的一一组组命命令令为为网网上上两两个个进进程程之之间间的的通通信信建建立立会会话话连连接接和和释释放会话连接，并管理它们在该连接上的对话放会话连接，并管理它们在该连接上的对话 表表示示层层协协议议以以对对应应用用实实体体有有意意义义的的形形式式提提供供有有关关信信息息表表示示的的服服务务这这些些服服务务有有文文本本压压缩缩、、代代码码转转换换、、数数据据加加密密与与解解密密、、文文件件格格式式变变换换、、信信息息格格式式变变换换、、终终端端属属性性的的转转换换等 应应用用层层协协议议是是用用户户访访问问网网络络的的接接口口层层，，直直接接为为正正在在通通信信的的端端点点用用户户的的应应用用进进程程服服务务，，如如电电子子邮邮件件、、远远程程操操作作访访问、虚拟终端等问、虚拟终端等 关关于于协协议议详详细细的的实实现现技技术术，，其其主主要要的的基基础础是是分分布布式式算算法，今后，同学们有可能学习这些内容。

法，今后，同学们有可能学习这些内容 网网络络信信息息安安全全、、加加密密、、病病毒毒、、高高性性能能计计算算与与通通信信、、信信息高速公路、数字地球息高速公路、数字地球2021/5/2151部分资料从网络收集整理而来，供大家参考，感谢您的关注！。