计算思维与信息表示

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

2、事物的感性认识资料，经过抽象抽象、概括概括，形成描述事物本质的概念，主要以推理推理和演绎演绎的方法，探寻概念之间相互联系的一种思维活动。实验思维实验思维：通过观察观察和实验实验的手段，揭示自然规律法则的一种思维方法。特征是观察、整理、归纳、对比和验证特征是观察、整理、归纳、对比和验证。计算思维计算思维：构造思维，是指从具体的算法设计设计规范入手，通过算法过程的构造构造与实施，来解决给定问题的一种思维方法。在当前环境下，理论与实验手段面临大规模数据的情况下，不可避免的要用计算手段来辅助进行。计算机能干什么计算机能干什么 多记忆一些数据，多接收一些信息，算的快一些，交流方便些。 以亿次的计算，求解

3、繁复的微分方程和方程组，描绘超乎想象的图像，模拟无法实现或耗资巨大的过程等等。计算机不能干什么计算机不能干什么 不能替人拿主意、定方案 人机分界面恰在思考二字，即把计算机所不具备的直觉、综合、机敏，甚至艺术家的灵感留给人，由人来创造性的开发各种所需的算法、模型、方法。计算思维的关键计算思维的关键：用计算机模拟现实世界计算思维的本质计算思维的本质: 抽象和自动化 计算思维中的抽象完全超越物理的时空观，并完全用符号来表示。自动化是机械地一步一步自动执行，其基础和前提是抽象。 案例：18世纪著名的古典数学问题哥尼斯堡七桥问题。哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡地处东普鲁士，位于普雷格尔河的两岸

4、及河中心的两个岛上，城市各部分由七座桥与两岸连结起来。多年来，当地的居民总有一个愿望：从家里出去散步，能否通过没每座桥恰好一次，再返回家中？但是任何人也没有找到这样一条理想的路径。1976年，瑞士数学家欧拉(Euler)解决问题的办法是把陆地抽陆地抽象为一个点象为一个点，用连接两个点的线段表示桥梁用连接两个点的线段表示桥梁，将该问题抽象成点与线连接图的数学问题。把一个实际问题抽象成合适的“数学模型”，这就是计算思维中的抽象。计算思维品质对人的能力影响作用计算思维品质对人的能力影响作用问题抽象层次的能力是衡量人的思维品质的重要方面。问题抽象层次的能力是衡量人的思维品质的重要方面。 根据求解问题的

5、需要，在分析问题的过程中，人们可以对问题进行多层次的抽象，将注意力集中在感兴趣的抽象层次或关系相对密切的上下层，抛弃那些不感兴趣的(不重要的)层次或细节，使问题分析相对简单，以控制问题解决的复杂性。抽象的概念是由具体概念依其“共性”而产生的，把具体概念的诸多个性排出，集中描述其共性，就会产生一个抽象性的概念。 人的大脑思维方法和思维品质的差异决定着： 同一问题解决办法和处理方式各不相同。其付出的代价与取得效果甚至可能天壤之别。 计算思维的应用领域计算思维的应用领域 计算思维是每个人应当具备的基本技能，也是创新人才的基本要求和专业素质，每个人都应当学习和应用计算思维。正如印刷出版促进了阅读、写作

6、和算术的传播一样，计算和计算机也促进着计算思维的传播。迄今为止，计算思维不仅渗透到每个人的生活，而且对生物信息学、生物计算、专家系统、经济学等学科领域产生了重大影响，在科技创新与教育教学中起着非常重要的作用。 计算思维领域提出的新思想、新方法不断地促进自然科学、工程技术和社会经济等领域产生革命性的发展。1.2 101.2.1数制概念及数制间的转化1.2.2计算机中数据的表示方法1.2.3 常用信息编码1.2.4 计算机中信息单位1.数制 即计数制，用一组固定的符号和统一的规则来表示 数值的方法 。计算机领域中涉及的数制有4种：十进制、二进制二进制、八进制、十六进制。例如：36D、1010lB、

7、76O、5AH分别标识十进制数36、二进制数1010、八进制数76、十六进制数5A。 1.2.11.2.1数制概念及数制间的转化数制概念及数制间的转化进制表示符号B 二进制O八进制D十进制H十六进制 在计算机内部，数据的存储和处理都是采用二进制数，主要原因是：（1）二进制数在物理上最容易实现。（2）二进制数的运算规则简单，这将使计算机的硬件结构大大简化。（3）二进制数的两个数字符号“1”和“0”正好与逻辑命题的两个值“真”和“假”相对应，为计算机实现逻辑运算提供了便利的条件。 但二进制数书写冗长，所以为书写方便，一般用十六进制数或八进制数作为二进制数的简化表示。 位权例如14十六进制数1十进制

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

9、制和十六进制转化成二进制八进制转化成二进制： 一位八进制数对应三位二进制数十六进制转化成二进制：一位十六进制数对应四位二进制数144(O)=001 100 100(B)64(H)=0110 0100(B) 6 4 二进制、八进制、十六进制数间的关系 八进制 对应二进制 十六进制对应二进制十六进制 对应二进制0000000008100010011000191001201020010A1010301130011B1011410040100C1100510150101D1101611060110E1110711170111F11113位对应位对应1位位4位对应位对应1位位八进制八进制二进制二进制十六

