本文为原创和借鉴，只为互相学习

主页:写程序的小王叔叔的博客欢迎来访

支持:点赞收藏关注

社区:JAVA全栈进阶学习社区欢迎加入

计算机系统知识

目录

1.1 计算机系统结构

1.2 计算机中的编码：

1.3 存储器系统：

1.4中央处理器CPU

1.5 输入/输出系统

1.6 计算机总线结构 

1.7 体系结构其他的知识

1.8 计算机的安全、可靠性评价

1.9 数学基础知识

---

1.1计算机系统结构

　计算机的发展历史：
　　 1946年，世界上第一台电子计算机ENIAC出现，之后经历了5个发展阶段： 

冯式结构计算机的组成部分：存储器、运算器、控制器、输入设备和输出设备。
强化的概念：

     计算机的工作过程：一般是由用户使用各种编程语言把所需要完成的任务以程序的形式提交给计算机，然后翻译成计算机能直接执行的机器语言程序，在计算机上运行。

计算机系统可以由下面的模型表示：

计算机系统结构（computer architecture）：指机器语言级机器（物理机器）的系统结构，它主要研究软件、硬件功能分配，确定软件、硬件界面（机器级界面），即从机器语言程序员或编译程序设计者的角度所看到的机器物理系统的抽象。

计算机组成（computer organization）：是指计算机系统的逻辑实现，包括机器内部数据流和控制流的组成以及逻辑设计等，其目标是合理的把各种部件、设备组成计算机，以实现特定的系统结构，同时满足所希望达到的性能价格比。

计算机实现（computer implementation）是指计算机组成的物理实现。

　　这几个概念之间的关系可以用下面的图加以说明：

           
计算机系统的分类：Flynn分类、冯氏分类、Handler分类和Kuck分类； 

Flynn分类：根据不同指令流—数据流组织方式把计算机系统分成4类。（重点理解）

指令流：机器指令的执行序列；

数据流：由指令流调用的数据序列，包括输入数据和中间结果；

多倍性：在系统性能的瓶颈部件上同时处于同样执行阶段的指令和数据的最大可能个数；

I.单指令流单数据流SISD——如单处理机

II.单指令流多数据流SIMD——如相联处理机

III.多指令流单数据流MISD——如流水线计算机

IV.多指令流多数据流MIMD——如多处理机

冯氏分类：以最大并行度Pm把计算机系统结构分为4类，其中字宽W表示在一个字中同时处理的二进制位数，位宽B表示在一个位片中能同时处理的字数。

I.字串位串WSBS（serial）(parallel)

II.字并位串WPBS

III.字串位并WSBP

IV.字并位并WPBP

Handler分类：根据并行度和流水线处理的程度将计算机系统结构分成3个层次

I.    程序控制部件PCU的个数K

II.   算术逻辑部件ALU或处理部件PE的个数D

III.  每个算术逻辑部件包含基本逻辑线路ELC的套数W

Kuck分类：与Flynn分类法类似，根据指令流、执行流和多倍性来分类。

I.    单指令流单执行流SISE——典型的单处理机

II.   单指令流多执行流SIME——带多操作部件的处理机

III.  多指令流单执行流MISE——带指令级多道程序的单处理机

IV.  多指令流多执行流MIME——多处理机

计算机不同级别程序员所见的计算机部分，透明性的概念：

　　透明性：一种实际存在的事物或属性，从某个角度看似乎不存在的现象。

低层机器级的概念结构和功能特性对于高级语言的程序员来说是透明的。

1.2 计算机中的编码：

(1)二进制、十进制和十六进制等常用数制及其相互转换：

  由于计算机的存储器和寄存器是两态部件，所以各种信息在计算机中是以二进制的方式存储和计算的。数制是由基数和基数个不同的数码组成的。

  BCD码：十进制的二进制表示，

  0：0000     1：0001      2：0010      3：0011     4：0100   

 5：0101      6：0110      7：0111      8：1000      9：1001

十进制的202可以表示成BCD码为0010 0000 0010；    

十六进制 二进制:十六进制表示法是用16位二进制数字组成的,每4位二进制数字表示一位十六进制数,十六进制的数字表示从0-9,A,B,C,D,E,F共十六个字符.十六进制与二进制相互转换就是一位十六进制字符与四位二进制数字的相互转换过程.

十进制　　　二进制:十进制向二进制转换分两步进行:首先把该数的整数部分和小数部分转换为二进制数;然后再把这两部分合并起来即可.十进制的整数部分向二进制转换是通过对十进制不断的除2取余数得到，十进制小数部分通过乘2取整的方法获得，直到小数部分为0，所得到的整数部分就形成了二进制编码；同样的，二进制向十进制转换如下所示：

十进制数N=（RnRn-1...R1R0R-1...R-m）

      = Rn *2n+Rn-1*2n-1+...+R1*2+R0+R-1*2-1...R-m*2-m

八进制   二进制:二进制向八进制转换的方法是从小数点开始分别向左右每3位二进制数编成一组,若不够3位 ,则小数点左侧的最高位和右侧的最低位用0补充,每一组用对应的八进制的数码表示即可;八进制向二进制转换的方法是从小数点开始,把每一位八进制的数码转换成对应的3位二进制即可.其小数点左侧的最高位或右侧的最低位的0可以省去.

⑵ 计算机中的二进制数运算方法：

1. 定点数运算：要判断是否溢出？()

 加法：[X+Y]=（[X]补+[Y]补） MOD 2

减法：[X-Y]=（[X]补+[-Y]补）MOD 2

乘法：采用原码比较方便，使用原码一位乘法来求两个定点数的乘积。运算规则为：

n 乘积的符号位等于乘数和被乘数的符号位进异或；

n 乘积的值等于两数绝对值之积，即乘数和被乘数的绝对值进行移位相加；

除法：采用原码比较方便。运算规则为：

商的符号位同定点数原码乘法的处理方法，由两数的符号位进行异或

两数的绝对值部分进行相除。

 2.浮点运算

1) 加减法：

a)对阶    b)尾数进行加、减运算    c)规格化

d)舍入    e)溢出判断

2) 乘除法：

浮点相乘，其积的阶码为两数阶码相加，积的尾数为两尾数相乘。

浮点数相除，其商的阶码为两数阶码之差，商的尾数为两尾数相除。

其结果都需要进行规格化处理，同时还需要进行溢出判断。

⑶ 逻辑代数的基本运算和逻辑表达式的化简：

    逻辑表达式就是以逻辑运算符把若干逻辑变量连接在一起表示某种关系的表达式。一个逻辑函数往往有多种不同的表达式。可以利用其本逻辑运算规律和一些常用的逻辑恒等式对逻辑表达式进行合并项、吸收项、配项、消去项等操作来化简。

基本的逻辑运算有“与”、“或”、“非”、“异或”。

常用的逻辑运算公式：

交换律：A+B=B+A  A*B=B*A

结合律：A+（B+C）=（A+B）+C

分配律：A*（B+C）=A*B+A*C  A+（B*C）=（A+B）*（A+C）

反演律：A+B= A * B

重叠律：A+A=A A*A=A

互补律：A+ A =1 A* A =0

对合律： A =A

0-1律：0+A=A A*A=0

⑷ 定点数与浮点数的机内表示 ：

  定点数的表示方法：

1.  定点整数：（符号位）（最高数据位）。。。（最低数据位）

2.  定点小数：（符号位）小数点（最高数据位）。。。（最低数据位）

