计算机文化、程序设计

计算概论-计算机文化、程序设计IntroductiontoComputing:ComputerCulture,andProgramming闫宏飞陈卿编著byHongfeiYanandChongChen2010/9/23内容简介本书主要是汇编各书和参考资料而成，比较系统地介绍了计算机文化，和程序设计。通过这两部分有机的结合（前者占1/3,后者占2/3）,即理论与实践结合，使学生理解和掌握有关计算机和信息技术的基本概念和基本原理，对计算机学科有全局性的认识；学会使用计算机进行信息处理，熟练掌握C++语言编程技术，为后续相关课程的学习打好基础。本书层次分明，由浅入深，具有学习和实用双重意义。本书可作为高等院校各专业一、二年级学生的教学参考书和技术资料，对广大从事计算机相关研究和应用开发的科技人员也有很大的参考价值。**刖R《计算概论》是普通高校面向理工科低年级学生开设的计算机基础教育课。课程前1/3部分为计算机文化，后2/3部分为程序设计。任教此课两年来，发现没有合适的教材，因此根据授课经验，汇编各书和参考资料，编成此书。编者2009年1月于北大燕园hITbTOC\o"1-5"\h\z\o"CurrentDocument"第1章引论. 1\o"CurrentDocument"计科学 2\o"CurrentDocument"摩尔定律 3\o"CurrentDocument"ScopeofProblems 5计《i化 9第2章统 10\o"CurrentDocument"ComputerIntroduction 10\o"CurrentDocument"TURINGMODEL 11\o"CurrentDocument"VONNEUMANNMODEL 16\o"CurrentDocument"Computercomponents 18\o"CurrentDocument"History 19\o"CurrentDocument"Practiceset 24\o"CurrentDocument"计射L系统漫游 25\o"CurrentDocument"InformationisBits+Context 27\o"CurrentDocument"ProgramsAreTranslatedbyOtherProgramsintoDifferentForms 29\o"CurrentDocument"ItPaystoUnderstandHowCompilationSystemsWork 31\o"CurrentDocument"ProcessorsReadandInterpretInstructionsStoredinMemory 32\o"CurrentDocument"CachesMatter 38\o"CurrentDocument"StorageDevicesFormaHierarchy 39\o"CurrentDocument"TheOperatingSystemManagestheHardware 40\o"CurrentDocument"SystemsCommunicateWithOtherSystemsUsingNetworks 47\o"CurrentDocument"TheNextStep 49第3章和数的^zj^・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・52\o"CurrentDocument"数据的表示 52数的表示 66\o"CurrentDocument"第4章程序设计语言和开发环境 70©Wtig言 70)I*♦♦・*・♦•♦・♦・♦•♦・♦・♦・♦•♦♦♦•・•♦•+•+•♦•+・***,+•*♦+•*•+♦+♦♦♦*♦*•・•*•+♦♦♦+♦+•+•+•+♦+・d♦•♦3♦*♦♦♦*♦.8^)下篇出设计 86第5章 87GettingStarted 87FundamentalTypes 91ArithmeticOperator 100\o"CurrentDocument"ControlStructures 123第6章M和结构 153\o"CurrentDocument"6.1数组 153Initializingarrays ! 未定义书签。Accessingthevaluesofanarray ! 未定义书签。Multidimensionalarrays ! 未定义书签。6.2结构 164Datastructures 错误！未定义书签。Pointerstostructures ! 未定义书签。Nestingstructures ! 未定义书签。\o"CurrentDocument"Quiz:Structures 199\o"CurrentDocument"第7章C++标准库 205\o"CurrentDocument"CLanguagelibrary 206\o"CurrentDocument"Input/OutputStreamlibrary 207\o"CurrentDocument"Stringlibrary 208\o"CurrentDocument"STL:StandardTemplateLibrary 208第8章函数和递归 错误！未定义书签。Functionswithnotype.Theuseofvoid 错误!未定义书签。Argumentspassedbyvalueandbyreference !未定义书签。Default\aluesinmrameters !未定义书签。Overloadedfunctions !未定义书签。INLINEFUNCTIONS 未定义书签。RECURSIVITY 未定义书签。Declaringfunctions 未定义书签。inTOC\o"1-5"\h\z\o"CurrentDocument"Referenceoperator(&) 212\o"CurrentDocument"Dereferenceoperator(*) …… 214\o"CurrentDocument"Declaringvariablesofpointertypes 215\o"CurrentDocument"Pointersandarrays 218\o"CurrentDocument"Pointerinitialization 220\o"CurrentDocument"Pointerarithmetics 221\o"CurrentDocument"Pointerstopointers 223\o"CurrentDocument"voidpointers 224\o"CurrentDocument"Nullpointer 225\o"CurrentDocument"Pointerstofunctions 226\o"CurrentDocument"9.2DYNAMICMomory 227\o"CurrentDocument"Operatorsnewandnew[] 227\o"CurrentDocument"Operatorsdeleteanddeletc[] 229\o"CurrentDocument"DynamicmemoryinANSI-C 231第10章VARIABLES:ADEEPERLOOK 232\o"CurrentDocument"10JMemoryorganization 232\o"CurrentDocument"VARIABLESCOPE 234\o"CurrentDocument"Understandingpointers 235\o"CurrentDocument"第11章算法 238\o"CurrentDocument"TheRoleofAlgorfthmsinComputing 239\o"CurrentDocument"Algorithms 239\o"CurrentDocument"Algorithmsasatechnology 244算法的概念 247算法的三种基本结构 247算法的表示 248介绍几种基本算法 248迭代与递归 248第12章龄设计 249简单计算题 249模拟 249可模型化的问题 250\o"CurrentDocument"Introduction(Beginner) 251\o"CurrentDocument"Elementary 254\o"CurrentDocument"Intermediate 255\o"CurrentDocument"Upper-Intermediate 257\o"CurrentDocument"Advanced 258\o"CurrentDocument"参考文献 262第1章引论计算机文化这个词的出现到被广泛认可的时间并无确切的考证，但基本上是在20世纪80年代后期。计算机开始是一种装置，进而到一门学科，再发展成为一种“文化”，它对人类的影响力之大的确令人惊叹。计算机文化是指能够理解计算机是什么，以及它如何被作为资源使用的。简单地说，计算机文化不但是知道如何使用计算机，更重要的是知道什么时候使用计算机。在当今世界，几乎所有专业都与计算机息息相关。但是，只有某些特定职业和学科才会深入研究计算机本身的制造、编程和使用技术。用来诠释计算机学科内不同研究领域的各个学术名词的涵义不断发生变化，同时新学科也层出不穷。五个主要的计算机学科(disiplineofcomputing)包括1•计算机工程学(ComputerEngineering),是电子工程的一个分支，主要研究计算机软硬件和二者间的彼此联系。・计算机科学(ComputerScience),是对计算机进行学术研究的传统称谓。主要研究计算技术和执行特定任务的高效算法。该门学科为我们解决确定一个问题在计算机领域内是否可解，如可解其效率圳何，以及如何作成更加高效率的程序。时至今日，在计算机科学内已经派生了许多分支,每一个分支都针对不同类别的问题进行深入研究。软件工程学(SoftwareEngineering),着重于研究开发高质量软件系统的方法学和实践方式，并试图压缩并预测开发成本及开发周期。信息系统(InfbrmationSystems),研究计算机在一个广泛的有组织环境(商业为主)中的计算机应用。信息技术(InfbrmationTechnology),指计算机相关的管理和维护。《计算概论》课程关注的是计算机学科。较大规模的致力于计算机科学的组织有：美国计算机协会(AssociationofComputingMachinery,简称ACM)；美国电气电子工程师协会(InstituteofElectricalandElectronicsEngineers.简称为IEEE)。1ComputingCurricula2005:TheOverviewReport,http:〃/education/curricvols/CC2005-March06Final.pdf计算机科学计算机科学是一门包含各种各样与计算和信息处理相关主题的系统学科，从抽象的算法分析、形式化语法等等，到更具体的主题如编程语言、程序设计、软件和硬件等。作为一门学科，它与数学、计算机程序设计、软件工程和计算机工程有显著的不同，却通常被混清，尽管这些学科之间存在不同程度的交叉和覆盖。2计算机科学研究的课题是：计算机程序能做什么和不能做什么（可计算性）；如何使程序更高效的执行特定任务（算法和复杂性理论）；程序如何存取不同类型的数据（数据结构和数据库）；程序如何显得更具有智能（人工智能）；人类如何与程序沟通（人机互动和人机界面）。计算机科学的大部分研究是基于“冯•诺依曼计算机”和“图灵机”的，它们是绝大多数实际机器的计算模型。作为此模型的开山鼻祖，邱奇-图灵论题（Church-TuringThesis）表明，尽管在计算的时间，空间效率上可能有所差异，现有的各种计算设备在计算的能力上是等同的。尽管这个理论通常被认为是计算机科学的基础，可是科学家也研究其它种类的机器，如在实际层面上的并行计算机和在理论层面上概率计算机、oracle计算机和量子计算机。在这个意义上来讲,计算机只是一种计算的工具：著名的计算机科学家Dijkstra有一句名言“计算机科学之关注于计算机并不甚于天文学之关注于望远镜。计算机科学根植于电子工程、数学和语言学，是科学、工程和艺术的结晶。它在20世纪最后的三十年间兴起成为一门独立的学科，并发展出自己的方法与术语。早期，虽然英国的剑桥大学和其他大学已经开始教授计算机科学课程，但它只被视为数学或工程学的一个分支，并非独立的学科。剑桥大学声称有世界上第一个传授计算的资格。世界上第一个计算机科学系是由美国的普渡大学在1962年设立，第一个计算机学院于1980年由美国的东北大学设立。现在，多数大学都把计算机科学系列为独立的部门，一部分将它与工程系、应用数学系或其他学科联合。计算机科学领域的最高荣誉是ACM设立的图灵奖，被誉为是计算机科学的诺贝尔奖。它的获得者都是本领域最为出色的科学家和先驱。华人中首获图灵奖的是姚期智博士。他于2000年以其时计算理论做出的诸多''根本性的、意义重大的”贡献而获得这一崇高荣誉。http:〃/wiki/计算机科学

