不插電的計算機(jī)科學(xué)課件

不插電的計算機(jī)科學(xué)課件不插電的計算機(jī)科學(xué)課件不插電的計算機(jī)科學(xué)課件ComputerScienceUnpluggedCSUnpluggedisabookofactivitiesthatillustratecomputerscienceprincipleswithoutusingacomputer.Activitiesareshortandaredesignedtobeeasilyintegratedintoclassesandincludeexercisesandlessonplansforteachers.2021/2/42ComputerScienceUnpluggedCSUnpluggedisabookofactivitiesthatillustratecomputerscienceprincipleswithoutusingacomputer.Activitiesareshortandaredesignedtobeeasilyintegratedintoclassesandincludeexercisesandlessonplansforteachers.2021/2/42COUNTTHEDOTSDataincomputersisstoredandtransmittedasaseriesofzerosandones.Howcanwerepresentwordsandnumbersusingjustthesetwosymbols?2021/2/43COUNTTHEDOTSWhatnumericalpropertydoyouseeinthedotsonthecards?Displaythecardssothefollowingnumberofdotsareshowing:615212021/2/44COUNTTHEDOTSWhenabinarynumbercardisnotshowing,itisrepresentedbyazero.Whenitisshowing,itisrepresentedbyaone.Thisisthebinarynumbersystem(base2).Whatarethefollowingbinarynumbers?0100121001122021/2/45COUNTTHEDOTSWhatisthehighestnumberwecanrepresentusing5cards?111112=31Whatisthelowestnumberwecanrepresentusing5cards?000002=0Countfrom0to31inbinary.2021/2/46COUNTTHEDOTSLettersarerepresentedincomputersinbinaryalso!blank 0 000002 A 1 000012

B 2 000102 C 3 000112 ... Z 26 1101022021/2/47COUNTTHEDOTS010010001100101000000001110010001010000101101ICE_CREAMblank 0A 1B 2C 3D 4E 5F 6G 7H 8I 9J 10K 11L 12M 13N 14O 15P 16Q 17R 18S 19T 20U 21V 22W 23X 24Y 25Z 262021/2/48COUNTTHEDOTSHAPPYBIRTHDAY,CARLOSSANTANA!

BornJuly20,19472021/2/49COLORBYNUMBERSComputerscreensaredividedupintoagridofsmalldotscalledpixels(pictureelements).Inablackandwhitepicture,eachpixeliseitherblackorwhite.Computersstoredrawings,photographsandotherpicturesusingonlynumbers.Thefollowingactivitydemonstrateshowacomputerimagecanbestoredefficiently.2021/2/410COLORBYNUMBERSTheletterahasbeenmagnifiedtoshowthepixels.Whenacomputerstoresapicture,allthatitneedstostoreiswhichdotsareblackandwhicharewhite.1,34,11,40,1,3,10,1,3,11,42021/2/411COLORBYNUMBERS6,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,52021/2/412COLORBYNUMBERSThistechniqueiscalledrun-lengthencoding.FaxtransmissionCompressionofimagesColorencodingUsetwonumbersperrunFirstnumberishowmanypixelsasbeforeSecondnumberiswhatcolor(1=red,2=green,...)2021/2/413CARDFLIPMAGICWhendataisstoredonadiskortransmittedfromonecomputertoanother,weusuallyassumethatitdoesn'tgetchangedintheprocess.Butsometimesthingsgowrongandthedataischangedaccidentally.Thisactivityusesamagictricktoshowhowtodetectwhendatahasbeencorrupted,andtocorrectit.2021/2/414CARDFLIPMAGIC2021/2/415CARDFLIPMAGICThisexerciseillustratesevenparity.Whencomputerdataistransmittedtoanothercomputer,extrabitsareaddedsothatthenumberof1siseven.Thereceivingcomputercandetectifsomethinggetsmessedupduringthetransmissionandcancorrectitifthereisoneerror.Whathappensiftherearetwoerrors?2021/2/416CARDFLIPMAGICHereisanexampleofparityinreallife:1X10=104X9=362X8=165X7=359X6=543X5=157X4=286X3=187X2=14226/11=20remainder6 ChecksumDigit=11-6=52021/2/417CARDFLIPMAGICMoreparity:2021/2/418YOUCANSAYTHATAGAIN!Sincecomputersonlyhavealimitedamountofspacetoholdinformation,theyneedtorepresentinformationasefficientlyaspossible.Thisiscalledcompression.Bycodingdatabeforeitisstored,anddecodingitwhenitisretrieved,thecomputercanstoremoredata,orsenditfasterthroughtheInternet.Thisexerciseillustrateshowachildren'srhymecanbecompressed.2021/2/419YOUCANSAYTHATAGAIN!PITTERPATTERPITTERPATTERLISTENTOTHERAINPITTERPATTERPITTERPATTERONTHEWINDOWPANE2021/2/420YOUCANSAYTHATAGAIN!PITTERPATTERPITTERPATTERLISTENTOTHERAINPITTERPATTERPITTERPATTERONTHEWINDOWPANEBEFORE:78lettersAFTER:

