计算学科中的基本概念

1、 b b 1 0 1 0 0 0 1 0 b b b 读 写 头 控 制 器 状 态 ql b b 1 0 1 0 0 0 1 0 b b b 读 写 头 控 制 器 状 态 ql 计算结果是10100011，即对给定的数加1。 b b 1 0 1 0 0 0 1 0 b b b 读 写 头 控 制 器 状 态 ql 以上命令计算的是这样一个函数：S(x)x1。当没有输入时，即初始状态所指的方格为空格（b）时，不改变空格符，读写头不动并停机。 o 第一第一，把图灵机看作识别器，即判断带子上最，把图灵机看作识别器，即判断带子上最初的内容能否被图灵机所接受。假定图灵机从初的内容能否被图灵机所接受。

2、假定图灵机从左向右扫描完带子上的内容后停机则为接受，左向右扫描完带子上的内容后停机则为接受，否则为不接受。否则为不接受。o 例例2 一台图灵机可以设计成识别下面的序列：一台图灵机可以设计成识别下面的序列： 1000110, 10011101, 010101011。o 第二，第二，把图灵机看作生成器，对给定的输入集把图灵机看作生成器，对给定的输入集合，考察输出集合，并研究输入输出集合性质合，考察输出集合，并研究输入输出集合性质之间的关系，这就研究了图灵机的生成能力。之间的关系，这就研究了图灵机的生成能力。o 例例3 设一台图灵机的输入集合为设一台图灵机的输入集合为In1n0nnN，可设计一台图灵