摩尔定律http:〃en.w汰/wiki/Moore%27sLawMoore'slawdescribesalong-termtrendinthehistoryofcomputinghardware.Sincetheinventionoftheintegratedcircuitin1958,thenumberoftransistorsthatcanbeplacedinexpensivelyonanintegratedcircuithasincreasedexponentially,doublingapproximatelyeverytwoyears.ThetrendwasfirstobservedbyIntelco-fbunderGordonE.Mooreina1965paper.lthascontinuedforalmosthalfofacenturyandisnotexpectedtostopforanotherdecadeatleastandperhapsmuchos-0一cnos-0一scnuall1,000,000,000—100,000,00010,000,0001,000,000—100,00010,0002,3001.1.、CurveshowsMoore'sLaw':transistorcountdoublingeverytwoyearsDateofintroduction图CPUTransistorCounts1971-2008&Moore'sLaw,Growthoftransistorcounts

forIntelprocessors(dots)andMoore'sLaw(logarithmicverticalscale)AlmosteverymeasureofthecapabilitiesofdigitalelectronicdevicesislinkedtoMoore'slaw:processingspeed,memorycapacity,eventhenumberandsizeofpixelsindigitalcameras.Alloftheseareimprovingat(roughly)exponentialratesaswell.Thishasdramaticallyincreasedtheusefulnessofdigitalelectronicsinnearlyeverysegmentoftheworldeconomy.Moore'slawdescribesthisdrivingforceoftechnologicalandsocialchangeinthelate20thandearly21stcenturies./view/17904.htm计算机第一定律 摩尔定律Moore定律。归纳起来，主要有以下三种“版本”：集成电路芯片上所集成的电路的数目，每隔18个月就翻一番。微处理器的性能每隔18个月提高一倍，而价格下降一倍。用一个美元所能买到的电脑性能，每隔18个月翻两番。图1-2ComputerSpeedupMoore'sLaw:MThedensityoftransistorsonachipdoublesevery18months,farthesamecost半导体集成电路的密度或容量每18个月翻一番Moore'sLawisstillvalid.Hislawhasnothingtodowiththespeedoftheprocceso匚Ithastodowiththenumberoftransitotrswhichisstilldoubleingeverycoupleofyears.Caseinpointthereisnowmultiplecoresinthesamespaceinsteadofonecore.戈登•摩尔(GordonMoore),CPU生产商Intel公司的创始人之」1965年提出“摩尔定律”，1968年创办Intel公司。摩尔1929年出生在美国加州的旧金山。曾获得加州大学伯克利分校的化学学士学位，并且在加州理工大学(CIT)获得物理和化学两个博士学位。50年代中期他和集成电路的发明者罗伯特•诺伊斯(RobertNoyce)--起，在威廉•肖克利半导体公司工作。后来，诺伊斯和摩尔等8人集体辞职创办了半导体工业史上有名的仙童半导体公司(FairchildSemiconductor)。仙童成为现在的Intel和AMD之父。1968年，摩尔和诺伊斯一起退出仙童公司，创办了Intel。Intel初期致力于开发当时计算机工业尚未开发的数据存储领域，后来，Intel进行战略转移，专攻微型计算机的''心脏”部件-CPU。1.3ScopeofProblemsWhatcanyoudowith1computer?Whatcanyoudowith100computers?Whatcanyoudowithanentiredatacenter?httD:〃en.wikiD/wiki/DistributedcomDuting#ProiectsProjects:Avarietyofdistributedcomputingprojectshavegrownupinrecentyears.Manyarerunonavolunteerbasis,andinvolveusersdonatingtheirunusedcomputationalpowertoworkoninterestingcomputationalproblems.ExamplesofsuchprojectsincludetheStanfordUniversityChemistryDepartmentFolding@homeproject,whichisfocusedonsimulationsofproteinfoldingtofinddiseasecuresandtounderstandbiophysicalsystems;WorldCommunityGrid,anefforttocreatetheworld*slargestpubliccomputinggridtotacklescientificresearchprojectsthatbenefithumanity,runandfundedbyIBM;SETI@home,whichisfocusedonanalyzingradio-telescopedatatofindevidenceofintelligentsignalsfromspace,hostedbytheSpaceSciencesLaboratoryattheUniversityofCalifornia,Berkeley(theBerkeleyOpenInfrastructureforNetworkComputing(BOINC),wasoriginallydevelopedtosupportthisproject);LHC@home,whichisusedtohelpdesignandtunetheLargeHadronCollider,hostedbyCERNinGeneva;and,whichisfocusedonfindingoptimalGolombrulersandbreakingvariouscryptographicciphers.http:〃/English/MainhtlD:〃zh.wikiD/wiki/Folding@homchttp:〃/grouD/DandegrouD/images/FAH・May2008.Dng