浮点数表示方法：

 浮点数编码：符号位-阶码-尾数，阶码由移码表示，尾数由补码或原码表示；

 规格化处理：以纯小数表示尾数，分为原码和补码；

⑸ 原码、补码、反码、移码 ；

   数值数据的机器内表示形式称为机器码，机器码所代表的数值为该机器码的真值。

原码表示：[X]=X或2n-1-X；+0和-0的表示不同；（定点整数）

补码表示：[X]=X或2n+X；（定点整数）

反码表示：[X]=X或(2n-1)+X； （定点整数）

移码表示：[X]=X或2­­­­­­­的(n-1)次方+X；0表示方法唯一10000000  (定点整数)

⑹ ASCII码及汉字编码等常用的编码 ：  

   ASCII码采用7bit编码， 共有128种编码；表示128个不同的字符；计算机里存储和传送单位通常使用Byte，所以7位的ASCII码也用一个字节来表示，最高一位没有用，通常也添0，也可以把它作为校验位或用来扩展字符集。

   EBCDIC码采用8bit编码，共有256个编码，表示256个不同字符；

   汉字编码：

1.数字编码：每个汉字分配一个数字码，用以代表汉字；

2. 拼音码：用每个汉字的汉语拼音符号作为汉字的输入编码；

3.字形码：以汉字的形状特点编码，例如五笔字型编码

汉字存储：以内码形式存放，以连续两个字节表示，两个字节的最高位均为1，汉字的内码是在计算机内处理汉字信息时采用的机内代码，把汉字的输入编码称为外码。

汉字输出：汉字的点阵字型码，点阵的密度决定了汉字的美观程度，汉字需要大量的存储空间，例如16*16点阵，每个汉字要占用16*16=32Byte

  (7) 数据校验码：计算机在存储和传送数据过程中，为了保证数据的准确性，一般都要进行数据校验和纠错。通常使用校验码的方法来检测数据是否出错。其基本思想是把数据可能出现的编码区分为合法编码和错误编码。

使用校验码来查错，涉及到一个重要概念——码距。它是指一个编码系统中任意两个合法编码之间至少有多少个二进制位不同。码距为1的编码是不能发现错误的。

常用的校验码有3种。

▲奇偶校验码：不能发现偶数位错误

该编码通过增加一位校验位来使编码中1的个数为奇数（奇校验）或者为偶数（偶校验）从而使码距变为2，来检测数据代码中奇数出错的编码。因为其利用的是编码中1的个数的奇偶性作为依据，所以不能发现偶数位错误。

校验位的添加方法有三种：

n  水平奇偶校验码：对每个数据的编码添加校验位

n  垂直奇偶校验码：对一组数据的相同位添加一个校验位；

n  水平垂直奇偶校验码：先对一组数据垂直校验，所得结果再添加一位水平校验位；

▲海明校验码：

也是利用奇偶性来检错和纠错，通过在数据之间插入k个校验位，扩大数据编码的码距，从而有能力检测出n位错，并能纠正1位或n位错。

▲循环校验码（CRC）校验码：采用模2运算，可检测所有等于、小于校验位长度的突发错，利用生成多项式为k个数据位产生r个校验位进行编码，其编码长度为n=k+rk,又称为（n，k）码，生成的多项式与被校验的数据无关。

概念：

编码效率=（log2（码字数））/总位数：

例题：在无线电通信中常采用7中取3定比码，它规定码字长为7位，并且其中总有且仅有3个“1”。这种码的编码效率为；35=

举一个例子：关于二进制的编码的考试题目

根据“冗余校验”的思想，码距可用来判断使校验码制冗余的程度，并估价其查错、纠错能力。“8421”码的码距为A ，因而它B 。若一组海明（Hamming）码有效信息位k=4，校验位r=3，则其码距为C ，用它能够发现D位错，并可纠正E位错。

 A、C、D、E：    ①0         ②1         ③2         ④3         ⑤4         ⑥7

 B：  ①能发现1位错   ②能纠正1位错   ③能发现并纠正1位错   ④不能查错、纠错

    本题主要考查数据校验方法的相关知识。

    在这部分知识点中有个很重要的概念——码距。码距是指一个编码系统中任意两个合法编

    这里有个定理，即若一种校验码合法码字集的码矩为2d+1，则它能够发现2d位错，并能纠正d位错

　A: 2   B: 4  C: 4  D: 3  E: 2

1.3存储器系统：

概述：

计算机中的存储系统是用来保存数据和程序的。对存储器最基本的要求就是存储容量要大、存取速度快、成本价格低。为了满足这一要求，提出了多级存储体系结构。一般可分为高速缓冲存储器、主存、外存3个层次，有时候还包括CPU内部的寄存器以及控制存储器。

n 衡量存储器的主要因素：存储器访问速度、存储容量和存储器的价格；

n 存储器的介质：半导体、磁介质和光存储器。

n 存储器的组成：存储芯片+控制电路（存储体+地址寄存器+数据缓冲器+时序控制）；

n 存储体系结构从上层到下层离CPU越来越远、存储量越来越大、每位的价格越来越便宜，而且访问的速度越来越慢

存储器系统分布在计算机各个不同部件的多种存储设备组成，位于CPU内部的寄存器以及用于CU的控制寄存器。内部存储器是可以被处理器直接存取的存储器，又称为主存储器，外部存储器需要通过I/O模块与处理器交换数据，又称为辅助存储器，弥补CPU处理器速度之间的差异还设置了CACHE，容量小但速度极快，位于CPU和主存之间，用于存放CPU正在执行的程序段和所需数据。 

整个计算机的存储器体系结构可以用下面的图来说明：

   

 通常衡量主存容量大小的单位是字节或者字，而外存的容量则用字节来表示。字是存储器组织的基本单元，一个字可以是一个字节，也可以是多个字节。

信息存取方式：信息的存取方式影响到存储信息的组织，常用的有4种，

◆顺序存取

存储器的数据是以记录的形式进行组织，对数据的访问必须按特定的线性顺序进行。磁带存储器的存取方式就是顺序存取。

◆直接存取

共享读写装置，但是每个记录都有一个唯一的地址标识，共享的读写装置可以直接移动到目的数据块所在位置进行访问。因此存取时间也是可变的。磁盘存储器采用的这种方式。

◆随机存取

存储器的每一个可寻址单元都具有唯一地址和读写装置，系统可以在相同的时间内对任意一个存储单元的数据进行访问，而与先前的访问序列无关。主存储器采用的是这种方式。

◆相联存取

也是一种随机存取的形式，但是选择某一单元进行读写是取决于其内容而不是其地址。Cache可能采用该方法进行访问。

衡量存储器系统性能的指标有以下几种：

Ø  存取时间：一次读/写存储器的时间

Ø  存储器带宽：每秒能访问的位数。

Ø  存储器周期：两次相邻的存取之间的时间

Ø  数据传输率：每秒钟数据传输的bit数目。

 主存储器：

主存储器是指能由CPU直接编程访问的存储器，它存放需要执行的程序与需要处理的数据。因为它通常位于所谓主机的范畴，常称为内存。如果内存的地址为n位，容量为2的n次。

主存储器的种类很多，主要有：

Ø  随机存储器（RAM）：可以读出和写入，随机访问存取，断电消失

Ø 只读存储器（ROM）：只能读出原有的内容，不能写入新内容

Ø 可编程ROM（PROM）

Ø 可擦除PROM（EPROM）

Ø 电可擦除PROM（E2PROM）

