Chapter1信息与计算科学

1、计算科学导论华侨大学计算机科学系教授陈锻生 博士课程目标与主要内容课程目标与主要内容课程目标课程目标: n理解理解计算计算在在问题求解问题求解中所能起的作用；中所能起的作用；n接触信息技术的基础知识，接触信息技术的基础知识，n培养学习计算机及计算思维的专业技能的兴趣，包括动手编程，为培养学习计算机及计算思维的专业技能的兴趣，包括动手编程，为深入学习计算机专业课程打下良好基础。深入学习计算机专业课程打下良好基础。主要内容主要内容n信息与计算科学信息与计算科学n计算机系统计算机系统n多媒体技术基础多媒体技术基础n程序数据的结构、组织与管理程序数据的结构、组织与管理n数据库技术基础数据库技术基础n计

2、算机网络与应用计算机网络与应用n信息系统安全与社会责任信息系统安全与社会责任n大部分教学材料在书上，n有的相关解释在课堂，而不在书上主要参考资源:n大学信息技术基础省计算机教学指导委员会n计算机科学引论（影印版）（含CD-ROM光盘一张）. （美）奥利里编著. 高等教育出版社。￥39，可当做专业英语学nZelle, John. Python Programming: An Introduction to Computer Science. Wilsonville, OR: Franklin, Beedle & Associates, 2003. MITnWebnhttp:/ 第一章信息

3、与计算科学信息与计算科学n本章要点本章要点探索信息的真谛探索信息的真谛信息技术与信息科学信息技术与信息科学计算与计算科学计算与计算科学计算机的信息表示与编码计算机的信息表示与编码计算机的逻辑运算与逻辑门电路计算机的逻辑运算与逻辑门电路1.1 1.1 探索信息的真谛探索信息的真谛什么是信息 ? ? 现代“信息”的概念，已经与半导体技术、微电子技术、计算机技术、通讯技术、网络技术、多媒体技术、信息服务业、信息产业、信息经济、信息化社会、信息管理、信息论等含义紧密地联系在一起。维纳(N. Wiener), 1894年11月26日生于密苏里州的哥伦比亚，1964年3月18日去世。美国数学家，控制论的创

4、始人。“信息信息就是就是差异差异”,是是我们在我们在适应外部世界，并使这种适适应外部世界，并使这种适应反作用于外部世界的过程应反作用于外部世界的过程中，同外部世界进行交换的中，同外部世界进行交换的内容的名称。内容的名称。要有效的生活要有效的生活,就必须有足够的信息就必须有足够的信息.1.1 探索信息的真谛香农香农（C. E. Shannon) 1916年4月30日出生于美国密歇根州，2001年2月26日去世。美国数学家、信息论的创始人。信息信息是能够减少或消除不确定性的东西。(1948)信息是有秩序的量度，是人们对事物了解的不确定性的消除或减少。熵返回目录返回目录香农的研究成果标志着信息论（香

5、农的研究成果标志着信息论（Information Information TheoryTheory）的诞生。）的诞生。 信息论的三个发展阶段：信息论的三个发展阶段：阶段阶段意义意义研究重点研究重点狭义信息论狭义信息论基础基础用数学方法研究信息，提用数学方法研究信息，提出通信模型出通信模型一般信息论一般信息论发展发展注重信号被噪声干扰时的注重信号被噪声干扰时的处理问题处理问题广义信息论广义信息论丰富丰富拓展拓展注重信息的内容，研究范注重信息的内容，研究范围远远超出通信领域围远远超出通信领域香农对信息的定义香农对信息的定义 信息是有秩序的量度，是人们对事物了解信息是有秩序的量度，是人们对事物了解的

6、不确定性的消除或减少。信息是对组织程度的不确定性的消除或减少。信息是对组织程度的一种测度，信息能使物质系统有序性增强，的一种测度，信息能使物质系统有序性增强，减少破坏、混乱和噪音。减少破坏、混乱和噪音。 通信系统模型：通信系统模型：信源信源信道信道编码编码信宿信宿解码解码信息信息信息信息信号信号信号信号干扰干扰信道：在物理线路上信道：在物理线路上划分的逻辑通道。划分的逻辑通道。香农将香农将“熵熵”的概念引入信息领域。一的概念引入信息领域。一个系统的熵就是它的无组织程度的度量。而个系统的熵就是它的无组织程度的度量。而一个系统中的一个系统中的信息量是它的组织化程度的度信息量是它的组织化程度的度量量

