第二講

計算的起源、發(fā)展與本質(zhì)重慶大學計算機學院曾一zyjckxx@計算的起源、發(fā)展與本質(zhì)人類與計算計算模型與電子計算機圖靈獎與計算學科計算的本質(zhì)1.人類與計算文明時代的前夜公元前1萬年-4000年男耕而食，婦織而衣，刑政不用而治，甲兵不起而王?！兑住は缔o》：“上古結(jié)繩而治，后世圣人易之以書契，百官以治，萬命以察。”東漢鄭玄《周易注》：“結(jié)繩為約，事大，大結(jié)其繩，事小，小結(jié)其繩?！惫庞〖拥蹏ü?1世紀）結(jié)繩記事的實物圖，這種結(jié)繩記錄著古印加帝國5500公里的帝國數(shù)據(jù)。1.人類與計算刻痕（契刻）記數(shù)漢朝劉熙在《釋名·釋書契》中說：“契，刻也，刻識其數(shù)也?！庇覉D是在中國甘肅省西寧縣周家寨出土的仰韶期遺址的骨契圖形。1.人類與計算約公元前26世紀-前21世紀初《史記?五帝本紀》：黃帝者，少典之子，姓公孫，名曰軒轅。生而神靈，弱而能言，幼而徇齊，長而敦敏，成而聰明。黃帝大戰(zhàn)蚩尤、炎黃爭帝、堯舜禹禪讓軒轅黃帝為中華民族始祖，人文初祖，中國遠古時期部落聯(lián)盟首領。黃帝(英文：Thehuangdi；Yellowemperor）（前2697-前2599年）少典之子，本姓公孫，長居姬水，因改姓姬，居軒轅之丘（在今河南新鄭西北），故號軒轅氏，出生、創(chuàng)業(yè)和建都于有熊（今河南新鄭），故亦稱有熊氏，因有土德之瑞，故號黃帝。他首先統(tǒng)一中華民族的偉績而載入史冊。他播百谷草木，大力發(fā)展生產(chǎn)，創(chuàng)造文字，始制衣冠，建造舟車，發(fā)明指南車，定算數(shù)，制音律，創(chuàng)醫(yī)學等。與炎帝、蚩尤同為中華民族的祖先，居五帝之首。有嫘祖、嫫母等四位夫人。有《黃帝內(nèi)經(jīng)》傳世。中國數(shù)字，商周時期印度-阿拉伯數(shù)碼，公元8世紀起1.人類與計算1.人類與計算文明時代中國人的發(fā)明中國人發(fā)明算籌有書記載約春秋時期即公元前770-476年春秋戰(zhàn)國時期《老子》：“善數(shù)，不用籌策”。算籌已作為專門的計算工具被普遍采用，籌的算法已趨成熟。到秦漢時代，算籌的長短、粗細有了明確的規(guī)定?！稘h書?律歷志》稱：“其法用竹，徑一寸，長六寸，二百七十一枚而成六觚，為一握?！?。“運籌策于帷幄之中，決勝于千里之外?！弊鏇_之計算π，南北朝約公元500前后3.1415926<π<3.14159271.人類與計算漢末三國時期徐岳《數(shù)術(shù)記遺》：“珠算，控帶四時，經(jīng)緯三才”。約公元14世紀（明朝）算盤取代算籌1.人類與計算1623年，Tubingen大學教授WilhelmSchickhard

在歐洲設計并制造了最早的自動實現(xiàn)四種運算的機器1633年，Oughhtred發(fā)明計算尺1642年，法國數(shù)學家BlaisePascal發(fā)明機械齒輪式加法器1673年，德國數(shù)學家Leibniz改進了Pascal發(fā)明齒輪式加法器，制成了能做四則運算的計算器1.人類與計算1823年，CharlesBabbage制作差分機；1834年，Babbage完成分析機的設計，提出自動通用計算機的思想1854年，英國數(shù)學家George

Boole創(chuàng)建邏輯代數(shù)理論1885年，D.E.Felt設計自動計算器1889年，美國HermanHollerith制成穿孔卡片制表機，并于1990年用于美國人口普查1896年，Hollerith制表機公司成立1.人類與計算1911年，Hollerith制表機公司與其他公司合并成立了計算制表-記錄設備公司，并于1924年命名為IBM公司1936年，英國數(shù)學家AlanTuring發(fā)表“論可計算數(shù)及其在判定問題中的應用”論文，提出了著名的理論計算機模型-圖靈機1938年，德國Konrad

Zuse建成了采用二進制機械式計算機Z11941年，Zuse建成了繼電器計算機Z3并用了符點數(shù)的表示1.人類與計算1943年，英國的一臺名叫“巨人”（Colossus）的計算機投入了運行，用于譯解德國密碼1944年，美國HarvardUniversity的HovardAiken與IBM合作完成機電式自動時序控制計算機MarkI2.計算模型與電子計算機1936年，英國數(shù)學家AlanTuring發(fā)表“論可計算數(shù)及其在判定問題中的應用”論文，提出了著名的理論計算機模型-圖靈機圖靈用形式化方法成功地表述了計算這一過程的本質(zhì)：所謂計算就是計算者（人或機器）對一條兩端可無限延長的紙帶上的一串0和1執(zhí)行指令，一步一步地改變紙帶上的0或1，經(jīng)過有限步驟，最后得到一個滿足預先規(guī)定的符號串的變換過程。圖靈的研究成果是可計算性=圖靈可計算性。丘奇-圖靈論點：即直觀的能行可計算函數(shù)等同于一般遞歸函數(shù)、可λ定義函數(shù)和圖靈機可計算函數(shù)。結(jié)論：任一過程是能行的（能夠具體表現(xiàn)在一個算法中），當且僅當它能夠被一臺圖靈機實現(xiàn)。2.計算模型與電子計算機為了模擬人的這種運算過程，圖靈構(gòu)造出一臺假想的機器，該機器由以下幾個部分組成：①一條無限長的紙帶、②一個讀寫頭、③一個狀態(tài)寄存器、④一套控制規(guī)則。紙帶被劃分為一個個小格子，每個格子上包含一個來自有限字母表的符號，字母表中用一個特殊符號b表示空白。紙帶上的格子從左到右依此被編號為012...，紙帶的右端可以無限伸展。2.計算模型與電子計算機讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，并能改變當前格子上的符號。狀態(tài)寄存器用來保存圖靈機當前所處的狀態(tài)。圖靈機的所有可能狀態(tài)的數(shù)目是有限的，并且有一個特殊的狀態(tài)，稱為停機狀態(tài)。控制規(guī)則它根據(jù)當前機器所處的狀態(tài)以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，并改變狀態(tài)寄存器的值，令機器進入一個新的狀態(tài)。圖靈機模型0101001011010010ABCJKLMNFProgramprogram①無限長的紙帶②讀寫頭③狀態(tài)寄存器④控制規(guī)則圖靈認為：這樣一臺機器就能模擬人類所能進行的任何計算過程?？刂埔?guī)則5元組(qi

Sj

Sk

R(L,N)q1)表示機器目前所處的狀態(tài)表示機器從單元格中讀入的符號表示機器將要寫入單元格中的符號R、L和N分別表示向右(Right)移一格，向左(Left)移一格，不移動(NotMove)表示下一步機器的狀態(tài)（當前狀態(tài)，當前單元格內(nèi)容，要寫的值，移動方向，要輸入的新狀態(tài)）圖靈機模型假設：