Ø 闪速存储器（flash memory）

实际的存储器总是由一片或多片存储芯片配以控制电路组成的，其容量往往是W×B来表示。W表示该存储器的存储单元（word）的数量，而B表示每一个word由多少bit组成。

辅助存储器：

由于主存容量有限（受地址位数、成本、速度等因素制约），在大多数计算机系统中设置一级大容量存储器作为对主存的补充与后援。它们位于主机的逻辑范畴之外，常称为外存储器，简称外存。

外存的最大特点是容量大、可靠性高、价格低，主要有两大类。

◆磁表面存储器：这类外存储器主要包括磁带和磁盘存储器。

▲磁带

磁带存储设备是一种顺序存取的设备，存取时间较长，但存储容量大。磁带上的信息是以文件块的形式存放的，而且便于携带，价格便宜。按它的读写方式可分为两种：启停式和数据流。

▲磁盘存储器

磁盘存储器是目前应用最广泛的外存储器。它存取速度较快，具有较大的存储容量，适用于调用较频繁的场合，往往作为主存的直接后援，为虚拟存储提供了物理基础。可分为软盘和硬盘。

◆光存储器

光盘存储器是利用激光束在记录表面存储信息，根据激光束的反射光来读出信息。按照它的记录原理可分为形变型、相变型（晶相结构）和磁光型。有CD、CD-ROM、WORM、EOD等。

CD-ROM：只读光盘，只能一次性写入数据，由生产厂家将数据写入，永远保存

CD-WO：可由用户写入一次，写入后不能修改或擦除，但是可以多次读出

CD-MO：可改写光盘，可以读出也可以写入数据；

光盘存储器的特点：

大容量、标准化、相容性、持久性、实用性

辅助存储器方面的计算：

1.存储容量为capacity=n*t*s*b，n为存放数据的总盘面数；t为每面的磁道数；s为每道的扇区数；b为每个扇区存储的字节数

2.寻道时间为磁头移动到目标磁道所需的时间。

3.等待时间为待读写的扇区旋转到磁头下方所用的时间。一般用磁道旋转一周所用的时

间的一半作为平均等待时间。

4．磁盘存取时间=寻道时间+等待时间。

5．位密度：沿磁道方向，单位长度存储二进制信息的个数；

6．道密度：沿磁盘半径方向，单位长度内磁道的数目；

7. 数据传输速率R=B/T，B为一个磁道上记录的字节数，T为每转一周的时间

8．磁带机的容量计算：（这些公式要熟悉记住）

数据传输率=磁带记录密度*带速；

数据块长度=字节数*块因子/记录密度+块间间隔；

读N条记录所需时间T=启停时间+有效时间+间隔时间；

例题：

假设一个有 3 个盘片的硬盘，共有 4 个记录面，转速为 7200 转/分，盘面有效记录区域的外直径为 30cm，内直径为 lOcm，记录位密度为 250位/mm，磁道密度为 8道/mm，每磁道分16个扇区，每扇区 512字节，则该硬盘的非格式化容量和格式化容量约为__(58)__，数据传输率约为__(58)__若一个文件超出一个磁道容量，剩下的部分__(60)__。

 58：B      59: D      60: B

RAID存储器（廉价磁盘冗余阵列）：基本思想是用多个小的磁盘存储器，通过合理的分布数据，支持多个磁盘同时进行访问，从而改善磁盘存储器的性能。其采用的主要技术：

1．分块技术：把数据分块写到阵列中的磁盘上；

2．交叉技术：对分布式的数据采用交叉式进行读写，提高访问速度；

3．重聚技术：对多个磁盘空间重新编址，数据按照编址后的空间存放；

主要特点如下：

1．物理上多个磁盘，但操作系统看是一个逻辑磁盘；

2．数据分布在磁盘阵列中的磁盘存储器上；

3．采用冗余技术和校验技术提高可靠性，可恢复数据；

4．RAID速度快、容量大、功耗低、价格便宜、容易扩展。

RAID0：无冗余、无校验，具有最高的I/O性能和最高的磁盘空间利用率

RAID1：磁盘镜像、磁盘利用率50%，具有最高的安全性

RAID2：海明码纠错、数据分块、并行访问、适合大批量数据、已很少使用

RAID3：奇偶校验、数据分块、并行访问、单独校验盘

RAID4：奇偶校验、独立存取、单独校验盘、适合访问频繁、传输率低

RAID5：独立存取、无单独校验盘、适合访问频繁、传输率低

Cache存储器：（对系统和应用程序员都是透明的）（重点）

Cache位于主存储器与CPU通用寄存器组之间，全部由硬件来调度，用于提高CPU的数据I/O效率，对程序员和系统程序员都是透明的。Cache容量小但速度快，它在计算机的存储体系中是访问速度最快的层次。

       使用Cache改善系统性能的依据是程序的局部性原理，即程序的地址访问流有很强的时序相关性，未来的访问模式与最近已发生的访问模式相似。根据这一局部性原理，把主存储器中访问概率最高的内容存放在Cache中，当CPU需要读取数据时就首先在Cache中查找是否有所需内容，如果有则直接从Cache中读取；若没有再从主存中读取该数据，然后同时送往CPU和Cache。

       系统的平均存储周期t3与命中率h有很密切的关系，如下的公式：t3=h×t1+(1-h)×t2

       其中，t1表示Cache的周期时间，t2表示主存的周期时间。

当CPU发出访存请求后，存储器地址先被送到Cache控制器以确定数据是否已在Cache中，若命中则直接对Cache进行访问，否则直接进行主存访问。

Cache的地址映射是指把主存地址空间映射到Cache地址空间，Cache和主存都使用同样大小的块为单位。Cache中常见的映射方法有三种。

Ø  直接映射：一对一,(不需要替换算法)

Ø  全相联映射：多对多

Ø  组相联映射：将块划分成组，主存中的一组与Cache相对应，根据高位地址标志符来访问数据，组相联可以允许相同的Block和word标志，而tag标志不同。

随着程序的执行，访问频繁地区将逐渐迁移，Cache中的内容逐渐变得陈旧，访问命中率下降，就需要更新内容。常用的替换算法有三种。

Ø   随机淘汰法：

Ø   先进先出法FIFO：

Ø   近期最少使用法LRU：

对于这个算法可以从整体上把握，每个的优点、缺点，不需要记算法的过程。

另外，为了保证环存在Cache中得数据与主存中的内容一致，对写操作来说有以下几种方法：

Ø   写直达：同时

Ø   写回：

Ø  标记法

例题：

● 一般来说，Cache 的功能__(53)__。某 32 位计算机的 cache 容量为 16KB，cache 块的大小为16B，若主存与 cache 的地址映射采用直接映射方式，则主存地址为 1234E8F8（十六进制）的单元装入的 cache地址为__(54)__。在下列 cache 替换算法中，平均命中率最高的是__(55)__。

        53) A.全部由软件实现

            B.全部由硬件实现

            C.由硬件和软件相结合实现

            D.有的计算机由硬件实现，有的计算机由软件实现

       (54) A. 00 0100 0100 1101 (二进制)

            B. 01 0010 0011 0100 (二进制)

            C. 10 1000 1111 1000 (二进制)

            D. 11 0100 1110 1000 (二进制)

       (55) A.先入后出（FILO）算法

            B.随机替换（RAND）算法

            C.先入先出（FIFO）算法

            D.近期最少使用（LRU）算法

虚拟存储器：（重点）（对应用程序员透明）

