《计算机导论》全套PPT电子课件教案- 第2章 计算机的基础知识.ppt

第2章 计算机的基础知识 内容提要 v计算机的运算基础 v命题逻辑与逻辑代数基础 v计算机的基本结构与工作原理 v程序设计基础 v算法基础 v数据结构基础 基本要求： v掌握数制间的转换方法以及数据在计 算机内部的表示形式 v理解逻辑代数、计算机的工作原理、 程序设计以及算法与数据结构的基本知识 ，为学习本书的以下各章和后续课程打好 基础 十进制 v数制：按进位的原则进行计数称为进位计 数制，简称数制。 v十进制：是使用数字1、2、 、9、0等符 号来表示数值且采用“逢十进一”的进位计数制 。 v位权表示法数制的特点： 数字的总个数等于基数。 最大的数字比基数小1。 每个数字都要乘以基数的幂次，该 幂次由每个数字所在的位置决定。 v任何一个n进制数a可表示为：aan an1 a1 a0.a1 a2 am -m aini i=n 二进制 v二进制：使用数字0和1等符号来表示数值且采用“ 逢二进一”的进位计数制。 v二进制数制的特点： 仅使用0和1两个数字。 最大的数字为1，最小的数字为0。 每个数字都要乘以基数2的幂次，该幂次由 每个数字所在的位置决定。 v二进制加法和乘法运算规则： 0000 00 011 0 10 1011 00 1111 11 八进制与十六进制 v八进制：使用数字0、1、2、3、4、5、6、7 等符号来表示数值的，且采用“逢八进一”的进 位计数制。 v十六进制：使用数字0、1、2、3、4、5、6 、7、8、9和a、b、c、d、e、f等符号来表示数值 ，其中a、b、c、d、e、f分别表示数字10、11、 12、13、14、15。十六进制的计数方法为“逢十 六进一”。 十进制整数转换为非十进制整数 v 除基取余法：“除基取余，先余为低（位），后余为高（位）” 。 例2-1 （55）10（110111）2 余数 2 55 1 2 27 1 2 13 1 2 6 0 2 3 1 2 1 1 0 十进制整数转换为非十进制整数 例2-2 （55）10（67）8 余数 8 55 7 8 6 6 0 例2-3 （55）10（37）16 余数 16 55 7 16 3 3 0 十进制小数转换为非十进制小数 乘基取整法:“乘基取整，先整为高(位),后整为低(位 )” 例2-4 （ 0.625）10（0.101）2 0.625 整数 2 1 .25 1 0.25 2 0.5 0 2 1.0 1 十进制小数转换为非十进制小数 例2-5 （0.32）10（0.0101）2 0.32 整数 2 0.64 0 2 1.28 1 0.28 2 0.56 0 2 1.12 1 十进制小数转换为非十进制小数 十进制小数并不是都能够用有限位的其他进制数精确 地表示,这时应根据精度要求转换到一定的位数为止， 作为其近似值。 如果一个十进制数既有整数部分，又有小数部分，则 应将整数部分和小数部分分别进行转换。 非十进制数转换为十进制数 位权法：把各非十进制数按权展开，然后求和。 例2-7 （10110）2 124023122121020 160420 （22）10 例2-8 （10101.1011）2 124023122021 120 12-1+02 2123 1604010.500.125 （21.625）10 例2-9 （1207）818 328 208 178 0 51212807 （647）10 例2-10（1b2e）16116 3b16 2216 1e16 0 1409611256216141（6958 ）10 二进制与八进制之间的转换 v二进制数转换为八进制数：以小数点为界，将整 数部分自右向左和小数部分自左向右分别按每三位为一 组（不足三位用0补足），然后将各个三位二进制数转 换为对应的一位八进制数。 v八进制数转换为二进制数：把每一位八进制数转 换为对应的三位二进制数。 例2-11 （10111001010.1011011）2（010 111 001 010 . 101 101 100 ）2 （2712.554）8 例2-12 （456.174）8 （100 101110.001 111 100）2 （100101110.0011111）2 二进制与十六进制之间的转换 v二进制数转换为十六进制数：以小数点为界，将整 数部分自右向左和小数部分自左向右分别按每四位为一 组，不足四位用0补足，然后将各个四位二进制数转换为 对应的一位十六进制数。 v十六进制数转换为二进制数：把每一位十六进制数 转换为对应的四位二进制数。 例2-13 （10111001010.1011011）2（0101 1100 1010.1011 0110）2 （5ca.b6）16 例2-14 （1a9f.1bd ）16（0001 1010 1001 1111.0001 1011 1101） 2 （1101010011111.000110111101）2 码制 v原码表示法：用符号位和数值表示带符号数，正数的 符号位用“0”表示，负数的符号位用“1”表示，数值 部分用二进制形式表示。 v反码表示法：正数的反码与原码相同，负数的反码为 对该数的原码除符号位外各位取反。 v补码表示法：正数的补码与原码相同，负数的补码为 对该数的原码除符号位外各位取反，然后在最后一位加1 。 v数的原码表示适合于进行乘除运算；补码用于进行加 减运算 定点小数格式 v定点小数格式：把小数点固定在数值部分最高位的左边 。 n0 . n-1 n-2 n-m 符号位 小数点 数值部分 v数的范围：二进制的（m+1）位定点小数格式的数n，所 能表示的数的范围为n 1 2-m。 v比例因子：对于绝对值大于1的数，如果直接使用定点 小数格式将会产生“溢出”，需根据实际需要使用一个比 例因子，将原始数据按该比例缩小，以定点小数格式表示 ，得出结果后再按该比例扩大得到实际的结果。 浮点表示法 v浮点表示法：小数点的位置不固定，一个浮点数分为阶 码和尾数两部分。 v阶码：用于表示小数点在该数中的位置，是一个整数。 v尾数：用于表示数的有效数值，可以采用整数或纯小数 两种形式 v可供选择的一种位数分配形式：设字长为32位 符号位 阶码部分 尾 数 部 分 1位 8位23 位 v规格化的浮点数：为了提高浮点数表示的精度通常规定 其尾数的最高位必须是非零的有效位，称为浮点数的规格 化形式。 bcd码与ascii码 vbcd码：是一种二十进制的编码，使用四位二进制数表示 一位十进制数。 v十进制数与bcd码之间的转换：可按位（或四位二进制数组 ）直接进行。 vascii(american standards committee of iformation)码 :是由美国信息交换标准委员会制定的、国际上使用最广泛的 字符编码方案。 vascii码的编码方案：采用7位二进制数表示一个字符，把7 位二进制数分为高三位（b7b6b5）和低四位 （b4b3b2b1 ） v7位ascii编码表：如表2-5所示，利用该表可以查找数字、 运算符、标点符号以及控制符等字符与ascii码之间的对应关 系。 汉字编码体系 v汉字输入码：由输入设备产生的汉字编码，如区位码、国 标码、拼音码、新全拼、新双拼、五笔字型码、简码、表形 码、自然码、智能abc汉字输入码等。 v汉字内码：用于计算机内部存储和处理的汉字编码，通常 由该汉字的国标码的两个字节（最高位置“1”）形成。 v汉字字形码：确定一个汉字字形点阵的编码，用于汉字显 示和打印输出。保留在存储介质中的全部汉字字形码称为字 库。 v汉字交换码：用于在不同的汉字信息处理系统之间或与其 他计算机系统之间进行信息交换。 v汉字地址码：表示汉字字形信息在汉字库中的地址，用于 在汉字库中查找汉字字形信息的汉字地址码等。 数据校验码 v奇偶校验码：在表示数据的n位代码中增加一位奇偶校 验位，使n1位中“1”的个数为奇数（奇校验）或偶数 （偶校验）。 v海明校验码：在有效信息代码中增加校验位，用来校验 代码中“1”的个数是奇数（奇校验）还是偶数（偶校验 ），通过奇偶校验可以发现代码传输过程中的错误并自动 校正。 v应用：用于计算机各部件之间信息传输以及计算机网络 的信息传输。 命题 v命题：有具体意义且能够判断真假的陈述句。 v命题的真值:命题所具有的值“真”(true，简记为 t)或“假”（false,简记为f）称为其真值。 v命题标识符：表示命题的符号，该标识符称为命题 常量。 v原子命题：不能分解为更为简单的陈述句的命题。 v复合命题：将原子命题用连接词和标点符号复合而 成的命题。 连接词“与”（ ） “与”( ):两个命题a和b的“与”(又称为a和b的“合 取”)是一个复合命题，记为ab。当且仅当a和b同时为真 时ab为真，在其他的情况下ab的真值均为假。 ab的真值表: a b ab t t t t f f f t f f f f 连接词 “或”（） v“或”（）：两个命题a和b的“或”（又称为a和b的 “析取”）是一个复合命题，记为ab。当且仅当a和b同 时为假时ab为假，在其他的情况下ab的真值均为真。 vab的真值表： a b ab t t t t f t f t t f f f 连接词“非”（） v“非”（）：命题a的“非”（又称为a的“否定”） 是一个复合命题，记为 a。若a为真，则a为假；若a 为假，则a为真。 va的真值表： aa tf ft 连接词 “异或”（） “异或” （）：两个命题的a和b的“异或”（又称 为a和b的“不可兼或”）是一个复合命题，记为ab。当 且仅当a和b同时为真或者同时为假时ab为假，在其他的 情况下ab的真值为真。 vab的真值表： a b ab t t f t f t f t t f f f 连接词“条件”（ ） v“条件”（ ）：两个命题的a和b的“条件”是一个 复合命题，记为 ab,读作“如果a，则b”。 当且仅当a的真值为 真，b的真值为假时，ab为假，在其他的情况下ab的 真值均为真。 vab的真值表： a b a b t t t t f f f t t f f t 连接词 “双条件”( ) v“双条件”( ):两个命题的a和b的“双条件”（又 称为a当且仅当b）是一个复合命题，记为a b，读作 “a当且仅当b”。 当且仅当a的真值与b的真值相同时， a b为真，否则a b的真值均为假。 va b的真值表： a b a b t t t t f f f t f f f t 命题公式 v命题公式： 由命题变元、连接词和括号组成的合式的式子称为命 题公式。 v命题公式等价：如果两个不同的命题公式p和q，无论其命题变元取 什么值它们的真值都相同，则称该两个命题公式等价，记为pq。 例2-25证明 （ab）与ab是等价的。 ab（ab）ab tt f f t f tt f t f f f f f f 命题公式的等价律 其中a、b、c等为命题变元，t表示“真”，f表示“假 ” v零律： afa aff v幺律： att a ta v幂等律：aaa a aa v求补律：aat aaf v交换律：abba abba 命题公式的等价律（续） v结合律： a（bc）（ab）c a（bc）（ab）c v分配律： a（bc）abac a（bc）（ab）（ac） v吸收律： ababa （ab）（ab）a v狄摩根定律：（ab）ab （ab）ab v双重否定律： aa 证明狄摩根定律 例2-26证明狄摩根定律之一：（ab） ab。 a b ab（ab）abab tttffff tfftft t ftft tft ffftttt 逻辑代数的等价律 v零律： a0a a 00 v幺律： a11 a 1a v幂等律：aaa a aa v求补律：a 1 a 0 逻辑代数的等价律（续） b b b b (a+b) a (a b) v交换律：abba a bb a v结合律：a（bc）（ab）c a（b c）（a b）c v分配律：a（bc）a ba c ab c（ab）（ac） v吸收律：a ba a （ab）（a ）a v狄摩根定律： v双重否定律： a a 逻辑函数的化简 例2-27试将逻辑函数fa b化简。 解：fa b （a ）(ab)（分配律 ） 1 (ab) （求补律 ） ab （幺律） 例2-28试将逻辑函数faba b 化简。 解：f aba b a（b ） （b ）（分配律） a （求补律） 1 （求补律） b b b b (a b) (a b) 计算机硬件的基本结构 辅助存储器 内存储器 运 算 器 控制 器 输入设备 输出设备 程序 原始数据 运算 结果 控制信息数据 运算器 v运算器：对二进制数进行运算的部件。它在控制器的控制 下执行程序中的指令,完成各种算术运算、逻辑运算、比较运 算、移位运算以及字符运算等。 v运算器的组成：算术逻辑部件（alu）完成加、减、乘、除 等四则运算以及与、或、非、移位等逻辑运算；寄存器用来 暂存参加运算的操作数或中间结果，常用的寄存器有累加寄 存器、暂存寄存器、标志寄存器和通用寄存器等。 v运算器的主要技术指标：运算速度，其单位是mips（百万 指令/秒），通常是按照一定的频度执行各类指令的统计值。 控制器 v控制器：是指挥计算机的各个部件按照指令的功能要求协 调工作的部件。 v控制器的组成： 程序计数器（pc）：用来对程序中的指令进行 计数，使控制器能依次读取指令； 指令寄存器（ir）：在指令执行期间暂时保存 正在执行的指令。 指令译码器（id）：用来识别指令的功能，分 析指令的操作要求。 时序控制电路：用来生成时序信号，以协调在 指令执行周期内各部件的工作。 微操作控制电路：用来产生各种控制操作命令 。 存储器 v存储器：用来存储数据和程序的部件。 v存储单位：“位”（bit）、“字节”（byte）、“字”和 “字长” v存储容量：存储器所包含的存储单元的总数，其单位为k （1k2101024）。 v存储器的分类： 内存储器：又称为主存储器，简称为内存或主 存，用来存放现行程序的指令和数据。包括随机存取 存储器（ram）和只读存储器（rom）等。 外存储器：又称为辅助存储器，简称为外存或 辅存，用来存放需要长期保存的信息。 存储器的层次结构 缓存主存层次和主存辅存层次 输入/输出设备 v输入/输出设备：简称为i/o设备，是外部与计算机交换 信息的渠道。 v输入设备：用于输入程序、数据、操作命令、图形、图 像以及声音等信息。常用的输入设备有键盘、鼠标器、扫 描仪、光笔、数字化仪以及语音输入装置等。 v输出设备：用于显示或打印程序、运算结果、文字、图 形、图像等，也可以播放声音。常用的输出设备有显示器 、打印机、xy绘图仪以及声音播放装置等。 计算机的指令系统 v指令：能被计算机识别并执行的二进制代码，它规定了 计算机能完成的某一种操作。 v指令系统：一台计算机能执行的所有指令的集合。 v指令的格式：一条指令由操作码和地址码组成。操作码 规定了该指令进行的操作种类；地址码给出了操作数、结 果以及下一条指令的地址。 v指令的分类： 数据传送型指令 数据处理型指令 输入输出型指令 硬件控制指令 计算机的工作原理 见教材52页 图2-6 指令的执行过程 指令的执行过程 v取指令：即按照指令计数器中的地址，从内存储器中取 出指令，并送往指令寄存器中。 v分析指令：即对指令寄存器中存放的指令进行分析，由 操作码确定执行什么操作，由地址码确定操作数的地址。 v执行指令：即根据分析的结果，由控制器发出完成该操 作所需要的一系列控制信息，去完成该指令所要求的操作 。 v上述步骤完成后，指令计数器加1，为执行下一条指令 做好准备。如果遇到转移指令，则将转移地址送入指令计 数器。 计算机组织与系统结构领域的一些主要技术 v精简指令集技术 v高速缓冲存储技术 v虚拟存储技术 v指令流水线技术 v并行处理技术 程序设计语言 v机器语言：由计算机的指令系统组成，使用机器语言编写 的程序计算机能够直接理解并执行，但编程和理解都十分的 困难。 v汇编语言：使用“助忆符”来表示指令的操作码，并使用 存储单元或寄存器的名字表示地址码，以便于记忆和书写。 v高级程序设计语言：是一种与机器的指令系统无关、表达 形式更接近于被描述的问题的程序设计语言，便于程序的编 写。使用高级程序设计语言编写的程序称为源程序，它必须 经过程序设计语言翻译系统的处理后才能执行。 面向过程程序设计语言 面向对象程序设计语言 程序设计 v程序设计：是一个使用程序设计语言产生一系列的指令 以告诉计算机该做什么的过程。 v广义的程序设计： 需求分析 总体设计 详细设计 编码 测试 运行与维护 结构化程序设计 结构化程序设计：采用自顶向下逐步求精的设计方法和单入口单出 口的控制成分（顺序、分支和循环）。 t f t f 条 件 a a b （a）顺序结构 （b）选择型分支结构 （c）循环结构 ab 条 件 标识符：按意命名、保留字用大写字母、使用统一的 缩写规则。 注释： 添加必要的注释，以说明程序、过程和语句 等的功能及注意事项。 表达式：使用括号、使用库函数、条件化简、函数与 过程 模块化：模块的独立性（高内聚、低耦合）、模块的 规模适中。 程序行的排列格式：排列格式美观、层次分明、使用统 一的缩进格式，同一嵌套深度并列的语句对齐。 良好的程序设计风格 算法 v算法：是由一系列规则组成的过程，这些规则确定了 一个操作的顺序，以便能在有限步骤内得到特定问题的解 。 v算法的性质： 确定性 通用性 有限性 v算法的描述工具： 自然语言 流程图 决策表 算法描述语言 欧几里德算法（euclids algorithm） 例2-32若给定两个正整数m和n，试写出求它们的最大 公因子的算法。 该算法的步骤用文字表述如下： 第1步：读入两个正整数m和n（设mn）。 第2步：求m和n的余数rmod（m,n）。 第3步：用n的值取代 m，用r的值取代n。 第4步：判别r的值是否为零，如果r0，则m为最 大公因子；否则返回 第2步。 第5步：输出m的值，即为最大公因子。 欧几里德算法（算法描述语言表示） procedure euclid； begin read（m,n）; repeat; r:=mod（m,n）; m:=n; n:=r; until r0; write (m) end 欧几里德算法（流程图表示） m=n begin read m，n r=mod(m,n) n=r write m r0 end y n 怎样衡量算法的优劣 1、算法的时间特性 2、算法的空间特性 3、算法的易理解性 数据结构 v数据：描述客观事物的数、字符以及所有能输入到计算机 并被计算机程序处理的符号的集合，如数值、字符、图形、 图像、声音等。 v数据结构：带有结构的数据元素的集合，结构反映了数据 元素相互之间存在的某种联系。从学科的角度来看，数据结 构是计算机科学技术的一个分支，它