《本科教学水平评估》PPT课件.ppt

1,计算机科学技术的基础知识,内容提要： 计算机的运算基础 命题逻辑与逻辑代数基础 计算机的基本结构与工作原理 程序设计基础 算法基础 数据结构基础 要求：通过本章的学习，应掌握数制间的转换方法以及数据在计算机内部的表示形式，理解逻辑代数、计算机的工作原理、程序设计以及算法与数据结构的基本知识，为学习本书的以下各章和后续课程打好基础,2,数制,十进制：是使用数字1、2、 、9、0等符号来表示数值且采用“逢十进一”的进位计数制 位权表示法数制的特点： 数字的总个数等于基数。如十进制使用10个数字（09） 最大的数字比基数小1。如十进制中最大的数字为9 每个数字都要乘以基数的幂次，该幂次由每个数字所在的位置决定 任何一个N进制数AAn An1 A1 A0.A1 A2 Am,3,二进制,二进制：使用数字0和1等符号来表示数值且采用“逢二进一”的进位计数制 二进制数制的特点： 仅使用0和1两个数字 最大的数字为1，最小的数字为0 每个数字都要乘以基数2的幂次，该幂次由每个数字所在的位置决定 二进制加法和乘法运算规则： 000; 0 00; 011; 0 10 101; 1 00; 111; 1 11,4,八进制与十六进制,八进制：使用数字0、1、2、3、4、5、6、7等符号来表示数值的，且采用“逢八进一”的进位计数制 十六进制：使用数字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。十六进制的计数方法为“逢十六进一”,5,十进制整数转换为非十进制整数,除基取余法：“除基取余，先余为低（位），后余为高（位）” 例2-1 （55）10（110111）2,6,十进制整数转换为非十进制整数（续）,例2-2,例2-3 （55）10=（67）8=（37）16,7,十进制小数转换为非十进制小数,乘基取整法:“乘基取整，先整为高（位），后整为低（位）” 例2-4（ 0.625）10（0.101）2,8,十进制小数转换为非十进制小数,十进制小数并不是都能够用有限位的其他进制数精确地表示,这时应根据精度要求转换到一定的位数为止，作为其近似值 如果一个十进制数既有整数部分，又有小数部分，则应将整数部分和小数部分分别进行转换,9,十进制小数转换为非十进制小数(续),例2-5 （0.32）10（0.0101）2,2,0.32,0.64,1.28,2,0.56,2,0,整数,0,1,0.28,2,1.12,1,10,非十进制数转换为十进制数,位权法：把各非十进制数按权展开，然后求和 例2-7 （10110）2 124023122121020 160420 （22）10 例2-8 （10101.1011）2 124023122021120 12-1+02 2123 1604010.500.125 （21.625）10 例2-9（1207）8183282081780 51212807 （647）10 例2-10（1B2E）161163B1622161E160 1409611256216141（6958）10,11,二进制与八进制之间的转换,二进制数转换为八进制数：以小数点为界，将整数部分自右向左和小数部分自左向右分别按每三位为一组（不足三位用0补足），然后将各个三位二进制数转换为对应的一位八进制数 八进制数转换为二进制数：把每一位八进制数转换为对应的三位二进制数 例2-11（10111001010.1011011）2（010 111 001 010 . 101 101 100）2 （2712.554）8 例2-12（456.174）8 （100 101 110.001 111 100）2 （100101110.0011111）2,12,二进制与十六进制之间的转换,二进制数转换为十六进制数：以小数点为界，将整数部分自右向左和小数部分自左向右分别按每四位为一组，不足四位用0补足，然后将各个四位二进制数转换为对应的一位十六进制数 十六进制数转换为二进制数：把每一位十六进制数转换为对应的四位二进制数 例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,13,码制,原码表示法：用符号位和数值表示带符号数，正数的符号位用“0”表示，负数的符号位用“1”表示，数值部分用二进制形式表示 反码表示法：正数的反码与原码相同，负数的反码为对该数的原码除符号位外各位取反 补码表示法：正数的补码与原码相同，负数的补码为对该数的原码除符号位外各位取反，然后在最后一位加1 数的原码表示适合于进行乘除运算；补码用于进行加减运算,14,定点小数格式,定点小数格式：把小数点固定在数值部分最高位的左边 数的范围：二进制的（m+1）位定点小数格式的数N，所能表示的数的范围为N 1 2-m 比例因子：对于绝对值大于1的数，如果直接使用定点小数格式将会产生“溢出”，需根据实际需要使用一个比例因子，将原始数据按该比例缩小，以定点小数格式表示，得出结果后再按该比例扩大得到实际的结果,15,定点整数格式,定点整数格式：把小数点固定在数值部分最低位的右边 数的范围：二进制的（m+1）位定点整数格式的数N，所能表示的数的范围为N 2m 1 比例因子：对于绝对值大于该范围的数，如果直接使用定点小数格式也将会产生“溢出”，需根据实际需要选择一个比例因子进行调整，使所表示的数据在规定的范围之内,16,浮点表示法,浮点表示法：小数点的位置不固定，一个浮点数分为阶码和尾数两部分 阶码：用于表示小数点在该数中的位置，是一个整数 尾数：用于表示数的有效数值，可以采用整数或纯小数两种形式 可供选择的一种位数分配形式：设字长为32位 规格化的浮点数：为了提高浮点数表示的精度通常规定其尾数的最高位必须是非零的有效位，称为浮点数的规格化形式,符号位,尾数部分,阶码部分,1位,8位,23位,17,BCD码与ASCII码,BCD码：是一种二十进制的编码，即使用四位二进制数表示一位十进制数 十进制数与BCD码之间的转换：可以按位（或四位二进制数组）直接进行 ASCII（American Standards Committee of Information）码：是由美国信息交换标准委员会制定的、国际上使用最广泛的字符编码方案 ASCII码的编码方案：采用7位二进制数表示一个字符，把7位二进制数分为高三位（b7b6b5）和低四位（b4b3b2b1）。 7位ASCII编码表：利用该表可以查找数字、运算符、标点符号以及控制符等字符与ASCII码之间的对应关系,18,汉字编码体系,汉字输入码：由输入设备产生的汉字编码，如区位码、国标码、拼音码、新全拼、新双拼、五笔字型码、简码、表形码、自然码智能ABC汉字输入码等 汉字内码：用于计算机内部存储和处理的汉字编码，通常是由该汉字的国标码的两个字节（最高位置“1”）形成的 汉字字形码：是确定一个汉字字形点阵的编码，用于汉字显示和打印输出。保留在存储介质中的全部汉字字形码称为字库 汉字交换码：用于在不同的汉字信息处理系统之间或与其他计算机系统之间进行信息交换 汉字地址码：表示汉字字形信息在汉字库中的地址，用于在汉字库中查找汉字字形信息的汉字地址码等,19,数据校验码,奇偶校验码：在表示数据的N位代码中增加一位奇偶校验位，使N1位中“1”的个数为奇数（奇校验）或偶数（偶校验） 海明校验码：在有效信息代码中增加校验位，用来校验代码中“1”的个数是奇数（奇校验）还是偶数（偶校验），通过奇偶校验可以发现代码传输过程中的错误并自动校正 应用：数据校验码用于计算机各部件之间信息传输以及计算机网络的信息传输,20,命题,命题：一个有具体意义且能够判断真假的陈述句 命题的真值：命题所具有的值“真”（true，简记为T）或“假”（false,简记为F）称为其真值 命题标识符：表示命题的符号，该标识符称为命题常量 原子命题：不能分解为更为简单的陈述句的命题 复合命题：将原子命题用连接词和标点符号复合而成的命题,21,“与”（ ）,“与”（ ）:两个命题A和B的“与”（又称为A和B的“合取”）是一个复合命题，记为AB。当且仅当A和B同时为真时AB为真，在其他的情况下AB的真值均为假 AB的真值表:,22,“或”（）,“或”（）：两个命题A和B的“或”（又称为A和B的“析取”）是一个复合命题，记为AB。当且仅当A和B同时为假时AB为假，在其他的情况下AB的真值均为真 AB的真值表：,23,“非”（）,“非”（）：命题A的“非”（又称为A的“否定”）是一个复合命题，记为 A。若A为真，则A为假；若A为假，则A为真 A的真值表：,24,“异或”（）,“异或” （）：两个命题的A和B的“异或”（又称为A和B的“不可兼或”）是一个复合命题，记为AB。当且仅当A和B同时为真或者同时为假时AB为假，在其他的情况下AB的真值为真 AB的真值表：,25,“条件”（ ）,“条件”（ ）：两个命题的A和B的“条件”是一个复合命题，记为AB，读作“如果A，则B”。 当且仅当A的真值为真，B的真值为假时，AB为假，在其他的情况下AB的真值均为真 AB的真值表：,26,“双条件”( ),“双条件”( ) ：两个命题的A和B的“双条件”（又称为A当且仅当B）是一个复合命题，读作“A当且仅当B”，记为A B，。 当且仅当A的真值与B的真值相同时，A B为真，否则A B的真值均为假 A B的真值表：,27,命题公式,命题公式： 由命题变元、连接词和括号组成的合式的式子称为命题公式 命题公式等价：如果两个不同的命题公式P和Q，无论其命题变元取什么值它们的真值都相同，则称该两个命题公式等价，记为PQ 例2-25证明 （AB）与AB是等价的,28,命题公式的等价律,其中A、B、C等为命题变元，T表示“真”，F表示“假” 零律： AFA；AFF 幺律： ATT；A TA 幂等律：AAA；A AA 求补律：AAT；AAF 交换律：ABBA；ABBA 结合律：A（BC）（AB）C； A（BC）（AB）C 分配律：A（BC）ABAC； ABC（AB）（AC） 吸收律：ABABA；（AB）（AB）A 狄摩根定律：（AB）AB； （AB）AB 双重否定律： AA,29,证明狄摩根定律,例2-26证明狄摩根定律之一： （AB）AB,30,逻辑代数等价律,零律： A0A；A 00 幺律： A11；A 1A 幂等律：AAA；A AA 求补律：AA1；A A0 交换律：ABBA； A BB A 结合律：A（BC）（AB）C A（B C）（A B）C 分配律：A（BC）A BA C AB C（AB）（AC） 吸收律：A BA BA；（AB）（AB）A 狄摩根定律：（AB）A B； （A B）AB 双重否定律： AA,31,逻辑函数的化简,例2-27试将逻辑函数FAAB化简 解：F AAB （AA）(AB) （分配律） 1 (AB) （求补律） AB （幺律） 例2-28试将逻辑函数FABABABAB化简。 解：F ABABABAB A（BB）A（BB） （分配律） AA （求补律） 1 （求补律）,32,计算机硬件的基本结构,33,运算器,运算器：对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令，完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算等 运算器的组成：算术逻辑部件（ALU）完成加、减、乘、除等四则运算以及与、或、非、移位等逻辑运算；寄存器用来暂存参加运算的操作数或中间结果，常用的寄存器有累加寄存器、暂存寄存器、标志寄存器和通用寄存器等 运算器的主要技术指标：运算速度，其单位是MIPS（百万指令/秒），通常是按照一定的频度执行各类指令的统计值,34,存储器,存储器：用来存储数据和程序的部件 存储单位：位（bit）、字节（byte）、字和字长 存储容量：存储器所包含的存储单元的总数，其单位为K（1K2101024） 存储器的分类： 内存储器：又称为主存储器，简称为内存或主存，用来存放现行程序的指令和数据。包括随机存取存储器（Random Access Memory，简记为RAM）和只读存储器（Read Only Memory，简记为ROM）等 外存储器：又称为辅助存储器，简称为外存或辅存，用来存放需要长期保存的信息,35,控制器,控制器：是指挥计算机的各个部件按照指令的功能要求协调工作的部件 控制器的组成： 程序计数器（PC）：用来对程序中的指令进行计数，使控制器能依次读取指令 指令寄存器（IR）：在指令执行期间暂时保存正在执行的指令 指令译码器（ID）：用来识别指令的功能，分析指令的操作要求 时序控制电路：用来生成时序信号，以协调在指令执行周期内各部件的工作 微操作控制电路：用来产生各种控制操作命令,36,输入/输出设备,输入/输出设备：简称为I/O设备，是外部与计算机交换信息的渠道 输入设备：用于输入程序、数据、操作命令、图形、图像以及声音等信息。常用的输入设备有键盘、鼠标器、扫描仪、光笔、数字化仪以及语音输入装置等 输出设备：用于显示或打印程序、运算结果、文字、图形、图像等，也可以播放声音。常用的输出设备有显示器、打印机、XY绘图仪以及声音播放装置等,37,计算机的指令系统,指令：能被计算机识别并执行的二进制代码，它规定了计算机能完成的某一种操作 指令系统：一台计算机能执行的所有指令的集合 指令的格式：一条指令由操作码和地址码组成。操作码规定了该指令进行的操作种类；地址码给出了操作数、结果以及下一条指令的地址 指令的分类：数据传送型指令、数据处理型指令、输入输出型指令、硬件控制指令,38,计算机的工作原理,累加寄存器,算术、逻辑运算部件,0100 0101 0102 0250 ,内容,地址,指令 指令 020750 数据 ,操作 控制线路,译码器,07,指令寄存器,0102,指令 计数器,控制器,运算器,内存储器,39,指令的执行过程,取指令：即按照指令计数器中的地址，从内存储器中取出指令，并送往指令寄存器中 分析指令：即对指令寄存器中存放的指令进行分析，由操作码确定执行什么操作，由地址码确定操作数的地址 执行指令：即根据分析的结果，由控制器发出完成该操作所需要的一系列控制信息，去完成该指令所要求的操作 上述步骤完成后，指令计数器加1，为执行下一条指令做好准备。如果遇到转移指令，则将转移地址送入指令计数器,40,计算机组织与系统结构领域的一些主要技术,精简指令集技术 高速缓冲存储技术 虚拟存储技术 指令流水线技术 并行处理技术,41,程序设计语言,机器语言：由计算机的指令系统组成，使用机器语言编写的程序计算机能够直接理解并执行，但编程和理解都十分的困难 汇编语言：使用“助忆符”来表示指令的操作码，并使用存储单元或寄存器的名字表示地址码，以便于记忆和书写 高级程序设计语言：是一种与机器的指令系统无关、表达形式更接近于被描述的问题的程序设计语言，便于程序的编写，如C语言、C语言、FORTRAN语言、PASCAL语言等。高级程序设计语言又可分为面向过程和面向对象两种类型。使用高级程序设计语言编写的程序称为源程序，它必须经过程序设计语言翻译系统的处理后才能执行,42,程序设计,程序设计：是一个使用程序设计语言（如机器语言、汇编语言和高级程序设计语言）产生一系列的指令以告诉计算机该做什么的过程 广义的程序设计：并不仅仅是简单的编写程序代码，包括以下6个步骤： 需求分析 总体设计 详细设计 编码 测试 运行与维护,43,结构化程序设计,结构化程序设计：采用自顶向下逐步求精的设计方法和单入口单出口的控制成分（顺序、分支和循环）,A,A,A,A,A,条件,条件,T,T,F,F,顺序结构,循环结构,选择型分支结构,44,良好的程序设计风格,标识符：按意命名、保留字用大写字母、使用统一的缩写规则 表达式：使用括号、使用库函数、条件化简、函数与过程 模块化：模块的独立性（高内聚、低耦合）、模块的规模适中 程序行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句对齐 注释：添加必要的注释，以说明程序、过程和语句等的功能及注意事项,45,算法,算法：是由一系列规则组成的过程，这些规则确定了一个操作的顺序，以 便能在有限步骤内得到特定问题的解 算法的性质： 确定性：即描述操作过程的规则必须是确定的、无二义性的 通用性：即算法是给出一类问题的求解方法，而不是表示解决某一个特殊的具体问题。 有限性：即算法在执行了有限步之后必须要终止 算法的描述工具： 自然语言、流程图、决策表、算法描述语言,46,欧几里德算法（Euclids Algorithm）,例2-1若给定两个正整数m和n，试写出求它们的最大公因子的算法 该算法的步骤用文字表述如下： 第1步：读入两个正整数m和n（设mn）。 第2步：求m和n的余数rmod（m,n）。 第3步：用n的值取代 m，用r的值取代n。 第4步：判别r的值是否为零，如果r0，则m为最大公因子；否则返回 第2步。 第5步：输出m的值，即为最大公因子,47,欧几里德算法（算法描述语言表示）,PROCEDURE Euclid； BEGIN READ（m,n）; REPEAT; r:=MOD（m,n）; m:=n; n:=r; UNTIL r0; WRITE (m) END,48,欧几里德算法（流程图表示）,BEGIN,END,r=mod(m,n),n=r,m=n,WRITE m,r0,READ m，n,N,Y,49,求斐波那契数（算法描述语言表示）,例2-2求小于100的斐波那契数（Fibonacci-numbers）的算法 斐波那契数的序列为0，1，2，3，5，8，13，21，34， ，即F00，F11，Fn+2Fn+1+Fn，n0。 PROCEDURE Fibonacci； BEGIN BEGIN n3:=n1+n2; n1:=0; WRITE (n3); n2:=1; n1:=n2; n3:=0; n2:=n3 WRITE (n1,n2); END WHILE n3100 DO END,50,求斐波那契数算法（流程图表示）,BEGIN,END,n1=0,n2=1,WRITE n1,n2,n3=n1+n2,n3100,WRITE n3,n2=n3,n1=n2,Y,N,51,如何评价算法的优劣,算法的时间特性：是指依据算法编制成程序后在计算机中运行时所耗费的时间的大小，称为算法的时间复杂度，记为T（n），其中n为问题的规模。T（n）是表示当n充分大时该程序运行时间的一个数量级 算法的空间特性：是指依据算法编制成程序后在计算机中运行时所占用的空间的大小，称为算法的空间复杂度，记为S（n），其中n为问题的规模。S（n）是表示当n充分大时该程序运行时所占用空间的一个数量级 算法的易理解性：算法具有良好的结构、易理解、易修改、易维护的程度,52,数据结构,数据：描述客观事物的数、字符以及所有能输入到计算机并被计算机程序处理的符号的集合，如数值、字符、图形、图像、声音等 数据结构：带有结构的数据元素的集合，结构反映了数据元素相互之间存在的某种联系 从学科的角度来看，数据