[理学]2011新生研讨课第二讲.ppt

第二讲  计算的起源、发展与本质 重庆大学计算机学院 曾一 zyjckxx@cqu.edu.cn 计算的起源、发展与本质 人类与计算 计算模型与电子计算机 图灵奖与计算学科 计算的本质 1.人类与计算 文明时代的前夜 公元前1万年-4000年 男耕而食，妇织而衣，刑政不用而治，甲兵不起而王。 《易·系辞》：“上古结绳而治，后世圣人易之以书契，百官以治，万命以察。” 东汉郑玄《周易注》：“结绳为约，事大，大结其绳，事小，小结其绳。” 古印加帝国（公元11世纪）结绳记事的实物图，这种结绳记录着古印加帝国5500公里的帝国数据。 1.人类与计算 刻痕（契刻）记数 汉朝刘熙在《释名·释书契》中说：“契，刻也，刻识其数也。” 右图是在中国甘肃省西宁县周家寨出土的仰韶期遗址的骨契图形。 1.人类与计算 约公元前26世纪-前21世纪初 《史记?五帝本纪》：黄帝者，少典之子，姓公孙，名曰轩辕。生而神灵，弱而能言，幼而徇齐，长而敦敏，成而聪明。 黄帝大战蚩尤、炎黄争帝、尧舜禹禅让 轩辕黄帝为中华民族始祖，人文初祖，中国远古时期部落联盟首领。黄帝(英文：The huangdi；Yellow emperor）（前2697-前2599年）少典之子，本姓公孙，长居姬水，因改姓姬，居轩辕之丘（在今河南新郑西北），故号轩辕氏，出生、创业和建都于有熊（今河南新郑），故亦称有熊氏，因有土德之瑞，故号黄帝。他首先统一中华民族的伟绩而载入史册。他播百谷草木，大力发展生产，创造文字，始制衣冠，建造舟车，发明指南车，定算数，制音律，创医学等。与炎帝、蚩尤同为中华民族的祖先，居五帝之首。有嫘祖、嫫母等四位夫人。有《黄帝内经》传世。 1.人类与计算 中国数字，商周时期 印度-阿拉伯数码，公元8世纪起 1.人类与计算 文明时代中国人的发明 中国人发明算筹 有书记载约春秋时期即公元前770-476年 春秋战国时期《老子》：“善数，不用筹策”。算筹已作为专门的计算工具被普遍采用，筹的算法已趋成熟。 到秦汉时代，算筹的长短、粗细有了明确的规定。《汉书?律历志》称：“其法用竹，径一寸，长六寸，二百七十一枚而成六觚，为一握。”。 “运筹策于帷幄之中，决胜于千里之外。” 祖冲之计算π，南北朝约公元500前后 1.人类与计算 汉末三国时期徐岳《数术记遗》：“珠算，控带四时，经纬三才” 。 约公元14世纪（明朝）算盘取代算筹 1.人类与计算 1623年，T ubingen大学教授Wilhelm Schickhard 在欧洲设计并制造了最早的自动实现四种运算的机器 1633年，Oughhtred发明计算尺 1642年，法国数学家Blaise Pascal发明机械齿轮式加法器 1673年，德国数学家Leibniz改进了Pascal发明齿轮式加法器，制成了能做四则运算的计算器 1.人类与计算 1823年，Charles Babbage制作差分机；1834年， Babbage完成分析机的设计，提出自动通用计算机的思想 1854年，英国数学家G eorge Boole创建逻辑代数理论 1885年，D.E.Felt设计自动计算器 1889年，美国Herman Hollerith制成穿孔卡片制表机，并于1990年用于美国人口普查 1896年， Hollerith制表机公司成立 1.人类与计算 1911年， Hollerith制表机公司与其他公司合并成立了计算制表-记录设备公司，并于1924年命名为IBM公司 1936年，英国数学家Alan Turing发表“论可计算数及其在判定问题中的应用”论文，提出了著名的理论计算机模型-图灵机 1938年，德国Konrad Zuse建成了采用二进制机械式计算机Z1 1941年，Zuse建成了继电器计算机Z3并用了符点数的表示 1.人类与计算 1943年，英国的一台名叫“巨人”（Colossus）的计算机投入了运行，用于译解德国密码 1944年，美国Harvard University 的Hovard Aiken与IBM合作完成机电式自动时序控制计算机Mark I 2.计算模型与电子计算机 1936年，英国数学家Alan Turing发表“论可计算数及其在判定问题中的应用”论文，提出了著名的理论计算机模型-图灵机 图灵用形式化方法成功地表述了计算这一过程的本质： 所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。 图灵的研究成果是 可计算性=图灵可计算性。 丘奇-图灵论点：即直观的能行可计算函数等同于一般递归函数、可λ定义函数和图灵机可计算函数。 结论：任一过程是能行的（能够具体表现在一个算法中），当且仅当它能够被一台图灵机实