29letters2021/2/421YOUCANSAYTHATAGAIN!Thearrowsandboxesarepresentedwith2numbers.PITTERPA(7,4)7:countback7positions4:copy4letters/spacesSometimesboxespointbacktoaboxwithablankinside.

BAN2021/2/422YOUCANSAYTHATAGAIN!Thestoragecapacityofcomputersisgrowingatanunbelievablerate.Inthelast25years,theamountofstorageprovidedonatypicalcomputerhasgrownaboutamillionfold.Wecancompressthedatasothatittakesuplessspace.ThisexerciseusesZiv-Lempelcoding,orLZcoding,inventedbytwoIsraeliprofessorsinthe1970s.ZIPfiles,GIFimages2021/2/423MARCHINGORDERSComputersareusuallyprogrammedusinga"language",whichisalimitedvocabularyofinstructionsthatcanbeobeyed.Oneofthemostfrustratingthingsaboutprogrammingisthatcomputersalwaysobeytheinstructionstotheletter,eveniftheyproduceacrazyresult.Thisactivitygiveskidssomeexperiencewiththisaspectofprogramming.2021/2/424MARCHINGORDERS2021/2/425MARCHINGORDERS2021/2/426BEATTHECLOCKThisactivityillustratesstructuresusedinparallelsortingnetworks.Kidssortdatabywalkingthroughasortingnetworklaidoutonthefloor.Thenetworksimulateshowaparallelnetworkwouldsortdata.Kidsfindoutthatdatacanbesortedalotfasterinparallel!2021/2/427BEATTHECLOCK2021/2/428BEATTHECLOCK

VIDEO

Searchfor“computerscienceunplugged”2021/2/429TWENTYGUESSESHowmuchinformationisthereina1000book?Istheremoreinformationina1000telephonebook,orinTolkien'sLordoftheRings?Ifwecanmeasurethis,wecanestimatehowmuchspaceisneededtostoretheinformation.Thisactivityintroducesawayofmeasuringinformationcontent.2021/2/430TWENTYGUESSESCanyoureadthefollowingsentence?

Thssntncehsthvwlsmssng.

Youprobablycan,becausethereisnotmuch"information"inthevowels.2021/2/431TWENTYGUESSESIamthinkingofanumberbetween

1and100.Iwillstartyouoffwith20piecesofcandy.Youmayonlyaskquestionsthathavea"yes"or"no"answer.Foreachincorrectguess,youwillloseonepieceofcandy.Onceyouguesscorrectly,youcankeepwhatevercandyremains.422021/2/432TWENTYGUESSESTopickanumberbetween0and100,youonlyneed7guesses.Alwaysshootforthemiddlenumberoftherangeandeliminatehalfthepossibilities!Thisconceptiscalledbinarysearch.Ifthenumberwasbetween0and1000,youwouldonlyneed3additionalguesses.Youcanguessanumberbetween0and

1millioninonly20guesses!2021/2/433BATTLESHIPSComputersareoftenrequiredtofindinformationinlargecollectionsofdata.Computerscientistsstudyquickandefficientwaysofdoingthis.Thisactivitydemonstratesthreedifferentsearchmethodssochildrencancomparethem.2021/2/434BATTLESHIPSBattleshipsarelinedupatsea.Eachbattleshiphasanumberthatishidden.Howmanyguessesdoesittakeforyoutofindaspecificbattleship?Thenumberofguessesisthechild'sscore.Thelowestscorewins.2021/2/435BATTLESHIPSGAME1:Shipsarerandomlyordered.FINDSHIP#7171630926341274054429711331764015797688346515718625258771875258802019191414414305691187177021307633362021/2/436BATTLESHIPSGAME2:Shipsareinincreasingorder.FINDSHIP#58973318373091119271943220022153451351940555548565557855897590561186296662567716831715178068077902493282021/2/437BATTLESHIPSGAME3:Shipsareorderedinto10groupsbasedonamysteryfunction.FINDSHIP#84172021/2/438BATTLESHIPSThesethreegamesillustratelinearsearchbinarysearchhashingWhatisthemaximumnumberofguessesrequiredforeachofthesesearchtechniquesfor26battleships?fornbattleships?2021/2/439POORCARTOGRAPHERManyoptimizationproblemsinvolvesituationswherecertaineventscannotoccuratthesametime(e.g.schedulingmeetingsandclasses).Coloringregionsofamapwithdifferentcolorsiseffectivelythesameproblemaswewillshowinthisexercise.2021/2/440POORCARTOGRAPHERGivenamap,coloreachregionwithacolorsothatnotwoadjacentregionsusethesamecolor.Iftworegiontouchonlyatonepoint,they

arenotconsideredadjacent.Example:ArizonaandColoradoHowmanycolorsaresufficient

