信息技术与社会进步4-2

HPM&SIRemember:10%ofwhatIread,20%ofwhatIhear,30%ofwhatIsee,50%ofwhatIseeandhear,+70%ofwhatIdiscusswithothers,80%ofwhatIexperiencebydoing,95%ofwhatIteachothers.HPM&S计算李波[e-mail]计算机教学实验中心高效能建模与仿真研究小组（HPM&S)西安交通大学2011年10月改编自J.G.BrookshearBehrouzForouzan陈国良等HPM&S本讲内容z数学与计算机科学的关系z计算机的数学理论模型－图灵机z计算理论（可计算性）z冯.诺伊曼结构zCPU的内部结构和工作原理z主存储器及其与CPU之间的信息传输z指令系统（略）z计算机程序的基本控制结构（略）HPM&S数学与计算机科学的关系z一枚硬币的两面TwosidesofacoinzFunction（功能）和Procedure（过程）z程序设计中的声明式与定义式，接口定义与接口实现zUML中Operation和Method，Property和Attributionz软件工程中的规格与实现z一枚硬币的两面TwosidesofacoinzFunction（功能）和Procedure（过程）z程序设计中的声明式与定义式，接口定义与接口实现zUML中Operation和Method，Property和Attributionz软件工程中的规格与实现通常知识分为声明性（称述性）知识declarativeknowledge和命令性（操纵性）知识imperativeknowledge在数学中主要关注声明性描述（whatis）describingpropertiesofthings在CS中主要关注操纵性描述（howto）describinghowtodothings通常知识分为声明性（称述性）知识declarativeknowledge和命令性（操纵性）知识imperativeknowledge在数学中主要关注声明性描述（whatis）describingpropertiesofthings在CS中主要关注操纵性描述（howto）describinghowtodothingsHPM&SDeclarativeKnowledgez“Whatis”knowledgez什么是平方根z对于非负的实数X，如果存在一个数G，使得X=G*Gz则G是X的平方根z在实数范围内，正数有两个平房根，负数没有平房根，0的平房根为0请大家根据定义求2的平方根？请大家根据定义求2的平方根？HPM&SImperativeKnowledgez“Howto”knowledgezTofindanapproximationofsquarerootofx:zMakeaguessGzImprovetheguessbyaveragingGandx/GzKeepimprovingtheguessuntilitisgoodenough.2for:Example=xxX=2G=1HPM&SImperativeKnowledgez“Howto”knowledgezTofindanapproximationofsquarerootofx:zMakeaguessGzImprovetheguessbyaveragingGandx/GzKeepimprovingtheguessuntilitisgoodenough.2for:Example=xxX=2G=1X/G=2G=½(1+2)=1.5HPM&SImperativeKnowledgez“Howto”knowledgezTofindanapproximationofsquarerootofx:zMakeaguessGzImprovetheguessbyaveragingGandx/GzKeepimprovingtheguessuntilitisgoodenough.2for:Example=xxX=2G=1X/G=2G=½(1+2)=1.5X/G=4/3G=½(3/2+4/3)=17/12=1.416666HPM&SImperativeKnowledgez“Howto”knowledgezTofindanapproximationofsquarerootofx:zMakeaguessGzImprovetheguessbyaveragingGandx/GzKeepimprovingtheguessuntilitisgoodenough.2for:Example=xxX=2G=1X/G=2G=½(1+2)=1.5X/G=4/3G=½(3/2+4/3)=17/12=1.416666X/G=24/17G=½(17/12+24/17)=1.4142156HPM&SzDeclarativeandimperativedescriptionsareintimatelyrelated,asindeedaremathematicsandcomputerscience.zForinstance,tosaythattheanswerproducedbyaprogramiscorrectzCorrectnessofaprogramistomakeadeclarativestatementabouttheprogram.zimperativestatements(fromwhichprogramsareconstructed)anddeclarativestatements(whichcanbeusedtodeducethings).数学与计算科学的关系-Twosidesofacoin数学与计算科学的关系-TwosidesofacoinHPM&S计算机的数学理论模型－图灵机HPM&S可计算性对于一个问题，如果存在一个机械的过程，当我们给定一个输入，这个过程能够在有限步内终止并给出正确答案，那么，这个问题就称为是可计算的/具有可计算性。HPM&S计算理论和计算模型引自陈国良院士人类对计算本质的认识过程①计算手段应该器械化（算盘、手摇计算机、微分机、模拟机等）②计算过程应该形式化（图灵模型）③计算执行应该自动化（冯·诺依曼模型）13计算理论①函数及其计算②图灵机③通用BareBones语言④不可计算函数与停机问题⑤计算复杂性（多项式与多项式函数，P类问题，NP类问题，NPC类问题）冯·诺依曼计算机模型①计算机体系结构②机器指令与机器语言③汇编语言程序的执行举例④虚拟机HPM&S计算机理论的发展历史z图灵研究了可计算性z提出了图灵机和图灵机能解决的问题类z证明了存在着图灵机无法解决的问题类z冯·诺伊曼给出了现代计算机的设计蓝图z提出了数字计算机的组成原理和体系结构z对指令、指令周期、指令系统和存储式程序控制原理都给出了明确的方案z库克（StephenA.Cook）研究了计算复杂性z有一些问题，虽然可计算，但随着问题规模的增加，就连最快的计算机用几百年也不能结束计算HPM&S0.Definitionofcomputationandcalculation①DefinitionofcomputationzComputationisageneraltermforanytypeofprocess,algorithmormeasurement;thisoftenincludesbutisnotlimitedtodigitaldata.zThisincludesphenomenarangingfromhumanthinkingtocalculationswithamorenarrowmeaning.zComputationisaprocessfollowingawell-definedmodelthatisunderstoodandcanbeexpressedinanalgorithm,protocol,networktopology,etc.zComputationisalsoamajorsubjectmatterofcomputerscience:itinvestigateswhatcanorcannotbedoneinacomputationalmanner.2.10HPM&S②DefinitionofcalculationAcalculationisadeliberateprocessfortransformingoneormoreinputsintooneormoreresults,withvariablechange.Thetermisusedinavarietyofsenses,fromtheverydefinitearithmeticalcalculationofusinganalgorithmtothevagueheuristicsofcalculatingastrategyinacompetitionorcalculatingthechanceofasuccessfulrelationshipbetweentwopeople.HPM&S1.Computationalapproachshouldbeimplementedbythecomputationalmachinery(1)Chinesecountingboard–abacus(beadabacus,Suanpan):①Prototypeofabacus:Arectangularwoodenframewiththinrodsacrossit,thatisdividedintotwounequalpartsbyastripofwood.Oneachrodareplaced7woodenbeads:5belowthestripand2aboveit.HPM&S②Chinese“AlgorithmizationThinking”:Chineseancientscholarsthoughtthatamathematicalproblemwassolvableonlyifsomerulesexistforcalculatingitwithabacus.ThisideaiscalledtheChinesealgorithmizationthinking(enablement).HPM&S(2)Llull'sThinkingMachine(Turningtoys,orLearningtoys):-From'sthinkingmachinemarkedthebeginningoftheformalizationrevolution.①R.Llull(1232–1315)wasbornanddiedintheislandofMallorca,oneofthemostprominentEuropeanwriters,philosophersandscientistsof13thand14thcenturies.②HardwareofLlull'smachineRaymondLullyRaymondLullyHPM&S(3)OthercomputationalMachinery①BlaisePascal’s1641“Pascaline”machine(Paris)②GottfriedWilhelmvonLeibniz’scalculatingwheel(1671)HPM&S(3)OthercomputationalMachinery④VannevarBush’sanalogcomputer③C.Bobbage’sDifferenceEngine#2HPM&S(4)Conclusions:„Thehistoryofcomputingpresentedabovereflectedtheeffortsofhumanbeingsforexploringtheessenceandthefundamentalproblemsofcomputi