计算思维与信息表示

1、计算思维与计算机中的信息表示,计算思维 计算机中的信息表示,2006年3月，美国卡内基梅隆大学计算机科学系主任周以真（Jeannette M. Wing）教授在美国计算机权威期刊Communications of the ACM杂志上给出，并定义的计算思维（Computational Thinking）。周教授认为： 计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。 21世纪每个人都应该具备的能力。,计算思维,计算思维是人类应具备的第三种思维 理论思维：对事物的感性认识资料，经过抽象、概括，形成描述事物本质的概念，主要以推理和演

2、绎的方法，探寻概念之间相互联系的一种思维活动。 实验思维：通过观察和实验的手段，揭示自然规律法则的一种思维方法。特征是观察、整理、归纳、对比和验证。 计算思维：构造思维，是指从具体的算法设计规范入手，通过算法过程的构造与实施，来解决给定问题的一种思维方法。 在当前环境下，理论与实验手段面临大规模数据的情况下，不可避免的要用计算手段来辅助进行。,计算机能干什么 多记忆一些数据，多接收一些信息，算的快一些，交流方便些。 以亿次的计算，求解繁复的微分方程和方程组，描绘超乎想象的图像，模拟无法实现或耗资巨大的过程等等。 计算机不能干什么 不能替人拿主意、定方案 人机分界面恰在思考二字，即把计算机所不具

3、备的直觉、综合、机敏，甚至艺术家的灵感留给人，由人来创造性的开发各种所需的算法、模型、方法。,计算思维的关键：用计算机模拟现实世界 计算思维的本质: 抽象和自动化 计算思维中的抽象完全超越物理的时空观，并完全用符号来表示。自动化是机械地一步一步自动执行，其基础和前提是抽象。 案例：18世纪著名的古典数学问题哥尼斯堡七桥问题。,哥尼斯堡七桥问题 哥尼斯堡地处东普鲁士，位于普雷格尔河的两岸及河中心的两个岛上，城市各部分由七座桥与两岸连结起来。多年来，当地的居民总有一个愿望：从家里出去散步，能否通过没每座桥恰好一次，再返回家中？但是任何人也没有找到这样一条理想的路径。,1976年，瑞士数学家欧拉(E

4、uler)解决问题的办法是把陆地抽象为一个点，用连接两个点的线段表示桥梁，将该问题抽象成点与线连接图的数学问题。把一个实际问题抽象成合适的“数学模型”，这就是计算思维中的抽象。,计算思维品质对人的能力影响作用,问题抽象层次的能力是衡量人的思维品质的重要方面。,根据求解问题的需要，在分析问题的过程中，人们可以对问题进行多层次的抽象，将注意力集中在感兴趣的抽象层次或关系相对密切的上下层，抛弃那些不感兴趣的(不重要的)层次或细节，使问题分析相对简单，以控制问题解决的复杂性。,抽象的概念是由具体概念依其“共性”而产生的，把具体概念的诸多个性排出，集中描述其共性，就会产生一个抽象性的概念。,人的大脑思维

5、方法和思维品质的差异决定着： 同一问题解决办法和处理方式各不相同。其付出的代价与取得效果甚至可能天壤之别。,计算思维的应用领域,计算思维是每个人应当具备的基本技能，也是创新人才的基本要求和专业素质，每个人都应当学习和应用计算思维。正如印刷出版促进了阅读、写作和算术的传播一样，计算和计算机也促进着计算思维的传播。,迄今为止，计算思维不仅渗透到每个人的生活，而且对生物信息学、生物计算、专家系统、经济学等学科领域产生了重大影响，在科技创新与教育教学中起着非常重要的作用。,计算思维领域提出的新思想、新方法不断地促进自然科学、工程技术和社会 经济等领域产生革命性的发展。,1.2 计算机中的信息表示,10

6、,1.2.1数制概念及数制间的转化 1.2.2计算机中数据的表示方法 1.2.3 常用信息编码 1.2.4 计算机中信息单位,1.数制 即计数制，用一组固定的符号和统一的规则来表示 数值的方法 。 计算机领域中涉及的数制有4种： 十进制、二进制、八进制、十六进制。 例如：36D、1010lB、76O、5AH 分别标识十进制数36、二进制数1010、 八进制数76、十六进制数5A。,1.2.1数制概念及数制间的转化,进制表示符号 B 二进制 O八进制 D十进制 H十六进制,在计算机内部，数据的存储和处理都是采用二进制数，主要原因是：（1）二进制数在物理上最容易实现。（2）二进制数的运算规则简单，

