計算機科學的本史元春.ppt

1、計算機科學的本質史元春清華大學計算機科學與技術系,Computing History is only,Mainframe Computing,Whats Computer?,Computing is becomingpervasive/ubiquitous,1946 ENIAC Von Neumann Computer Modern Computers,History of Computing Machines,The Abacus The Mechanical Calculators The Electromechanical Machines,History of Computing Ma

2、chines:1946,算盤 數(shù)字由算珠的數(shù)量表示 數(shù)位由算珠的位置確定 通過手動完成從低位到高位的數(shù)字傳送（十進制） 執(zhí)行運算就是按照一定的規(guī)則移動算珠的位置,History of Computing Machines:1946,機械時代,History of Computing Machines:1946,1642，Pascal（法）： Pascaline，加法機 1694，Leibnitz（德）：calculator，加減乘除演算機 1834，Babbage（英）：Difference Engine，計算平方等,借助機械裝置(齒輪、杠桿等)傳送十進制位，機械裝置的動力來自計算人員的手,機

3、電時代,History of Computing Machines:1946,1886，Herman Hollerith：Tabulator 1944，Howard Aiken: Harvard Mark I,使用電力做動力，但計算結構本身還是機械式的,ENIAC：Electronic Numerical Integrator And Calculator (電子數(shù)字積分器和計算器) 1946，U Penn 170m2，30 tons，150kwatts, 18800 vacuum tubes，5000 ps The first high speed general electronic co

4、mputer,History of Computing Machines:ENIAC,ENIAC的致命缺點：程序與計算兩分離 指揮近2萬電子管“開關”工作的程序指令，存放在機器的外部電路里。計算某個題目前，數(shù)十人用幾小時甚至好幾天把數(shù)百條線路用手接通，才能進行幾分鐘運算 1946, Stored Program: EDVAC (electronic discrete variable automatic computer, 離散變量自動電子計算機) All computers more or less based on the same basic design,The Von Neumann

5、 Architecture,Model for designing and building computers, based on the following three characteristics: The computer consists of four main sub-systems: Memory ALU (Arithmetic/Logic Unit) Control Unit Input/Output System (I/O) Program is stored in memory during execution. Program instructions are exe

6、cuted sequentially.,The Von Neumann Architecture,Memory,Processor (CPU),Input-Output,Control Unit,ALU,Store data and program,Execute program,Do arithmetic/logic operationsrequested by program,Communicate with outside world, e.g. Screen Keyboard Storage devices .,Bus,The Von Neumann Architecture,von

7、Neumann Architecture,1946 ENIAC Von Neumann Computer Modern Computers,History of Computing Machines,First Four Generations,First generation: Vacuum tube computers (1940s - 1950s) Second generation (1950s): Transistors,First Four Generations,First generation: Vacuum tube computers (1940s - 1950s) Sec

8、ond generation (1950s): Transistors Third generation (1960s and 1970s): Integrated circuits Fourth generation (late 1970s through present): LSI and VLSI Personal computers, computer networks, WWW, etc. Next generation: New user interfaces (voice activation, etc.) New computational paradigm (parallel

9、 processing, neural network, etc.) Parallel processing, artificial intelligence, optical processing, visual programming, gigabit networks, etc.,History of Computing Machines What we can learn from Moores Law Founders of Computing Theory The Essential Issue of Computer Science Computing as a Discipli

10、ne,Syllabus,What we can learn from Moores Law,Moores Law In 1965, Gordon Moore (co-founder of Intel), wrote an article on the future development of semiconductor industry at Electronics magazine. He noted that the complexity of minimum cost semiconductor components had doubled per year since the fir

11、st prototype microchip was produced in 1959. This exponential increase in the number of components on a chip became later known as Moores Law.,What we can learn from Moores Law,Moores Law In the 1980s, Moores Law started to be described as the doubling of number of transistors on a chip every 18 mon

12、ths. At the beginning of the 1990s, Moores Law became commonly interpreted as the doubling of microprocessor power every 18 months. In the 1990s, Moores Law became widely associated with the claim that computing power at fixed cost is doubling every 18 months.,Moores Law Intels 4004 (1971) to the pr