3、机，对给定的，可设计一台图灵机，对给定的输入集合输入集合In，得到输出集合，得到输出集合Out0n1nnN。其中，。其中，N是全体自然数的集合。是全体自然数的集合。o 第三第三，把图灵机看作计算器，相当于一个函数。，把图灵机看作计算器，相当于一个函数。图灵机的输入是函数的自变量的值，图灵机的图灵机的输入是函数的自变量的值，图灵机的输出是函数的值。输出是函数的值。 例例4 图灵机可以计算下列函数：图灵机可以计算下列函数： (1) s(x)x1； (2) o(x)0； (3) A(0，y)y1， A(x1，0)A(x，1)， A(x1，y1)A(x，A(x1，y)。o 第一和第二个函数读者不难从图

4、灵机的定义出第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数，而第发感悟到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断。顺便提三个函数就比较复杂，一时难于判断。顺便提一下，第三个函数叫做一下，第三个函数叫做阿克曼函数阿克曼函数，它是阿克，它是阿克曼（曼（W.Ackermann）在研究原始递归函数和）在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理递归函数的关系时给出的。这个函数在计算理论中具有重要价值。论中具有重要价值。o 事实上，图灵机还可以计算形式上比第三个函事实上，图灵机还可以计算形式上比第三个函数更复杂的函数。数更复杂的函数。

5、nn-110-1-m+1-m其中，其中，10称为十进制的基数称为十进制的基数,ki0,1,2,3,4,5,6,7,8 9，m，n为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。 Sknkn-1 k0. k-m kn2nkn-12n-1k020k-m2-m -m ki2i in 其中，其中，2称为二进制的基数，称为二进制的基数，ki0,1,m,n为正整数。为正整数。 进一步，读者可从十进制数和二进制数的一般表示进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，公式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。不同之处

6、只是基数不一样。 二进制的运算规则比十进制的运算规则简二进制的运算规则比十进制的运算规则简单得多。单得多。只要建立两种进制的数据之间的转换只要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势。方法，那么，二进制将具有更多的优势。计算计算机的理论基础是逻辑和代数。当二进制与同样机的理论基础是逻辑和代数。当二进制与同样只使用只使用“真真”和和“假假”两个值的逻辑代数建立两个值的逻辑代数建立了联系后，这就为计算机的逻辑设计提供了便了联系后，这就为计算机的逻辑设计提供了便利的工具。利的工具。 图灵机的出现为现代计算机的发明提供了图灵机的出现为现代计算机的发明提供了重要的思想。图灵机的带子

7、可以看成是计算机重要的思想。图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根的存储设备，数据可以存储在上面，也可以根据需要擦去。图灵机的命令相当于一组事先设据需要擦去。图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，计、存储好了的程序，它们在控制器安排下，决定读写头的每一步操作。这样一种数学机器，决定读写头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，如果不考虑它的实用性，就思想和原理而言，确实包含了确实包含了存储程序存储程序的重要思想。的重要思想。 存 储 器 运 算 器 控 制 器 输入/输出设备 命令寄存器 “与与”、“或

8、或”、“非非”三种门电路示意图三种门电路示意图 P P P A B C A B C A （a） （b） （c） o 用计算机求解一个问题，必须事先编制好程序。程用计算机求解一个问题，必须事先编制好程序。程序是由指令组成的。每一台计算机都设计规定了一序是由指令组成的。每一台计算机都设计规定了一组指令集合，称为机器指令系统。组指令集合，称为机器指令系统。o 机器指令的格式一般分为两部分，如下所示：机器指令的格式一般分为两部分，如下所示： 指令格式：指令格式： 操作码操作码 地址部分地址部分 其中，操作码指出运算的种类，如，其中，操作码指出运算的种类，如，跳转等，地址部分用来指示参与运算的数据保，跳

9、转等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器存在什么地方，如存储器的某个地址或某个寄存器等。操作码和地址部分都用二进制代码表示。等。操作码和地址部分都用二进制代码表示。o 机器指令一般可根据其功能划分为以下几类：机器指令一般可根据其功能划分为以下几类： (1) (1)控制指令；控制指令；(2)(2)算术运算指令；算术运算指令；(3)(3)逻辑逻辑运算指令；运算指令；(4)(4)移位操作指令；移位操作指令；(5)(5)传送操作传送操作指令；指令；(6)(6)输入输入/ /输出指令。输出指令。o 应当注意的是，不同的机器，其指令系统是应当注意的是，不同的机器，

10、其指令系统是不同的。不同的。o 指令系统的日渐增大虽然给用户的程序设计指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的带来了方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而增加和因译码、存储、寻址等开销的增大而使运算速度下降。研究发现，使运算速度下降。研究发现，指令系统存在指令系统存在着改进的必要和可能。着改进的必要和可能。 RISCo 思路主要是通过减少指令总数和简化指令的思路主要是通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提高指功能来降低硬件设计的复杂度，从而提高指令的执行速度。令的执行速度。o 优点优点:与与CISC技术

11、相比技术相比n 简化了指令系统，适合超大规模集成电路简化了指令系统，适合超大规模集成电路的实现；的实现；n 提高了机器执行的速度和效率；提高了机器执行的速度和效率；n 降低了设计成本，提高了系统的可靠性；降低了设计成本，提高了系统的可靠性；n 提供了直接支持高级语言的能力，简化了提供了直接支持高级语言的能力，简化了编译程序的设计。编译程序的设计。机器指令o 机器指令系统每台数字电子计算机在设计中，都规定了一组指令。o 机器语言用机器指令形式编写的程序。o 在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，它的符号集是0，1，n 支撑实际机器的理论是图灵机等计算模型；n 在图灵机等计

12、算模型理论的指导下，有关设计形态的主要成果有冯诺依曼型计算机等具体实现思想和技术，以及各类数字电子计算机产品。计算机语言抽象理论设计裸机级的主要内容和成果 语言的符号集为：0，1；用机器指令对算法进行描述图灵机（过程语言的基础）、波斯特系统（字符串处理语言的基础）、-演算（函数式语言的基础）等计算模型冯 诺 依曼型计算机等实现技术；数字电子计算机产品汇编语言o 汇编语言实际上是由一组汇编指令构成的语汇编语言实际上是由一组汇编指令构成的语言。每一条汇编指令用某个西文字符串的缩言。每一条汇编指令用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数写来表示其所代表的操作，用符号来代表数据的二进

13、制、八进制和十进制数字序列。大据的二进制、八进制和十进制数字序列。大多数情况下，一条汇编指令对应一条机器指多数情况下，一条汇编指令对应一条机器指令，少数对应几条机器指令。例如，下面是令，少数对应几条机器指令。例如，下面是几条汇编指令的操作符，右边中文是名称。几条汇编指令的操作符，右边中文是名称。 addadd 加法加法 idividiv 有符号除法有符号除法 mulmul 无符无符号乘法号乘法 negneg 求补求补 xchgxchg 交换交换 testtest 逻辑比较逻辑比较 jmpjmp 无条件转移无条件转移汇编语言o 当然，汇编语言在可读性和编写程序时仍然当然，汇编语言在可读性和编写程

14、序时仍然是不能令人满意的，这导致进一步发展了高是不能令人满意的，这导致进一步发展了高级程序设计语言。不过，由于高级语言在使级程序设计语言。不过，由于高级语言在使用时通常还是要通过编译程序逐步将高级语用时通常还是要通过编译程序逐步将高级语言写的程序翻译成机器指令的程序，而这种言写的程序翻译成机器指令的程序，而这种翻译的结果往往不如机器指令或汇编语言写翻译的结果往往不如机器指令或汇编语言写的程序效率高，所以，直到今天，不少工程的程序效率高，所以，直到今天，不少工程师在系统软件的开发中还在使用机器指令和师在系统软件的开发中还在使用机器指令和汇编语言。汇编语言。 求解一个给定的问题，不同的人常编写求解

15、一个给定的问题，不同的人常编写出不同的然而都是正确的程序，这是为什么出不同的然而都是正确的程序，这是为什么呢？呢？ 这里存在两个层面的问题，一个是与计这里存在两个层面的问题，一个是与计算方法密切相关的算法问题，另一个是程序算方法密切相关的算法问题，另一个是程序设计的技术问题。设计的技术问题。o 不难想象，不同的求解方法将产生出不同的不难想象，不同的求解方法将产生出不同的算法，不同的算法将使我们设计出不同的程算法，不同的算法将使我们设计出不同的程序，而决定这个程序功能的本质是计算方法序，而决定这个程序功能的本质是计算方法及其算法。一般地说，对不同计算方法过程及其算法。一般地说，对不同计算方法过程

16、的抽象描述就产生了相应的不同算法，但同的抽象描述就产生了相应的不同算法，但同一算法由不同的人来写程序则完全可能设计一算法由不同的人来写程序则完全可能设计出差别很大的程序。出差别很大的程序。o 凭直觉想象给出的算法往往不是最好的算法。凭直觉想象给出的算法往往不是最好的算法。 算法算法被认为是计算科学的核心问题之一。被认为是计算科学的核心问题之一。 o 定风定风1 1：给定问题和设备，一个算法是用该设备可：给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法的精理解的语言表示的，解决这个问题的一种方法的精确刻划。特别，算法具有下列特征属性：确刻划。特别，算法具有下列特征属性

17、： (1) (1) 算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果；将在有穷步动作序列之后得到结果； (2) (2) 该序列有一个唯一的初始动作；该序列有一个唯一的初始动作； (3) (3) 该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动作；作； (4) (4) 该序列终止时或者得到这个问题的解，或者该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。o 定风定风1 1：给定问题和设备，一个算法是用该设备可：给定问题和设备，一个算法是用该设备可理解的语言表

18、示的，解决这个问题的一种方法的精理解的语言表示的，解决这个问题的一种方法的精确刻划。特别，算法具有下列特征属性：确刻划。特别，算法具有下列特征属性： (1) (1) 算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果；将在有穷步动作序列之后得到结果； (2) (2) 该序列有一个唯一的初始动作；该序列有一个唯一的初始动作； (3) (3) 该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动作；作； (4) (4) 该序列终止时或者得到这个问题的解，或者该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可

19、解说明。因该问题不可解而获得不可解说明。定义定义2（Knuth算法定义）算法定义） 一个算法，就是一个有穷规则的集合，其中之规则一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。此外，确定了一个解决某一特定类型问题的运算序列。此外，算法的规则序列须满足如下五个重要条件（特性）：算法的规则序列须满足如下五个重要条件（特性）： (1) (1) 有穷性。算法必须总是在执行有穷步之后结束；有穷性。算法必须总是在执行有穷步之后结束； (2) (2) 确定性。算法的每一个步骤必须是确切地定义确定性。算法的每一个步骤必须是确切地定义的；的； (3) (3) 输入。算法有零

20、个或多个输入；输入。算法有零个或多个输入； (4) (4) 输出。算法有一个或多个输出，即与输入有某输出。算法有一个或多个输出，即与输入有某个特定关系的量；个特定关系的量； (5) (5) 能行性。算法中有待执行的运算和操作必须是能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上都是能够精确地进行相当基本的，即是说，它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。的，而且用笔和纸做有穷次就可以完成。nHn1312111 X=1 Y=2 X=X+Y Y=Y+1 Y100 结 束 开 始 Y N 开 始 X=0 I=1 X=X+1/I I=I+1 I=N 结 束

21、 N Y 开 始 n = 0 X = 0 ， Y = 1 P rin t X ， Y I= 1 I n -1 Z = X + Y X = Y Y = Z P rin t Y I= I+ 1 结 束 Y = 0 P rin t Y Y N Y N 在梵天塔问题中，需要移动的盘子次数为在梵天塔问题中，需要移动的盘子次数为h(n)=2n-1，则该问题的算法时间复杂度表示则该问题的算法时间复杂度表示为为 (2n)；例例4.4的算法时间复杂度表示为的算法时间复杂度表示为 (1)；例例4.5的算法时间复杂度表示为的算法时间复杂度表示为 (n)；例例4.6的的算法时间复杂度表示为算法时间复杂度表示为 (n)

22、等等。等等。 一般而言，对于较复杂的算法，应将它分一般而言，对于较复杂的算法，应将它分成容易估算的几个部分，然后用成容易估算的几个部分，然后用 的求解原则的求解原则计算整个算法的时间复杂度，最好不要采用计算整个算法的时间复杂度，最好不要采用指数级和阶乘级的算法，而应尽可能选用多指数级和阶乘级的算法，而应尽可能选用多项式级或线性级等时间复杂度较小的算法。项式级或线性级等时间复杂度较小的算法。另外，还要在算法最好、平均和最坏的情况另外，还要在算法最好、平均和最坏的情况下区别执行效率的不同。下区别执行效率的不同。 在阶乘级的算法中，如果问题规模在阶乘级的算法中，如果问题规模n为为10，则算法时间复杂

23、度为则算法时间复杂度为10！（！（3，628，800）。）。若要检验若要检验10！种情况，设每种情况需要！种情况，设每种情况需要1毫秒毫秒的计算时间，则整个计算将需的计算时间，则整个计算将需1小时左右。一小时左右。一般来说，如果选用了阶乘级的算法，则当问般来说，如果选用了阶乘级的算法，则当问题规模等于或者大于题规模等于或者大于10时，就要认真考虑算时，就要认真考虑算法的适用性问题。法的适用性问题。 C A B D E F G H I J K L C A B D 一个程序具有一个单一的、不可分的结构，它规定了某个数据结构上的一个算法。瑞士著名计算机科学家尼可莱沃思（Nikiklaus Wirth

24、）在1976年曾提出这样一个公式： 算法算法+数据结构数据结构=程序程序 这一公式仅可以作为一种参考，不能作这一公式仅可以作为一种参考，不能作为教学中的定义。为教学中的定义。 由此看来，我们前面提到的算法和数据结构是计算机程序的两个最基本的概念。算法是程序的核心，它在程序编制、软件开发，乃至在整个计算机科学中都占据重要地位。数据结构是加工的对象，一个程序要进行计算或处理总是以某些数据为对象的，而要设计一个好的程序就需将这些松散的数据按某种要求组成一种数据结构。然而，随着计算机科学的发展，人们现在已经意识到程序除了以上两个主要要素外，还应包括程序的设计方法以及相应的语言工具和计算环境。 抽象理论

25、设计常用的符号：数字(09)，大小写字母(AZ、az)，括号，运算符(+，*，/)等;用高级语言对算法进行的描述；语言的分类方法；各种数据类型的抽象实现模型；词法分析、编译、解释和代码优化的方法；词法分析器、扫描器、编译器组件和编译器的自动生成方法形式语言和自动机理论；形式语义学：操作、指称、公理、代数、并发和分布式程序的形式语义特定语言：过程式的COBOL，FORTURN，ALGOL，Pascal，Ada，C），函数式的（LISP），数据流的（SISAL，VAL），面向对象的（Smalltalk，C+），逻辑的（Prolog），字符串（SNOBOL），和并发（Concurrent Pasca

26、l，Modula 2）等语言；词法分析器和扫描器的产生器（如YACC，LEX），编译器产生器；语法和语义检查，成型、调试和追踪程序o 对程序结构本质的深入研究促进了对程序质对程序结构本质的深入研究促进了对程序质量的认识量的认识o 开发程序的效率和质量取决于程序设计方法开发程序的效率和质量取决于程序设计方法和技术和技术o 多年的研究发展了许多程序设计方法和技术。多年的研究发展了许多程序设计方法和技术。如自顶向下逐步求精的程序设计方法、自底如自顶向下逐步求精的程序设计方法、自底向上的程序设计方法、程序推导的设计方法、向上的程序设计方法、程序推导的设计方法、程序变换的设计方法、函数式程序设计技术、程

27、序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计技逻辑程序设计技术、面向对象的程序设计技术、程序验证技术、约束程序设计技术、并术、程序验证技术、约束程序设计技术、并发程序设计技术等。发程序设计技术等。o 例如，对于许多问题的计算，可以用类似于例如，对于许多问题的计算，可以用类似于计算函数的方法来进行，也可以用表（一种计算函数的方法来进行，也可以用表（一种数据结构）处理的方法进行，甚至还可以用数据结构）处理的方法进行，甚至还可以用逻辑公式演绎推导的方法进行，在实现技术逻辑公式演绎推导的方法进行，在实现技术上，既可以用递归技术计算，也可以用迭代上，既可以用递归技术计算，也

28、可以用迭代技术或其它技术进行计算。技术或其它技术进行计算。o 作为一门科学，高级语言和程序设计确实对作为一门科学，高级语言和程序设计确实对学科的发展产生了巨大的影响。程序设计方学科的发展产生了巨大的影响。程序设计方法和技术在各个时期的发展不仅直接导致了法和技术在各个时期的发展不仅直接导致了一大批风格各异的高级语言的诞生，而且许一大批风格各异的高级语言的诞生，而且许多新思想、新概念、新方法和新技术不仅在多新思想、新概念、新方法和新技术不仅在语言中得到体现，同时渗透到了计算机科学语言中得到体现，同时渗透到了计算机科学的各个方向，从理论、硬件、软件到应用等的各个方向，从理论、硬件、软件到应用等多方面

29、深刻影响了学科的发展。多方面深刻影响了学科的发展。o 对高级语言和程序设计的掌握是计算机科学对高级语言和程序设计的掌握是计算机科学专业的基本功之一。专业的基本功之一。o 从计算机（硬件裸机）到计算机系统从计算机（硬件裸机）到计算机系统o 从计算机系统到计算机体系结构从计算机系统到计算机体系结构o 软件是一个发展的概念，早期软件和程序几软件是一个发展的概念，早期软件和程序几乎是同义词。后来，软件的概念在程序的基乎是同义词。后来，软件的概念在程序的基础上得到了延伸。础上得到了延伸。1983年，年，IEEE对软件给出对软件给出了一个较为新颖的定义，指出：了一个较为新颖的定义，指出：软件是计算软件是计

30、算机程序、方法、规范及其相应的文稿以及在机程序、方法、规范及其相应的文稿以及在计算机上运行时所必须的数据。计算机上运行时所必须的数据。o 系统软件和应用软件迄今并没有严格的定系统软件和应用软件迄今并没有严格的定义。义。图像处理图像处理计计算算机机图图形形学学模模式式识识别别图图 像像计算几何计算几何特特 征征 数数 据据几几 何何 模模 型型CAD/CAM计算机艺术计算机艺术计算机动画计算机动画计算机视觉计算机视觉o 随着计算科学及其应用的高速发展，用户对软硬件和随着计算科学及其应用的高速发展，用户对软硬件和信息资源共享的需求和一大类问题本身具有地域上分信息资源共享的需求和一大类问题本身具有地

31、域上分布的特点，促进了计算机网络的发展。布的特点，促进了计算机网络的发展。o 所谓所谓计算机网络是使用通信设备和通信线路将一组地计算机网络是使用通信设备和通信线路将一组地理上分布的相同（称为同质）或不同（称为异质）的理上分布的相同（称为同质）或不同（称为异质）的计算机、终端及其附属设备按照某种方式互联起来得计算机、终端及其附属设备按照某种方式互联起来得到的一个计算机硬件系统到的一个计算机硬件系统，也叫网络计算机。在这种，也叫网络计算机。在这种计算机硬件系统的基础上，通过开发能协调各台计算计算机硬件系统的基础上，通过开发能协调各台计算机系统工作的通信系统或更进一步的网络操作系统，机系统工作的通信

32、系统或更进一步的网络操作系统，就能使一组计算机实现软硬件资源共享、协同计算，就能使一组计算机实现软硬件资源共享、协同计算，合作求解一个问题。由这种通信系统或网络操作系统合作求解一个问题。由这种通信系统或网络操作系统连同网络计算机一起，就形成了网络计算机系统。连同网络计算机一起，就形成了网络计算机系统。o 按照数据传输范围和实现技术的不同，计算机网按照数据传输范围和实现技术的不同，计算机网络存在络存在局域计算机网络局域计算机网络和和广域计算机网络广域计算机网络之分。之分。局域计算机网络是一个数据通信系统，其传输范局域计算机网络是一个数据通信系统，其传输范围在中等地理区域，使用中等或高速数据传输速

33、围在中等地理区域，使用中等或高速数据传输速率，使用专用数据通信线或总线进行通信，可联率，使用专用数据通信线或总线进行通信，可联接大量独立设备，在物理通信通道上互相通信。接大量独立设备，在物理通信通道上互相通信。o 广域计算机网络把不同城市、不同国家中的计算广域计算机网络把不同城市、不同国家中的计算机或计算机网络通过分级互联技术联接起来，其机或计算机网络通过分级互联技术联接起来，其传输范围可达到相当远的距离。目前最常见的是传输范围可达到相当远的距离。目前最常见的是使用公用或专用电话线通信，主干网和一些局域使用公用或专用电话线通信，主干网和一些局域网使用可进行数字通信的光纤光缆数据通信专用网使用可

34、进行数字通信的光纤光缆数据通信专用线。线。o 网络互联的拓扑结构是计算机网络的重要特性。网络互联的拓扑结构是计算机网络的重要特性。网络的拓扑结构是一种抽象的由点和线组成的图。网络的拓扑结构是一种抽象的由点和线组成的图。网络上的每台计算机用一个结点表示，机器与机网络上的每台计算机用一个结点表示，机器与机器之间的链路用线和路径表示，于是，图论构成器之间的链路用线和路径表示，于是，图论构成了网络计算机体系结构中一些基本算法研究中数了网络计算机体系结构中一些基本算法研究中数学描述的理论基础。学描述的理论基础。o 网络的结构一般有：主从型、环型、星型、等网络的结构一般有：主从型、环型、星型、等o 支持计

35、算机网络的重要技术是通信，即实现计算支持计算机网络的重要技术是通信，即实现计算机之间信息传输的一种技术方式。网络通信的核机之间信息传输的一种技术方式。网络通信的核心内容是通信协议。所谓通信协议是网络通信中心内容是通信协议。所谓通信协议是网络通信中一组约定的集合，由它确定了经由通信网络传输一组约定的集合，由它确定了经由通信网络传输的信息或存储在报文和数据库中的信息的格式和的信息或存储在报文和数据库中的信息的格式和控制方式。研究通信协议主要是为了在网络计算控制方式。研究通信协议主要是为了在网络计算机系统中实现可靠的、高效的数据交换，差错控机系统中实现可靠的、高效的数据交换，差错控制，信息编码，线路

36、利用，同步，使通信数据具制，信息编码，线路利用，同步，使通信数据具有透明性。有透明性。 网络上连接着大量的计算机系统，每台计算机系网络上连接着大量的计算机系统，每台计算机系统上可能有多个用户在同时使用计算机与其它网上用统上可能有多个用户在同时使用计算机与其它网上用户进行通信，而网络通信线路通常设计成公用资源，户进行通信，而网络通信线路通常设计成公用资源，这样，网络通信为了实现可靠的数据交换，因需要做这样，网络通信为了实现可靠的数据交换，因需要做许多具体的操作运算而变得十分复杂。由于从用户发许多具体的操作运算而变得十分复杂。由于从用户发送或接收可以识别的符号信息到实际在正确的通信线送或接收可以识

37、别的符号信息到实际在正确的通信线路上传递物理信息之间存在转换、线路利用、分组交路上传递物理信息之间存在转换、线路利用、分组交换、差错纠正等一系列的操作，为了便于协议的有效换、差错纠正等一系列的操作，为了便于协议的有效实现和对不同的用户开放，最大限度地实现线路的有实现和对不同的用户开放，最大限度地实现线路的有效利用，有必要对网络计算机系统进行通信结构分层。效利用，有必要对网络计算机系统进行通信结构分层。于是产生了网络协议层。每一层包含一组通信功能和于是产生了网络协议层。每一层包含一组通信功能和相应的层间通信协议，支持通信双方在不同的层间进相应的层间通信协议，支持通信双方在不同的层间进行通信，并提

38、供了实现通信的具体思想和方法。行通信，并提供了实现通信的具体思想和方法。 按照按照ISOISO的建议，网络结构模型是开放系统互连模型的建议，网络结构模型是开放系统互连模型OSIOSI（七层协议），包括物理层，数据链路层，网络层，七层协议），包括物理层，数据链路层，网络层，传输层，会话层，表示层，应用层共七层，产生了七传输层，会话层，表示层，应用层共七层，产生了七层协议。层协议。 开放系统开放系统A A 开放系统开放系统B B 应用层协议应用层协议 应用层应用层 应用层应用层 表示层协议表示层协议 表示层表示层 表示层表示层 会话层协议会话层协议 会话层会话层 会话层会话层 传输层协议传输层协议 传输层传输层 传输层传输层 网络层协议网络层协议 网络层网络层 网络层网络层 数据链路层协议数据链路层协议 数据链路层数据链路层数据链路层数据链路层 物理层协议物理层协议 物理层物理层 物理层物理层 物理传输介质物理传输介质 o 物理层协议实现物理上互连系统间位流信息的透物理层协议实现物理上互连系统间位流信息的透明传输，即实现了一位（组）数据在两个通信实明传输，即实现了一位（组）数据在两个通信实体之间的可靠传送通信，它描述了经通信介质在体之间的可靠传送通信，它描述了经通信介质在数据链路实体之间建立、维护和拆除物理连接。数据链路实体之间建立、维护和拆除物理连接。o