虚拟存储系统的作用是给程序员一个更大的虚拟的存储空间，其容量可远远超过主存储器的容量，而与辅助存储器容量相当。

我们提供给用户的这个存储器，即在软件编程上可以使用的存储器，就称为虚拟存储器。它的容量即虚拟存储空间，简称虚拟空间。面向虚拟存储器的编程地址称为虚拟地址，或称为逻辑地址。与主存和辅助存储器地址相对应。

为了实现虚拟存储器，需将虚拟存储空间与物理实存空间，按一定的格式分区组织管理，根据管理的方式不同可以分为三种虚拟存储器：页式、段式和段页式。

Ø 页式管理：  Ø 段式管理：   Ø  段页式管理：

此外可以增加一个小容量的高速存储器实现一种快表查询，而快表和慢表也构成了两级存储器系统

另外，与Cache一样，虚拟存储器系统还需采用一定的调度策略实现主存内容的变换，使当前需要的程序和数据都在主存之中。常用的淘汰算法有：

Ø  FIFO算法：选择最先进入主存的页面淘汰

Ø  LRU算法：选择在最近一段时间内访问频率最低的页面淘汰

1.4中央处理器CPU

  CPU由寄存器组、算术逻辑单元ALU和控制单元CU这3部分组成。

CPU的功能：

Ø   读取指令   Ø   解释指令   Ø  读取数据    Ø  处理数据    Ø   保存数据

1. 寄存器组分为两大类：

Ø  用户可见的寄存器，有通用寄存器、数据寄存器、地址寄存器、标志寄存器等；

Ø 状态寄存器，包括程序计数器PC、指令寄存器IR、存储器地址寄存器MAR、存储器缓冲寄存器MBR、程序状态字PSW。

2.运算器ALU：负责对数据进行算术和逻辑运算。

3.控制器CU：负责控制整个计算机系统的运行，读取指令寄存器、状态控制寄存器以及外部来的控制信号，发布外控制信号控制CPU与存储器、I/O设备进行数据交换；发布内控制信号控制寄存器间的数据交换；控制ALU完成指定的运算功能；管理其他的CPU内部操作。

  控制器的实现有硬布线逻辑和微程序控制两种方案

中断控制机制：

计算机系统通常提供了中断机制，允许某一事件中止CPU正在执行的程序，转去对该事件进行处理，然后再返回原程序被中止处继续执行。其作用是提高CPU的处理效率，使CPU与I/O设备并行工作，还可以实现分时操作过程。

中断处理过程可分为：中断响应过程和中断服务过程。

中断的分类：按中断源位置可分为内部中断和外部中断；

按中断源的类型可分为硬件中断和软件中断；

按中断源的屏蔽特性可分为可屏蔽中断和不可屏蔽中断。

CPU处理中断有两种策略：中断排队和中断嵌套。

计算机的指令系统：

机器指令的格式、分类及功能:

CPU所完成的操作是由其执行的指令来决定的，这些指令被称为机器指令。

CPU所能执行的所有机器指令的集合称为该CPU的指令系统。

机器指令一般由操作码、源操作数、目的操作数和下一条指令的地址组成。

Ø   操作码指明要执行的操作；

Ø   源操作数是该操作的输入数据；

Ø  目的操作数是该操作的输出数据；

Ø  下一条指令地址通知CPU到该地址去取下一条将执行的指令。

指令系统可分为数据传送类、算术运算类、逻辑类、数据变换类、输入/输出类、系统控制类、控制权转移类等类型。

指令的寻址方式

常用的寻址方式：有立即数寻址、直接寻址、间接寻址、

   寄存器寻址、基址寻址、变址寻址、相对寻址。

指令的执行过程

1.计算下一条要执行的指令的地址；

2.从该地址读取指令；

3.对指令译码以确定其所要实现的功能；

4.计算操作数的地址；

5.从该地址读取操作数；

6.执行操作；

7.保存结果；

1.5 输入/输出系统

I/O系统在CPU、存储器和各种外部设备之间负责协调和控制数据的输入/输出。

I/O系统控制器基本结构：

n  数据寄存器：

n  状态寄存器：

n  控制寄存器：

n  控制电路：

n  外设接口控制：

I/O系统的工作方式：

Ø 程序控制：CPU完全控制，CPU必须时时查询I/O设备的状态；

Ø 程序中断：I/O设备以中断方式通知CPU，定期查询状态

Ø  DMA方式：CPU只在数据传输前和完成后才介入

I/O系统的发展主要阶段：

Ø 数据通信：CPU直接控制外设；

Ø 程序控制：CPU不关心外设的具体细节，I/O增加了数据交换的功能；

Ø 中断方式：中断机制减少了CPU的等待时间，

Ø DMA方式：暂停、周期窃取、共享方式

Ø 输入输出通道：专门的处理器控制I/O功能；

Ø 输入输出处理机：不仅拥有处理器，还有本地存储器

根据外部设备和I/O系统交换数据方式，设备接口可分为串行和并行接口。

常见的磁盘设备接口有：总线、DMA、通道、SCSI、并行口、RS232C、USB、IEEE1394

SCSI接口：并行接口；系统级的设备接口

P1394接口：高速串行总线，数据传输率高，价格低容易实现

I/O设备的类型和特性：

键盘：标准101键，主要作为字符、数字和汉字的输入

鼠标：坐标定位部件，有机械式、光电式和混合式三种。

显示器：输出设备，输出图象和字符，性能参数是分辨率和灰度级

打印机：输出设备，分击打式和非击打式打印机

扫描仪：图象输入设备，扫描图象或文本成数字图片，然后输入计算机处理

摄像头：图象输入设备图象数字化后存入到磁盘。

例题：

为了快速传送大量数据，微型计算机中采用存储器直接访问技术，简称DMA。用DMA方式传送时，在存储器和A之间直接建立高速传输数据的通路，不需要B的干预。利用DMA方式传送数据时，数据的传送过程完全由成为DMA控制器的硬件控制。DMA控制器具有如下功能：

1)  向CPU申请C传送。

2)   在CPU允许DMA工作时，处理总线控制的传交。

3)   在DMA期间管理D，控制数据传送。

4)  确定数据传送的起始地址和E ，并在传送过程中不断修正。

5)  数据传送结束时，给出表示DMA操作完成的信号。

       A~E：  ①控制台       ②硬件         ③外部设备       ④数据长度    ⑤CPU        

                    ⑥存储器       ⑦DMA         ⑧系统总线      ⑨数据方向    ⑩传输速率

[分析]

 DMA（Direct Memory Access，直接存储器访问）是一种不需要CPU干预，在存储器和外部设备之间直接通过系统总线高速传输数据的方法。DMA方法使用DMA控制器DMAC来控制和管理数据传输。

[答案]

A：③    B：⑤   C：⑦   D：⑧    E：④

1.6 计算机总线结构 

  总线：一种连接多个设备的信息传递通道。

典型的计算机总线结构由内部总和外部总线组成。

Ø  内部总线用于连接CPU内部各个模块；

Ø  外部总线用于连接CPU、存储器和I/O系统，又称为系统总线。

系统总线：可分为 数据总线、地址总线、控制总线3类。 

数据总线：各个模块间传送数据的通道； 

地址总线：传递地址信息，来指示数据总线上的数据的来源或去向，CPU根据地址信息从相应的存储单元读出数据或向该存储单元写入数据； 

控制总线：控制数据总线和地址总线。

