西安交通大学 大学计算机基础ch1_

1、第第1 1章章 引言引言主要内容主要内容n计算机系统的概念结构计算机系统的概念结构n主机系统主机系统n计算模型计算模型2了解系统的整体结构了解系统的整体结构了解计算机的能力局限了解计算机的能力局限一、计算机系统一、计算机系统3计算机系统组成计算机系统组成Personal Computer5计算机系统组成计算机系统组成计算机系统组成计算机系统组成6计算机计算机硬件系统硬件系统软件系统软件系统7计算机系统计算机系统硬件系统硬件系统软件系统软件系统主机系统主机系统外部设备外部设备所有可以通过所有可以通过输入输出接口输入输出接口与计算机进行与计算机进行信息交换的电信息交换的电子设备子设备二、主机系统二

2、、主机系统89主机系统主机系统CPUCPU存储器存储器输入输出接口输入输出接口总线总线10CPU（微微处理器处理器）nCPUCPU（Central Central Processing UnitProcessing Unit）是计算机的核）是计算机的核心。心。n提供运算和控制功能。提供运算和控制功能。n例：例：nIntel 8086Intel 8086、Pentium ProPentium Pro、P4P4、Core 2Core 2、Core i7Core i7nAMD SempronAMD Sempron、DuronDuron、AthlonAthlon11CPUn主要包括：主要包括： 运算器

3、（运算器（ALUALU） 控制器（控制器（ CUCU） 寄存器组（寄存器组（RegistersRegisters）微处理器的基本结构微处理器的基本结构1213存储器存储器n计算机中的记忆装置计算机中的记忆装置n用于存放需要计算机处理的各种信息。用于存放需要计算机处理的各种信息。内存储器内存储器外存储器外存储器存储器存储器n有关存储器的术语：有关存储器的术语：n存储容量存储容量n存放的数据量。用字节表示存放的数据量。用字节表示。n对存储器的操作对存储器的操作n读（出），写（入）读（出），写（入）14每每8 8位位0 0或或1 1称称为为1 1字节字节（ByteByte）对某个器件的读对某个器件的

4、读/ /写写= =与其的信息交换与其的信息交换151 1）外存储器外存储器n脱机外存脱机外存n光盘、优盘、移动硬盘、等光盘、优盘、移动硬盘、等n联机外存联机外存n硬磁盘硬磁盘n固态盘固态盘半导体材料制造半导体材料制造硬盘管理硬盘管理n硬盘由多个盘片叠加在一起构成，信息记录在硬盘由多个盘片叠加在一起构成，信息记录在盘片上。每个盘片包括两个记录面。盘片上。每个盘片包括两个记录面。n磁盘管理：磁盘管理：n记录面或磁头数（信息存储）记录面或磁头数（信息存储）n磁道磁道n盘面上划分出的不同半径的同心圆盘面上划分出的不同半径的同心圆n扇区扇区n每条磁道上划分出的等分区段（每条磁道上划分出的等分区段（512

5、512字节）字节）n磁盘存储容量：磁盘存储容量：n磁头数柱面数扇区数磁头数柱面数扇区数512512（B B）16硬磁盘硬磁盘n特点（相对于内存）：特点（相对于内存）：n存储容量大存储容量大n存取速度慢存取速度慢n价格较低价格较低n不能与不能与CPUCPU直接进行信息交换直接进行信息交换n无需后备电源无需后备电源n硬盘在系统中主要用于信息的长期存储。硬盘在系统中主要用于信息的长期存储。17182）内存储器内存储器n特点特点: :n存取速度较快，容量相对较小。存取速度较快，容量相对较小。19内存储器内存储器n内存按单元组织内存按单元组织n每个内存单元中存放每个内存单元中存放1Byte1Byte数据

6、数据n内存单元个数称为内存容量内存单元个数称为内存容量。38F04H内存地址内存地址单元内容单元内容10110110内存储器内存储器内存单元内存单元20总线总线n是是一组导线和相关控制、驱动电路一组导线和相关控制、驱动电路的的集合。是集合。是计算机系统各部件之间传输地址、数据和控制计算机系统各部件之间传输地址、数据和控制信息信息的的通道。通道。n按照层次结构，总线可以分为：按照层次结构，总线可以分为：CPUCPU总线总线系统总线系统总线外设总线外设总线21多总线结构多总线结构n现代微型机中采用多现代微型机中采用多总线结构总线结构 22总线的主要性能指标总线的主要性能指标n总线总线带宽带宽n单位