10、进制十六进制1位对应位对应3位位1位对应位对应4位位二进制二进制十进制十进制八进制八进制十六进制十六进制基数乘除法按权展开求和1.2.21.2.2计算机中数据的表示方法计算机中数据的表示方法 例如，在机器中用8位二进制表示一个数90，其格式为：01011010符号位符号位 0表示正表示正在计算机中数据都是采用二进制表示，对于数的符号，也用“0”或“1”表示，“0”表示正，“1”表示负；数的最高位为符号位。 在机器内存放的正负号符号化的数称为机器数机器数，把机器外存放的由正负号表示的数称作真值真值。例：-0101100 真值 -76 机器数10101100 机器数在运算时必须考虑符号位的处理。为

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

12、低位的左边小数点固定在数值部分最低位的左边定定点点数数符号位符号位隐含小数位（隐含小数位（+0.5)符号位符号位隐含小数位（隐含小数位（-3)31 30 24 23 22 31 30 24 23 22 0 0浮浮点点数数阶符阶符 阶码阶码 数符数符 尾数尾数 阶码部分阶码部分 尾数部分尾数部分 小数点浮动-科学计数法 123.456=0.123456103浮点数分为阶码阶码( (指数指数) )和尾数尾数两部分例：二进制数0.110111*26 在计算机中以浮点格式存放1.2.3 1.2.3 常用信息编码常用信息编码 ACSII码码(American Standard Code for Info

13、rmation Interchange) 128个常用字符，个常用字符，用用7位二进制编码位二进制编码，从，从0到到127 控制字符：控制字符：032，127；普通字符：；普通字符：94个。个。 例如：例如：“a”字符的编码为字符的编码为1100001，对应的十进制数是，对应的十进制数是97； 换行换行 0AH 10 回车回车 0DH 13 空格空格 20H 32 09 30H39H 4857 AZ 41H5AH 6590 az 61H7AH 97122汉字编码汉字编码 输入码 国标码 字形码 机内码 地址码 汉字输出 汉字输入 (1) 汉字输入码 音码类 全拼、双拼、微软拼音、智能ABC等

14、形码类 五笔字型法、郑码输入法等 。(2) 汉字国标码(GB231280)：每个汉字占两个字节。 一级汉字：3755个；二级汉字：3008个。 汉字分区，每个区94个汉字。(3)机内码汉字在设备或信息处理系统内部最基本的表达形式。汉字 国标码 汉字内码中 8680(01010110 01010000)B (11010110 11010000)B 华 5942(00111011 00101010)B (10111011 10101010)B 汉字汉字（4）字形码点阵：汉字字形点阵的代码 矢量：存储的是描述汉字字形的轮廓特征 1.1.2 2.4 .4 计算机中信息单位计算机中信息单位位（Bit）：

15、二进制数的最小单位，通常用“b”表示。字节（Byte）：以8位二进制数组成1个字节，通常用“B”表示。最常用的基本单位K 字节1K = 1024 byteM（兆）字节 1M = 1024 KG（吉） 字节 1G = 1024 M T（太）字节1T = 1024 G字（ word ）：由若干个字节组成，通常我们把计算机一次所能处理的数据的最大位数称为该机器的字长。 著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式： 算法 + 数据结构 = 程序数据结构:对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式算法:对操作的描述。即要求计算机进行操作的步骤1.3

16、 一个程序除了算法和数据结构这主要要素外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示 算法、数据结构、程序设计方法和语言工具是一个程序设计人员应具备的知识 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法” 计算机算法可分为两大类别：数值运算算法：求数值解非数值运算算法：事务管理领域例：图书检索，人事管理等例： 求12345 可以用最原始的方法进行：步骤1：先求1*2，得到结果2。步骤2：将步骤1得到的乘积2再乘以3，得到结果6。步骤3：将6再乘以4，得24。步骤4：将24再乘以5，得120。这就是最后的结果。例：例： 求求12345 1000太繁琐太繁琐 改

17、进的算法：设变量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：使i=2，或写成2 = i S3：使t与i相乘，乘积仍放在变量t中，可表示为：t*i = t S4：使i的值加1，即i+1 = i S5：如果i不大于5，返回重新执行S3；否则，算法结束 最后得到t的值就是 5!的值若求若求1357911

18、33221111相当于相当于i 11 一个有效算法应该具有以下特点：(1) 有穷性。一个算法应包含有限的操作步骤，而不能是无限的。(2) 确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。 一个有效算法应该具有以下特点：(3) 有零个或多个输入。所谓输入是指在执行算法时需要从外界取得必要的信息。(4) 有一个或多个输出。算法的目的是为了求解，“解” 就是输出。没有输出的算法是没有意义的。(5) 有效性。算法中的每一个步骤都应当能有效地执行，并得到确定的结果。 常用的方法有：自然语言传统流程图结构化流程图伪代码 用自然语言表示通俗易懂，但文字冗长，容易出现歧义性 用自然语言

19、描述包含分支和循环的算法，不很方便 除了很简单的问题外，一般不用自然语言 流程图是用一些图框来表示各种操作 用图形表示算法，直观形象，易于理解起止框起止框输入输出框输入输出框处理框处理框判断框判断框流程线流程线连接点连接点x0YN一个入口一个入口两个出口两个出口 流程图是用一些图框来表示各种操作 用图形表示算法，直观形象，易于理解起止框起止框输入输出框输入输出框判断框判断框流程线流程线连接点连接点位置不够位置不够 例：求5！的算法用流程图表示。 求123451 = t输出输出ti5开始开始2 = it*i = ti+1 = i结束结束NY1.传统流程图的弊端 传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制 使用者可以毫不受限制地使流程随意地转来转去，使人难以理解算法的逻辑2.三种基本结构(1) 顺序结构AB2.三种基本结构(2) 选择结构ABYpNAYpN2.三种基本结构(3)