计算机科学的本史元春课件

计算机科学的本质

ComputingHistoryisonly MainframeComputingDesktopComputingWhat’sComputer?

Computingisbecoming pervasive/ubiquitousPervasive/UbiquitousComputingResource

PoorResourceRichTheAbacusTheMechanicalCalculatorsTheElectromechanicalMachinesHistoryofComputingMachines:－1946算盘数字由算珠的数量表示数位由算珠的位置确定通过手动完成从低位到高位的数字传送（十进制）执行运算就是按照一定的规则移动算珠的位置HistoryofComputingMachines:－1946机械时代HistoryofComputingMachines:－19461642，Pascal（法）：Pascaline，加法机1694，Leibnitz（德）：calculator，加减乘除演算机1834，Babbage（英）：DifferenceEngine，计算平方等借助机械装置(齿轮、杠杆等)传送十进制位，机械装置的动力来自计算人员的手ENIAC：ElectronicNumericalIntegratorAndCalculator(电子数字积分器和计算器)

1946，UPenn170m2，30tons，150kwatts,18800vacuumtubes，5000psThefirsthighspeedgeneralelectroniccomputerHistoryofComputingMachines:ENIACENIAC的致命缺点：程序与计算两分离指挥近2万电子管“开关”工作的程序指令，存放在机器的外部电路里。计算某个题目前，数十人用几小时甚至好几天把数百条线路用手接通，才能进行几分钟运算1946,StoredProgram:EDVAC(electronicdiscretevariableautomaticcomputer,离散变量自动电子计算机)AllcomputersmoreorlessbasedonthesamebasicdesignTheVonNeumannArchitectureModelfordesigningandbuildingcomputers,basedonthefollowingthreecharacteristics:Thecomputerconsistsoffourmainsub-systems:MemoryALU(Arithmetic/LogicUnit)ControlUnitInput/OutputSystem(I/O)Programisstoredinmemoryduringexecution.Programinstructionsareexecutedsequentially.TheVonNeumannArchitecturevonNeumannArchitecture－1946ENIACVonNeumannComputerModernComputersHistoryofComputingMachinesFirstFourGenerationsFirstgeneration:Vacuumtubecomputers(1940s-1950s)Secondgeneration(1950s):TransistorsHistoryofComputingMachinesWhatwecanlearnfromMoore’sLawFoundersofComputingTheoryTheEssentialIssueofComputerScienceComputingasaDisciplineSyllabusWhatwecanlearnfromMoore’sLawMoore’sLawIn1965,GordonMoore(co-founderofIntel),wroteanarticleonthefuturedevelopmentofsemiconductorindustryatElectronicsmagazine.Henotedthatthecomplexityofminimumcostsemiconductorcomponentshaddoubledperyearsincethefirstprototypemicrochipwasproducedin1959.ThisexponentialincreaseinthenumberofcomponentsonachipbecamelaterknownasMoore'sLaw.WhatwecanlearnfromMoore’sLawMoore’sLawInthe1980s,Moore'sLawstartedtobedescribedasthedoublingofnumberoftransistorsonachipevery18months.Atthebeginningofthe1990s,Moore'sLawbecamecommonlyinterpretedasthedoublingofmicroprocessorpowerevery18months.Inthe1990s,Moore'sLawbecamewidelyassociatedwiththeclaimthatcomputingpoweratfixedcostisdoublingevery18months.WhatwecanlearnfromMoore’sLawMicroelectronictechniqueRevolutionNowinLSImanufacture,0.07μmIntelproduce65nmprocessor,2006Panasonicproduce45nmLSI,2007微电子工业发展的每下一步线宽约是前一步的0.7倍硅微集成电路的物理极限是10纳米纳米计算机、并行计算机、量子计算机Q:摩尔定律是否像牛顿定律一样，是自然界不变的定律？WhatwecanlearnfromMoore’sLawInferencefromMoore’sLaw计算机的高速发展“时间就是金钱”计算机的性价比永远在提高具有“自我强化”特征厂商需要不断改进性价比“过去无关紧要”知识和技术发展很快产品技术几年即过时掌握基本概念、原理和核心技术的重要性终身学习，保持与知识的发展同步WhatwecanlearnfromMoore’sLawGeorgeBoole1815–1864,MathematicianandPhilosopher