7、时间内总线上可传送的数据量（单位时间内总线上可传送的数据量（B/SB/S）n= =（位宽（位宽/8/8）工作工作频率频率能同时传送的能同时传送的数据数据位数（位数（bitbit）工作频率越高，位宽越宽，则总线带宽越大工作频率越高，位宽越宽，则总线带宽越大23输入输入/ /输出接口输出接口nI/OI/O（Input/OutputInput/Output）接口是）接口是CPUCPU与外部设与外部设备间的桥梁备间的桥梁CPUI/OI/O接口接口外设外设24接口的主要功能接口的主要功能n实现主机与外设间的运行匹配实现主机与外设间的运行匹配n对外设的控制管理对外设的控制管理CPUCache存存储储器器网

8、卡网卡并行通信并行通信至局域网至局域网串行通信串行通信系统系统总线总线微机系统概念结构微机系统概念结构微型计算机系统微型计算机系统硬件系统硬件系统软件系统软件系统主机系统主机系统外部设备外部设备CPUCPU存储器存储器总线总线I/OI/O接口接口系统软件系统软件应用软件应用软件能够与能够与CPUCPU直接进行直接进行信息交换信息交换的的部件属于部件属于主机系统主机系统不能够与不能够与CPUCPU直接进行信息交换的部件属于直接进行信息交换的部件属于外部设外部设备备外存储器属外存储器属于主机吗？于主机吗？主机系统主机系统三、图灵模型与计算三、图灵模型与计算28虽然虽然这里这里的的“计算计算” ”

9、可可能是广义的能是广义的计算机是一种计算装置计算机是一种计算装置为什么能够发明出计算机？为什么能够发明出计算机？计算机的理论基础是什么？计算机的理论基础是什么？nAlan Mathison Turingn英国著名数学家和逻辑学家英国著名数学家和逻辑学家n设计理论计算机设计理论计算机n计算与自动进行的机械操作联系在计算与自动进行的机械操作联系在一起一起291. 图灵机模型图灵机模型n论文论文: :“论数字计算在决断难题中的应用论数字计算在决断难题中的应用”n给出给出“可计算性可计算性”的严格的数学定义的严格的数学定义n图灵机（图灵机（Turing MachineTuring Machine，TM

10、TM）n用机器来模拟人们用笔和纸用机器来模拟人们用笔和纸进行运算进行运算的过程的过程30将计算与自动进行的机械操作联系在一起将计算与自动进行的机械操作联系在一起图灵机图灵机模型模型n组成：组成：n一条无限长的纸带一条无限长的纸带TypeTypen一个读写头一个读写头HeadHeadn一组内部状态一组内部状态n一套控制规则一套控制规则TableTable。31图灵机图灵机基本基本工作原理工作原理32纸带纸带单元格单元格带符带符n3 3个动作：个动作：n改写当前格改写当前格n左移左移1 1格格n或右移或右移1 1格。格。包含一组固定的状包含一组固定的状态和规则（程序）态和规则（程序）n图灵机工作条

11、件：图灵机工作条件：输入带符的集合输入带符的集合内部状态的集合内部状态的集合一组控制规则一组控制规则n图灵机的工作状态图灵机的工作状态（读写头移动（读写头移动或不移动，改写或不移动，改写带符或不带符或不改写）改写）取决于：取决于：33图灵机图灵机基本工作原理基本工作原理工作状态取决于工作状态取决于规则和内部状态规则和内部状态图灵机图灵机基本工作原理基本工作原理n图灵机的工作过程：图灵机的工作过程：n读写头从纸带上读出一个方格中的信息；读写头从纸带上读出一个方格中的信息；n根据内部状态查规则表根据内部状态查规则表TableTable；n确定输出动作确定输出动作选择以下三个动作之一：选择以下三个动

12、作之一：向纸带上写向纸带上写/ /不写入信息；不写入信息；使读写头向前移动一个方格；使读写头向前移动一个方格；使读写头向后移动一个方格。使读写头向后移动一个方格。n说明下一时刻内部状态的变化。说明下一时刻内部状态的变化。34输入输入控制控制程序程序输出输出图灵机图灵机基本工作原理基本工作原理n规则表：规则表：35当前内部状态当前内部状态S输入数值输入数值i输出动作输出动作O下一时刻的内部状态下一时刻的内部状态SB1前移前移CA0往纸带上写往纸带上写1BC0后移后移A图灵机图灵机示例示例n设计计算设计计算“5+15+1”的图灵机，要求计算结束后读的图灵机，要求计算结束后读写头回到原位。写头回到原

13、位。n题目分析：题目分析：nTMTM的工作条件是：的工作条件是：n输入带符集合，内部状态集合，一组控制规则输入带符集合，内部状态集合，一组控制规则n设计：设计：n输入符号集合输入符号集合 （采用（采用0 0和和1 1表示）表示）n=0=0，1 1，* * n状态集合状态集合Q QnStartStart，addadd，carrycarry，noncarrynoncarry，overflowoverflow，returnreturn，halthalt 36图灵机图灵机示例示例n ：控制器规则的集合：控制器规则的集合37输入输入响应响应当前状态当前状态当前符号当前符号新符合新符合读写头移动读写头移动

