计算机导论Chapter1.补充.ppt

计算科学导论,华侨大学计算机科学系教授 陈锻生 博士 ,第一章信息与计算科学,本章要点 探索信息的真谛 信息技术与信息科学 计算与计算科学 计算机的信息表示与编码 计算机的逻辑运算与逻辑门电路,1.1 探索信息的真谛,什么是信息 ?,消息,事实,数据,知识,见闻,通知,报告,情报,等. 随着时间的推移，时代赋予了信息新的含义，信息是一个动态的概念。现代“信息”的概念，已经与半导体技术、微电子技术、计算机技术、通讯技术、网络技术、多媒体技术、信息服务业、信息产业、信息经济、信息化社会、信息管理、信息论等含义紧密地联系在一起。,维纳(N. Wiener), 1894年11月26日生于密苏里州的哥伦比亚，1964年3月18日去世。美国数学家，控制论的创始人。,信息就是我们在适应外部世界，并使这种适应反作用于外部世界的过程中，同外部世界进行交换的内容的名称。 要有效的生活,就必须有足够的信息.,1.1 探索信息的真谛,香农（C. E. Shannon) 1916年4月30日出生于美国密歇根州，2001年2月26日去世。美国数学家、信息论的创始人。,信息是能够减少或消除不确定性的东西。,信息是有秩序的量度，是人们对事物了解的不确定性的消除或减少。 平均信息量,熵 page6,返回目录,信息,就是差异。(Longo,1975) 评述此指信息量，而量与质是相关的，没有差异就没有结构，也就没有信息。因而信息量是结构的差异。 是集合的变异度 (Ashby,1956) (狭义)是收信者事先不知道的报道 (广义)是对各种事物的存在方式、运动状态和相互联系特征的一种表达和陈述,是自然界,人类社会和人类思维活动普遍存在的一切物质和事物的属性。 （标准化）信息是事物及其属性标识的集合 确定性的增加 信息就是信息，信息是物质、能量、信息的标示。,评述,在诸多信息定义当中，维纳的定义是很重要的。其重要性就在他指出构成系统要有三个要素，即物质、能量和信息。 物质、能量和信息分别从不同侧面反映了系统三象性质缺一不可但又相互联系。,1.2 信息技术与信息科学,1.2.1 信息技术的发展与定义 信息技术是人类开发和利用信息资源的所有手段的总和； 信息技术既包括有关信息的产生、收集、表示、检测、处理和存储等方面的技术，也包括有关信息的传递、变换、显示、识别、提取、控制和利用等方面的技术。,迄今为止，人类社会已经发生过四次信息技术革命： 第一次革命是人类创造了语言和文字，接着现出了文献。 第二次革命是造纸和印刷术的出现。 第三次革命是电报、电话、电视及其他通讯技术的发明和应用。 第四次革命是电子计算机和现代通讯技术在信息工作中的应用。 目前正在进行第五次信息技术革命，第五次是计算机及计算机网络与通信卫星、光纤等等现代通讯技术的结合.,1.2 信息技术与信息科学,1.2.2 信息技术主要包括 计算机技术（人的思维器官处理信息和决策的功能的扩展）、 微电子技术（扩展了人对信息的存储和使用能力）; 通信技术（扩展人的神经系统传递信息的功能），以及 传感技术（扩展人的感觉器官收集信息的功能）和 控制技术。,1.2 信息技术与信息科学,扩展人类(头脑、躯体、神经、五官等)某器官的能力。旨在改造自然。 哪种更关键？关键还是思路、算法。 而NBIC旨在提升人类自身能力，大科学，以人为本。,1.2 信息技术与信息科学,1.2.3 信息科学 主要研究信息的产生，获取，存储，传输，处理及其应用。是研究信息及其运动规律、扩展人的信息功能(特别是智力功能为主要研究目标)的新兴、边缘、综合性学科。 信息科学的崛起，是信息现象日趋复杂化、信息爆炸性增长、知识重要性增加、信息技术飞速发展等因素相互作用的结果。是信息时代的必然产物。 信息科学是以信息为基本研究对象，传统科学都是以物质和能量为主要研究对象，这是信息科学有别于一切传统科学最基本的特征。,返回目录,1.3 计算与计算科学,1.3.1 探索计算(computing)之源 计算：即符号串的变换。 算法：求解某类问题的通用法则或方法，即符号串变换的规则。,2500年前古希腊数学家哲学家毕达哥拉斯名言： “凡物皆数”。,“心中有数”。 学科=科学？数学描述？,1.3.2 计算模型与图灵(Alan Turing)机。 图灵机计算模型,1.3 计算与计算科学,图灵机是一种抽象计算模型，用来精确定义可计算函数。图灵机由一个控制器，一条可以无限延伸的带子和一个在带子上左右移动的读写头组成。这个概念如此简单的机器，理论上却可以计算任何直观可计算函数。图灵在设计了上述模型后提出，凡是可计算的函数都可用这样的机器来实现，这就是著名的图灵论题（1934）。 图灵机为现代计算机的出现提供了重要的依据： 带子存储设备 命令相当于一组预先设计、存储好的程序 控制器决定读写头的每一步操作,1.3 计算与计算科学,1.3.3 图灵测试,图灵试验的方法：被测试的有一个人，另一个是声称自己有人类智力的机器。测试时，测试人与被测试人是分开的，测试人只有通过一些装置（如键盘）向被测试人问一些问题，这些问题随便是什么问题都可以。 问过一些问题后，如果测试人能够正确地分出谁是人谁是机器，那机器就没有通过图灵测试，如果测试人没有分出谁是机器谁是人，那这个机器就是有人类智能的。 图灵试验对智能问题从行为主义的角度给出了定义,图灵为这项测试亲自拟定了几个示范性问题：,问： 请给我写出有关“第四号桥”主题的十四行诗。 答：不要问我这道题，我从来不会写诗。 问：34957加70764等于多少？ 答：（停30秒后）105721 问：你会下国际象棋吗？ 答：是的。 问：我在我的K1处有棋子K；你仅在K6处有棋子K，在R1处有棋子R。现在轮到你走，你应该下那步棋？ 答：（停15秒钟后）棋子R走到R8处，将军！ 图灵指出：“如果机器在某些现实的条件下，能够非常好地模仿人回答问题，以至提问者在相当长时间里误认它不是机器，那么机器就可以被认为是能够思维的。”,从表面上看，要使机器回答按一定范围提出的问题似乎没有什么困难，可以通过编制特殊的程序来实现。然而，如果提问者并不遵循常规标准，编制回答的程序是极其困难的事情。,例如，提问与回答呈现出下列状况： 问：你会下国际象棋吗？ 答：是的。 问：你会下国际象棋吗？ 答：是的。 问：请再次回答，你会下国际象棋吗？ 答：是的。 你多半会想到，面前的这位是一部笨机器。,如果提问与回答呈现出另一种状态： 问： 你会下国际象棋吗？ 答：是的。 问：你会下国际象棋吗？ 答：是的，我不是已经说过了吗？ 问：请再次回答，你会下国际象棋吗？ 答：你烦不烦，干嘛老提同样的问题。 那么，你面前的这位，大概是人而不是机器。,上述两种对话的区别在于，第一种可明显地感到回答者是从知识库里提取简单的答案，第二种则具有分析综合的能力，回答者知道观察者在反复提出同样的问题。 “图灵测试”没有规定问题的范围和提问的标准，如果想要制造出能通过试验的机器，以我们现在的技术水平，必须在电脑中储存人类所有可以想到的问题，储存对这些问题的所有合乎常理的回答，并且还需要理智地作出选择。,阿兰图灵(Alan Turing，1912-1954 )英国数学家，1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。,24岁论文“论数字计算在决断难题中的应用(1936)”提出了图灵机理论,31岁参与了Colossus(二战时，英国破解德国通讯密码的计算机)的研制,33岁时构思了仿真系统,35岁提出自动程序设计概念,38岁在论文“机器能思考吗”设计了“图灵测试”,后来还创造了一门新学科非线性力学, 42岁去世 。,返回目录,ACM(美国计算机学会)1966年起设立图灵奖。,图灵奖,美国计算机学会（ACM）的年度“图灵奖”，自从1966年设立以来，一直是世界计算机科学领域的最高荣誉，相当于计算机科学界的诺贝尔奖。 图灵奖已经被先后授予给了47位计算机科学界的杰出人物，其中包括关系数据库理论的开创者Edgar Codd、程序语言和算法理论的知名科学家Dijkstra、UNIX操作系统的开创者Dennis Ritchie、面向对象程序设计理论的奠基人以及苹果个人电脑基于鼠标的GUI界面（也就是WINDOWS图形界面的最原始来源）的首创者Alan Kay、Fortran语言的设计者John Backus、IBM-RISC体系结构的创立者John Cocke等大名鼎鼎的计算机科学家。,1.3.4 计算科学(Computing Science),计算科学对描述和变换信息的过程，包括对其理论、分析、设计、效率、实现和应用等进行系统的研究。 包括对算法和可计算性的研究，到根据可计算硬件和软件的实际实现问题的研究，范围极广，但基本问题是： 什么能被有效的自动进行？ 计算机科学(Computer Science存在性？)与技术 计算机体系结构 计算机软件与理论 计算机应用技术 软件工程、信息管理、网络工程、信息技术等 计算科学的最核心任务是算法研究,摘自2005年总统信息技术顾问委员会计算科学确保美国的竞争力. 美国总统报告,计算科学是一个快速发展的多学科领域，它采用高级计算能力来理解和解决复杂问题。计算科学融合了三种要素： 算法(数值或非数值的)和建模与仿真软件：为解决科学（如生物、物理和社会）工程和人文学科问题。 计算机与信息科学：为解决计算需求所发展和优化的高级系统硬件、软件、联网和数据管理组件。 计算基础设施：支持科学与工程问题的解决和发展计算机与信息科学。,算法实例：求两个正整数的最大公约数的Euclidean算法,设M=较大的数，N=较小的数 R=M/N的余数(将整除的余数赋给R) 如果R非零，则M=N(将N值赋给M)，N=R (将R值赋给N),并返回2；否则，最大公约数就是当前N值.,寻找算法实际上就是寻找问题的解决方案。 WinXP是算法吗？,计算机科学算法的科学,算法过程可以解决什么问题？ 如何更简单地找出算法？ 描述和交互算法的技术如何改进？ 如何应用我们算法的知识和技术来制造更好的机器？ 任何分析和比较不同算法的特性？,所有这些问题的一般性主题就是算法的研究。,1.4 计算机的信息表示与编码,1.4.1 信息在计算机中的表示 二进制 基数为2，用0，1表示 逢二进一 二进制计数的优点： 容易表示（可行性） 运算简单 0+0=0,0+1=1+0=1,1+1=10 00=01=10=0,11=1 逻辑性 可靠性,十进制到二进制的转换 整数部分：除二取余； 小数部分：乘二取整。 例如：(29.345)D=(?)B Decimal-Binary,29的二进制,2 29 1 2 14 0 2 7 1 2 3 1 2 1 1 得（11101）B,0.345的二进制,0.345 2 0 0.690 2 1 1.38 2 0 0.76 2 1 1.52 2 1 1.04 得（0.01011）B 小数加整数(29.345)D (11101.01011)B,二进制到十进制的转换：直接按权值展开 例如： (11101.101)B= (29.625)D 其它进制的转换,1.4.2 信息的编码 字符的编码 ASCII码（American Standard Code for Information Interchange） 概念 位（bit） 字节（Byte） 字（Word） ASCII码 7位的二进制编码，表示128个字符，用一个字节表示，最高位不用，为0 34个功能/控制符，94个字符为信息