b表示空格;

q1表示機器初始狀態(tài);

q4表示機器結(jié)束狀態(tài);

輸入10100010;

讀入頭對準最右邊第一個為0的方格;

狀態(tài)是初始狀態(tài)q1。

則按照下面規(guī)則，輸出正確的計算結(jié)果。q101Lq2 1q110Lq3 2q1bbNq4 3q200Lq2 4q211Lq2 5q2bbNq4 6q301Lq2 7q310Lq3 8q3bbNq4 9圖靈的貢獻b10100010b1q2Programq2q1q101Lq2q110Lq3q1bbNq4q200Lq2q211Lq2q2bbNq4q301Lq2q310Lq3q3bbNq4q4輸入：10100010輸出：10100011S（x）＝x＋1后繼函數(shù)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.計算模型與電子計算機正如飛機的真正成功得力于空氣動力學一樣，計算機由模擬計算向數(shù)字計算的飛躍中，圖靈的理論起了至關(guān)重要的作用。為了紀念圖靈在計算機領域奠基性的貢獻，美國計算機學會決定設立“圖靈獎”，從1966年開始頒發(fā)給最優(yōu)秀的計算機科學家，它就像科學界的諾貝爾獎那樣，是計算機領域的最高榮譽。2.計算模型與電子計算機1945年，美籍數(shù)學家VonNeumann等人首次發(fā)表“電子計算機邏輯結(jié)構(gòu)初探”的報告（PreliminaryDiscussionoftheLogicalDesignofanElectronicComputingInstrument），即計算機史上著名的“101頁報告”（101document），奠定了存儲程序式計算機的理論基礎，奠定了現(xiàn)代計算機體系結(jié)構(gòu)堅實的根基，確立了現(xiàn)代計算機的體系結(jié)構(gòu)（計算機之父）。開始研制相應的EDVAC計算機（ElectronicDiscreteVariableAutomaticComputer，離散變量自動電子計算機）。盡管EDVAC方案在1945年就已經(jīng)完成，但是由于工程上遇到困難，直到1952年1月才制成實際的計算機。馮?諾依曼體系結(jié)構(gòu)的特點主要體現(xiàn)在硬件基本構(gòu)成、二進制系統(tǒng)和程序存儲三個方面。2.計算模型與電子計算機1946年2月14日，世界上第