多层总线结构：大多数计算机系统都使用多总线体系结构进行互联。它的优点就在于根据各个部件对数据传输率的不同要求，用不同层次的总线进行互联，以适应各自的特性与需求，不同层次目的总线相对独立，允许使用不同的信号和以不同的速率运行。对某一层次总线结构的修改不会影响其他层次的总线结构。

常用的微机总线：ISA（工业标准体系结构）、EISA（扩展ISA）、

 VESA、PCI（外围元件互联结构）总线。

例题：

某系统总线的一个总线周期包含3个时钟周期，每个总线周期中可以传送32位数据。若总线的时钟频率为33MHz，则总线带宽为 (55) 。

            (55) A．132MB/s     B．33MB/s     C．44MB/s     D．396MB/s

1.7 体系结构其他的知识

 1．流水线技术

流水线技术其实是通过并行硬件来提高系统性能的常用方法，其基本思想在冯·诺依曼第一台存储程序计算机中已经提出。

流水线技术的基本原理实际上是一种任务分解的技术。把一件任务分解成若干顺序执行的子任务，不同的子任务由不同的执行机构负责执行，而这些机构可以同时并行的工作。在任一时刻，任一任务只占用其中一个执行机构，这样就可以实现多个任务的重叠执行，以提高工作效率。

流水线技术包括指令流水线和运算操作流水线。需要注意的是，对流水线技术而言，其对性能的提高程度取决于其执行顺序中最慢的一步。

在实际情况中，流水线各个阶段可能会相互影响，阻塞流水线，使其性能下降。影响流水线性能的主要因素有两个：执行转移指令和共享资源冲突。

在实际处理中，为了使流水线能维持最大的吞吐率，同时确保流水线各段不会产生冲突，就需要对流水线进行很好的控制。一般采用预留表来预测冲突。预留表是从流水线设计直接推导出来的，表中列出的是流水线上各个部件操作的时间信息，每一行代表流水线中的一段，而每一列则代表一个时间步。

    流水线周期：

另外，流水线计算机处理中断的方法通常有两种。

Ø  不精确断点法

Ø   精确断点法

 2．RISC技术

RISC（reduced instruction set computer）即精简指令集计算机，它的主要特点是CPU的指令集大大简化，从而减少指令的执行周期数，提高运算速度。

一般来说，CPU的执行速度受三个因素的影响：

Ø  程序中的指令数I

Ø  每条指令执行所需的周期数CPI

Ø   每个周期的时间T

它们之间的关系可表示为：程序执行时间=I*CPI*T

与CISC（复杂指令集系统）相比，RISC具有以下的特点。

CISC	RISC
1)指令数量众多 2)指令使用频率相差悬殊 3)支持很多种寻址方式 4)变长的指令格式 5)指令可以对存储器中数据直接进行处理	1) 指令数量少 2) 指令的寻址方式少 3) 指令长度固定 4) 只提供了Load/Store指令访问存储器 5) 以硬布线逻辑控制为主 6) 单周期指令执行 7) 拥有相当多的寄存器 8) 优化的编译器

RISC采用窗口重叠技术完成寄存器的组织和参数的传递，对于RISC的流水线的处理是采用延迟转移的方法解决流水线阻塞和互锁。

另外，采用RISC技术的CPU硬件一般具有寄存器数量多、采用流水线组织、控制器的实现采用硬布线逻辑电路等特点。

3．并行处理技术

并行性（parallelism）就是指在同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的工作，只要时间上相互重叠，就都蕴含了并行性。并行性有两重含义：

Ø   同时性（simultaneity）：两个或两个以上事件在同一时刻发生

Ø   并发性（concurrency）：两个或两个以上事件在同一时间间隔内发生

 并行性有不同的层次，从不同的角度看其层次结构也不一样。

程序执行的并行性

Ø   指令内部并行：一条指令内的微操作之间的并行；

Ø   指令间并行：多条指令的并行执行；

Ø   任务或进程并行：软件的进程任务分解

Ø   作业或程序并行：软件和硬件的分配

数据处理的并行性

Ø   位串字串：一次只对一个字的一位进行处理

Ø  位并字串

Ø   位串字并

Ø   位并字并（全并行）

操作并行性

Ø 存储器操作并行：多个存储单元同时被访问

Ø  处理器操作步骤并行：指令的执行步骤重叠

Ø   处理器操作并行：大量的处理单元按同一指令对多个数据操作；

 提高计算机系统并行性的措施主要有3类。

◆时间重叠

         在并行性概念中导入时间因素，让多个处理过程在时间上错开，轮流重叠的使用同一套硬件设备的各个部件，以加快硬件周转，提高处理速度。

◆资源重复

在并行性概念中导入空间因素，基于“以数量取胜”的原则，通过重复设置硬件资源来提高系统可靠性或性能。

◆资源共享

多个用户按一定时间顺序轮流的使用同一套资源，以提高其利用率，从而相应的提高整个系统的性能。

并行处理机（也称为阵列处理机）使用按地址访问的RAM，以SIMD方式工作，主要用于要求大量高速进行向量或矩阵运算的应用领域。并行处理机的并行性来源于资源重复，它依靠操作级的并行处理来提高系统性能。

根据存储器的不同组织形式，并行处理机有两种典型的结构。

Ø  具有分布式存储器的并行处理机

Ø   具有集中共享存储器的并行处理机

并行性处理机的特点：

Ø  强大的向量运算能力

Ø   并行方式

Ø   适用于专门领域，如矩阵运算、向量运算

Ø   标量运算速度对系统性能的影响也很明显

Ø   具有向量化功能的高级语言编译程序有助于提高并行处理机的通用性，以及减少编译时间

例题：

利用并行处理技术可以缩短计算机的处理时间,所谓并行性是指__(51)__。可以采用多种措施来提高计算机系统的并行性,它们可分成三类,即__(52)__。

提供专门用途的一类并行处理机(亦称阵列处理机)以__(53)__方式工作,它适用于__(54)__。多处理机是目前较高性能计算机的基本结构,它的并行任务的派生是__(55)__。

(51):A.多道程序工作                    B.多用户工作

       C.非单指令流单数据流方式工作      D.在同一时间完成两种或两种以上工作

(52):A.多处理机,多级存储器和互连网络   B.流水结构,高速缓存和精简指令集

       C.微指令,虚拟存储和I/O通道        D.资源重复,资源共享和时间重叠。

(53):A.SISD         B.SIMD         C.MISD         D.MB4D

(54):A.事务处理     B.工业控制     C.矩阵运算     D.大量浮点计算

(55):A.需要专门的指令来表示程序中并发关系和控制并发执行

       B.靠指令本身就可以启动多个处理单元并行工作

       C.只执行没有并发约束关系的程序

       D.先并行执行,事后再用专门程序去解决并发约束

51：D 52: D 53: B 54: C 55: A

 4．多处理机

多处理机具有两个或两个以上的处理机，共享输入/输出子系统，在统一的操作系统控制下，通过共享主存或高速通信网络进行通信，协同求解一个大而复杂的问题。

多处理机通过利用多台处理机进行多任务处理来提高速度，利用系统的重组能力来提高可靠性、适应性和可用性。多处理机是新一代计算机结构的基本特征。

多处理机具有共享存储器和分布存储器两种不同的结构。

    多处理机属于MIMD系统，与SIMD的并行处理机相比有很大差异。其根源在于两者的并行性等层次不同，多处理机要实现的是更高一层的作业任务间的并行。

