计算思维与信息表示

计算思维与计算机中的信息表示计算思维计算机中的信息表示•2006年3月，美国卡内基·梅隆大学计算机科学系主任周以真（JeannetteM.Wing）教授在美国计算机权威期刊《CommunicationsoftheACM》杂志上给出，并定义的计算思维（ComputationalThinking）。周教授认为：•计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。•21世纪每个人都应该具备的能力。计算思维计算思维是人类应具备的第三种思维•理论思维：对事物的感性认识资料，经过抽象、概括，形成描述事物本质的概念，主要以推理和演绎的方法，探寻概念之间相互联系的一种思维活动。•实验思维：通过观察和实验的手段，揭示自然规律法则的一种思维方法。特征是观察、整理、归纳、对比和验证。•计算思维：构造思维，是指从具体的算法设计规范入手，通过算法过程的构造与实施，来解决给定问题的一种思维方法。在当前环境下，理论与实验手段面临大规模数据的情况下，不可避免的要用计算手段来辅助进行。计算机能干什么多记忆一些数据，多接收一些信息，算的快一些，交流方便些。以亿次的计算，求解繁复的微分方程和方程组，描绘超乎想象的图像，模拟无法实现或耗资巨大的过程等等。计算机不能干什么不能替人拿主意、定方案人机分界面恰在思考二字，即把计算机所不具备的直觉、综合、机敏，甚至艺术家的灵感留给人，由人来创造性的开发各种所需的算法、模型、方法。计算思维的关键：用计算机模拟现实世界计算思维的本质:抽象和自动化计算思维中的抽象完全超越物理的时空观，并完全用符号来表示。自动化是机械地一步一步自动执行，其基础和前提是抽象。案例：18世纪著名的古典数学问题——哥尼斯堡七桥问题。哥尼斯堡七桥问题哥尼斯堡地处东普鲁士，位于普雷格尔河的两岸及河中心的两个岛上，城市各部分由七座桥与两岸连结起来。多年来，当地的居民总有一个愿望：从家里出去散步，能否通过没每座桥恰好一次，再返回家中？但是任何人也没有找到这样一条理想的路径。1976年，瑞士数学家欧拉(Euler)解决问题的办法是把陆地抽象为一个点，用连接两个点的线段表示桥梁，将该问题抽象成点与线连接图的数学问题。把一个实际问题抽象成合适的“数学模型”，这就是计算思维中的抽象。计算思维品质对人的能力影响作用问题抽象层次的能力是衡量人的思维品质的重要方面。根据求解问题的需要，在分析问题的过程中，人们可以对问题进行多层次的抽象，将注意力集中在感兴趣的抽象层次或关系相对密切的上下层，抛弃那些不感兴趣的(不重要的)层次或细节，使问题分析相对简单，以控制问题解决的复杂性。抽象的概念是由具体概念依其“共性”而产生的，把具体概念的诸多个性排出，集中描述其共性，就会产生一个抽象性的概念。人的大脑思维方法和思维品质的差异决定着：同一问题解决办法和处理方式各不相同。其付出的代价与取得效果甚至可能天壤之别。计算思维的应用领域计算思维是每个人应当具备的基本技能，也是创新人才的基本要求和专业素质，每个人都应当学习和应用计算思维。正如印刷出版促进了阅读、写作和算术的传播一样，计算和计算机也促进着计算思维的传播。迄今为止，计算思维不仅渗透到每个人的生活，而且对生物信息学、生物计算、专家系统、经济学等学科领域产生了重大影响，在科技创新与教育教学中起着非常重要的作用。计算思维领域提出的新思想、新方法不断地促进自然科学、工程技术和社会经济等领域产生革命性的发展。1.2计算机中的信息表示101.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）二进制数的运算规则简单，这将使计算机的硬件结构大大简化。（3）二进制数的两个数字符号“1”和“0”正好与逻辑命题的两个值“真”和“假”相对应，为计算机实现逻辑运算提供了便利的条件。但二进制数书写冗长，所以为书写方便，一般用十六进制数或八进制数作为二进制数的简化表示。1．N为基数，N个数码，逢N进一数制的特点2．采用位权表示法位权在一个数字当中，处在不同位置上的相同数字所表示的值也是不同的。一个数字在某个位置上的值等于该数字与这个位置上的因子的乘积，而该因子的值恰是由所在位置相对于小数点的距离来确定，这个因子就是位权。例如：（286）10中，2的位权是100；8的位权是10，6的位权是114十六进制数2．数制的相互转换1．十进制数转化为二进制数、八进制数、十六进制数整数：除以基值取余法，直到商为零时为止，逆读小数：乘以基值取整法，直到积中的小数部分为零，或者达到所要求的精度为止，顺读2．二进制、八进制、十六进制转化为十进制----按权展开，相加求和(110101)2=1×25+1×24+0×23+1×22+0×21+1×20=32+16+0+4+0+1=(53)103.二进制转化成八进制和十六进制转化成八进制：以小数点为中心向两边分组,每三位一组.整数部分不足位数左补0，小数部分不足位数右补转化成十六进制：以小数点为中心向两边分组,每四位一组.整数部分不足位数左补0，小数部分不足位数右补04.八进制和十六进制转化成二进制八进制转化成二进制：一位八进制数对应三位二进制数十六进制转化成二进制：一位十六进制数对应四位二进制数144(O)=001100100(B)64(H)=01100100(B)64二进制、八进制、十六进制数间的关系八进制对应二进制十六进制对应二进制十六进制对应二进制0000000008100010011000191001201020010A1010301130011B1011410040100C1100510150101D1101611060110E1110711170111F1111常用数制间的转换小结3位对应1位4位对应1位八进制二进制十六进制1位对应3位1位对应4位二进制十进制八进制十六进制1.2.2计算机中数据的表示方法•例如，在机器中用8位二进制表示一个数90，其格式为：01011010符号位0表示正•在计算机中数据都是采用二进制表示，对于数的符号，也用“0”或“1”表示，“0”表示正，“1”表示负；数的最高位为符号位。•在机器内存放的正负号符号化的数称为机器数，把机器外存放的由正负号表示的数称作真值。例：-0101100真值-76机器数10101100•机器数在运算时必须考虑符号位的处理。为了便于运算，在机器中有三种表示数的方法：•1、原码原码的最高位为符号位，数值部分为原数的绝对值。[+105]原=01101001[-105]原=11101001•2、反码正数的反码与其原码相同。而负数的反码等于其绝对值各位求反。[+105]反=01101001[-105]反=10010110•3、补码正数的补码与其原码相同。负数的补码是把其原码除符号位外的各位先求其反码，然后在最低位加1。。[+105]补=01101001[-105]补=10010111•0100000010000011定点小数：小数点固定在数值部分最高位的左边定点整数：小数点固定在数值部分最低位的左边定点数符号位隐含小数位（+0.5)符号位隐含小数位（-3)31302423220浮点数阶符阶码数符尾数阶码部分尾数部分……小数点浮动--科学计数法123.456=0.123456×103浮点数分为阶码(指数)和尾数两部分例：二进制数0.110111*26在计算机中以浮点格式存放1.2.3常用信息编码西文字符ACSII码(AmericanStandardCodeforInformationInterchange)128个常用字符，用7位二进制编码，从0到127控制字符：0～32，127；普通字符：94个。例如：“a”字符的编码为1100001，对应的十进制数是97；换行0AH10回车0DH13空格20H32‘0’～‘9’30H～39H48～57‘A’～‘Z’41H～5AH65～90‘a’～‘z’61H～7AH97～122汉字编码输入码国标码字形码机内码地址码汉字输出汉字输入(1)汉字输入码音码类全拼、双拼、微软拼音、智能ABC等形码类五笔字型法、郑码输入法等。(2)汉字国标码(GB2312－80)：每个汉字占两个字节。一级汉字：3755个；二级汉字：3008个。汉字分区，每个区94个汉字。(3)机内码汉字在设备或信息处理系统内部最基本的表达形式。汉字国标码汉字内码中8680(0101011001010000)B(1101011011010000)B华5942(0011101100101010)B(1011101110101010)B汉字（4）字形码点阵：汉字字形点阵的代码矢量：存储的是描述汉字字形的轮廓特征1.2.4计算机中信息单位位（Bit）：二进制数的最小单位，通常用“b”表示。字节（Byte）：以8位二进制数组成1个字节，通常用“B”表示。最常用的基本单位K字节1K=1024byteM（兆）字节1M=1024KG（吉）字节1G=1024MT（太）字节1T=1024G字（word）：由若干个字节组成，通常我们把计算机一次所能处理的数据的最大位数称为该机器的字长。•著名计算机科学家沃思(NikiklausWirth)提出一个公式：算法+数据结构=程序数据结构:对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式算法:对操作的描述。即要求计算机进行操作的步骤1.3计算机程序概述•一个程序除了算法和数据结构这主要要素外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示•算法、数据结构、程序设计方法和语言工具是一个程序设计人员应具备的知识什么是算法•广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”•计算机算法可分为两大类别：–数值运算算法：求数值解–非数值运算算法：事务管理领域例：图书检索，人事管理等简单的算法举例例：求1×2×3×4×5•可以用最原始的方法进行：–步骤1：先求1*2，得到结果2。–步骤2：将步骤1得到的乘积2再乘以3，得到结果6。–步骤3：将6再乘以4，得24。–步骤4：将24再乘以5，得120。这就是最后的结果。例：求1×2×3×4×5×…×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：使i=2，或写成2=i•S3：使t与i相乘，乘积仍放在变量t中，可表示为：t*i=t•S4：使i的值加1，即i+1=i•S5：如果i不大于5，返回重新执行S3；否则，算法结束•最后得到t的值就是5!的值若求1×3×5×7×9×1133221111相当于i≦11算法的特性•一个有效算法应该具有以下特点：(1)有穷性。一个算法应包含有限的操作步骤，而不能是无限的。(2)确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。•一个有效算法应该具有以下特点：(3)有零个或多个输入。所谓输入是指在执行算法时需要从外界取得必要的信息。(4)有一个或多个输出。算法的目的是为了求解，“解”就是输出。–没有输出的算法是没有意义的。(5)有效性。算法中的每一个步骤都应当能有效地执行，并得到确定的结果。怎样表示一个算法•常用的方法有：–自然语言–传统流程图–结