不插电的计算机科学PPT课件

.,1,ComputerScienceUnplugged,Dr.TomCortinaCarnegieMellonUniversitySponsoredby,.,2,ComputerScienceUnplugged,CSUnpluggedisabookofactivitiesthatillustratecomputerscienceprincipleswithoutusingacomputer.Activitiesareshortandaredesignedtobeeasilyintegratedintoclassesandincludeexercisesandlessonplansforteachers.,.,3,COUNTTHEDOTS,Dataincomputersisstoredandtransmittedasaseriesofzerosandones.Howcanwerepresentwordsandnumbersusingjustthesetwosymbols?,.,4,COUNTTHEDOTS,Whatnumericalpropertydoyouseeinthedotsonthecards?Displaythecardssothefollowingnumberofdotsareshowing:61521,.,5,COUNTTHEDOTS,Whenabinarynumbercardisnotshowing,itisrepresentedbyazero.Whenitisshowing,itisrepresentedbyaone.Thisisthebinarynumbersystem(base2).Whatarethefollowingbinarynumbers?010012100112,.,6,COUNTTHEDOTS,Whatisthehighestnumberwecanrepresentusing5cards?111112=31Whatisthelowestnumberwecanrepresentusing5cards?000002=0Countfrom0to31inbinary.,.,7,COUNTTHEDOTS,Lettersarerepresentedincomputersinbinaryalso!blank0000002A1000012B2000102C3000112.Z26110102,.,8,COUNTTHEDOTS,010010001100101000000001110010001010000101101,ICE_CREAM,blank0A1B2C3D4E5F6G7H8I9J10K11L12M13,N14O15P16Q17R18S19T20U21V22W23X24Y25Z26,.,9,COUNTTHEDOTS,HAPPYBIRTHDAY,CARLOSSANTANA!BornJuly20,1947,.,10,COLORBYNUMBERS,Computerscreensaredividedupintoagridofsmalldotscalledpixels(pictureelements).Inablackandwhitepicture,eachpixeliseitherblackorwhite.Computersstoredrawings,photographsandotherpicturesusingonlynumbers.Thefollowingactivitydemonstrateshowacomputerimagecanbestoredefficiently.,.,11,COLORBYNUMBERS,Theletterahasbeenmagnifiedtoshowthepixels.Whenacomputerstoresapicture,allthatitneedstostoreiswhichdotsareblackandwhicharewhite.,1,34,11,40,1,3,10,1,3,11,4,.,12,COLORBYNUMBERS,6,5,2,34,2,5,2,3,13,1,9,1,2,13,1,9,1,1,12,1,11,12,1,10,22,1,9,1,1,12,1,8,1,2,12,1,7,1,3,11,1,1,1,4,2,3,10,1,2,1,2,2,5,10,1,3,2,5,21,3,2,5,.,13,COLORBYNUMBERS,Thistechniqueiscalledrun-lengthencoding.FaxtransmissionCompressionofimagesColorencodingUsetwonumbersperrunFirstnumberishowmanypixelsasbeforeSecondnumberiswhatcolor(1=red,2=green,.),.,14,CARDFLIPMAGIC,Whendataisstoredonadiskortransmittedfromonecomputertoanother,weusuallyassumethatitdoesntgetchangedintheprocess.Butsometimesthingsgowrongandthedataischangedaccidentally.Thisactivityusesamagictricktoshowhowtodetectwhendatahasbeencorrupted,andtocorrectit.,.,15,CARDFLIPMAGIC,.,16,CARDFLIPMAGIC,Thisexerciseillustratesevenparity.Whencomputerdataistransmittedtoanothercomputer,extrabitsareaddedsothatthenumberof1siseven.Thereceivingcomputercandetectifsomethinggetsmessedupduringthetransmissionandcancorrectitifthereisoneerror.Whathappensiftherearetwoerrors?,.,17,CARDFLIPMAGIC,Hereisanexampleofparityinreallife:,1X10=104X9=362X8=165X7=359X6=543X5=157X4=286X3=187X2=14226/11=20remainder6ChecksumDigit=11-6=5,.,18,CARDFLIPMAGIC,Moreparity:,.,19,YOUCANSAYTHATAGAIN!,Sincecomputersonlyhavealimitedamountofspacetoholdinformation,theyneedtorepresentinformationasefficientlyaspossible.Thisiscalledcompression.Bycodingdatabeforeitisstored,anddecodingitwhenitisretrieved,thecomputercanstoremoredata,orsenditfasterthroughtheInternet.Thisexerciseillustrateshowachildrensrhymecanbecompressed.,.,20,YOUCANSAYTHATAGAIN!,PITTERPATTERPITTERPATTERLISTENTOTHERAINPITTERPATTERPITTERPATTERONTHEWINDOWPANE,.,21,YOUCANSAYTHATAGAIN!,PITTERPATTERPITTERPATTERLISTENTOTHERAINPITTERPATTERPITTERPATTERONTHEWINDOWPANE,BEFORE:78letters,AFTER:29letters,.,22,YOUCANSAYTHATAGAIN!,Thearrowsandboxesarepresentedwith2numbers.PITTERPA(7,4)7:countback7positions4:copy4letters/spacesSometimesboxespointbacktoaboxwithablankinside.,.,23,YOUCANSAYTHATAGAIN!,Thestoragecapacityofcomputersisgrowingatanunbelievablerate.Inthelast25years,theamountofstorageprovidedonatypicalcomputerhasgrownaboutamillionfold.Wecancompressthedatasothatittakesuplessspace.ThisexerciseusesZiv-Lempelcoding,orLZcoding,inventedbytwoIsraeliprofessorsinthe1970s.ZIPfiles,GIFimages,.,24,MARCHINGORDERS,Computersareusuallyprogrammedusingalanguage,whichisalimitedvocabularyofinstructionsthatcanbeobeyed.Oneofthemostfrustratingthingsaboutprogrammingisthatcomputersalwaysobeytheinstructionstotheletter,eveniftheyproduceacrazyresult.Thisactivitygiveskidssomeexperiencewiththisaspectofprogramming.,.,25,MARCHINGORDERS,.,26,MARCHINGORDERS,.,27,BEATTHECLOCK,Thisactivityillustratesstructuresusedinparallelsortingnetworks.Kidssortdatabywalkingthroughasortingnetworklaidoutonthefloor.Thenetworksimulateshowaparallelnetworkwouldsortdata.Kidsfindoutthatdatacanbesortedalotfasterinparallel!,.,28,BEATTHECLOCK,.,29,BEATTHECLOCKVIDEO,Searchfor“computerscienceunplugged”,.,30,TWENTYGUESSES,Howmuchinformationisthereina1000-pagebook?Istheremoreinformationina1000-pagetelephonebook,orinTolkiensLordoftheRings?Ifwecanmeasurethis,wecanestimatehowmuchspaceisneededtostoretheinformation.Thisactivityintroducesawayofmeasuringinformationcontent.,.,31,TWENTYGUESSES,Canyoureadthefollowingsentence?Thssntncehsthvwlsmssng.Youprobablycan,becausethereisnotmuchinformationinthevowels.,.,32,TWENTYGUESSES,Iamthinkingofanumberbetween1and100.Iwillstartyouoffwith20piecesofcandy.Youmayonlyaskquestionsthathaveayesornoanswer.Foreachincorrectguess,youwillloseonepieceofcandy.Onceyouguesscorrectly,youcankeepwhatevercandyremains.,42,.,33,TWENTYGUESSES,Topickanumberbetween0and100,youonlyneed7guesses.Alwaysshootforthemiddlenumberoftherangeandeliminatehalfthepossibilities!Thisconceptiscalledbinarysearch.Ifthenumberwasbetween0and1000,youwouldonlyneed3additionalguesses.Youcanguessanumberbetween0and1millioninonly20guesses!,.,34,BATTLESHIPS,Computersareoftenrequiredtofindinformationinlargecollectionsofdata.Computerscientistsstudyquickandefficientwaysofdoingthis.Thisactivitydemonstratesthreedifferentsearchmethodssochildrencancomparethem.,.,35,BATTLESHIPS,Battleshipsarelinedupatsea.Eachbattleshiphasanumberthatishidden.Howmanyguessesdoesittakeforyoutofindaspecificbattleship?Thenumberofguessesisthechildsscore.Thelowestscorewins.,.,36,BATTLESHIPS,GAME1:Shipsarerandomlyordered.,FINDSHIP#717,1630926341274054429711331764015797688346515718625,25877187525880201919141441430569118717702130763336,.,37,BATTLESHIPS,GAME2:Shipsareinincreasingorder.,FINDSHIP#5897,33183730911192719432200221534513519405555485655,5785589759056118629666256771683171517806807790249328,.,38,BATTLESHIPS,GAME3:Shipsareorderedinto10groupsbasedonamysteryfunction.,FINDSHIP#8417,.,39,BATTLESHIPS,ThesethreegamesillustratelinearsearchbinarysearchhashingWhatisthemaximumnumberofguessesrequiredforeachofthesesearchtechniquesfor26battleships?fornbattleships?,.,40,POORCARTOGRAPHER,Manyoptimizationproblemsinvolvesituationswherecertaineventscannotoccuratthesametime(e.g.schedulingmeetingsandclasses).Coloringregionsofamapwithdifferentcolorsiseffectivelythesameproblemaswewillshowinthisexercise.,.,41,POORCARTOGRAPHER,Givenamap,coloreachregionwithacolorsothatnotwoadjacentregionsusethesamecolor.Iftworegiontouchonlyatonepoint,theyarenotconsideredadjacent.Example:ArizonaandColoradoHowmanycolorsaresufficienttocoloramap?Howmanycolorsarenecessarytocoloramap?,.,42,POORCARTOGRAPHER,.,43,POORCARTOGRAPHER,.,44,POORCARTOGRAPHER,.,45,POORCARTOGRAPHER,undirectedgraph,A,I,H,G,B,F,E,C,D,J,G,A,B,C,D,E,F,J,H,I,.,46,POORCARTOGRAPHER,Scheduling,.,47,POORCARTOGRAPHER,Canwecoloramapwith3colors?Thisproblemisintractable.Theonlywayweknowtosolvethisproblemingeneralistoderiveallpossiblecoloringsandseeifwecomeacrossavalidcoloring.Howmanycoloringsarethereforamapwith25regions?Howlongwouldittaketoanalyzeallofthesecoloringsifittakes1secondtoanalyzeonecoloring?,.,48,THECOOPERATIONGAME,Whenyouhavealotofpeopleusingoneresource(suchascarsusingroads,ormessagesgettingthroughtheInternet),thereisthepossibilityofdeadlock.Awayofworkingcooperativelyisneededtoavoidthishappening.Thisexerciseillustratescooperativeproblemsolvingand(potentially)deadlock.,.,49,THECOOPERATIONGAME,AsharedresourceinPittsburgh:,.,50,THECOOPERATIONGAME,AsharedresourceinNewYork:,.,51,THECOOPERATIONGAME,Setup:Eachchildisassignedacolor.Givetwocolorcardstoeachchildexceptonechild,whogetsonlyone.Eachchildshouldnotholdhisorherowncolorinitially.Thechildrenformacircle.Goal:Eachchildmustendupwiththecard(s)ofhisorherowncolor.,.,52,THECOOPERATIONGAME,PassingRules:Onlyonecardmaybeheldineachhand.Acardcanonlybepassedtoanemptyhandofanimmediateneighborinthecircle.(Achildcanpasseitheroftheirtwocardstotheirneighbor.)(optional)Notalking.,.,53,THECOOPERATIONGAME,AlternateConfigurations,.,54,THECOOPERATIONGAME,Routinganddeadlockareproblemsinmanynetworks,suchasroadsystems,telephoneandcomputersystems.Engineersspendalotoftimefiguringouthowtosolvetheseproblems-andhowtodesignnetworksthatmaketheproblemseasiertosolve.,.,55,TREASUREHUNT,Computerprogramsoftenneedtoprocessasequenceofsymbolssuchaswordsinadocumentoreventhetextofanotherprogram.ComputerscientistsuseaFiniteStateAutomaton(FSA),asetofinstructionstoseeifthesequenceisacceptableornot.ThisexerciseusestheFSAideausingtreasuremaps!,.,56,TREASUREHUNT,Goal:FindTreasureIsland,startingfromPiratesIsland.Friendlypirateshipssailalongfixedroutesbetweenislandsofferingridestotravelers.Eachislandhastwodepartingships,AandB.DetermineallpossiblesequencesofshipsthatatravelercantaketoarriveatTreasureIsland.Useyourmaptorecordalltheshiproutes.,.,57,TREASUREHUNT,A,B,.,58,TREASUREHUNT,A,B,.,59,TREASUREHUNT,A,B,.,60,TREASUREHUNT,A,B,.,61,TREASUREHUNT,A,B,.,62,TREASUREHUNT,A,B,.,63,TREASUREHUNT,PLAYAGAIN,.,64,TREASUREHUNT,Whatisthequickestroute?,directedgraph,.,65,LIGHTEST&HEAVIEST,Computersareoftenusedtoputlistsintosomesortoforder(sintoalphabeticalorder,appointmentsore-mailbydate,etc.)Ifyouusethewrongmethod,itcantakealongtimetosortalargelistintoorder,evenonafastcomputer.Inthisactivitychildrenwilldiscoverdifferentmethodsforsorting,andseehowaclevermethodcanperformthetaskmuchmorequicklythanasimpleone.,.,66,LIGHTEST&HEAVIEST,Startwith8containerswithdifferentamountsofsandorwaterinside.Sealtightly.Childrenareonlyallowedtousethescalestocomparetherelativeweightsoftwocontainers.Onlytwocontainerscanbecomparedatatime.,.,67,LIGHTEST&HEAVIEST,METHOD1Weighfirsttwocontainers.Keepthelightercontainerandweighitagainstthethirdcontainer.Keepthelightercontainerandweighitagainstthefourthcontainer.continue.Keepthelightercontainerandweighitagainsttheeighthcontainer.Keepthelightercontainer.Thismustbethelightestcontainer.,.,68,LIGHTEST&HEAVIEST,METHOD1(contd)Repeatthisprocessagainusingthe7remainingcontainerstogetthenextlightestcontainer.Repeatthisprocessagainusingthe6remainingcontainerstogetthenextlightestcontainer.Continueuntilallcontainersaresortedbyweight.Howmayweightcomparisonsdowehavetodotosor