大规模并行处理机MPP是由众多的微处理器组成的大规模并行处理系统。对称多处理机SMP与MPP最大的差别在于存储系统，SMP有一个统一的共享主存空间，而MPP则每个微处理器都拥有自己本地存储器。

MPP和SMP都是基于RISC处理器的。

1.8 计算机的安全、可靠性评价

安全与保密

   数据加密即是对明文（未经加密的数据）按照某种的加密算法（数据的变换算法）进行处理，而形成难以理解的密文（经加密后的数据）。这是计算机安全中最重要的技术措施之一。

数据加密和解密是一对可逆的过程，其关键在于密钥的管理和加密/解密算法。通常加密/解密算法的设计需要满足3个条件：

Ø 可逆性

Ø  密钥安全

Ø   数据安全

按照加密密钥K1和解密密钥K2的异同，分为两种密钥体制，比较如下：

密钥体制	特点	典型算法
秘密密钥加密体制（K1=K2）或对称密钥体制	1. 加密与解密采用相同密钥 2. 加密速度快，通常用于加密大批量的数据	1.日本NTT的快速加密标准FEAL 2.瑞士的国际数据加密算法IDEA 3.美国的数据加密标准DES
公开密钥加密体制（K1≠K2）或不对称密钥体制	1.加密和解密使用不同的密钥，其中一个公开，另一个是保密的 2.加密速度较慢，往往用在少量数据的通信中	1. RSA算法 2. NTT的ESIGN

 数据完整性保护是数据中加入一定的冗余信息，从而能发现对数据的任何修改、增加或删除。

   在某些商业或金融领域经常需要一种“数字签名”的技术，防止通信的一方否认或伪造通信内容。数字签名是利用密码技术进行的，其安全性取决于密码体制的安全程度。它的目的是在保证真实的发送方和真实的接受方之间传送真实的信息。

数字签名有两个特点：

Ø         动态变化，随着密钥和数据的不同而不同

Ø         签名和数据不可分离

数据加密的安全性在很大程度上取决于密钥的安全性。

对于密钥的管理主要包括以下几个方面：

Ø         密钥体制的选择

Ø         密钥的分发

Ø         现场密钥保护

Ø         密钥的销毁

例题：

常规的数据加密标准DES采用__(l)__位。有效密钥对____(2)__位的数据块进行加密。

 1．A    2. B

计算机可靠性、可用性和可维护性（computer reliability、availability and serviceability ,RAS）技术和容错技术是研究、设计、生产、评价计算机系统的重要内容。

计算机可靠性

计算机系统的可靠性是指从它开始运行（t=0）到某个时刻t这段时间内能正常运行的概率，用R（t）表示。失效率则是指单位时间内失效的元件数与元件总数的比例，以λ表示。当为λ常数时，可靠性与失效率的关系为：

R（t）=

 两次故障之间系统能正常工作的时间的平均值称为平均无故障时间：MTBF=1/λ

    通常用平均修复时间（MTRF）来表示计算机的可维修性，即计算机的维修效率，指从故障发生到机器修复平均所需要的时间。计算机的可用性是指计算机的使用效率，它以系统到执行任务的任意时刻能正常工作的概率A来表示：

A=MTBF/（MTBF+MTRF）

    计算机的RAS技术，就是指用可靠性R、可用性A和可维修性S三个指标来衡量一个计算机系统。

    常见的计算机系统可靠性数学模型有3种。

  串联系统：

该系统由N个子系统组成，当且仅当所有的子系统都能正常工作时，系统才能正常工作。整个系统的可靠性R和失效率λ分别为：

可靠性：R=R1R2…Rn

失效率：λ=λ1+λ2+…+λn

  并联系统：

该系统由N个子系统组成，只要有一个子系统正常工作，系统就能正常运行。整个系统的可靠性R和失效率μ分别为：

可靠性：R=1-(1- R1)(1-R2)…(1- Rn)

失效率：

   N模冗余系统：

该系统由N个（N=2n+1）相同的子系统和一个表决器组成，表决器把N个子系统中占多数相同结果的输出作为系统的输出。N模冗余系统的可靠性为：

可靠性：（其中表示从N个元素中取j个元素的组合数）

计算机可用性： 是指该系统在某一时刻提供有效使用的程度，以可用度A表示，可用度是在任意指定时刻系统能正确运行的概率。一般情况下，系统发生故障是可以修复的，，可用下列公式计算：A=MTBF/（MTBF+MTTR），其中MTBF为平均无故障时间，MTTR是平均修复时间。平均修复时间是指多次故障中，从开始失效到系统修复所用的平均时间，可用下式计算：

系统修复时间=申请维修时间+等待时间+维修时间+恢复时间

提高计算机可用性的途径是：提高计算机可靠性；提高计算机的可维护性，完善故障诊断与测试技术以及系统恢复和部件更换技术；提高维护人员的素质。

计算机可维护性：是指系统失效后在规定时间内可修复到规定功能的能力，参数修复率和平均修复时间MTTR。

故障诊断与容错：容错是指计算机系统在运行过程中发生一定的硬件故障或软件故障时仍能保持正常工作而不影响正确结果的一种性能或措施。

计算机的故障根据表现特点可以分为三类。

Ø         永久性故障：表现出稳定性和持续性，特点是故障可重复出现。

Ø         间歇性故障：表现出不稳定性和对系统状态的依赖性

Ø         瞬时性故障：偶然原因引起的短暂故障

Ø         软件故障：来源于程序错误

故障诊断包括故障检测和故障定位两个方面。通常，故障诊断的主要方法有三种：

Ø         对电路直接进行测试的故障定位测试法

Ø         “检查诊断程序”法

Ø         微诊断法

容错是采用冗余方法来消除故障影响。针对硬件，有时间冗余和元器件冗余两种方法。主要的容错技术有简单的双机备份和操作系统支持的双机容错。

计算机性能评价：

计算机性能评测是为了一定目的、按照一定步骤、选用一定的度量项目通过建模、计算和实验，对计算机性能进行测试并对测试结果作出评价的技术。

计算机性能评测的度量项目：

n          性能指标：

Ø         工作量类，吞吐率、指令执行速率和数据处理速率；

Ø         响应性类：响应时间

Ø         利用率： 资源利用率

n          可靠性、可用性和可维护性

n          环境适应性

n          兼容性和开放性

n          可扩充性

n          安全性

n          性能价格比

计算机性能评估的常用方法主要有：

Ø         时钟频率和指令执行速度：可用于比较和评价同一系统上求解同一问题的不同算法的性能。

Ø         等效指令速度法：通过各种指令在程序中所占的比例进行计算得到的

Ø         核心程序法：

Ø         数据处理速率： 主要对CPU和主存数据处理速度进行计算得出的

基准程序法（benchmark）是目前一致承认的测试性能较好方法，有多种多样的基准程序。

Ø         整数测试程序

Ø         浮点测试程序

Ø         SPEC基准程序

Ø         TPC基准程序

1.9 数学基础知识

1.9.1命题逻辑的基础知识

1. 命题

     命题表述为具有确定真假意义的陈述句。

命题必须具备二个条件：

其一，语句是陈述句；

其二，语句有唯一确定的真假意义。

2. 联结词   

3. 命题公式、永真性的判定或命题公式的分类

h命题公式与赋值，命题P含有n个命题变项P1，P2,…,Pn，给P1，P2,…,Pn各指定一个真值0或1，称为对P的一个赋值(真值指派)。 若指定的一组值使P的值为1，则这组值为P的真指派；若使P的值为0，则称这组值称为P的假指派。

