1IntroductionFoundationsofComputerScience?CengageLearning1DefinetheTuringmodelofacomputer.DefinethevonNeumannmodelofacomputer.Describethethreecomponentsofacomputer:hardware,

data,andsoftware.Listtopicsrelatedtocomputerhardware.Listtopicsrelatedtodata.Listtopicsrelatedtosoftware.Discusssomesocialandethicalissuesrelatedtotheuseof

computers.Giveashorthistoryofcomputers.ObjectivesAfterstudyingthischapter,thestudentshouldbeableto:21-1TURINGMODELTheideaofauniversalcomputationaldevicewasfirstdescribedbyAlanTuringin1937.Heproposedthatallcomputationcouldbeperformedbyaspecialkindofamachine,nowcalledaTuringmachine.Hebasedthemodelontheactionsthatpeopleperformwheninvolvedincomputation.Heabstractedtheseactionsintoamodelforacomputationalmachinethathasreallychangedtheworld.3DataprocessorsBeforediscussingtheTuringmodel,letusdefineacomputerasadataprocessor.Usingthisdefinition,acomputeractsasablackboxthatacceptsinputdata,processesthedata,andcreatesoutputdata(Figure1.1).Althoughthismodelcandefinethefunctionalityofacomputertoday,itistoogeneral.Inthismodel,apocketcalculatorisalsoacomputer(whichitis,inaliteralsense).Figure1.1Asinglepurposecomputingmachine4ProgrammabledataprocessorsTheTuringmodelisabettermodelforageneral-purposecomputer.Thismodeladdsanextraelementtothespecificcomputingmachine:theprogram.Aprogramisasetofinstructionsthattellsthecomputerwhattodowithdata.Figure1.2showstheTuringmodel.Figure1.2AcomputerbasedontheTuringmodel5Figure1.3Thesameprogram,differentdata6Figure1.4Thesamedata,differentprograms7TheuniversalTuringmachineAuniversalTuringmachine,amachinethatcandoanycomputationiftheappropriateprogramisprovided,wasthefirstdescriptionofamoderncomputer.ItcanbeprovedthataverypowerfulcomputerandauniversalTuringmachinecancomputethesamething.Weneedonlyprovidethedataandtheprogram—thedescriptionofhowtodothecomputation—toeithermachine.Infact,auniversalTuringmachineiscapableofcomputinganythingthatiscomputable.81-2VONNEUMANNMODELComputersbuiltontheTuringuniversalmachinestoredataintheirmemory.Around1944–1945,JohnvonNeumannproposedthat,sinceprogramanddataarelogicallythesame,programsshouldalsobestoredinthememoryofacomputer.9ComputersbuiltonthevonNeumannmodeldividethecomputerhardwareintofoursubsystems:memory,arithmeticlogicunit,controlunit,andinput/output(Figure1.5).FoursubsystemsFigure1.5ThevonNeumannmodel10ThevonNeumannmodelstatesthattheprogrammustbestoredinmemory.Thisistotallydifferentfromthearchitectureofearlycomputersinwhichonlythedatawasstoredinmemory:theprogramsfortheirtaskwasimplementedbymanipulatingasetofswitchesorbychangingthewiringsystem. Thememoryofmoderncomputershostsbothaprogramanditscorrespondingdata.Thisimpliesthatboththedataandprogramsshouldhavethesameformat,becausetheyarestoredinmemory.Infact,theyarestoredasbinarypatternsinmemory—asequenceof0sand1s.Thestoredprogramconcept11AprograminthevonNeumannmodelismadeofafinitenumberofinstructions.Inthismodel,thecontrolunitfetchesoneinstructionfrommemory,decodesit,thenexecutesit.Inotherwords,theinstructionsareexecutedoneafteranother.Ofcourse,oneinstructionmayrequestthecontrolunittojumptosomepreviousorfollowinginstruction,butthisdoesnotmeanthattheinstructionsarenotexecutedsequentially.SequentialexecutionofaprogramwastheinitialrequirementofacomputerbasedonthevonNeumannmodel.Today’scomputersexecuteprogramsintheorderthatisthemostefficient.Sequentialexecutionofinstructions121-3COMPUTERCOMPONENTSWecanthinkofacomputerasbeingmadeupofthreecomponents:computerhardware,data,andcomputersoftware.13ComputerhardwaretodayhasfourcomponentsunderthevonNeumannmodel,althoughwecanhavedifferenttypesofmemory,differenttypesofinput/outputsubsystems,andsoon.WediscusscomputerhardwareinmoredetailinChapter5.ComputerhardwareThevonNeumannmodelclearlydefinesacomputerasadataprocessingmachinethatacceptstheinputdata,processesit,andoutputstheresult.Data14ThemainfeatureoftheTuringorvonNeumannmodelsistheconceptoftheprogram.Althoughearlycomputersdidnotstoretheprograminthecomputer’smemory,theydidusetheconceptofprograms.Programmingthoseearlycomputersmeantchangingthewiringsystemsorturningasetofswitchesonoroff.Programmingwasthereforeataskdonebyanoperatororengineerbeforetheactualdataprocessingbegan.Computersoftware15Figure1.6Programanddatainmemory16Figure1.7Aprogrammadeofinstructions171-4HISTORYInthissectionwebrieflyreviewthehistoryofcomputingandcomputers.Wedividethishistoryintothreeperiods.18Mechanicalmachines(before1930)Duringthisperiod,severalcomputingmachineswereinventedthatbearlittleresemblancetothemodernconceptofacomputer.Inthe17thcentury,BlaisePascal,aFrenchmathematicianand

philosopher,inventedPascaline.Inthelate17thcentury,aGermanmathematiciancalledGottfriedLeibnitzinventedwhatisknownasLeibnitz’Wheel.