一臺電子計算機-ENIAC

（埃尼阿克，Electronic

NumericalIntegratorAnd

Computer，電子數(shù)值積分

和計算機）研制成功。ENIAC標志著電子計算機的創(chuàng)世，人類社會從此大步邁進了電子計算機時代的門檻。2.計算模型與電子計算機馮·諾依曼型計算機的特點五大部件存儲程序二進制程序自頂向下執(zhí)行馮·諾依曼“瓶頸”：CPU與M之間頻繁存取數(shù)據(jù)(程序和數(shù)據(jù)）導致速度問題2.計算模型與電子計算機電子管（1946）-晶體管1955-集成電路1961/1964（IBM360/370）-LSI/VLSI從1970年以后一直到現(xiàn)在是第四代計算機的發(fā)展時期。1971年，美國英特爾（Intel）公司的工程師特德·霍夫（TedHoff，1937.10.28～）把2250個晶體管集成到一塊米粒大小的硅片上，制出了世界上第一塊大規(guī)模集成電路?！澳柖伞?Moore'sLaw)“Thenumberoftransistorsperintegratedcircuitwoulddoubleevery18month.”第四代計算機采用大規(guī)模集成電路（Large-ScaleIntegration，簡稱LSI）和超大規(guī)模集成電路（VeryLargeScaleIntegratedcircuit，簡稱VLSI）為主要電子器件制成，其主存儲器采用集成度很高的半導體存儲器，運算速度可達每秒幾百萬次甚至上億次基本運算。第四代計算機以大規(guī)模集成電路和超大規(guī)模集成電路（門數(shù)超過5000個，或元件數(shù)高于10萬個的稱超大規(guī)模集成電路）作為邏輯元件和存儲器，使計算機向著巨型化和微型化兩個方向發(fā)展。在軟件方面，出現(xiàn)了數(shù)據(jù)庫系統(tǒng)、分布式操作系統(tǒng)等，應用軟件的開發(fā)已逐步成為一個龐大的現(xiàn)代產(chǎn)業(yè)。2.計算模型與電子計算機2.計算模型與電子計算機巨型化1974年美國伊利諾斯州立大學研制成功了陣列巨型機ILLIAC－IV1975年，Amdahl公司研制成Amdahl470V/6型計算機日本富士通（Fujitsu）公司生產(chǎn)出FACOM(FujitsuAutomaticCOMputer)M-190機中國銀河-I/II/III巨型計算機—1億/10億/100億次計算，面向工程應用和大規(guī)模數(shù)據(jù)處理，分布式共享存儲結(jié)構(gòu)，64位字長中國的曙光“星云”3000萬億次IBM“紅杉系統(tǒng)”這部超級計算機擁有逾160萬個微型處理器，分布在96部雪柜大小的巨箱內(nèi),需要3422平方英尺的地方安裝。雖然體積龐大，但由于微型處理器變得愈來愈小兼威力大增，每年只消耗6000瓦的電源，即相當于500個美國家庭的耗電量，因此非常具能源效益。速度每秒2千萬億次。2.計算模型與電子計算機微型化智能終端，如手機等日本研制出一種世界上最小的計算機——“空間立方體”，這是一款專門為太空環(huán)境操作設計的計算機，可用于美國宇航局(NASA)、歐洲宇航局(ESA)和日本宇宙航空研究開發(fā)機構(gòu)(JAXA)進行連接通信。2.計算模型與電子計算機商報綜合消息據(jù)外媒報道，美國密歇根大學的科學家近日發(fā)明了世界上最小的計算機系統(tǒng)。這個尚未命名的系統(tǒng)面積只有1平方毫米，用于壓力監(jiān)測，可以植入青光眼患者的眼部，來持續(xù)跟蹤病癥的發(fā)展狀況。系統(tǒng)雖然微小卻五臟俱全，包括耗電極微的微處理器、感壓器、記憶體、薄膜電池，太陽能電池和帶有天線、可以將數(shù)據(jù)傳至外部接收器的無線電臺。2.計算模型與電子計算機其他計算機生物計算機脫氧核糖核酸（DNA）的雙螺旋結(jié)構(gòu)能容納巨量信息，其存儲量相當于半導體芯片的數(shù)百萬倍。一個蛋白質(zhì)分子就是一個存儲體，而且阻抗低、能耗少、發(fā)熱量極小?；诖耍玫鞍踪|(zhì)分子制造出基因芯片，研制生物計算機（也稱分子計算機、基因計算機），已成為當今計算機技術(shù)的最前沿。生物計算機比硅晶片計算機在速度、性能上有質(zhì)的飛躍，被視為極具發(fā)展?jié)摿Α?.計算模型與電子計算機光計算機光計算機和傳統(tǒng)硅芯片計算機的差異在于用光束來代替電子作為信息載體，進行運算和存儲。它用不同波長的光來代表不同的數(shù)據(jù)，可快速完成復雜的計算工作。然而要想造出光計算機，需要開發(fā)出可用一條光束控制另一條光束變化的光學“晶體管”。現(xiàn)有的光學“晶體管”龐大而笨拙，用其造成臺式計算機，將有一輛汽車那么大。因此，短期內(nèi)光計算機達到實用很困難。2.計算模型與電子計算機神經(jīng)網(wǎng)絡計算機模擬人的大腦思維。用硬件實現(xiàn)或用軟件模擬的方法、按照人工神經(jīng)網(wǎng)絡的基本原理而研制的計算機系統(tǒng)。20世紀50年代以來，人們一直對動物或人的大腦和神經(jīng)系統(tǒng)為何能如此有效地進行信息處理進行著研究，并企圖從中得到有關(guān)改進自動信息處理系統(tǒng)的啟發(fā)。2.計算模型與電子計算機網(wǎng)絡計算機網(wǎng)絡計算機（NetworkComputer，簡稱NC）是專用于高速網(wǎng)絡環(huán)境下的計算機終端設備。是一種新的桌面計算機。NC除了有人機交互必需的顯示器，鍵盤鼠標外，它沒有硬盤，軟盤，光驅(qū)等外部存儲設備，是一種瘦客戶機。NC的應用程序和數(shù)據(jù)都放在服務器上，通過網(wǎng)絡從服務器上獲取大部分資源。網(wǎng)絡計算機適應了現(xiàn)代高速網(wǎng)絡環(huán)境對客戶端計算機的要求，能充分利用計算機的資源。3.圖靈獎與計算學科ACM圖靈獎是計算機界的最高獎1966-2010先后有45科學家獲得此殊榮從這些獲獎名單及其所作的貢獻可以看到計算學科發(fā)展的道路，也可以從中學到許多東西歷年圖靈