BooleanAlgebra（布尔代数）AlanTuring1912-1954,Founderofcomputerscience,MathematicianandPhilosopherTuringMachine&TuringTest（图灵机和图灵测试）FoundersofComputingTheory家贫，16岁助教/自学，未受正规学校训练AsaprofessorofMathematicsatQueensCollegeinCork,hepublishedhismasterpiece,AnInvestigationoftheLawsofThought《思维定律研究》in1847：符号和它所代表的数值是可以分开的；符号以及符号之间的关系有其自身的规律；研究人类思维规律的符号逻辑系统BooleanAlgebra将逻辑表述映射到符号采用数学方法处理逻辑推理GeorgeBooleDeduction2:任何布尔函数都可以用3级门来实现这3级门电路分别是一级非门、一级与门和一级或门理论上，计算任何布尔函数的时间最多是3个门延迟任何一个可以用布尔函数表示的计算问题都只需要3级门的时间（<1ns）就可以完成NormalFormTheoremofBooleanAlgebra说谎岛上的居民所说的每一句话都是假的Y=“Y是假的”，不论Y是真是假，马上推出相反结论TheLiarParadox（说谎者悖论）Y的值将在0、1之间震荡，不会稳定到0或1悖论的原因是自我引用，在电路上表现为循环电路布尔函数只有计算或者处理能力，没有记忆能力；引入循环电路，记忆能力就可以实现信号Q表示记忆：X=1时，新Q保持了Q的内容X=0时，新Q是Y的值计算机中内存的实现原理LogicCircuits数字逻辑电路中：不含循环的：组合电路（combinationallogiccircuits）含循环的：时序电路（sequentiallogiccircuits）进行数值运算和逻辑运算与判断问题：如果我们考虑所有的可以含有组合逻辑和时序逻辑的二值逻辑电路，我们能得到多强的计算装置？可否计算所有问题？可计算性问题（Computability）GeorgeBoole1815–1864,MathematicianandPhilosopherBooleanAlgebraAlanTuring1912-1954,FounderofComputerScience,MathematicianandPhilosopherTuringMachine&TuringTestFoundersofComputingTheoryAlanTuring热爱数学，CambridgeUniversity,probability,logicPrincetonUniversity.Ph.D.Logic,algebra,numbertheory;advisor:VonNeuman1937,“Oncomputablenumbers,withanapplicationtotheEntscheidungsproblem”《论应用于解决问题的可计算数字》

：TuringMachine1950,“Canmachinesthink?”TuringTest他用计算机、人工智能在现代数理逻辑和现实世界间搭一起一座不朽的桥梁1966,ACM(AssociationforComputingMachinery)设立TuringAwardAlanTuring所谓可计算性其实是一个哲学定义：如果存在一个机械过程，如果我们给一个输入，这个过程（或机器）就能在有限步内给出答案，那么这个问题就称作是可计算的Turing回答了可计算性问题：哪些问题类是可以用计算机解决的，计算机的通用计算能力问题，并给出了理论计算模型——图灵机和它的输入数据、计算程序和输出结果的表示方式图灵机由一条双向都可以无限延长的、被分成一个个小方格的磁带；一个有限状态控制器；一个读写磁头3部分组成TuringMachine

图灵机一步一步地进行工作，其工作情况取决于三个条件：

有限状态控制器内部状态读写磁头扫描在磁带的哪个方格上该方格上有什么信息每一步工作的过程：

读“读写磁头”当前所扫描的磁带方格的存储内容si

根据si的值以及“有限状态控制器”当前内部状态qi，

决定在当前方格写入新的内容s’i

并决定“读写磁头”由当前位置或左移(一格)、或右移(一格)、或不移动、或停机并决定“有限控状态制器”新的控制状态qi+1

进入下一步工作，按同样的方式工作；如此周而复始，直到遇到命令机器停机。TuringMachineFundamentals

10110

q1q2q3q4q5q6q7

00110

q1q2q3q4q5q6q7当控制器前处于状态q2，磁头所指的磁带方格内容为1，现在要采取得动作是：将该磁带方格的内容改写为0，磁头向右移动一格，控制器内状态变为q5ExampleTuringMachine图灵机的这种由状态、符号确定的工作过程叫做图灵机程序，可以由一个五元组序列来定义：

<q,b,a,m,q’>q：当前状态b：当前方格中的符号

