2011新生研讨课第二讲

第二讲

计算的起源、发展与本质重庆大学计算机学院曾一zyjckxx@计算的起源、发展与本质人类与计算计算模型与电子计算机图灵奖与计算学科计算的本质1.人类与计算文明时代的前夜公元前1万年-4000年男耕而食，妇织而衣，刑政不用而治，甲兵不起而王。《易·系辞》：“上古结绳而治，后世圣人易之以书契，百官以治，万命以察。”东汉郑玄《周易注》：“结绳为约，事大，大结其绳，事小，小结其绳。”古印加帝国（公元11世纪）结绳记事的实物图，这种结绳记录着古印加帝国5500公里的帝国数据。1.人类与计算刻痕（契刻）记数汉朝刘熙在《释名·释书契》中说：“契，刻也，刻识其数也。”右图是在中国甘肃省西宁县周家寨出土的仰韶期遗址的骨契图形。1.人类与计算约公元前26世纪-前21世纪初《史记•五帝本纪》：黄帝者，少典之子，姓公孙，名曰轩辕。生而神灵，弱而能言，幼而徇齐，长而敦敏，成而聪明。黄帝大战蚩尤、炎黄争帝、尧舜禹禅让轩辕黄帝为中华民族始祖，人文初祖，中国远古时期部落联盟首领。黄帝(英文：Thehuangdi；Yellowemperor）（前2697-前2599年）少典之子，本姓公孙，长居姬水，因改姓姬，居轩辕之丘（在今河南新郑西北），故号轩辕氏，出生、创业和建都于有熊（今河南新郑），故亦称有熊氏，因有土德之瑞，故号黄帝。他首先统一中华民族的伟绩而载入史册。他播百谷草木，大力发展生产，创造文字，始制衣冠，建造舟车，发明指南车，定算数，制音律，创医学等。与炎帝、蚩尤同为中华民族的祖先，居五帝之首。有嫘祖、嫫母等四位夫人。有《黄帝内经》传世。中国数字，商周时期印度-阿拉伯数码，公元8世纪起1.人类与计算1.人类与计算文明时代中国人的发明中国人发明算筹有书记载约春秋时期即公元前770-476年春秋战国时期《老子》：“善数，不用筹策”。算筹已作为专门的计算工具被普遍采用，筹的算法已趋成熟。到秦汉时代，算筹的长短、粗细有了明确的规定。《汉书•律历志》称：“其法用竹，径一寸，长六寸，二百七十一枚而成六觚，为一握。”。“运筹策于帷幄之中，决胜于千里之外。”祖冲之计算π，南北朝约公元500前后3.1415926<π<3.14159271.人类与计算汉末三国时期徐岳《数术记遗》：“珠算，控带四时，经纬三才”。约公元14世纪（明朝）算盘取代算筹1.人类与计算1623年，Tubingen大学教授WilhelmSchickhard

在欧洲设计并制造了最早的自动实现四种运算的机器1633年，Oughhtred发明计算尺1642年，法国数学家BlaisePascal发明机械齿轮式加法器1673年，德国数学家Leibniz改进了Pascal发明齿轮式加法器，制成了能做四则运算的计算器1.人类与计算1823年，CharlesBabbage制作差分机；1834年，Babbage完成分析机的设计，提出自动通用计算机的思想1854年，英国数学家George

Boole创建逻辑代数理论1885年，D.E.Felt设计自动计算器1889年，美国HermanHollerith制成穿孔卡片制表机，并于1990年用于美国人口普查1896年，Hollerith制表机公司成立1.人类与计算1911年，Hollerith制表机公司与其他公司合并成立了计算制表-记录设备公司，并于1924年命名为IBM公司1936年，英国数学家AlanTuring发表“论可计算数及其在判定问题中的应用”论文，提出了著名的理论计算机模型-图灵机1938年，德国Konrad

Zuse建成了采用二进制机械式计算机Z11941年，Zuse建成了继电器计算机Z3并用了符点数的表示1.人类与计算1943年，英国的一台名叫“巨人”（Colossus）的计算机投入了运行，用于译解德国密码1944年，美国HarvardUniversity的HovardAiken与IBM合作完成机电式自动时序控制计算机MarkI2.计算模型与电子计算机1936年，英国数学家AlanTuring发表“论可计算数及其在判定问题中的应用”论文，提出了著名的理论计算机模型-图灵机图灵用形式化方法成功地表述了计算这一过程的本质：所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。图灵的研究成果是可计算性=图灵可计算性。丘奇-图灵论点：即直观的能行可计算函数等同于一般递归函数、可λ定义函数和图灵机可计算函数。结论：任一过程是能行的（能够具体表现在一个算法中），当且仅当它能够被一台图灵机实现。2.计算模型与电子计算机为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：①一条无限长的纸带、②一个读写头、③一个状态寄存器、④一套控制规则。纸带被划分为一个个小格子，每个格子上包含一个来自有限字母表的符号，字母表中用一个特殊符号b表示空白。纸带上的格子从左到右依此被编号为012...，纸带的右端可以无限伸展。2.计算模型与电子计算机读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。状态寄存器用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。控制规则它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。图灵机模型0101001011010010ABCJKLMNFProgramprogram①无限长的纸带②读写头③状态寄存器④控制规则图灵认为：这样一台机器就能模拟人类所能进行的任何计算过程。控制规则5元组(qi

Sj

Sk

R(L,N)q1)表示机器目前所处的状态表示机器从单元格中读入的符号表示机器将要写入单元格中的符号R、L和N分别表示向右(Right)移一格，向左(Left)移一格，不移动(NotMove)表示下一步机器的状态（当前状态，当前单元格内容，要写的值，移动方向，要输入的新状态）图灵机模型假设：

b表示空格;

q1表示机器初始状态;

q4表示机器结束状态;

输入10100010;

读入头对准最右边第一个为0的方格;

状态是初始状态q1。

则按照下面规则，输出正确的计算结果。q101Lq2 1q110Lq3 2q1bbNq4 3q200Lq2 4q211Lq2 5q2bbNq4 6q301Lq2 7q310Lq3 8q3bbNq4 9图灵的贡献b10100010b1q2Programq2q1q101Lq2q110Lq3q1bbNq4q200Lq2q211Lq2q2bbNq4q301Lq2q310Lq3q3bbNq4q4输入：10100010输出：10100011S（x）＝x＋1后继函数q1(0,1)/L(b,b)/N(1,1)/L(b,,b)/N(0,1)/L(1,0)/L(0,0)/Lq2q4q3(b,b)/N(1,0)/L2.计算模型与电子计算机正如飞机的真正成功得力于空气动力学一样，计算机由模拟计算向数字计算的飞跃中，图灵的理论起了至关重要的作用。为了纪念图灵在计算机领域奠基性的贡献，美国计算机学会决定设立“图灵奖”，从1966年开始颁发给最优秀的计算机科学家，它就像科学界的诺贝尔奖那样，是计算机领域的最高荣誉。2.计算模型与电子计算机1945年，美籍数学家VonNeumann等人首次发表“电子计算机逻辑结构初探”的报告（PreliminaryDiscussionoftheLogicalDesignofanElectronicComputingInstrument），即计算机史上著名的“101页报告”（101document），奠定了存储程序式计算机的理论基础，奠定了现代计算机体系结构坚实的根基，确立了现代计算机的体系结构（计算机之父）。开始研制相应的EDVAC计算机（ElectronicDiscreteVariableAutomaticComputer，离散变量自动电子计算机）。尽管EDVAC方案在1945年就已经完成，但是由于工程上遇到困难，直到1952年1月才制成实际的计算机。冯•诺依曼体系结构的特点主要体现在硬件基本构成、二进制系统和程序存储三个方面。2.计算模型与电子计算机1946年2月14日，世界上第

一台电子计算机-ENIAC

（埃尼阿克，Electronic

NumericalIntegratorAnd

Computer，电子数值积分

和计算机）研制成功。ENIAC标志着电子计算机的创世，人类社会从此大步迈进了电子计算机时代的门槛。2.计算模型与电子计算机冯·诺依曼型计算机的特点五大部件存储程序二进制程序自顶向下执行冯·诺依曼“瓶颈”：CPU与M之间频繁存取数据(程序和数据）导致速度问题2.计算模型与电子计算机电子管（1946）-晶体管1955-集成电路1961/1964（IBM360/370）-LSI/VLSI从1970年以后一直到现在是第四代计算机的发展时期。1971年，美国英特尔（Intel）公司的工程师特德·霍夫（TedHoff，1937.10.28～）把2250个晶体管集成到一块米粒大小的硅片上，制出了世界上第一块大规模集成电路。“摩尔定律”(Moore'sLaw)“Thenumberoftransistorsperintegratedcircuitwoulddoubleevery18month.”第四代计算机采用大规模集成电路（Large-ScaleIntegration，简称LSI）和超大规模集成电路（VeryLargeScaleIntegratedcircuit，简称VLSI）为主要电子器件制成，其主存储器采用集成度很高的半导体存储器，运算速度可达每秒几百万次甚至上亿次基本运算。第四代计算机以大规模集成电路和超大规模集成电路（门数超过5000个，或元件数高于10万个的称超大规模集成电路）作为逻辑元件和存储器，使计算机向着巨型化和微型化两个方向发展。在软件方面，出现了数据库系统、分布式操作系统等，应用软件的开发已逐步成为一个庞大的现代产业。2.计算模型与电子计算机2.计算模型与电子计算机巨型化1974年美国伊利诺斯州立大学研制成功了阵列巨型机ILLIAC－IV1975年，Amdahl公司研制成Amdahl470V/6型计算机日本富士通（Fujitsu）公司生产出FACOM(FujitsuAutomaticCOMputer)M-190机中国银河-I/II/III巨型计算机—1亿/10亿/100亿次计算，面向工程应用和大规模数据处理，分布式共享存储结构，64位字长中国的曙光“星云”3000万亿次IBM“红杉系统”这部超级计算机拥有逾160万个微型处理器，分布在96部雪柜大小的巨箱内,需要3422平方英尺的地方安装。虽然体积庞大，但由于微型处理器变得愈来愈小兼威力大增，每年只消耗6000瓦的电源，即相当于500个美国家庭的耗电量，因此非常具能源效益。速度每秒2千万亿次。2.计算模型与电子计算机微型化智能终端，如手机等日本研制出一种世界上最小的计算机——“空间立方体”，这是一款专门为太空环境操作设计的计算机，可用于美国宇航局(NASA)、欧洲宇航局(ESA)和日本宇宙航空研究开发机构(JAXA)进行连接通信。2.计算模型与电子计算机商报综合消息据外媒报道，美国密歇根大学的科学家近日发明了世界上最小的计算机系统。这个尚未命名的系统面积只有1平方毫米，用于压力监测，可以植入青光眼患者的眼部，来持续跟踪病症的发展状况。系统虽然微小却五脏俱全，包括耗电极微的微处理器、感压器、记忆体、薄膜电池，太阳能电池和带有天线、可以将数据传至外部接收器的无线电台。2.计算模型与电子计算机其他计算机生物计算机脱氧核糖核酸（DNA）的双螺旋结构能容纳巨量信息，其存储量相当于半导体芯片的数百万倍。一个蛋白质分子就是一个存储体，而且阻抗低、能耗少、发热量极小。基于此，利用蛋白质分子制造出基因芯片，研制生物计算机（也称分子计算机、基因计算机），已成为当今计算机技术的最前沿。生物计算机比硅晶片计算机在速度、性能上有质的飞跃，被视为极具发展潜力。2.计算模型与电子计算机光计算机光计算机和传统硅芯片计算机的差异在于用光束来代替电子作为信息载体，进行运算和存储。它用不同波长的光来代表不同的数据，可快速完成复杂的计算工作。然而要想造出光计算机，需要开发出可用一条光束控制另一条光束变化的光学“晶体管”。现有的光学“晶体管”庞大而笨拙，用其造成台式计算机，将有一辆汽车那么大。因此，短期内光计算机达到实用很困难。2.计算模型与电子计算机神经网络计算机模拟人的大脑思维。用硬件实现或用软件模拟的方法、按照人工神经网络的基本原理而研制的计算机系统。20世纪50年代以来，人们一直对动物或人的大脑和神经系统为何能如此有效地进行信息处理进行着研究，并企图从中得到有关改进自动信息处理系统的启发。2.计算模型与电子计算机网络计算机网络计算机（NetworkComputer，简称NC）是专用于高速网络环境下的计算机终端设备。是一种新的桌面计算机。NC除了有人机交互必需的显示器，键盘鼠标外，它没有硬盘，软盘，光驱等外部存储设备，是一种瘦客户机。NC的应用程序和数据都放在服务器上，通过网络从服务器上获取大部分资源。网络计算机适应了现代高速网络环境对客户端计算机的要求，能充分利用计算机的资源。3.图灵奖与计算学科ACM图灵奖是计算机界的最高奖1966-2010先后有45科学家获得此殊荣从这些获奖名单及其所作的贡献可以看到计算学科发展的道路，也可以从中学到许多东西历年图灵