计算机导论最新版本ppt课件

第2章计算机基础知识 2 1计算机的运算基础2 2命题逻辑与逻辑代数基础2 3计算机的基本结构与工作原理2 4程序设计基础2 5算法基础2 6数据结构基础2 7本章小结 基本要求 掌握数制间的转换方法以及数据在计算机内部的表示形式理解逻辑代数 计算机的工作原理 程序设计以及算法与数据结构的基本知识 为学习本书的以下各章和后续课程打好基础 计算机中的数制数值型数据的表示字符型数据的编码表示汉字的编码表示 2 1计算机的运算基础 2 1 1计算机中的数制 不同数制的表示在计算机内部用二进制形式表示和存储数据 人们习惯于用十进制记数 为了书写简单方便也使用八进制和十六进制 用加后缀或角标的形式区别不同进制数据 B 表示二进制数 O或Q 表示八进制数 D 表示十进制数 D可省略 H 表示十六进制数 2 1 1计算机中的数制 二进制转换成其他进制二进制数转换成十进制数 按权展开相加即可 二进制数转换成八进制数时 以小数点为界 分别向左向右分成3位一组 不够3位补0 分完组后对应成八进制数即可 二进制数转换成十六进制数时 以小数点为界 分别向左向右分成4位一组 不够4位补0 分完组后对应成十六进制数即可 2 1 1计算机中的数制 二进制转换成其他进制示例 1011001 10111 2 1 26 1 24 1 23 1 20 1 2 1 1 2 3 1 2 4 1 2 5 64 16 8 1 0 5 0 125 0 0625 0 03125 0 015625 99 734375 10 1011001 10111 2 001011001 101110 2 131 56 8 1011001 10111 2 01011001 10111000 2 59 B8 16 2 1 1计算机中的数制 其他进制转换成二进制十进制数转换成二进制数 先把十进制数分解成若干个数相加 每个数都是2的若干次幂 然后对应成二进制数 八进制数转换成二进制数时 每一个八进制位展开成3个二进制位即可 十六进制数转换成二进制数时 每一个十六进制位展开成4个二进制位即可 2 1 1数据表示 其他进制转换成二进制示例 98 75 10 64 32 2 0 5 0 25 1100010 11 2 276 15 8 010111110 001101 2 10111110 001101 2 3AC 1E 16 001110101100 00011110 2 1110101100 0001111 2 2 1 2数值型数据的表示 无符号数据的表示按一定规则把无符号整数转换成二进制形式在计算机内部表示和存储 带符号数据的表示带符号数中的正负号及小数中的小数点都以二进制形式表示 需要考虑的因素机器数的范围 机器数的符号 机器数中小数点的位置 2 1 2数值型数据的表示 机器数的范围机器数的表示范围由CPU中的寄存器决定 对于无符号数 8位寄存器的表示范围是0 255 16位寄存器的表示范围是0 65535 对于带符号数 8位寄存器的表示范围是 128 127 16位寄存器的表示范围是 32768 32767 2 1 2数值型数据的表示 机器数的符号在计算机内部 任何数据 符号 都只能用二进制的两个数码0和1来表示 带符号数的表示 除了用0和1的组合来表示数值的绝对值大小外 其正负号也必须用0和1来表示 最高位为符号位 并用0表示正 用1表示负 有原码 反码 补码等表示形式 2 1 2数值型数据的表示 机器数示例无符号十进制数57的机器数表示 57的二进制形式为111001 57 原 00111001 正数的原码最高位为0 数值位补足7位 57 原 10111001 负数的原码最高位为1 数值位补足7位 57 反 00111001 正数的反码与其原码相同 57 反 11000110 负数的反码 符号位不变 数值位为原码数值位取反 57 补 00111001 正数的补码与其原码相同 57 补 11000111 负数的补码在其反码的末尾加1 2 1 2数值型数据的表示 机器数中小数点的位置定点数 定点整数 定点小数 浮点数 2 1 3字符型数据的编码表示 基本含义对于字符型数据 没有相应的转换规则可以使用 需要人们规定出每个字符对应的二进制编码形式 常用的字符型数据编码ASCII码 美国标准信息交换码的简称 使用一个字节表示一个ASCII码字符 主要用于小型机和微型机 EBCDIC码 扩展BCD码 BCD码又称二 十进制编码 用二进制编码形式表示十进制数 在BCD码的基础上 又增加了一些符号和英文字母的表示 主要用于超级计算机和大型计算机 BCD码与ASCII码BCD码 是一种二 十进制的编码 使用四位二进制数表示一位十进制数 十进制数与BCD码之间的转换 可按位 或四位二进制数组 直接进行 ASCII AmericanStandardsCommitteeofIformation 码 是由美国信息交换标准委员会制定的 国际上使用最广泛的字符编码方案 ASCII码的编码方案 采用7位二进制数表示一个字符 把7位二进制数分为高三位 b7b6b5 和低四位 b4b3b2b1 7位ASCII编码表 如表2 5所示 利用该表可以查找数字 运算符 标点符号以及控制符等字符与ASCII码之间的对应关系 数据校验码奇偶校验码 在表示数据的N位代码中增加一位奇偶校验位 使N 1位中 1 的个数为奇数 奇校验 或偶数 偶校验 海明校验码 在有效信息代码中增加校验位 用来校验代码中 1 的个数是奇数 奇校验 还是偶数 偶校验 通过奇偶校验可以发现代码传输过程中的错误并自动校正 应用 用于计算机各部件之间信息传输以及计算机网络的信息传输 2 1 4汉字的编码表示 与汉字处理有关的几种编码汉字输入码数字码 国标区位码 拼音码 全拼输入法 紫光输入法 智能ABC输入法 字形码 五笔字型编码 汉字机内码 一个汉字占用2个字节 最高位置1 计算机内部使用的汉字代码 汉字交换码 在不同信息处理系统之间进行信息交换 国标码 BIG5码 汉字字形码 用于显示和打印 2 2逻辑代数基础 命题命题公式命题公式的等价律逻辑函数的化简 命题逻辑基础命题 有具体意义且能够判断真假的陈述句 命题的真值 命题所具有的值 真 true 简记为T 或 假 false 简记为F 称为其真值 命题标识符 表示命题的符号 该标识符称为命题常量 原子命题 不能分解为更为简单的陈述句的命题 复合命题 将原子命题用连接词和标点符号复合而成的命题 2 2逻辑代数基础 连接词 与 与 两个命题A和B的 与 又称为A和B的 合取 是一个复合命题 记为A B 当且仅当A和B同时为真时A B为真 在其他的情况下A B的真值均为假 A B的真值表 2 2逻辑代数基础 连接词 或 或 两个命题A和B的 或 又称为A和B的 析取 是一个复合命题 记为A B 当且仅当A和B同时为假时A B为假 在其他的情况下A B的真值均为真 A B的真值表 2 2逻辑代数基础 连接词 非 非 命题A的 非 又称为A的 否定 是一个复合命题 记为 A 若A为真 则 A为假 若A为假 则 A为真 A的真值表 2 2逻辑代数基础 连接词 异或 异或 两个命题的A和B的 异或 又称为A和B的 不可兼或 是一个复合命题 记为A B 当且仅当A和B同时为真或者同时为假时A B为假 在其他的情况下A B的真值为真 A B的真值表 2 2逻辑代数基础 连接词 条件 条件 两个命题的A和B的 条件 是一个复合命题 记为A B 读作 如果A 则B 当且仅当A的真值为真 B的真值为假时 A B为假 在其他的情况下A B的真值均为真 A B的真值表 2 2逻辑代数基础 连接词 双条件 双条件 两个命题的A和B的 双条件 又称为A当且仅当B 是一个复合命题 记为AB 读作 A当且仅当B 当且仅当A的真值与B的真值相同时 AB为真 否则AB的真值均为假 AB的真值表 2 2逻辑代数基础 命题公式命题公式 由命题变元 连接词和括号组成的合式的式子称为命题公式 命题公式等价 如果两个不同的命题公式P和Q 无论其命题变元取什么值它们的真值都相同 则称该两个命题公式等价 记为P Q 例2 25 证明 A B 与A B是等价的 2 2逻辑代数基础 命题公式的等价律其中A B C等为命题变元 T表示 真 F表示 假 零律 A F AA F F幺律 A T TA T A幂等律 A A AA A A求补律 A A TA A F交换律 A B B AA B B A 2 2逻辑代数基础 命题公式的等价律 续 结合律 A B C A B CA B C A B C分配律 A B C A B A CA B C A B A C 吸收律 A B A B A A B A B A狄 摩根定律 A B A B A B A B双重否定律 A A 2 2逻辑代数基础 证明狄 摩根定律 例2 26 证明狄 摩根定律之一 A B A B 2 2逻辑代数基础 逻辑代数的等价律零律 A 0 AA0 0幺律 A 1 1A1 A幂等律 A A AAA A求补律 A 1A 0 2 2逻辑代数基础 逻辑代数的等价律 续 交换律 A B B AAB BA结合律 A B C A B CA BC AB C分配律 A B C AB ACA BC A B A C 吸收律 AB A A A B A A狄 摩根定律 双重否定律 A 2 2逻辑代数基础 逻辑函数的化简 例2 27 试将逻辑函数F A B化简 解 F A B A A B 分配律 1 A B 求补律 A B 幺律 例2 28 试将逻辑函数F AB A B 化简 解 F AB A B A B B 分配律 A 求补律 1 求补律 2 2逻辑代数基础 2 3计算机的基本结构与工作原理 运算器运算器 对二进制数进行运算的部件 它在控制器的控制下执行程序中的指令 完成各种算术运算 逻辑运算 比较运算 移位运算以及字符运算等 运算器的组成 算术逻辑部件 ALU 完成加 减 乘 除等四则运算以及与 或 非 移位等逻辑运算 寄存器用来暂存参加运算的操作数或中间结果 常用的寄存器有累加寄存器 暂存寄存器 标志寄存器和通用寄存器等 运算器的主要技术指标 运算速度 其单位是MIPS 百万指令 秒 通常是按照一定的频度执行各类指令的统计值 2 3计算机的基本结构与工作原理 存储器存储器 用来存储数据和程序的部件 存储单位 位 bit 字节 byte 字 和 字长 存储容量 存储器所包含的存储单元的总数 其单位为K 1K 210 1024 存储器的分类 内存储器 又称为主存储器 简称为内存或主存 用来存放现行程序的指令和数据 包括随机存取存储器 RAM 和只读存储器 ROM 等 外存储器 又称为辅助存储器 简称为外存或辅存 用来存放需要长期保存的信息 2 3计算机的基本结构与工作原理 控制器控制器 是指挥计算机的各个部件按照指令的功能要求协调工作的部件 控制器的组成 程序计数器 PC 用来对程序中的指令进行计数 使控制器能依次读取指令 指令寄存器 IR 在指令执行期间暂时保存正在执行的指令 指令译码器 ID 用来识别指令的功能 分析指令的操作要求 时序控制电路 用来生成时序信号 以协调在指令执行周期内各部件的工作 微操作控制电路 用来产生各种控制操作命令 2 3计算机的基本结构与工作原理 输入 输出设备输入 输出设备 简称为I O设备 是外部与计算机交换信息的渠道 输入设备 用于输入程序 数据 操作命令 图形 图像以及声音等信息 常用的输入设备有键盘 鼠标器 扫描仪 光笔 数字化仪以及语音输入装置等 输出设备 用于显示或打印程序 运算结果 文字 图形 图像等 也可以播放声音 常用的输出设备有显示器 打印机 XY绘图仪以及声音播放装置等 2 3计算机的基本结构与工作原理 计算机的指令系统指令 能被计算机识别并执行的二进制代码 它规定了计算机能完成的某一种操作 指令系统 一台计算机能执行的所有指令的集合 指令的格式 一条指令由操作码和地址码组成 操作码规定了该指令进行的操作种类 地址码给出了操作数 结果以及下一条指令的地址 指令的分类 数据传送型指令数据处理型指令输入输出型指令硬件控制指令 2 3计算机的基本结构与工作原理 计算机的工作原理见教材52页图2 6指令的执行过程 2 3计算机的基本结构与工作原理 指令的执行过程取指令 即按照指令计数器中的地址 从内存储器中取出指令 并送往指令寄存器中 分析指令 即对指令寄存器中存放的指令进行分析 由操作码确定执行什么操作 由地址码确定操作数的地址 执行指令 即根据分析的结果 由控制器发出完成该操作所需要的一系列控制信息 去完成该指令所要求的操作 上述步骤完成后 指令计数器加1 为执行下一条指令做好准备 如果遇到转移指令 则将转移地址送入指令计数器 2 3计算机的基本结构与工作原理 计算机组织与系统结构领域的一些主要技术1精简指令集技术在指令系统中仅包含 1 使用频率高的指令 2 支持操作系统和高级语言的程序设计的指令 精简指令计算机 reducedinstructionsetcomputer RISC 复杂指令计算机 complexinstructionsetcomputer CISC 2高速缓冲存储技术 cache 为使慢速的RAM与快速的CPU相匹配 采用cache技术 方法 将CPU从RAM某一地址读取数据 自动将该地址相近的整批数据读入cache中 2 3计算机的基本结构与工作原理 3虚拟存储技术利用硬盘的支持以小的物理内存模拟大的内存 从而程序能够使用整个内存地址空间的技术 4指令流水线技术CPU可以在完成一条指令之前将开始执行另外一条指令 以加快计算机的处理速度 5并行处理技术把一个程序划分为多个能够并行地有单独处理器执行的进程 多个处理机协同地并行工作 达到甚至超过了巨型机的高性能 并行计算机系统有 SISD 单指令流但数据流 SIMD MISD MIMD 2 3计算机的基本结构与工作原理 机器语言汇编语言高级语言结构化程序设计语言面向对象程序设计语言可视化程序设计语言人工智能程序设计语言 学习语言是设计程序的基础 2 4程序设计基础 2 4 1机器语言 机器语言的特点由二进制编码指令构成的语言 是一种依附于机器硬件的语言 机器语言程序可以直接执行 机器语言程序片段0001010101101100 把地址为01101100的内存单元中的数装入0101号寄存器0001011001101101 把地址为01101101的内存单元中的数装入0110号寄存器0101000001010110 把01101100和01101101中的数相加 结果存入0000号寄存器0011000001101110 把0000号寄存器中的数存入地址为01101110的内存单元中 2 4 2汇编语言 汇编语言的特点由助记符指令构成的语言 也是一种依附于机器硬件的语言 汇编语言源程序需要汇编后才能执行 汇编语言程序片段MOVR5 X 把内存单元X中的数装入R5寄存器ADDR5 Y 把R5中的数与Y单元中的数相加 结果存入R5MOVZ R5 把R5中的数存入Z单元中 2 4 3高级语言 高级语言的特点由自然语言和数学公式表示的语言 是一种独立于机器硬件的语言 高级语言程序需要编译后才能执行 高级语言程序片段Z X Y 把内存单元X中的数与Y中的数相加 结果存入Z单元 2 4 3高级语言 常用高级语言FORTRAN语言FORTRAN是FORmulaTRANslator 公式翻译器 的缩写 主要用于复杂的科学计算领域 ALGOL语言ALGOL是ALGOrithmLanguage 算法语言 的缩写 主要用于数学与科学计算 2 4 3高级语言 常用高级语言COBOL语言COBOL是COmmonBusiness OrientedLanguage 面向商业的通用语言 的缩写 主要用于企业管理和事务处理 BASIC语言BASIC是Beginner sAll purposeSymbolicInstructionCode 初学者通用符号指令码 的缩写 主要用于初学者和较小规模的程序开发 2 4 4结构化程序设计语言 早期程序设计方法的不足注重功能的实现 注重内存的节省 注重执行效率的提高 不注重程序结构的清晰性 不注重程序的可理解性和可修改性 结构化程序设计语言的特点注重程序结构的清晰性 注重程序的可理解性和可修改性 采用模块化程序设计方法 结构化程序设计结构化程序设计 采用自顶向下逐步求精的设计方法和单入口单出口的控制成分 顺序 分支和循环 2 4 4结构化程序设计语言 良好的程序设计风格标识符 按意命名 保留字用大写字母 使用统一的缩写规则 表达式 使用括号 使用库函数 条件化简 函数与过程模块化 模块的独立性 高内聚 低耦合 模块的规模适中 程序行的排列格式 排列格式美观 层次分明 使用统一的缩进格式 同一嵌套深度并列的语句对齐 注释 添加必要的注释 以说明程序 过程和语句等的功能及注意事项 2 4 4结构化程序设计语言 2 4 4结构化程序设计语言 常用结构化程序设计语言PASCAL语言是在ALGOL语言的基础上发展起来的 以法国著名科学家帕斯卡的名字命名 严格的语法格式与结构化形式 C语言是在ALGOL60语言的基础上发展起来的 兼具低级语言和高级语言的特点 是最为流行的程序设计语言之一 2 4 5面向对象程序设计语言 结构化程序设计方法的不足面向过程的设计方法与人们习惯的思维方式仍然存在一定的距离 所以很难自然 准确地反映真实世界 因而用编写出来的程序 特别是规模比较大的程序 其质量是难以保证的 强调了要实现功能的操作方法 模块 而被操作的数据 变量 处于实现功能的从属地位 即程序模块和数据结构是松散地耦合在一起 当程序复杂度较高时 容易出错 而且错误难以查找和修改 2 4 5面向对象程序设计语言 面向对象程序设计语言的特点将问题分解为对象 对象将自己的属性和方法封装成一个整体 供程序设计者使用 对象之间的相互作用则通过消息传递来实现 使人们对复杂系统的认识过程与程序设计过程尽可能一致 2 4 5面向对象程序设计语言 常用面向对象程序设计语言Simula67发布于1967年 是面向对象语言的鼻祖 C 发布于1983年 是在C语言的基础上发展起来的 C 是得到广泛应用的一种面向对象语言 目前常用的版本有VisualC C VisualC Net等 Java发布于1995年 适合于网络程序设计 也是目前得到广泛应用的一种面向对象程序设计语言 2 4 6可视化程序设计语言 可视化程序设计语言的特点以图形化的编程方式将面向对象技术的特性体现出来 使开发软件这一原本枯燥 难以理解的工作变得相对轻松快捷 常用可视化程序设计语言VisualC 功能强大 比较适合专业人员使用 VisualBasic易于学习和掌握 比较适合非专业人员和初学者使用 2 4 7人工智能程序设计语言 人工智能程序设计语言的特点适合于知识表示和逻辑推理 常用人工智能程序设计语言LISPLISP是LIStProcessing 表处理 的缩写 可以解决人工智能中的符号处理问题 PROLOG是PROgramminginLOGic 逻辑程序设计 的缩写 自动实现模式匹配 自动回溯这两种人工智能中常用的基本操作 良好的程序设计风格标识符 按意命名 保留字用大写字母 使用统一的缩写规则 表达式 使用括号 使用库函数 条件化简 函数与过程模块化 模块的独立性 高内聚 低耦合 模块的规模适中 程序行的排列格式 排列格式美观 层次分明 使用统一的缩进格式 同一嵌套深度并列的语句对齐 注释 添加必要的注释 以说明程序 过程和语句等的功能及注意事项 2 4程序设计基础 算法算法 是由一系列规则组成的过程 这些规则确定了一个操作的顺序 以便能在有限步骤内得到特定问题的解 算法的性质 确定性通用性有限性算法的描述工具 自然语言流程图决策表算法描述语言 2 5算法基础 欧几里德算法 Euclid sAlgorithm 例2 32 若给定两个正整数m和n 试写出求它们的最大公因子的算法 该算法的步骤用文字表述如下 第1步 读入两个正整数m和n 设m n 第2步 求m和n的余数r mod m n 第3步 用n的值取代m 用r的值取代n 第4步 判别r的值是否为零 如果r 0 则m为最大公因