13、esent, the increasing of the number of transistors on its microprocessor fits it well CPU leads the development of Computer Industry New Moores Law: Number of Internet Users doubles every 9 months The same to data stream and bandwidth ,What we can learn from Moores Law,What we can learn from Moores

14、Law,Microelectronictechnique Revolution Now in LSI manufacture, 0.07m Intel produce 65nm processor, 2006 Panasonic produce 45nm LSI, 2007 微電子工業(yè)發(fā)展的每下一步線寬約是前一步的0.7倍 硅微集成電路的物理極限是10納米 納米計算機、并行計算機、量子計算機 Q: 摩爾定律是否像牛頓定律一樣，是自然界不變的定律？,What we can learn from Moores Law,Inference from Moores Law 計算機的高速發(fā)展 “時間就是

15、金錢” 計算機的性價比永遠在提高 具有“自我強化”特征 廠商需要不斷改進性價比 “過去無關緊要” 知識和技術發(fā)展很快 產(chǎn)品技術幾年即過時 掌握基本概念、原理和核心技術的重要性 終身學習，保持與知識的發(fā)展同步,What we can learn from Moores Law,History of Computing Machines What we can learn from Moores Law Founders of Computing Theory The Essential Issue of Computer Science Computing as a Discipline,Syl

16、labus,George Boole 18151864, Mathematician and Philosopher Boolean Algebra （布爾代數(shù)） Alan Turing 1912-1954, Founder of computer science, Mathematician and Philosopher Turing Machine advisor: Von Neuman 1937, “On computable numbers, with an application to the Entscheidungsproblem ”論應用于解決問題的可計算數(shù)字 ：Turing

17、 Machine 1950, “Can machines think?” Turing Test 他用計算機、人工智能在現(xiàn)代數(shù)理邏輯和現(xiàn)實世界間搭一起一座不朽的橋梁 1966, ACM (Association for Computing Machinery)設立Turing Award,Alan Turing,所謂可計算性其實是一個哲學定義：如果存在一個機械過程，如果我們給一個輸入，這個過程（或機器）就能在有限步內(nèi)給出答案，那么這個問題就稱作是可計算的 Turing回答了可計算性問題：哪些問題類是可以用計算機解決的，計算機的通用計算能力問題，并給出了理論計算模型圖靈機和它的輸入數(shù)據(jù)、計算程序

18、和輸出結果的表示方式 圖靈機由一條雙向都可以無限延長的、被分成一個個小方格的磁帶；一個有限狀態(tài)控制器；一個讀寫磁頭3部分組成,Turing Machine,圖靈機一步一步地進行工作，其工作情況取決于三個條件： 有限狀態(tài)控制器內(nèi)部狀態(tài) 讀寫磁頭掃描在磁帶的哪個方格上 該方格上有什么信息 每一步工作的過程： 讀 “讀寫磁頭”當前所掃描的磁帶方格的存儲內(nèi)容 si 根據(jù)si的值以及“有限狀態(tài)控制器”當前內(nèi)部狀態(tài)qi， 決定在當前方格寫入新的內(nèi)容 si 并決定 “讀寫磁頭”由當前位置 或左移(一格)、或右移(一格)、或不移動、或停機 并決定 “有限控狀態(tài)制器”新的控制狀態(tài) q i+1 進入下一步工作，按

19、同樣的方式工作；如此周而復始，直到遇到命令機器停機。,Turing Machine,Fundamentals,當控制器前處于狀態(tài)q2，磁頭所指的磁帶方格內(nèi)容為1，現(xiàn)在要采取得動作是：將該磁帶方格的內(nèi)容改寫為0，磁頭向右移動一格，控制器內(nèi)狀態(tài)變?yōu)閝5,Example,Turing Machine,圖靈機的這種由狀態(tài)、符號確定的工作過程叫做圖靈機程序，可以由一個五元組序列來定義： q：當前狀態(tài) b：當前方格中的符號 a：當前方格中修改后的符號 m：磁頭移動的方向，左移L（Left）、右移R（Right），不動N（No-motion） q：下一狀態(tài),Turing Machine,前面例子中，圖靈機的