h命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；

判定命题公式类型的方法：其一是真值表法，对于任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式。 其二是推导法。 利用基本等值式(双重否定律、幂等律、交换律、结合律、分配律、吸收律、摩根律、同一律、零律、否定律、蕴含等值式、等价等值式、假言易位和等价否定等值式等)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式。

h定理1：设F(A)是含命题公式A的命题，F(B)是用命题公式B置换F(A)中的A之后得到的命题公式。 如果AÛB，则F(A)ÛF(B)。

4. 范式

h 析取(合取)范式，仅有有限个简单合取式(合取式)构成的析取式(合取式)，就是析取(合取)范式。

h 极小项(极大项),，n个命题变项，每个变项与它的否定不同时出现，但是两者必须出现且仅出现一次，而且第i个命题变项或者其否定出现在从左算起第i个位置上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项)。

     极小项是n个变项的合取,m00=ØPØÙQ，m01=ØPÙQ,…; 极大项是n个变项的析取,M00=PÙQ，M01=PØÙQ,…;

h 主析取范式(主合取范式)，对于含有n个命题变项的命题公式如果有一个仅有极小项(极大项)的析取(合取)构成的等式，则该等式为原命题公式的主析取范式(主合取范式)。

     每项含有n个命题变项(变项字母齐全)合取式(析取式)的析取(合取)为主析取(主合取)范式。

     任意命题公式都存在与之等值的析取范式和合取范式，与之等值的主析取范式和主合取范式是惟一的。

     求范式，包括求析取范式、合取范式、主析取范式和主合取范式。 关键有两点：

其一是准确掌握范式定义；

其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律。 

求析取(合取)范式的步骤：