7、，这说明信息与熵恰好是一个相反的量，这说明信息与熵恰好是一个相反的量，信息是负熵。信息是负熵。信息的度量信息的度量l 自信息量及其计算自信息量及其计算若某若某事件事件的基本空间可能出现的元素分别为的基本空间可能出现的元素分别为x x1 1，x x2 2x xm m；且每一个可能值的概率为：；且每一个可能值的概率为： P P（X= xX= xi i）p p i i= =1,2,1,2,m,m 则定义一个随机事件则定义一个随机事件x x所含的信息量称为所含的信息量称为x x的自信的自信息量：息量：I I( (x x) )loglog（1 1/ /p p( (x x) )）log plog p( (

8、x x) ) 其中其中I I( (x x) )代表代表x x的自信息量，的自信息量，p p( (x x) )为事件为事件x x出出现的概率现的概率, ,当底数为当底数为2 2时，信息的计量单位为比特时，信息的计量单位为比特（bitbit）。）。 n 事件的分类事件的分类n 必然事件必然事件：在一定条件下必然要发生的事件：在一定条件下必然要发生的事件 如如: :星期一过后是星期二星期一过后是星期二 ，其发生的概率为，其发生的概率为1 1；n 不可能事件不可能事件：在一定条件下必然不会发生的事：在一定条件下必然不会发生的事件件 如如: :太阳从西边升起太阳从西边升起 ，其发生的概率为，其发生的概率

9、为0 0；n 随机事件随机事件：在相同条件下，可能发生也可能不：在相同条件下，可能发生也可能不发生的事件，其概率介于发生的事件，其概率介于0 0到到1 1之间。之间。例例1 1：假设我们想由甲地告诉乙地关于甲地的：假设我们想由甲地告诉乙地关于甲地的状态，如甲地共有状态，如甲地共有8 8种状态，每种状态发生的种状态，每种状态发生的概率是相等的，即概率是相等的，即1/81/8。如果甲告诉乙，甲处。如果甲告诉乙，甲处于第于第i i种状态，这时甲传给乙的信息量是多少？种状态，这时甲传给乙的信息量是多少？信息量信息量 I I-log-log2 2(1/8)(1/8)3 (bit)3 (bit)l信息熵及