20、一步動作可表示為： ,A Turing machine for incrementing a value,圖靈機計算實例 f(x) = 2x,在二進制圖靈機上計算函數(shù)f(x) = 2x，即x，f(x)都用二進制表示，磁帶方格中只能用0和1兩個符號，B表示空白。 約定： 1、開始時，磁帶上只有一連續(xù)的方格串上放入x的相應的二進制值符號，其余方格都為空白。 2、機器從狀態(tài)q1開始，磁頭指向x最左一位所在地方格。 3、停機時，磁帶上非空方格串所組成的二進制值即代表f(x)。,在前面的約定下，計算f(x) = 2x的圖靈機程序如下，其中：Halt表示停機，Error表示在計算中不會出現(xiàn),圖靈機計算實例

21、 f(x) = 2x,為什么以x的二進制數(shù)為符號作為磁帶初始值? 為什么停機后磁帶上的二進制值就是最終結果? 為什么有7種狀態(tài)? 為什么在每種狀態(tài)中要進行這些動作? 圖靈機程序設計,圖靈機計算實例 f(x) = 2x,開始,第1步,第2步,圖靈機計算實例 f(x) = 2x,第5步,第4步,第3步,圖靈機計算實例 f(x) = 2x,第8步,第7步,第6步,圖靈機計算實例 f(x) = 2x,第11步,第10步,第9步,圖靈機計算實例 f(x) = 2x,第14步,第13步,第12步,圖靈機計算實例 f(x) = 2x,第17步,第16步,第15步,圖靈機計算實例 f(x) = 2x,第20步

22、,第19步,第18步,圖靈機計算實例 f(x) = 2x,結束,f(2) = 22 = 4,第21步,第22步,圖靈機計算實例 f(x) = 2x,表面上看，圖靈機的計算功能似乎很弱，實際上，只要時間足夠長（即允許足夠的工作步數(shù)）和有足夠的空間（即磁帶足夠長），則圖靈機可以替代目前的任何計算機 圖靈論題：凡是可計算的函數(shù)都可以用圖靈機來計算： 可計算性 圖靈可計算性 稱其理論計算機模型為通用計算機 只考慮到理論上的可計算性而沒有考慮計算的復雜性（現(xiàn)實的可計算性）； 不是實際的計算機，在實際的計算機研制中需要有具體的實現(xiàn)方法和實現(xiàn)技術,Turing Machine,對于可計算的問題，有兩個重要性

23、質： 計算時間：時間復雜度 (Time Complexity) 內(nèi)存空間：空間復雜度 (Space Complexity) 例1：求解一元二次方程 ax2+bx+c=0 (a0),Computational Complexity,輸入a, b, c 三個常數(shù)，在有限的常數(shù)步時間內(nèi)，就可以完成計算 其時間復雜度和空間復雜度都是常數(shù)，O(1),Computational Complexity,由該公式知計算C=AB總共需要pqr次的數(shù)乘 需要的時間是 O(n3)，稱為立方時間,例2： 在科學計算中經(jīng)常要計算矩陣的乘積。若A是一個pq的矩陣，B是一個qr的矩陣，則其乘積C=AB是一個pr的矩陣。其標

24、準計算公式為：,q Cij= Aik Bkj 1=i=p, 1=j=r k=1,Computational Complexity,例3：The Hanoi Tower Long time ago, there were three pegs in Hanoi. In the very beginning, there were 64 disks with different sizes stacking on peg A, small disks always stepping on the bigger disks, so the stacking disks shaped like a t

25、ower. The goal of the Hanoi Tower puzzle is to move a stack of disks from a designated peg A to another designated peg C in the fewest possible moves and as quickly as possible, and end up in the same stacked ascending order (largest disk on the bottom, smallest on top) as the starting position. Onl

26、y one disk may be moved at a time and a larger disk may never be placed on top of a smaller disk. The disks can reside on an additional peg B as an interchange.,By the time when all 64 disks are moved to peg C, it will be the end of the world, or heaven of the world? If one disk is moved in one seco