a：当前方格中修改后的符号

m：磁头移动的方向，左移L（Left）、右移R（Right），不动N（No-motion）q’：下一状态TuringMachine前面例子中，图灵机的一步动作可表示为：<q2,1,0,R,q5>ATuringmachineforincrementingavalue图灵机计算实例

——f(x)=2x在二进制图灵机上计算函数f(x)=2x，即x，f(x)都用二进制表示，磁带方格中只能用0和1两个符号，B表示空白。约定：1、开始时，磁带上只有一连续的方格串上放入x的相应的二进制值符号，其余方格都为空白。2、机器从状态q1开始，磁头指向x最左一位所在地方格。3、停机时，磁带上非空方格串所组成的二进制值即代表f(x)。在前面的约定下，计算f(x)=2x的图灵机程序如下，其中：Halt表示停机，Error表示在计算中不会出现当前状态B被扫描时的写、移动、状态转移0被扫描时的写、移动、状态转移1被扫描时的写、移动、状态转移q11，L，q70，R，q11，R，q2q2B，R，q30，R，q21，R，q2q30，L，q40，R，q3Errorq4B，L，q50，L，q4Errorq5Error1，L，q50，L，q6q6B，R，q10，L，q61，L，q6q7HaltB，L，q7Error图灵机计算实例

——f(x)=2x为什么以x的二进制数为符号作为磁带初始值?为什么停机后磁带上的二进制值就是最终结果?为什么有7种状态?为什么在每种状态中要进行这些动作?图灵机程序设计图灵机计算实例

——f(x)=2x

10

q1q2q3q4q5q6q7

10

q1q2q3q4q5q6q7

10

q1q2q3q4q5q6q7开始第1步第2步图灵机计算实例

——f(x)=2x

10

q1q2q3q4q5q6q7

100

q1q2q3q4q5q6q7

100

q1q2q3q4q5q6q7第5步第4步第3步图灵机计算实例

——f(x)=2x

010

q1q2q3q4q5q6q7q1q2q3q4q5q6q7q1q2q3q4q5q6q7

110

010

第8步第7步第6步图灵机计算实例

——f(x)=2x

010

q1q2q3q4q5q6q7

010

q1q2q3q4q5q6q7

010

q1q2q3q4q5q6q7第11步第10步第9步图灵机计算实例

——f(x)=2x

010

q1q2q3q4q5q6q7

0100

q1q2q3q4q5q6q7

0100

q1q2q3q4q5q6q7第14步第13步第12步图灵机计算实例

——f(x)=2x

0100

q1q2q3q4q5q6q7

0000

q1q2q3q4q5q6q7

0000

q1q2q3q4q5q6q7第17步第16步第15步图灵机计算实例

——f(x)=2x

0000

q1q2q3q4q5q6q7

0000

q1q2q3q4q5q6q7

0000

q1q2q3q4q5q6q7第20步第19步第18步图灵机计算实例

——f(x)=2x

00100

q1q2q3q4q5q6q7

0100

q1q2q3q4q5q6q7

100

q1q2q3q4q5q6q7结束f(2)=22=4第21步第22步图灵机计算实例

——f(x)=2x表面上看，图灵机的计算功能似乎很弱，实际上，只要时间足够长（即允许足够的工作步数）和有足够的空间（即磁带足够长），则图灵机可以替代目前的任何计算机图灵论题：凡是可计算的函数都可以用图灵机来计算：

可计算性＝图灵可计算性称其理论计算机模型为通用计算机

只考虑到理论上的可计算性而没有考虑计算的复杂性（现实的可计算性）；不是实际的计算机，在实际的计算机研制中需要有具体的实现方法和实现技术TuringMachine对于可计算的问题，有两个重要性质：计算时间：时间复杂度(TimeComplexity)内存空间：空间复杂度(SpaceComplexity)

例1：求解一元二次方程ax2+bx+c=0(a≠0)ComputationalComplexity

输入a,b,c三个常数，在有限的常数步时间内，就可以完成计算

其时间复杂度和空间复杂度都是常数，O(1)利用公式ComputationalComplexity由该公式知计算C=AB总共需要pqr次的数乘

需要的时间是O(n3)，称为立方时间例2：在科学计算中经常要计算矩阵的乘积。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。其标准计算公式为：

qCij=ΣAikBkj1<=i<=p,1<=j<=r