10、其计算信息熵及其计算 信息熵：定义平均信息量来作为信息总体的信息熵：定义平均信息量来作为信息总体的测度。测度。设设X X为一离散随机变量，在集合为一离散随机变量，在集合 x x1 1，x x2 2x xn n 中取值，其概率分布为中取值，其概率分布为 P X= xP X= xi i p pi i i=1,2, i=1,2,n ,n 则定义则定义: :称称H(X)H(X)为离散变量为离散变量X X的信息熵。的信息熵。 niiiniiippppXH11log1log)(11 niip例例2 2：某信源有：某信源有8 8种相互独立的状态，其发生种相互独立的状态，其发生概率分别是概率分别是1/4,0,

11、0,1/4,0,0,0,1/2,1/4,0,0,1/4,0,0,0,1/2,这时信这时信源传给信宿的信息熵是多少？源传给信宿的信息熵是多少？信息熵信息熵 )21(21)41(41)41(41222LogLogLogH = 1.5(bit)= 1.5(bit)香农信息论的局限性香农信息论的局限性香农对信息的定义的出发点是假定事香农对信息的定义的出发点是假定事物状态可以用一个以经典集合论为基础的物状态可以用一个以经典集合论为基础的概率模型来描述。然而实际存在的某些事概率模型来描述。然而实际存在的某些事物运动状态要寻找一个合适的概率模型往物运动状态要寻找一个合适的概率模型往往是非常困难的。这个定义和

12、度量缺少考往是非常困难的。这个定义和度量缺少考虑收信者的主观性和信息的具体内容。虑收信者的主观性和信息的具体内容。数据、消息、信号与信息的区别数据、消息、信号与信息的区别l数据是对客观实体的一种描述形式，是信息的载数据是对客观实体的一种描述形式，是信息的载体。数据是未加工的信息，信息是经过加工的数体。数据是未加工的信息，信息是经过加工的数据，将数据加工为数据的过程称为信息加工或处据，将数据加工为数据的过程称为信息加工或处理。理。l消息：在通信过程中，信息总是经过编码消息：在通信过程中，信息总是经过编码( (符号化符号化) )成为消息以后，才能经由媒介传播的，而信息的成为消息以后，才能经由媒介传

13、播的，而信息的接收者收到信息后，总是要经过译码接收者收到信息后，总是要经过译码( (解读解读) )才获才获取其中的信息。取其中的信息。l信号是数据的电磁或光脉冲编码。信号可以分为信号是数据的电磁或光脉冲编码。信号可以分为模拟信号和数字信号。模拟信号和数字信号。 信息信息n就是差异。(Longo,1975) 评述此指信息量，而量与质是相关的，没有差异就没有结构，也就没有信息。因而信息量是结构的差异。n是集合的变异度 (Ashby,1956) n(狭义)是收信者事先不知道的报道n(广义)是对各种事物的存在方式、运动状态和相互联系特征的一种表达和陈述,是自然界,人类社会和人类思维活动普遍存在的一切物

14、质和事物的属性。n（标准化）信息是事物及其属性标识的集合信息是事物及其属性标识的集合n确定性的增加n信息就是信息，信息是物质、能量、信息的标示。 评述n在诸多信息定义当中，维纳的定义是很重要的。其重要性就在他指出构成系统要有三个要素，即物质、能量和信息。 物质、能量和信息分别从不同侧面反映了系统三象性质缺一不可但又相互联系。 1.21.2 信息技术与信息科学信息技术与信息科学 1.2.1 1.2.1 信息技术的发展与定义信息技术的发展与定义 信息技术是人类开发和利用信息资源信息技术是人类开发和利用信息资源的所有手段的总和；的所有手段的总和； 信息技术既包括有关信息的产生、收信息技术既包括有关信

15、息的产生、收集、表示、检测、处理和存储等方面的技集、表示、检测、处理和存储等方面的技术，也包括有关信息的传递、变换、显示、术，也包括有关信息的传递、变换、显示、识别、提取、控制和利用等方面的技术。识别、提取、控制和利用等方面的技术。迄今为止，人类社会已经发生过四次信息技术革命：迄今为止，人类社会已经发生过四次信息技术革命： 第一次革命第一次革命是人类创造了语言和文字，接着现出了是人类创造了语言和文字，接着现出了文献。文献。 第二次革命第二次革命是造纸和印刷术的出现。是造纸和印刷术的出现。 第三次革命第三次革命是电报、电话、电视及其他通讯技术的是电报、电话、电视及其他通讯技术的发明和应用。发明和

16、应用。 第四次革命第四次革命是电子计算机和现代通讯技术在信息工是电子计算机和现代通讯技术在信息工作中的应用。作中的应用。 目前正在进行目前正在进行第五次第五次信息技术革命，第五次是计信息技术革命，第五次是计算机及计算机网络与通信卫星、光纤等等现代通讯技算机及计算机网络与通信卫星、光纤等等现代通讯技术的结合术的结合.1.2 信息技术与信息科学 1.2.2 1.2.2 信息技术信息技术主要包括主要包括计算机技术计算机技术（人的思维器官处理信息和决策的功能的扩人的思维器官处理信息和决策的功能的扩展展）、）、微电子技术微电子技术（扩展了人对信息的存储和使用能力扩展了人对信息的存储和使用能力）; ;通信

17、技术通信技术（扩展人的神经系统传递信息的功能扩展人的神经系统传递信息的功能），），以及以及传感技术传感技术（扩展人的感觉器官收集信息的功能扩展人的感觉器官收集信息的功能）和）和 控制技术控制技术。1.21.2 信息技术与信息科学信息技术与信息科学 信息技术对人类信息器官的扩展信息技术对人类信息器官的扩展: :人体的信息人体的信息器官器官人体的信息人体的信息器官器官扩展信息器官功能的信扩展信息器官功能的信息技术息技术感觉器官感觉器官获取信息获取信息传感技术传感技术神经器官神经器官传递信息传递信息通信技术通信技术思维器官思维器官加工加工/再生产再生产信息信息计算机与智能技术计算机与智能技术效应器官

18、效应器官使用信息使用信息控制技术控制技术扩展扩展人类(头脑、躯体、神经、五官等)某器官的能力。旨在改造自然。n哪种更关键？关键还是思路、算法。而会聚技术(NBIC)旨在提升提升人类自身能力，大科学，以人为本。n会聚技术与人类以往所有技术不同之处是把提升人类自身能力作为其最终目标。n以往的技术，主要通过扩展人类某器官的能力，来更好地改造世界，让自然界为人类服务。实现人类自身和社会的进步。 1.21.2 信息技术与信息科学信息技术与信息科学 .3 信息科学信息科学 主要研究信息的产生，获取，存储，传输，处理及主要研究信息的产生，获取，存储，传输，处理及其应用。其应用。是研究信息及其

19、运动规律、扩展人的信息功是研究信息及其运动规律、扩展人的信息功能能( (特别是智力功能为主要研究目标特别是智力功能为主要研究目标) )的新兴、边缘、的新兴、边缘、综合性学科。综合性学科。 信息科学的崛起，是信息现象日趋复杂化、信息爆炸性增长、信息科学的崛起，是信息现象日趋复杂化、信息爆炸性增长、知识重要性增加、信息技术飞速发展等因素相互作用的结果。是知识重要性增加、信息技术飞速发展等因素相互作用的结果。是信息时代的必然产物。信息时代的必然产物。 信息科学是以信息科学是以信息信息为基本研究对象，传统科学都为基本研究对象，传统科学都是以物质和能量为主要研究对象，这是信息科学有别是以物质和能量为主要

20、研究对象，这是信息科学有别于一切传统科学最基本的特征。于一切传统科学最基本的特征。返回目录返回目录信息科学n在国家自然科学基金委“十一五”发展规划中曾指出：信息科学是研究信息的产生、获取、存储、显示、处理、传输和利用的科学。n信息科学应该是研究信息的产生、获取、存储、表示、处理、传输、利用及其相互关系的科学.n信息科学是研究信息和信息活动（产生、获取、存储、表示、处理、传输、利用）的规律、原理、相互关系以及技术实现的科学。信息科学发展战略研究中提出了15个优先发展的领域及其研究目标包括1、后摩尔时代的新型器件，纳米级集成电路，微纳光子器件与光电集成，太赫兹与新型红外、毫米波器件，高分辨率探测成

21、像，强场与超强场激光技术，7、低功耗艾级超级计算机系统，多机器人协调与仿生机器人，传感网络基础，B4G移动通信理论与技术，11、网络数据挖掘与理解，互联网计算（云计算），赛博空间安全，复杂控制理论与技术，复杂系统与复杂网络。5个重大交叉学科领域n生命信息检测与解读n量子计算与量子调控n基于光电子的精密测量n空间信息网络基础n面向社会发展的群智计算。社会计算（管理科学？）1.3 计算与计算科学计算与计算科学n1.3.1 探索计算(computing)之源n计算：即符号串的变换。n算法：求解某类问题的通用法则或方法，即符号串变换的规则。2500年前古希腊数学家哲学家毕达哥拉斯名言：“凡物皆数凡物皆

22、数”。“心中有数”。 学科=科学？数学描述？ 图灵机计算模型控制器1000011111111.3.2 计算模型与图灵(Alan Turing)机。 图灵机是一种抽象计算模型，用来精确定义可计算函数。图灵机由一个控制器，一条可以无限延伸的带子和一个在带子上左右移动的读写头组成。这个概念如此简单的机器，理论上却可以计算任何直观可计算函数。图灵在设计了上述模型后提出，凡是可计算的函数都可用这样的机器来实现，这就是著名的图灵论题（1934）。图灵机为现代计算机的出现提供了重要的依据：带子存储存储设备命令相当于一组预先设计、存储好的程序程序控制器决定读写头的每一步操作 1.3 计算与计算科学计算与计算科

23、学1.3.3 图灵测试 图灵试验的方法：被测试的有一个人，另一个是声称自己有人类智力的机器。测试时，测试人与被测试人是分开的，测试人只有通过一些装置（如键盘）向被测试人问一些问题，这些问题随便是什么问题都可以。 问过一些问题后，如果测试人能够正确地分出谁是人谁是机器，那机器就没有通过图灵测试，如果测试人没有分出谁是机器谁是人，那这个机器就是有人类智能的。 图灵试验对智能问题从行为主义的角度给出了定义 图灵为这项测试亲自拟定了几个示范性问题：问： 请给我写出有关“第四号桥”主题的十四行诗。答：不要问我这道题，我从来不会写诗。问：34957加70764等于多少？答：（停30秒后）105721问：你

24、会下国际象棋吗？答：是的。问：我在我的K1处有棋子K；你仅在K6处有棋子K，在R1处有棋子R。现在轮到你走，你应该下那步棋？答：（停15秒钟后）棋子R走到R8处，将军！图灵指出：“如果机器在某些现实的条件下，能够非常好地模仿人回答问题，以至提问者在相当长时间里误认它不是机器，那么机器就可以被认为是能够思维的。”从表面上看，要使机器回答按一定范围提出的问题似乎没有什么困难，可以通过编制特殊的程序来实现。然而，如果提问者并不遵循常规标准，编制回答的程序是极其困难的事情。例如，提问与回答呈现出下列状况：问：你会下国际象棋吗？答：是的。问：你会下国际象棋吗？答：是的。问：请再次回答，你会下国际象棋吗？

25、答：是的。你多半会想到，面前的这位是一部笨机器。 如果提问与回答呈现出另一种状态：问： 你会下国际象棋吗？答：是的。问：你会下国际象棋吗？答：是的，我不是已经说过了吗？问：请再次回答，你会下国际象棋吗？答：你烦不烦，干嘛老提同样的问题。那么，你面前的这位，大概是人而不是机器。 n上述两种对话的区别在于，第一种可明显地感到回答者是从知识库里提取简单的答案，第二种则具有分析综合的能力，回答者知道观察者在反复提出同样的问题。n“图灵测试”没有规定问题的范围和提问的标准，如果想要制造出能通过试验的机器，以我们现在的技术水平，必须在电脑中储存人类所有可以想到的问题，储存对这些问题的所有合乎常理的回答，并

26、且还需要理智地作出选择。 阿兰图灵(Alan Turing，1912-1954 )剑桥大学 “论数字计算在决断难题中的应用(1936)”返回目录返回目录ACM(美国计算机学会)1966年起设立图灵奖。图灵奖美国计算机学会（ACM）的年度“图灵奖”，自从1966年设立以来，一直是世界计算机科学领域的最高荣誉，相当于计算机科学界的诺贝尔奖。图灵奖已经被先后授予给了47位计算机科学界的杰出人物，其中包括关系数据库理论的开创者Edgar Codd、程序语言和算法理论的知名科学家Dijkstra、UNIX操作系统的开创者Dennis Ritchie、面向对象程序设计理论的奠基人以及苹果个人电脑基于鼠标的

27、GUI界面（也就是WINDOWS图形界面的最原始来源）的首创者Alan Kay、Fortran语言的设计者John Backus、IBM-RISC体系结构的创立者John Cocke等大名鼎鼎的计算机科学家。n这个以图灵的名字命名的大奖，代表着60年来世界计算机科学的重大进步和创新，代表着计算机科学和相关技术产业的一次次质的飞跃，同时，也代表着计算机科学界对图灵的崇高敬意。n1950年图灵认为50年后能作出像人一样能思考的机器,目前60年过去了,还没有成功,甚至还没有像人一样能看,听的机器.1.3.4 计算科学(Computing Science)计算科学计算科学对描述和变换信息的过程，包括对

28、其理论、分析、设计、效率、实现和应用等进行系统的研究。包括对算法和可计算性的研究，到根据可计算硬件和软件的实际实现问题的研究，范围极广，但基本问题是：什么能被有效的自动进行？什么能被有效的自动进行？计算机科学(Computer Science存在性？)与技术计算机体系结构计算机软件与理论计算机应用技术 软件工程、信息管理、网络工程、信息技术等n计算科学的最核心任务是算法算法研究摘自2005年总统信息技术顾问委员会计算科学确保美国的竞争力计算科学确保美国的竞争力. 美国总统报告计算科学计算科学是一个快速发展的多学科领域，它采用高是一个快速发展的多学科领域，它采用高级计算能力来理解和解决复杂问题。

29、计算科学融级计算能力来理解和解决复杂问题。计算科学融合了三种要素：合了三种要素：n算法(数值或非数值的)和建模与仿真软件：为解决科学（如生物、物理和社会）工程和人文学科问题。n计算机与信息科学：为解决计算需求所发展和优化的高级系统硬件、软件、联网和数据管理组件。n计算基础设施：支持科学与工程问题的解决和发展计算机与信息科学。算法实例：求两个正整数的最大公约数的Euclidean算法1.设M=较大的数，N=较小的数2.R=M/N的余数(将整除的余数赋给R)3.如果R非零，则M=N(将N值赋给M)，N=R (将R值赋给N),并返回2；否则，最大公约数就是当前N值.寻找算法实际上就是寻找问题的解决方

30、案。WinXP是算法吗？计算机科学算法的科学算法过程可以解决什么问题？如何更简单地找出算法？描述和交互算法的技术如何改进？如何应用我们算法的知识和技术来制造更好的机器？任何分析和比较不同算法的特性？所有这些问题的一般性主题就是算法的研究。所有这些问题的一般性主题就是算法的研究。计算机科学的新思维n算法研究已经从什么功能可以计算之类的转向如何用计算机,比如大型网络结构海量数据信息与检索.（高级的应用大都涉及智能）（高级的应用大都涉及智能）n课程变化: 你会碰到这类问题: random graphs, giant component, phase transition, spectral anal

31、ysis,small world phenomenaProbability and Statistics从高维的有噪声的数据中提取信息例:n选读学校n选购汽车n选科研课题nWikipedia/Encyclopedian特快专递/实时航班云图http:/ Law），2.阿姆达尔定律（Amdals Law）3.局部性法则（Principle of Locality）大部分重要的系统性能问题都与这三个规律有关.摩尔定律:英特尔(Intel)创始人之一戈登摩尔(Gordon Moore)n集成电路上可容纳的晶体管数目，约每隔18个月便会增加一倍(性能也将提升一倍).n微处理器的性能每隔18个月提高一倍

32、，而价格下降一半。 n用一个美元所能买到的电脑性能，每隔18个月翻两番。 阿姆达尔定律(Amdahl law)n阿姆达尔曾致力于并行处理系统的研究。对于固定负载情况下描述并行处理效果的加速比s，阿姆达尔经过深入研究给出了如下公式： nS=1/(a+(1-a)/n) 其中，a为串行计算部分所占比例，n为并行处理结点个数。这样，当a=0时，最大加速比s=n；当a=1时，最小加速比s=1；当n时，极限加速比s 1a，这也就是加速比的上限。例如，若串行代码占整个代码的25，则并行处理的总体性能不可能超过4。这一公式已被学术界所接受，并被称做“阿姆达尔定律” 。局部性法则（Principle of Locality）n好的程序经常呈现出良好的局部性.即经常用到最近用过的数据附近的数据项,或用到最近引用过自己的那些数据.这种倾向称为局部性法则,对软硬件系统的性能和设计有很大影响.n分为时间局部性和空间局部性.1.4 计算机的信息表示与编码计算机的信息表示与编码n1.4.1 信息在计算机中的表示信息在计算机中的表示n二进制