14、新状态新状态Start*LeftAddAdd01LeftNoncarryAdd10LeftCarryAdd*RightHaltCarry01LeftNoncarryCarry10LeftCarryCarry*1LeftOverflowNoncarry 00LeftNoncarryNoncarry 11LeftNoncarryNoncarry *RightReturnoverflow0或1*RightReturnReturn 00RightReturnReturn 11RightReturnReturn *stayHalt图灵机图灵机示例示例设置读写头的起始位置在最右侧，纸带上存储的内容为设置读

15、写头的起始位置在最右侧，纸带上存储的内容为5 538*10*1Start图灵机图灵机示例示例39*10*1Add按照规则表，读写头向左移动一格，状态变为按照规则表，读写头向左移动一格，状态变为“加加”输入输入响应响应当前状态当前状态当当前前带带符号符号新符号新符号读写头移动读写头移动新状态新状态Start*LeftAdd*10*1Start图灵机图灵机示例示例40*00*1Carry做加法，若当前方格中为内容为做加法，若当前方格中为内容为“1 1”，则使其变为，则使其变为“0 0”，然后读写头向左移动一位，并有进位。，然后读写头向左移动一位，并有进位。输输 入入响响 应应当前状态当前状态当当前

16、前带带符号符号新符号新符号读写头移动读写头移动新状态新状态Start*LeftAddAdd10LeftCarry*10*1Add图灵机图灵机示例示例41*01*1Noncarry若当前状态为若当前状态为“Carry”、方格中符号为、方格中符号为“0”，则使其变，则使其变为为“1”，然后读写头向左移动一位，变为，然后读写头向左移动一位，变为“无进位无进位”状状态。态。输输 入入响响 应应当前状态当前状态当当前前带带符号符号新符号新符号读写头移动读写头移动新状态新状态Start*LeftAddAdd10LeftCarryCarry01LeftNoncarry*00*1Carry图灵机图灵机示例示例

17、42*01*1Noncarry若当前状态为若当前状态为“NoncarryNoncarry”、方格中符号为、方格中符号为“1 1”，则使，则使其保持其保持“1 1”，读写头向左移动一位，状态不变。，读写头向左移动一位，状态不变。输输 入入响响 应应当前状态当前状态当当前前带带符号符号新符号新符号读写头移动读写头移动新状态新状态Start*LeftAddAdd10LeftCarryCarry01LeftNoncarryNoncarry 11LeftNoncarry*01*1Noncarry图灵机图灵机示例示例43*01*1Return按规则表操作：按规则表操作：输输 入入响响 应应当前状态当前状态

18、当当前前带带符号符号新符号新符号读写头移动读写头移动新状态新状态Start*LeftAddAdd10LeftCarryCarry01LeftNoncarryNoncarry 11LeftNoncarryNoncarry *RightReturn*01*1Noncarry图灵机图灵机示例示例44输入输入响应响应当前状态当前状态当当前前带带符号符号新符号新符号读写头移动读写头移动新状态新状态Start*LeftAddAdd10LeftCarryCarry01LeftNoncarryNoncarry 11LeftNoncarryNoncarry *RightReturnReturn *stayHal

19、t按规则表操作：按规则表操作：*01*1Halt理解图灵机模型理解图灵机模型n理解图灵模型（理解图灵模型（TMTM）的伟大）的伟大nTMTM是根据某项规则及当前状态，将输入变换为输出是根据某项规则及当前状态，将输入变换为输出n任何事物，包括人都可以抽象为图灵模型任何事物，包括人都可以抽象为图灵模型45图灵机是万能的吗？图灵机是万能的吗？2. 什么是计算什么是计算n计算计算n计算是对信息的变换计算是对信息的变换n计算是一个系统完成了一次从输入到输出的转换。计算是一个系统完成了一次从输入到输出的转换。n按确定的、有限的规则和步骤，将输入转换为输出按确定的、有限的规则和步骤，将输入转换为输出的过程。的过程。46算法算法计算无计算无处不在！处不在！3. 图灵机与计算图灵机与计算n图灵机图灵机n一个按照确定、有限的规则和步骤，将输入信息进行一个按照确定、有限的规则和步骤，将输入信息进行变换后给出输出信息，并在遇到停止状态时就结束工变换后给出输出信息，并在遇到停止状态时就结束工作的系统。作的系统。n图灵证明了：图灵证明了：n任何能够被图灵机完成的工作都是可计算的任何能够被图灵机完成的工作都是可计算的。n能够能够按照按照确确定、定、有限的规则和有限的规则和步骤步骤完成的计算完成的计算47图灵机是计算装置图灵机是计算装置什么问题是可计算的？什么问题是可计算的？不是所有问题都是