Computational+Thinking+and+thinking+about+computin

ComputationalThinkingandThinkingAboutComputingJeannetteM.WingPresident’sProfessorofComputerScienceCarnegieMellonUniversity©2008JeannetteM.Wing2CT&TCJeannetteM.WingOutline•ComputationalThinking•AVisionforourField•ThinkingaboutComputing•DriversofourField•5DeepQuestionsinComputingComputationalThinking4CT&TCJeannetteM.WingMyGrandVisionfortheField•Computationalthinkingwillbeafundamentalskillusedbyeveryoneintheworldbythemiddleofthe21stCentury.–Justlikereading,writing,andarithmetic.–Imagineeverychildknowinghowtothinklikeacomputerscientist!–Incestuous:Computingandcomputerswillenablethespreadofcomputationalthinking.–Inresearch:scientists,engineers,…,historians,artists–Ineducation:K-12studentsandteachers,undergrads,…J.M.Wing,“ComputationalThinking,”CACMViewpoint,March2006,pp.33-35.PaperoffCISEACwebsite;paperandtalksoff~wing/5CT&TCJeannetteM.WingExamplesofComputationalThinking•HowdifficultisthisproblemandhowbestcanIsolveit?–Theoreticalcomputersciencegivesprecisemeaningtotheseandrelatedquestionsandtheiranswers.•C.T.isthinkingrecursively.•C.T.isreformulatingaseeminglydifficultproblemintoonewhichweknowhowtosolve.–Reduction,embedding,transformation,simulation•C.T.ischoosinganappropriaterepresentationormodelingtherelevantaspectsofaproblemtomakeittractable.•C.T.isinterpretingcodeasdataanddataascode.•C.T.isusingabstractionanddecompositionintacklingalargecomplextask.•C.T.isjudgingasystem’sdesignforitssimplicityandelegance.•C.T.istypechecking,asageneralizationofdimensionalanalysis.•C.T.isprevention,detection,andrecoveryfromworst-casescenariosthroughredundancy,damagecontainment,anderrorcorrection.•C.T.ismodularizingsomethinginanticipationofmultipleusersandprefetchingandcachinginanticipationoffutureuse.•C.T.iscallinggridlockdeadlockandavoidingraceconditionswhensynchronizingmeetings.•C.T.isusingthedifficultyofsolvinghardAIproblemstofoilcomputingagents.•C.T.istakinganapproachtosolvingproblems,designingsystems,andunderstandinghumanbehaviorthatdrawsonconceptsfundamentaltocomputerscience.Pleasetellmeyourfavoriteexamplesofcomputationalthinking!6CT&TCJeannetteM.WingSimpleDailyExamples•Lookingupanameinanalphabeticallysortedlist–Linear:startatthetop–Binarysearch:startinthemiddle•Standinginlineatabank,supermarket,customs&immigration–Performanceanalysisoftaskscheduling•Puttingthingsinyourchild’sknapsackfortheday–Pre-fetchingandcaching•Takingyourkidstosoccer,gymnastics,andswimpractice–Travelingsalesman(withmoreconstraints)•Cookingagourmetmeal–Parallelprocessing:Youdon’twantthemeattogetcoldwhileyou’recookingthevegetables.•Cleaningoutyourgarage–Keepingonlywhatyouneedvs.throwingoutstuffwhenyourunoutofspace.•Storingawayyourchild’sLegopiecesscatteredontheLRfloor–Usinghashing(e.g.,byshape,bycolor)•Doinglaundry,gettingfoodatabuffet–Pipeliningthewash,dry,andironstages;plates,salad,entrée,dessertstations•Eveningradeschool,welearnalgorithms(longdivision,factoring,GCD,…)andabstractdatatypes(sets,tables,…).7CT&TCJeannetteM.WingTheFirstAtoComputationalThinking•Abstractionsareour“mental”tools•Theabstractionprocessincludes–Choosingtherightabstractions–Operatingsimultaneouslyatmultiplelayersofabstraction–Definingtherelationshipsthebetweenlayers8CT&TCJeannetteM.WingTheSecondAtoComputationalThinking•Thepowerofour“mental”toolsisamplifiedbyour“metal”tools.•Automationismechanizingourabstractions,abstractionlayers,andtheirrelationships–Mechanizationispossibleduetopreciseandexactingnotationsandmodels–Thereissome“computer”below(humanormachine,virtualorphysical)9CT&TCJeannetteM.WingTwoA’stoC.T.Combined•Computingistheautomationofourabstractions–Theygiveustheaudacityandabilitytoscale.•Computationalthinking–choosingtherightabstractions,etc.–choosingtheright“computer”forthetask10CT&TCJeannetteM.WingResearchImplications11CT&TCJeannetteM.WingCTinOtherSciences,Math,andEngineeringBiology-Shotgunalgorithmexpeditessequencingofhumangenome-DNAsequencesarestringsinalanguage-Proteinstructurescanbemodeledasknots-Proteinkineticscanbemodeledascomputationalprocesses-Cellsasaself-regulatorysystemarelikeelectroniccircuitsBrainScience-Modelingthebrainasacomputer-Visionasafeedbackloop-AnalyzingfMRIdatawithmachinelearning12CT&TCJeannetteM.WingCTinOtherSciences,Math,andEngineering[York,Minnesota]Chemistry[Madden,FellowofRoyalSocietyofEdinburgh]-Atomisticcalculationsareusedtoexplorechemicalphenomena-OptimizationandsearchingalgorithmsidentifybestchemicalsforimprovingreactionconditionstoimproveyieldsGeology-Modelingtheearth’ssurfacetothesun,fromtheinnercoretothesurface-Abstractionboundariesandhierarchiesofcomplexitymodeltheearthandouratmosphere13CT&TCJeannetteM.WingCTinOtherSciences,Math,andEngineeringAstronomy-SloanDigitalSkyServerbringsatelescopetoeverychild-KD-treeshelpastronomersanalyzeverylargemulti-dimensionaldatasetsEngineering(electrical,civil,mechanical,aero&astro,…)-Calculatinghigherordertermsimpliesmoreprecision,whichimpliesreducingweight,waste,costsinfabrication-Boeing777testedviacomputersimulationalone,notinawindtunnelMathematics-DiscoveringE8LieGroup:18mat