tocoloramap?Howmanycolorsarenecessary

tocoloramap?2021/2/441POORCARTOGRAPHER2021/2/442POORCARTOGRAPHER2021/2/443POORCARTOGRAPHER2021/2/444POORCARTOGRAPHER"undirectedgraph"AIHGBFECDJGABCDEFJHI2021/2/445POORCARTOGRAPHERScheduling2021/2/446POORCARTOGRAPHERCanwecoloramapwith3colors?Thisproblemisintractable.Theonlywayweknowtosolvethisproblemingeneralistoderiveallpossiblecoloringsandseeifwecomeacrossavalidcoloring.Howmanycoloringsarethereforamapwith25regions?Howlongwouldittaketoanalyzeallofthesecoloringsifittakes1secondtoanalyzeonecoloring?2021/2/447THECOOPERATIONGAMEWhenyouhavealotofpeopleusingoneresource(suchascarsusingroads,ormessagesgettingthroughtheInternet),thereisthepossibilityof"deadlock".Awayofworkingcooperativelyisneededtoavoidthishappening.Thisexerciseillustratescooperativeproblemsolvingand(potentially)deadlock.2021/2/448THECOOPERATIONGAMEAsharedresource

inPittsburgh:STOPSTOPSTOPSTOP2021/2/449THECOOPERATIONGAMEAsharedresource

inNewYork:STOPSTOPSTOPSTOP2021/2/450THECOOPERATIONGAMESetup:Eachchildisassignedacolor.Givetwocolorcardstoeachchildexceptonechild,whogetsonlyone.Eachchildshouldnotholdhisorherowncolorinitially.Thechildrenformacircle.Goal:Eachchildmustendupwiththecard(s)ofhisorherowncolor.2021/2/451THECOOPERATIONGAMEPassingRules:

Onlyonecardmaybeheldineachhand.

Acardcanonlybepassedtoanemptyhandofanimmediateneighborinthecircle.(Achildcanpasseitheroftheirtwocardstotheirneighbor.)

(optional)Notalking.2021/2/452THECOOPERATIONGAMEAlternateConfigurations2021/2/453THECOOPERATIONGAMERoutinganddeadlockareproblemsinmanynetworks,suchasroadsystems,telephoneandcomputersystems.Engineersspendalotoftimefiguringouthowtosolvetheseproblems-andhowtodesignnetworksthatmaketheproblemseasiertosolve.2021/2/454TREASUREHUNTComputerprogramsoftenneedtoprocessasequenceofsymbolssuchaswordsinadocumentoreventhetextofanotherprogram.ComputerscientistsuseaFiniteStateAutomaton(FSA),asetofinstructionstoseeifthesequenceisacceptableornot.ThisexerciseusestheFSAideausingtreasuremaps!2021/2/455TREASUREHUNTGoal:FindTreasureIsland,startingfromPirates'Island.Friendlypirateshipssailalongfixedroutesbetweenislandsofferingridestotravelers.Eachislandhastwodepartingships,AandB.DetermineallpossiblesequencesofshipsthatatravelercantaketoarriveatTreasureIsland.Useyourmaptorecordalltheshiproutes.2021/2/456TREASUREHUNTAB2021/2/457TREASUREHUNTAB2021/2/458TREASUREHUNTAB2021/2/459TREASUREHUNTAB2021/2/460TREASUREHUNTAB2021/2/461TREASUREHUNTAB2021/2/462TREASUREHUNTPLAYAGAIN2021/2/463TREASUREHUNTWhatisthequickestroute?"directedgraph"2021/2/464LIGHTEST&HEAVIESTComputersareoftenusedtoputlistsintosomesortoforder(e.g.namesintoalphabeticalorder,appointmentsore-mailbydate,etc.)Ifyouusethewrongmethod,itcantakealongtimetosortalargelistintoorder,evenonafastcomputer.Inthisactivitychildrenwilldiscoverdifferentmethodsforsorting,andseehowaclevermethodcanperformthetaskmuchmorequicklythanasimpleone.

2021/2/465LIGHTEST&HEAVIESTStartwith8containerswithdifferentamountsofsandorwaterinside.Sealtightly.Childrenareonlyallowedtousethescalestocomparetherelativeweightsoftwocontainers.Onlytwocontainerscanbecomparedatatime.

2021/2/466LIGHTEST&HEAVIESTMETHOD1Weighfirsttwocontainers.Keepthelightercontainerandweighitagainstthethirdcontainer.Keepthelightercontainerandweighitagainstthefourthcontainer....continue...Keepthelightercontainerandweighitagainsttheeighthcontainer.Keepthelightercontainer.Thismustbethelightestcontainer.2021/2/467LIGHTEST&HEAVIESTMETHOD1(cont'd)Repeatthisprocessagainusingthe7remainingcontainerstogetthenextlightestcontainer.Repeatthisprocessagainusingthe6remainingcontainerstogetthenextlightestcontainer.Continue