① 将公式中的联结词都化成Ø，Ù，Ú(在析取(合取)范式中不能有联结词®，«，Ú`)；

② 将否定联结词Ø消去或移到各命题变项之前；

③ 利用分配律、结合律等，将公式化为析取(合取)范式。

求命题公式A的主析取(合取)范式的步骤

① 求公式A的析取(合取)范式；

② “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如PØÙP(PØÚP)用0(1)替代。 用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如PÙP(PÚP)用P替代，miÚmi(MiÙMi)用mi(Mi)替代。

③ 若析取(合取)范式的某个合取项(析取项)B不含有命题变项Pi或ØPi，则添加PiØÚPi(PiØÙPi)，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全；

④ 将极小(极大)项按由小到大的顺序排列，用S(P)表示。

5. 命题演算的推理理论

     掌握演绎或形式证明。 要理解并掌握14个重言蕴含式(即I1～I14)，17个等值式(E1～E17)；二是会使用三个规则(P规则、T规则和CP规则)。

1.9.2 谓词逻辑、形式逻辑基础知识

1．谓词概念：用以刻画客体的性质或关系的词；

    用谓词表达命题必须包括两个部分：客体和谓词字母，其中客体表示的是对象而谓词字母表示的是客体之间的关系。可以分为一元谓词，记作A(b)，二元谓词，记作B(a ,b)等等。

单独一个谓词不是一个完整的命题，把谓词字母后填以客体所得的式子称为谓词填式。

2．命题函数：一个谓词，一些客体变元组成的表达式称为简单命题函数，有0元和n元命题函数。

   量词：分为全称量词和存在量词

全称量词："x读作‘对任意x’， "xP(x)表示‘对一切x,P(x)为真’

          ┐"x┐P(x)表示，‘并非对任意x, ┐P(x)是真’

存在量词：$x读作‘至少有一x’，‘存在一x’

        $x ┐P(x)表示，‘存在一x，使┐P(x) 为真’

                ┐$x ┐P(x)表示，‘并非存在一个x，使P(x)为真’

  任意谓词中任意个体变元的所有个体域称全总个体域

注：使用全总个体域后，个体变元取值范围一致。

        但不同论述对象须用不同的特性谓词加以刻划。

个体词：

个体域：

3．不出现命题联结词和量词的谓词命名式P(X1, X2…Xn)称为谓词演算的原子公式。

   谓词演算的合式公式简称谓词公式，定义如下：

    1)谓词演算的原子公式是谓词演算公式        

2)若A， B是谓词演算公式，则

(┐A)，(AÙB)，(AÚB)，(A→B)，(A«B)，

("XA)和($XA)是谓词演算公式

3)只有有限次应用步骤1）和2）构成的公式才是谓词演算公式

4．自由变元与约束变元：

   定义：在量词"X，$X辖域内变元X的一切出现叫约束出现，称这样的X为约束变元。

   变元的非约束出现称为自由出现,称这样的变元为自由变元。

谓词演算的永真公式：对公式A和B中的谓词变元（包括命题变元），指派任一在E上有定义的确定的谓词，指派E中任一确定的个体，若所得命题有相同的真值，称在E上AÛB。

例如：1."XP(X)→$XR(X)Û ┐"XP(X) Ú $XR(X)

2．"XA Û A $XA Û A 这里A不含自由变元X

3．a."XP(X) ÞP(Y)或"XP(X) ÞP(X)

       b.P(Y) Þ$X P(X)或P(X) P(X)

       c."XP(X) Þ$XP(X)  

4.a."XA(X)ÚP Û"X(A(X)ÚP)

b."XA(X)ÙP Û"X(A(X)ÙP)

c.$XA(X)ÚP Û$X(A(X)ÚP)

d.$XA(X)ÙP Û$X(A(X)ÙP)

5．前束范式：量词均在谓词公式开头，作用域延伸到整个谓词公式末尾的谓词公式称为前束范式。

例1："x"y$z(Q(x，y) →R(z))

例2："x"y(┐P(x，y) →Q(y))

例1把"x"y(┐($zP((x,y,z) ÙP(y,z)))→$uQ(x,y,u))化为前束范式。

解：原式

Û"x"y(┐($z(P(x，z) ÙP(y，z)) Ú$uQ(x，y，u))

Û"x"y("z(┐P(x，z) Ú┐P(y，z)) Ú$uQ(x，y，u))        

Û"x"y"z$u(┐P(x，y) Ú┐P(y，z) ÚQ(x，y，u))

定义：若谓词公式是前束范式且作用域为合取范式,则称为前束合取范式。

  前束合取范式形式:(□u1)(□u2)…..(□un)((A11Ú………ÚA1m1) Ù…Ù (An1Ú…. ÚAnmn))

定义：若谓词公式是前束范式且作用域为析取范式,则称为前束析取范式。

前束析取范式形式:

(□u1)(□u2)…..(□un)((A11Ù………ÙA1m1) Ú…  Ú (An1Ù…….. ÙAnmn))

6．推理规则与推理理论：

命题演算中的所有推理规则都是谓词演算中的推理规则，谓词演算的所有永真式也是谓词推理规则。

四条重要的推理规则

   1.全称指定规则，简记为US：对一切x，P(x)为真,可推得任意一个确定的c，使P(c)为真。

   2.存在指定规则，简记为EG：至少存在一个x使得A(x)为真.即可推得有一个确定的c,使P(c)为真。

   3.存在推广规则，简记为EG：c是某个确定的个体,若P(c)为真,则$x P(x)为真注意：c不能出现在P(c)中的x的辖域中

   4.全称推广规则，简记为UG：若对个体域中每一个客体c，P(c)断言为真则"x P(x)为真

1.9.3排列组合、概率论应用、应用统计

排列组合：

【复习基本原理】

1.加法原理   做一件事，完成它可以有n类办法，第一类办法中有m1种不同的方法，第二办法中有m2种不同的方法……，第n办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+…mn   种不同的方法.

2.乘法原理   做一件事，完成它需要分成n个步骤，做第一 步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，.那么完成这件事共有 N=m1´m2´m3´…´mn 种不同的方法.

3.两个原理的区别   一个与分类有关，一个与分步有关.

【原理浅释】

1.      进行分类时，要求各类办法彼此之间是相互排斥的，不论那一类办法中的哪一种方法，都能独立完成这件事.只有满足这个条件，才能直接用加法原理，否则不可以.

2.      如果完成一件事需要分成几个步骤，各步骤都不可缺少，需要依次完成所有步骤才能完成这件事，而各步要求相互独立，即相对于前一步的每一种方法，下一步都有m种不同的方法，那么完成这件事的方法数就可以直接用乘法原理.

【基本概念】

1.      什么叫排列？从n个不同元素中，任取m()个元素（这里的被取元素各不相同）按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列

2.      什么叫不同的排列？元素和顺序至少有一个不同.

3.      什么叫相同的排列？元素和顺序都相同的排列.

【排列数】

1.      定义：从n个不同元素中，任取m()个元素的所有排列的个数叫做从n个元素中取出m元素的排列数，用符号表示. 

用符号表示上述各题中的排列数.

2.      排列数公式：=n(n-1)(n-2)…(n-m+1) 

概率论应用：

随机事件：试验的某种结果，事前不能确定，事后可观察到是否发生，简称事件（是个判断句）以A、B、C…等表示。

基本事件：不能再分解的“最简单”的事件，试验中各种最基本的可能结果。

必然事件：试验中必然发生的事件。

不可能事件：试验中不可能发生的事件，是一个空集。

概率即可能性大小：事件A的概率记为P（A）

古典概型的概率很容易计算：

 概率的统计观点

⑴ 从概率的来源看，概率取值需要有统计的支撑

⑵ 从概率值对实践的指导意义看，也需要面对统计的过程

小概率原理：

当概率很大（超过0.9）或很小（小于0.1）时，对一次试验是有指导意义的。可以认为小概率事件在一次试验中基本上不会发生，这就是小概率原理。（试验次数多时，就不适用了，概率再小，也有可能发生。比如飞机失事的报道很多，但是人们仍然向往着坐飞机出行，又比如人们在做决策时，有90%以上的把握，都会断言“不出意外的话肯定成功”不过应当指出的是：小概率原理不能保证没有风险，以概率的观点看问题，凡有随机因素，便不可能有绝对的把握，对此要有清醒的认识。

两个事件的独立性： 事件A的发生与否不影响B的概率（如烧香和下雨），可认为A、B是相互独立的，即

、

随机变量：随机试验的结果往往表现为数量，如：击中次数、潮位数值、投掷骰子，若不表现为数量，可使其数量化，如抽牌时，将牌张编号。

    以X 表示试验的数值结果，则X 是随机变量。

离散型随机变量：X 的取值可以一一列出（有限或无限），则X 是离散型的。设X 的可能取值为Xk ( k = 1, 2, …, n)，若相应的概率P{X = xk} = pk都知道，则该随机变量的规律就完全搞清楚了。X 的规律是指 ①弄清可能取值 ②知道概率。

连续型随机变量：

概率密度

    X 的取值连成一片（成为一些区间），就是连续型随机变量。如零件尺寸、电池寿命、降雨量等。

P{ a ≤X ≤b }是连续和，应是定积分（a，b)可不同，但被积函数相同）

    （注意大、小写勿相混）这里函数 f ( x )称为随机变量X 的概率密度函数，简称密度。密度

概率的均匀分布，指数分布和正态分布；

概率的数字性质：包括数学期望和方差，两者都是遵循概率的分布规律而成的，常用的分布是两点分布、二项分布、泊松分布、均匀分布、指数分布和正态分布。

概率的数理统计部分：

研究对象的全体称为总体，组成总体的每个单元称为个体；抽取的个体数n ，称为样本的容量。

为了使抽样具有充分的代表性，所以要求：

（1）每个个体被抽到的机会均等；

（2）每次抽取是独立的（共抽取n 次）。

这样的抽样叫做简单随机抽样。通常的抽样都是无放回的，当总体很大时，可以满足独立性

在总体中抽取n 个个体，称为总体的一个样本，记为( X1 , X2 , ... , Xn ) ，其中每次

抽样Xi ( i = 1 , 2 ,...  , n )也都是随机变量（解释），共n 个随机变量，加上括号，

表示样本是一个整体。

三个重要统计量

（1）样本均值：

（2）样本方差：

（3）样本标准差（又称为样本均方差 ）：

 1.9.4线性规划

线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法。线性规划所研究的问题是：在线性约束条件下，使线性目标函数达到最优。为了解决实际问题，首先需要把它归结为数学问题，即建立数学模型.线性规划问题的数学模型是描述实际问题的抽象的数学形式。

线性规划问题的数学模型是指求一组满足一个线性方程组（或线性不等式组，或线性方程与线性不等式混合组）的非负变量，使这组变量的一个线性函数达到最大值或最小值的数学表达式。

建立数学模型的一般步骤：

1. 确定决策变量（有非负约束）；

2. 写出目标函数（求最大值或最小值）；

3. 写出约束条件（由等式或不等式组成）.

标准形式及其特点

为便于今后求解，我们把线性规划问题的数学模型规定统一的形式，称之为标准形式，简称标准型.线性规划问题的标准形式也是单纯形方法的基础.

线性规划问题的标准形式有以下特点：

1.目标函数求最小值；

2.约束条件中除决策变量 外，其余条件均为等式；

3.每个约束方程右边的常数都是非负数，即 .

线性规划问题数学模型的标准形式：

求

其中 均为常数

 化标准形式

（1）如果目标函数求最大值，即

 只须令 ，便可将目标函数求最大值转化为求最小值，即求

 

 （2）引进松弛变量，将约束条件中的不等式化为等式（决策变量非负约束除外）.

（3）在约束条件为等式的前提下，如果某个方程右边的常数是负数，则只须在方程两边乘以–1.

线性规划问题的一些重要概念

（1）基、基变量、非基变量

如果矩阵 B 是约束方程系数矩阵 A 中的 M 阶非奇异矩阵 ，则称方阵B为线性规划问题的一个基矩阵，简称为基.

 矩阵 B 中的每一列所对应 M 的 个变量称为基变量，除基变量以外的  个变量，我们称为非基变量.

 (2）基础解、基础可行解、基础最优解

在约束方程组中，如果令各非基变量等于零，所得的解，称为线性规划问题的基础解.

如果基础解满足非负限制，则称它为基础可行解.

使目标函数取得最小值的基础可行解，称为基础最优解.

（3）可行基、最优基

对应于基础可行解的基，称为可行基.

对应于基础最优解的基，称为最优基.

通过例题让大家理解这几个概念及基础最优解求出的过程.

线性规划的解法一般有图形法和单纯形法。

2．重点和难点：

1)       存储器部分：特别是cache和虚拟存储器是重点的复习方面

2)        计算机系统结构：计算机的安全和可靠性方面计算题目

3)       体系结构其他知识：RISC和并行处理的技术

4)       数学部分

---

声明：本文为博主原创文章，未经博主允许不得转载

如果我的文章有帮助到您，欢迎打赏一下鼓励博