27、nd, how long would it take to accomplish?,Computational Complexity,例3：The Hanoi Tower hanoi (int n, char left, char middle, char right) If (n=1) move (left, right) Else hanoi (n-1, left, right, middle); move (left, right); hanoi (n-1, middle, left, right); ,h(n) = 2h(n-1) + 1 = 2(2h(n-2)+1)+1 = 22h(

28、n-2)+2+1 = 23h(n-3)+22 + 2+1 = 2nh(0) + 2n-1 + +22+2+1 = 2n-1 + +22+2+1 = 2n -1,Computational Complexity,例3：The Hanoi Tower,博弈樹非常龐大，國際象棋10120，中國象棋10160，圍棋10768；計算機不可能在合理時間內(nèi)實現(xiàn)詳細搜索,h(n) = 2n-1 264-1 = 18446744073709551615 1 year = 31536000 second 1/s: 584900 million years 100million/s: 5849 years 其時間復

29、雜度是O(2n )，稱為指數(shù)時間,Computational Complexity,常見的復雜度，按照復雜度排序 O(1) :常數(shù)時間 O(logn) :次線性時間 O(n) :線性時間 O(nlogn):對數(shù)時間 O(n2 ) :平方時間 O(n3 ) :立方時間 稱需要O(nk)時間（k是一個常數(shù)）的問題為多項式復雜度問題（polynomial complexity） O(2n ) : 指數(shù)時間 （exponential complexity） 一個問題求解算法的時間復雜度大于多項式時間（如指數(shù)時間）時，算法的執(zhí)行時間將隨n的增加而急劇增長，以致即使是中等規(guī)模的問題也不能求解出來，稱為難解

30、問題,The origin of Artificial Intelligence “Can machines think?” - What is a “machine” - What is it to “think” The Imitation Game,Turing Test,A human “talks” to something and has to decide if it is a human of machine Can a machine simulate a person in a conversation in which other human elements, besi

31、des intelligence, are eliminated?,George Boole Boole提出將邏輯推理變?yōu)榇鷶?shù)運算 布爾代數(shù)是邏輯電路的數(shù)學工具 能得到多強的計算裝置？可否計算所有問題？可計算性問題（Computability） Alan Turing Turing Machine：可計算性 圖靈可計算性 計算的復雜性問題（現(xiàn)實的可計算性） Turing Test：機器可否模擬人的智力,Founders of Computing Theory,History of Computing Machines What we can learn from Moores Law Foun

32、ders of Computing Theory The Essential Issue of Computer Science Computing as a Discipline,Introduction,計算科學的本質： 我國古代：對于一個數(shù)學問題，只有當確定了其可用算盤解算它時，這個問題才算可解決。“能性行”問題 圖靈用形式化的方法成功地表述了計算這一過程的本質：計算就是計算者（人或機器）對一條兩端可無限延長的紙帶上的一串0和1執(zhí)行命令，一步步改變紙帶上的0或1，經(jīng)過有限步驟，最后得到一個滿足預先規(guī)定的符號串的過程 圖靈的描述是關于數(shù)值計算的；字母、漢字、圖等均可用數(shù)表示；圖靈機同樣可以

33、處理非數(shù)值計算 The Essential Issue of Computer Science：什么能被（有效地）自動進行 能行問題的討論對象都是離散對象：計算學科依賴“離散結構” 計算學科所有分支領域的根本任務就是進行計算，其實質就是進行字符串的變換,The Essential Issue of Computer Science,Algorithm: a set of steps that defines how a task is performed,The Fundamental Concept of CS: Algorithm,The major goal is to find a s

34、ingle set of directions that described how any problem of a particular type could be solved,The Fundamental Concept of CS: Algorithm,In the domain of computing machinery, algorithms are represented as programs within computers,The Central Role of Algorithms in CS,Algorithm,Languages Software Engineering,Data Manipulation OS,Data Storage Data Structures File Structures Database Structures,AI,Theory of Computation,History of Computing Machines What we can learn from Moores Law Founders of Computing Theory The Essential Issue of Computer