Thefirstmachinethatusedtheideaofstorageandprogramming

wastheJacquardloom,inventedbyJoseph-MarieJacquardatthe

beginningofthe19thcentury.19In1823,CharlesBabbageinventedtheDifferenceEngine.Later,

heinventedamachinecalledtheAnalyticalEnginethatparallels

theideaofmoderncomputers.In1890,HermanHollerith,workingattheUSCensusBureau,

designedandbuiltaprogrammermachinethatcouldautomatically

read,tally,andsortdatastoredonpunchedcards.20Thebirthofelectroniccomputers(1930–1950)Between1930and1950,severalcomputerswereinventedbyscientistswhocouldbeconsideredthepioneersoftheelectroniccomputerindustry.Theearlycomputersofthisperioddidnotstoretheprograminmemory—allwereprogrammedexternally.Fivecomputerswereprominentduringtheseyears:ABCZ1MarkI.ColossusENIACEarlyelectroniccomputers21ThefirstcomputerbasedonvonNeumann’sideaswasmadein1950attheUniversityofPennsylvaniaandwascalledEDVAC.Atthesametime,asimilarcomputercalledEDSACwasbuiltbyMauriceWilkesatCambridgeUniversityinEngland.ComputersbasedonthevonNeumannmodel22Computergenerations(1950–present)Computersbuiltafter1950moreorlessfollowthevonNeumannmodel.Theyhavebecomefaster,smaller,andcheaper,buttheprincipleisalmostthesame.Historiansdividethisperiodintogenerations,witheachgenerationwitnessingsomemajorchangeinhardwareorsoftware(butnotinthemodel).Thefirstgeneration(roughly1950–1959)ischaracterizedbytheemergenceofcommercialcomputers.Firstgeneration23Second-generationcomputers(roughly1959–1965)usedtransistorsinsteadofvacuumtubes.Twohigh-levelprogramminglanguages,FORTRANandCOBOLinventedandmadeprogrammingeasier.SecondgenerationTheinventionoftheintegratedcircuitreducedthecostandsizeofcomputersevenfurther.Minicomputersappearedonthemarket.Cannedprograms,popularlyknownassoftwarepackages,becameavailable.Thisgenerationlastedroughlyfrom1965to1975.Thirdgeneration24Thefourthgeneration(approximately1975–1985)sawtheappearanceofmicrocomputers.Thefirstdesktopcalculator,theAltair8800,becameavailablein1975.Thisgenerationalsosawtheemergenceofcomputernetworks.FourthgenerationThisopen-endedgenerationstartedin1985.Ithaswitnessedtheappearanceoflaptopandpalmtopcomputers,improvementsinsecondarystoragemedia(CD-ROM,DVDandsoon),theuseofmultimedia,andthephenomenonofvirtualreality.Fifthgeneration251-5SOCIALANDETHICALISSUESComputersciencehascreatedsomeperipheralissues,themostprevalentofwhichcanbecategorizedassocialandethicalissues.26SocialissuesComputershavecreatedsomearguments.Weintroducesomeoftheseargumentshere.Somepeoplethinkthatcomputershavecreatedakindofdependency,whichmakespeople’slivesmoredifficult.DependencySocialjusticeisanotherissueweoftenhearabout.Theadvocatesofthisissuearguethatusingcomputersathomeisaluxurybenefitthatnotallpeoplecanafford.Thecostofacomputer,peripheraldevices,andamonthlychargeforInternetaccessisanextraburdenonlow-incomepeople.Socialjustice27Theconceptofdigitaldividecoversboththeissuesofdependencyandsocialjusticediscussedabove.Theconceptdividessocietyintotwogroups:thosewhoareelectronicallyconnectedtotherestofsocietyandthosewhoarenot.Digitaldivide28EthicalissuesComputershavecreatedsomeethicalissues.Weintroducesomeofthesehere.Computersallowcommunicationbetweentwopartiestobedoneelectronically.However,muchneedstobedonetomakethistypeofcommunicationprivate.Societyispayingabigpriceforprivateelectroniccommunication.Networksecuritymaycreatethistypeofprivacy,butitneedseffortandcostsalot.Privacy29Anotherethicalissueinacomputerizedsocietyiscopyright:whoownsdata?TheInternethascreatedopportunitiestoshareideas,buthasalsobroughtwithitafurtherethicalissue:electroniccopyright.CopyrightComputersandinformationtechnologyhavecreatednewtypesofcrime.Hackershavebeenabletoaccessmanycomputersintheworldandhavestolenalotofmoney.ViruscreatorsdesignnewvirusestobesentthroughtheInternetanddamagetheinformationstoredincomputers.Althoughtherearemanyanti-virusprogramsinusetoday,societyispayingabigpriceforthistypeofcrime,whichdidnotexistbeforethecomputerandInternetera.Computercrime301-6COMPUTERSCIENCEASADISCIPLINEWiththeinventionofcomputers,anewdisciplinehasevolved:computerscience.Likeanyotherdiscipline,computersciencehasnowdividedintoseveralareas.Wecandividetheseareasintotwobroadcategories:systemsareasandapplicationsareas.Thisbookisabreadth-firstapproachtoalltheseareas.Afterreadingthebook,thereadershouldhaveenoughinformationtoselectthedesiredareaofspecialty.311-7OUTLINEOFTHECOURSEAfterthisintroductorychapter,thebookisdividedintofiveparts.PartI:DatarepresentationandoperationThispartincludesChapters2,3,and4.Chapter2discussesnumbersystems;howaquantitycanberepresentedusingsymbols.Chapter3discusseshowdifferentdataisstoredinsidethecomputer.Chapter4discussessomeprimitiveoperationsonbits.32PartII:Computerhardwar