http:〃/folding/Folding@home是如何工作的呢？Folding@home是一个研究研究蛋白质折叠，误折，聚合及山此引起的相关疾病的分布式计算工程。使用联网式的计算方式和大量的分布式计算能力来模拟蛋白质折叠的过程，并指引我们近期对由折叠引起的疾病的一系列研究。图1・3Folding@home

图1-4Shrek©DreamworksAnimation,renderingmultipleframesofhigh-quality

animationHappyFeet©KingdomFeatureProductions;LordoftheRings©NewLineCinema图1-5SimulatingseveralhundredorthousandcharactersIndexingtheweb(Google)Google()是一个搜索引擎，由两个斯坦福大学博士生LarryPage与SergeyBrin于1998年9月发明,GoogleInc.于1999年创立。Google网页搜索技术是来源于信息检索技术。Google的“网页快照”功能，能从Google服务器里直接取出缓存的网页。SimulatinganInternet-sizednetworkfornetworkingexperiments(PlanetLab)http:〃/PlanetLabisaglobalresearchnetworkthatsupportsthedevelopmentofnewnetworkservices.Sincethebeginningof2003,morethan1,000researchersattopacademicinstitutionsandindustrialresearchlabshaveusedPlanetLabtodevelopnewtechnologiesfordistributedstorage,networkmapping,peer-to-peersystems,distributedhashtables,andqueryprocessing.PlanetLabcurrentlyconsistsof1128nodesat511sites.Speedingupcontentdelivery(Akamai)美国Akamai是国际上最大的CDN服务商，它巨大的网络分发能力在峰值时可达到15Gbps«Akamai公司是为数不多的旨在消除Internet瓶颈和提高下载速度的几家新公司之一，是一个致力于网络交通提速的“内容发布”公司，是波士顿高技术区最卓越的新兴企业之一。Akamai公司向全球企业提供发送互联网内容，汇流媒体和应用程序的服务(目前，该公司为15个国家的企业管理着8000多台服务器）。1998年，丹尼尔.L和麻省理工学院的一些研究人员•起创立了这家公司,他在麻省理工学院的硕上论文构成了Akamai公司最初的“自由流”（Freeflow）技术的核心。根据美国航空公司的消息，丹尼尔.L31岁，在2001年9月11H撞击纽约世界贸易中心的被劫持飞机上遇难。上篇计算机文化上篇的主要目的是向读者介绍有关计算机和信息技术的基本概念和基本原理，使读者能够对计算机学科有全局性的认识。第2章计算机系统ComputerIntroduction本节大部分内容取自下面这本书的第一章。等号线之间内容是我加的。FoundationsofComputerScience,2e,byBehrouzForouzanandFirouzMosharraf.CcngagcLearningBusinessPress,December5,2007http:〃www.cengage.co.uk/forouzan/http:〃/Foundations・Computer-Science・Behrouz-Forouzan/dD/l844807002/reQsi3JdrbbproductThephrasecomputersciencehasaverybroadmeaningtoday.However,inthisbook,wedefinethephraseas“issuesrelatedtothecomputer0.Thisintroductorychapterfirsttriestofindoutwhatacomputeris,andtheninvestigatesotherissuesdirectlyrelatedtocomputers.WelookfirstattheTuringmodelasamathematicalandphilosophicaldefinitionofcomputation.Wethenshowhowtoday>——Give>——Give&shorthistoryofcomputefs.io-ObjectivesAfterstudyingthischapter,thestudentsshouldbeableto:DefinetheTuringmodelofacompute匚DefinethevonNeumannmodelofacomputer.Describethethreecomponentsofacomputer:hardware,data,andsoftware.——Listtopicsrelatedtocomputefhardware.——Listtopicsrelatedtodata.——Listtopicsrelatedtosoftware.2.1.1TURINGMODELTheideaofauniversalcomputationaldevicewasfirstdescribedbyAlanTuringin1937.Heproposedthatallcomputationcouldbeperformedbyaspecialkindofmachine,nowcalledaTuringmachine.AlthoughTuringpresentedamathematicaldescriptionofsuchamachine,hewasmoreinterestedinthephilosophicaldefinitonofcomputationthaninbuildingtheactualmachine.Hebasedthemodelontheactionsthatpeopleperfonnwheninvolvedincomputation.Heabstractedtheseactionsintoamodelforacomputationalmachinethathasreallychangedtheworld.Perceptualknowledge（感性认识）计算机组成部分http:〃/~course/cs101/2008/video/comDutercomponents.flvIntroductiontoComputerHardwarehttp:〃/~coursc/csl01/2008/video/intro2computcrhardwarc.flvInstall http:〃net.D/~course/cs101/2008/video/flvplayersetuD.exe,ifyourcomputercannotshowvideos.图2-1Motherboard（主板：集成多个部件、适配器，提供它们之间的互联）

主板（MainBoard）又名主机板、系统板、母板，是PC机的核心部件。PC机的主板包括CPU、芯片组（Chipset）、高速缓存（Cache）、ROM_BIOS芯片、CMOS芯片、内存RAM、总线通道、软硬磁盘接口、串行和并行接口、USB接口、扩展槽（Slots）,直流电源插座、可充电电池以及各种条线。图中从上到下，左到右：内存条，磁盘、光驱等的数据线接口；CPU风扇（一般F面是散热器，和CPU）：棕色AGP槽：只能接显卡；白色PCI槽：能接显卡、网卡、声卡等。图2-2CPU=运算器+控制器图2-3AlanTuring,founderofcomputerscience,andartificialintelligencehttp:〃/2008/0331/788473.shtml图灵是举世罕见的天才数学家和计算机科学家，仅仅在世42年。他的英年早逝，像他横溢的才华•样，令世界吃惊与难以置信。生命虽然短暂，但那传奇的人生，丰富多彩的创造力和智慧而深邃的思想，使他犹如一颗耀眼的明星，持续地照耀着人间后世在科学的浩瀚太空里探索未来的人们。自上个世纪60年代以来,计算机技术飞速发展，信息产业逐渐成为影响人类社会的最重要的工业之一。支持技术与工业发展的理论基础是计算机科学。众所周知，“诺贝尔奖”是世界上最负盛名的奖项,但仅用于奖励那些在物理、化学、文学、医学、经济学与促进世界和平等方面做出开拓性重大贡献的人士。“图灵奖”则是计算机科学领域的最高奖项，有“计算机界诺贝尔奖”之称。设立这个大奖，既是为了促进计算机科学的进一步发展，也是为了纪念一位天才数学家、计算机科学的奠基人艾兰•图灵。http:〃/wiki/图灵图灵被视为计算机科学之父。1931年进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma,帮助盟军取得了二战的胜利。图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为《机器会思考吗？》(CanMachineThink?)的论文，其中提出了一种用于判定机器是否具有智能的试验方法，即图灵试验。至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。http:〃/〜course/csl01/2008/video/alanturing.tlvAshortvideodescribingthelifeandunfortunatedeathofAlanTuring.http:〃/wiki/姚期智姚期智，美籍华人，计算机科学家，2000年图灵奖得主，是目前唯一一位获得此奖项的华人及亚洲人。目前是清华大学理论计算机科学研究中心教授。因为对计算理论，包括伪随机数生成，密码学与通信复杂度的诸多贡献，美国计算机协会(ACM)决定把该年度的图灵奖授予他。DataprocessorsInput Output ► Computer ►Figure1.1AsignlepurposecomputingmachineBeforediscussingtheTuringmodel,letusdefineacomputerasadataprocessor.Usingthisdefinition,acomputeractsablackboxthatacceptsinputdata,processesthedata,andcreatedoutputdata(Figure1.1).Althoughthismodelcandefinethefunctionalityofacomputertoday,itistoogeneral.Inthismodel,apocketcalculatorisalsoacomputer(whichitis,inaliteralsense).Anotherproblemwiththismodelisthatitdoesnotspecifythetypeofprocessing,orwhethermorethanonetypeofprocessingispossible.Inotherwords,itisnotclearhowmanytypesorsetsofoperationsamachinebasedonthismodelcanperform.Isitaspecific-purposemachineorageneral-purposemachine?Thismodelcouldrepresentaspecific-purposecomputer(orprocessor)thatisdesignedtodoasinglejob,suchascontrollingthetemperatureofabuildingorcontrollingthefuelusagesinacar.However,computers,asthetermisusedtoday,aregeneral-purposemahines.Theycandomanydifferenttypesoftasks.ThisimpliesthatweneedtochangethismodelintotheTuringmodeltobeabletoreflecttheactualcomputersoftoday.ProgrammabledataprocessorsTheTuringmodelisabettermodelforageneral-purposecomputer.Thismodeladdsanextraelementtothespecificcomputingmachine:theprogram.Aprogramisasetofinstructionsthattellsthecomputerwhattodowithdata.Figure1.2showstheTuringmodel.IntheTuringmodel,theoutputdatadependsonthecombinationoftwofactors:theinputdataandtheprogram.Withthesameinput,wecangeneratedifferentoutputsifwechangetheprogram.Similarly,withthesameprogram,wecangeneratedifferentoutputsifwechangetheinputdata.Finally,iftheinputdataandtheprogramremainthesame,theoutputshouldbethesame.Letuslookatthreecases.!ProgramOutputinput -Output► ComputerAcomputerbasedontheTuringmodel:programmabledataprocessor

Figure1.3showsthesamesortingprogramwithdifferentinputdata,althoughtheprogramisthesame,theoutputsaredifferent,becausedifferentinputdataisprocessed.Thesameprogram,differentdataFigure1.4showsthesameinputdatawithdifferentprograms.Eachprogrammakesthecomputerperformdifferentoperationsontheinputdata.Thefirstprogramsortsthedata,thesecondaddsthedata,andthethiredfindsthesmallestnumbe匚3,12,8,22Figure1.4Thesameinput,differentprogram3,8,12,223,12,8,22453,12,8,223,12,8,22Figure1.4Thesameinput,differentprogram3,8,12,223,12,8,22453,12,8,22Weexpectthesameresulteachtimeifbothinputdataandtheprogramarethesame,ofcourse.Inotherwords,whenthesameprogramisrunwiththesameinputdata,weexpectthesameoutput.TheuniversalTuringmachineAuniversalTuringmachine,amachinethatcandoanycomputationiftheappropriateprogramisprovided,wasthefirstdescriptionofamodemcomputer.ItcanbeprovedthataverypowerfulcomputerandauniversalTuringmachinecancomputethesamething.Weneedonlyprovidethedataandtheprogram-thedescriptionofhowtodothecomputation—toeithermachine.Infact,auniversalTuringmachineiscapableofcomputinganythingthatiscomputable.Acomputerisamachinethatmanipulatesdataaccordingtoalistofinstructions.VONNEUMANNMODELComputersbuiltontheTuringuniversalmachinestoredataintheirmemory.Around1944-1945,JohnvonNeumannproposedthat,sinceprogramanddataarelogicallythesame,programsshouldalsobestoredinthememoryofacomputer.FoursubsystemsComputersbuiltonthevonNeumannmodeldividethecomputerhardwareintofoursubsystems:memory,arithmeticlogicunit,controlunit,andinput/output(Figure1.5).Memoryisthestoragearea.Thisiswhereprogramsanddataarestoredduringprocessing.Wediscussthereasonsforstoringprogramsanddatalaterinthechapter.Thearithmeticlogicunit(ALU)iswherecalculationandlogicaloperationstakeplace.Foracomputertoactasadataprocessor,itmustbeabletodoarithmeticoperationsondata(suchasaddingalistofnumbers).Itshouldalsobeabletodologicaloperationsondata.Thecontrolunitcontrolstheoperationsofthememory,ALU,andtheinput/outputsubsystmes.Theinputsubsystemacceptsinputdataandtheprogramfromoutsidethecomputer,whiletheoutputsubsystemsendsresultsofprocessingtotheoutsideworld.Thedefinitionoftheinput/outputsubsystemisverybroad:italsoincludessecondarystoragedevicessuchasdiskortapethatstoredataandprogramsforprocessing.Whenadiskstoresdatathatresultsfromprocessing,itisconsideredanoutputdevice;whendataisreadfromthedisk,itisconsideredasainputdevice.ThestoredprogramconceptThevonNeumannmodelstatesthattheprogrammustbestoredinmemory.Thisistotallydifferentfromthearthiteccureofearlycomputersinwhichonlythedatawasstoredinmemory;theprogramsfortheirtasksimplementedbymanipulatingasetofswitchesorbychangingthewiringsystem.Thememoryofmodemcomputershostsbothaprogramanditscorrespondingdata.Thisimpliesthatboththedataandprogramsshouldhavethesameformat,becausetheyarestoredinmemory.Infact,theyarestoredasbinarypatternsinmemory-asequenceofOsandIs.SequentialexecutionofinstructionsAprograminthevonNeumannmodelismadeofafinitenumberofinstructions.Inthismodel,thecontrolunitfetchesoneinstructionfrommemory,decodesit,andthenexecutesit.Inotherwords,theinstructionsareexecutedoneafteranother.Ofcourse,oneinstructionmayrequestthecontrolunittojumptosomepreviousorfollowinginstructions,butthisdoesnotmeanthattheinstructionsarenotexecutedsequentially.SequentialexecutionofaprogramwastheinitialrequirementofacomputerbasedonthevonNeumannmodel.Today'scomputersexecuteprogramsintheorderthatismostefficient.ComputercomponentsWecanthinkofacomputerasbeingmadeupofthreecomponents:computerhardware,data,andcomputersoftware.ComputerhardwareComputerhardwaretodayhasfourcomponentsunderthevonNeumannmodel,althoughwecanhavedifferenttypesofmemory,differenttypesofinput/outputsubsystems,andsoon.DataThevonNeumannmodelclearlydefinesacomputerasadataprocessingmachinethatacceptstheinputdata,processesit,andoutputstheresult.ThevonNeumannmodeldoesnotdefinehowdatamustbestoredinacomputer.Ifacomputerisanelectronicdevice,thebestwaytostoredataisintheformofanelectricalsignal,specificallyitspresenceorabsence.Thisimpliesthatacomputercanstoredatainoneoftwostates.Obviously,thedataweuseindailylifeisnotjustinoneoftwostates.Forexample,ournumberingsystemusesdigitsthatcantakeoneoftenstates(0to9).Wecannot(asyes)storethistypeofinformationinacomputer;itneedstobechangedtoanothersystemthatusesonlytwostates(0and1).Wealsoneedtobeabletoprocessothertypesofdata(text,image,audio,andvideo).Thesealsocannotbestoredinacomputerdirectly,butneedtobechangedtotheappropriateform(OsandIs).加Chapter3,wewillleamhowtestoredifferenttypesofdat®asa-binarypattern,asequence6fOsandIs.InChapter4、weshowhowdataismanipulated,asabinarypattern,insideaccmputer.Althoughdatashouldbestoredinonlyoneforminsideacomputer,abinarypattern,dataoutsideacomputercantakemanyforms.Inaddition,computers(andthenotionofdataprocessing)havecreatedanewfieldofstudyknownasdataorganizaion,whichasksthequestion:canweorganizeourdataintodifferententitiesandformatsbeforestoringitinsideacomputer?Today,dataisnottreatedasaflatsequenceofinformation.Instead,dataisorganizedintosmallunits,smallunitsareorganizedintolargerunits,andsoon.Wewilllookatd@taf?omthispointofviewinChapters11-14.ComputersoftwareComputersoftwareisageneraltermusedtodescribeacollectionofcomputerprograms,proceduresanddocumentationthatperformsometasksonacomputersystem.Thetermincludesapplicationsoftwaresuchaswordprocessorswhichperformproductivetasksforusers,systemsoftwaresuchasoperatingsystems,whichinterfacewithhardwaretoprovidethenecessaryservicesfbrapplicationsoftware,andmiddlewarewhichcontrolsandco-ordinatesdistributedsystems.Softwareincludeswebsites,programs,videogamesetc.thatarecodedbyprogramminglanguageslikeC,C++,etc.HistoryInthissectionwebrieflyreviewthehistoryofcomputingandcomputers.Wedividethishistoryintothreeperiods.Mechanicalmachines(before1930)机械计算机器Duringthisperiod,severalcomputingmachineswereinventedthatbearlittleresemblancetothemodemconceptofacomputer.图2-2齿轮加法器1645年，法国Pascal发明了齿轮式加减法器.Inthe17thcentury,BlaisePascal,aFrenchmathematicianandphilosopher,inventedPascaline.1673年，德国数学家Leibniz发明了乘除器.Inthelate17thcentury,aGermanmathematiciancalledGottfriedLeibnitzinventedwhatisknownasLeibnitz9Wheel.ThefirstmachinethatusedtheideaofstorageandprogrammingwastheJacquardloom,inventedbyJoseph-MarieJacquardatthebeginningofthe19thcentury.第一台现代意义的计算机1821年，英国数学家C.Babbage设计了差分机，这是第一台可自动进行数学变换的机器，由于条件所限没有实现。他被誉为“计算机之父。In1823,CharlesBabbageinventedtheDifferenceEngine.Later,heinventedamachinecalledtheAnalyticalEnginethatparallelstheideaofmodemcomputers.图2・3国数学家C.Babbage设计了差分机In1890,HermanHollerith,workingattheUSCensusBureau,designedandbuiltaprogrammermachinethatcouldautomaticallyread,tally,andsortdatastoredonpunchedcards.Thebirthofelectroniccomputers(1930-1950)电子计算机的诞生Between1930and1950,severalcomputerswereinventedbyscientistswhocouldbeconsideredthepioneersoftheelectroniccomputerindustry.Theearlyelectroniccomputersofthisperioddidnotstoretheprograminmemory-allwereprogrammedexternally.Fivecomputerswereprominentduringtheseyears:ABC,Zl,MarkI,Colossus,andENIAC.

现代第一台通用的大型电子数字计算机1945年，ENIAC(ElectronicNumericalIntegratorandComputer)在宾夕法尼亚大学诞生。ENIAC用了近18000个真空管，重达30吨，耗电150千瓦，长30米，宽1米，高2.4米，每秒5000次加法运算。图24ENIACComputersbasedonthevonNeumannmodelThefirstcomputerbasedonvonNeumann'sideaswasmadein1950attheUniversityofPennsylvaniaandwascalledEDVAC.Atthesametime,asimilarcomputercalledEDSACwasbuiltbyMauriceWilkesatCambridgeUniversityinEngland.迈向现代计算机AlanTuring(1912-1954)1936年上研究生时提出了图灵机(TuringMachine),奠定了计算机的理论基础。ACMTuringAward:the“NobelPrizeofcomputing^^JohnvonNeumann。903/957)1946年发表了一篇关于如何用数字来表示逻辑操作的论文，vonNeumann体系结构为现代计算机普遍采用。Computergenerations(1950-present)计算机的诞生Computersbuiltafter1950moreorlessfollowthevonNeumannmod