k=1ComputationalComplexity例3：TheHanoiTowerLongtimeago,therewerethreepegsinHanoi.Intheverybeginning,therewere64diskswithdifferentsizesstackingonpegA,smalldisksalwayssteppingonthebiggerdisks,sothestackingdisksshapedlikeatower.ThegoaloftheHanoiTowerpuzzleistomoveastackofdisksfromadesignatedpegAtoanotherdesignatedpegC

inthefewestpossiblemovesandasquicklyaspossible,andendupinthesamestackedascendingorder(largestdiskonthebottom,smallestontop)asthestartingposition.Onlyonediskmaybemovedatatimeandalargerdiskmayneverbeplacedontopofasmallerdisk.ThediskscanresideonanadditionalpegBasaninterchange.Bythetimewhenall64disksaremovedtopegC,itwillbetheendoftheworld,orheavenoftheworld?Ifonediskismovedinonesecond,howlongwouldittaketoaccomplish?ComputationalComplexity例3：TheHanoiTowerhanoi(intn,charleft,charmiddle,charright){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(n-2)+2+1 =23h(n-3)+22+

2+1=2nh(0)+2n-1+…+22+2+1 =2n-1+…+22+2+1 =2n-1ComputationalComplexity例3：TheHanoiTower

博弈树非常庞大，国际象棋10120，中国象棋10160，围棋10768；计算机不可能在合理时间内实现详细搜索h(n)=2n-1264-1=1844674451year=31536000second1/s:584900millionyears100million/s:5849years其时间复杂度是O(2n)，称为指数时间ComputationalComplexity常见的复杂度，按照复杂度排序

O(1):常数时间

O(logn):次线性时间

O(n):线性时间

O(nlogn):对数时间O(n2):平方时间O(n3):立方时间称需要O(nk)时间（k是一个常数）的问题为多项式复杂度问题（polynomialcomplexity）O(2n):指数时间（exponentialcomplexity）

一个问题求解算法的时间复杂度大于多项式时间（如指数时间）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，称为难解问题TheoriginofArtificialIntelligence“Canmachinesthink?”-Whatisa“machine”-Whatisitto“think”TheImitationGameTuringTestPlayerAComputerPlayerBHumanInterrogatorHumanRoom1Room2

Ahuman“talks”tosomethingandhastodecideifitisahumanofmachineCanamachinesimulateapersoninaconversationinwhichotherhumanelements,besidesintelligence,areeliminated?GeorgeBooleBoole提出将逻辑推理变为代数运算布尔代数是逻辑电路的数学工具能得到多强的计算装置？可否计算所有问题？可计算性问题（Computability）AlanTuringTuringMachine：可计算性＝图灵可计算性计算的复杂性问题（现实的可计算性）TuringTest：机器可否模拟人的智力FoundersofComputingTheoryHistoryofComputingMachinesWhatwecanlearnfromMoore’sLawFoundersofComputingTheoryTheEssentialIssueofComputerScienceComputingasaDisciplineIntroduction计算科学的本质：我国古代：对于一个数学问题，只有当确定了其可用算盘解算它时，这个问题才算可解决。——“能性行”问题图灵用形式化的方法成功地表述了计算这一过程的本质：计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行命令，一步步改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的过程图灵的描述是关于数值计算的；字母、汉字、图等均可用数表示；图灵机同样可以处理非数值计算TheEssentialIssueofComputerScience：什么能被（有效地）自动进行能行问题的讨论对象都是离散对象：计算学科依赖“离散结构”计算学科所有分支领域的根本任务就是进行计算，其实质就是进行字符串的变换TheEssentialIssueofComputerScienceAlgorithm:asetofstepsthatdefineshowataskisperformedTheFundamentalConceptofCS:AlgorithmThemajorgoalistofindasinglesetofdirectionsthatdescribedhowanyproblemofaparticulartypecouldbesolvedTheFundamentalConceptofCS:AlgorithmInthedomainofcomputingmachinery,algorithmsarerepresentedasprogramswithincomputersAlgorithmsHardwareSoftwareProgramsApplicationsTheCentralRoleofAlgorithmsinCSAlgorithmLanguagesSoftwareEngineeringDataManipulationOSDataStorageDataStructuresDatabaseStructuresAITheoryofComputationHistoryofComputingMachinesWhatwecanlearnf