7、这将使计算机的硬件结构大大简化。（3）二进制数的两个数字符号“1”和“0”正好与逻辑命题的两个值“真”和“假”相对应，为计算机实现逻辑运算提供了便利的条件。 但二进制数书写冗长，所以为书写方便，一般用十六进制数或八进制数作为二进制数的简化表示。,位权 在一个数字当中， 处在不同位置上的相同数字所表示的值也是不同的。 一个数字在某个位置上的值等于该数字与这个位置上的因子的乘积，而该因子的值恰 是由所在位置相对于小数点的距离来确定，这个因子就是位权。 例如：（286）10中，2的位权是100；8的位权是10，6的位权是1,14,十六进制数,2 数制的相互转换,1十进制数转化为二进制数、八进制数、十

8、六进制数 整数：除以基值取余法，直到商为零时为止 ，逆读 小数：乘以基值取整法，直到积中的小数部分为零，或者达到所要求的精度为止，顺读,2二进制、八进制、十六进制转化为十进制-按权展开，相加求和,(110101)2=125+124+023+122+021+120 = 32+ 16+ 0+ 4+ 0+1 =(53)10,3.二进制转化成八进制和十六进制 转化成八进制： 以小数点为中心向两边分组,每三位一组. 整数部分不足位数左补0，小数部分不足位数右补 转化成十六进制：以小数点为中心向两边分组,每四位一组. 整数部分不足位数左补0，小数部分不足位数右补0,4.八进制和十六进制转化成二进制 八进制

9、转化成二进制：一位八进制数对应三位二进制数 十六进制转化成二进制：一位十六进制数对应四位二进制数,144(O)=001 100 100(B),二进制、八进制、十六进制数间的关系,常用数制间的转换小结,基数乘除法,按权展开求和,1.2.2计算机中数据的表示方法,例如，在机器中用8位二进制表示一个数90，其格式为：,符号位 0表示正,在计算机中数据都是采用二进制表示，对于数的符号，也用“0”或“1”表示，“0”表示正，“1”表示负；数的最高位为符号位。,在机器内存放的正负号符号化的数称为机器数，把机器外存放的由正负号表示的数称作真值。,例：-0101100 真值 -76 机器数10101100,机

10、器数在运算时必须考虑符号位的处理。为了便于运算，在机器中有三种表示数的方法： 1、原码原码的最高位为符号位，数值部分为原数的绝对值。 +105原=01101001 -105原=11101001 2、反码正数的反码与其原码相同。而负数的反码等于其绝对值各位求反。+105反=01101001 -105反=10010110 3、补码正数的补码与其原码相同。负数的补码是把其原码除符号位外的各位先求其反码，然后在最低位加1。+105补=01101001 -105补=10010111,定点小数：小数点固定在数值部分最高位的左边,定点整数：小数点固定在数值部分最低位的左边,定 点 数,符号位,隐含小数位（+

11、0.5),符号位,隐含小数位（-3),31 30 24 23 22 0,浮 点 数,小数点浮动-科学计数法 123.456=0.123456103 浮点数分为阶码(指数)和尾数两部分,例：二进制数0.110111*26 在计算机中以浮点格式存放,1.2.3 常用信息编码,西文字符 ACSII码(American Standard Code for Information Interchange) 128个常用字符，用7位二进制编码，从0到127 控制字符：032，127；普通字符：94个。 例如：“a”字符的编码为1100001，对应的十进制数是97； 换行 0AH 10 回车 0DH 13

12、空格 20H 32 09 30H39H 4857 AZ 41H5AH 6590 az 61H7AH 97122,汉字编码,(1) 汉字输入码 音码类 全拼、双拼、微软拼音、智能ABC等 形码类 五笔字型法、郑码输入法等 。 (2) 汉字国标码(GB231280)：每个汉字占两个字节。 一级汉字：3755个；二级汉字：3008个。 汉字分区，每个区94个汉字。 (3)机内码 汉字在设备或信息处理系统内部最基本的表达形式。 汉字 国标码 汉字内码 中 8680(01010110 01010000)B (11010110 11010000)B 华 5942(00111011 00101010)B (

13、10111011 10101010)B 汉字（4）字形码 点阵：汉字字形点阵的代码 矢量：存储的是描述汉字字形的轮廓特征,1.2.4 计算机中信息单位,位（Bit）：二进制数的最小单位，通常用“b”表示。,字节（Byte）：以8位二进制数组成1个字节，通常用 “B”表示。最常用的基本单位,K 字节1K = 1024 byte M（兆）字节1M = 1024 K G（吉） 字节1G = 1024 M T（太）字节1T = 1024 G,字（ word ）：由若干个字节组成，通常我们把计算机一次所能处理的数据的最大位数称为该机器的字长。,著名计算机科学家沃思(Nikiklaus Wirth)提出一

14、个公式： 算法 + 数据结构 = 程序 数据结构:对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式 算法:对操作的描述。即要求计算机进行操作的步骤,1.3 计算机程序概述,一个程序除了算法和数据结构这主要要素外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示 算法、数据结构、程序设计方法和语言工具是一个程序设计人员应具备的知识,什么是算法,广义地说，为解决一个问题而采取的方法和步骤，就称为“算法” 计算机算法可分为两大类别： 数值运算算法：求数值解 非数值运算算法：事务管理领域 例：图书检索，人事管理等,简单的算法举例,例： 求12345 可以用

15、最原始的方法进行： 步骤1：先求1*2，得到结果2。 步骤2：将步骤1得到的乘积2再乘以3，得到结果6。 步骤3：将6再乘以4，得24。 步骤4：将24再乘以5，得120。这就是最后的结果。,例： 求12345 1000,太繁琐,改进的算法： 设变量t为被乘数 变量i为乘数 用循环算法求结果,S1：使t=1，或写成1=t S2：使i=2，或写成2 = i S3：使t与i相乘，乘积仍放在变量t中，可表示为：t*i =t S4：使i的值加1，即i+1 = i S5：如果i不大于5，返回重新执行S3；否则，算法结束 最后得到t的值就是 5!的值,若是1000？,S1：使t=1，或写成1=t S2：使

16、i=2，或写成2 = i S3：使t与i相乘，乘积仍放在变量t中，可表示为：t*i = t S4：使i的值加1，即i+1 = i S5：如果i不大于5，返回重新执行S3；否则，算法结束 最后得到t的值就是 5!的值,若求1357911,3,3,2,2,11,11,相当于i 11,算法的特性,一个有效算法应该具有以下特点： (1) 有穷性。一个算法应包含有限的操作步骤，而不能是无限的。 (2) 确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。,一个有效算法应该具有以下特点： (3) 有零个或多个输入。所谓输入是指在执行算法时需要从外界取得必要的信息。 (4) 有一个或多个

17、输出。算法的目的是为了求解，“解” 就是输出。 没有输出的算法是没有意义的。 (5) 有效性。算法中的每一个步骤都应当能有效地执行，并得到确定的结果。,怎样表示一个算法,常用的方法有： 自然语言 传统流程图 结构化流程图 伪代码 ,用自然语言表示算法,用自然语言表示通俗易懂，但文字冗长，容易出现歧义性 用自然语言描述包含分支和循环的算法，不很方便 除了很简单的问题外，一般不用自然语言,2.4.2用流程图表示算法,流程图是用一些图框来表示各种操作 用图形表示算法，直观形象，易于理解,起止框,输入输出框,处理框,判断框,流程线,连接点,x0,Y,N,一个入口,两个出口,2.4.2用流程图表示算法,

18、流程图是用一些图框来表示各种操作 用图形表示算法，直观形象，易于理解,起止框,输入输出框,判断框,流程线,连接点,位置不够,例：求5！的算法用流程图表示。 求12345,1 = t,输出t,i5,开始,2 = i,t*i = t,i+1 = i,结束,N,Y,三种基本结构和改进的流程图,1.传统流程图的弊端 传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制 使用者可以毫不受限制地使流程随意地转来转去，使人难以理解算法的逻辑,2.三种基本结构 (1) 顺序结构,A,B,2.三种基本结构 (2) 选择结构,A,B,Y,N,A,Y,N,2.三种基本结构 (3) 循环结构 当型循环结构,A,Y,N,Y,N,0 = x,x+1