2010計算思維讀書筆記

周以真教授和李國杰院士有關計算思維的

觀點總結(jié)2010-12-25測驗小題Thinkinglikeacomputerscientistmeansmorethanbeingabletoprogramacomputer.Itrequiresthinkingatmultiplelevelsofabstraction.ComputationalThinkingAbstractingCT提綱引言兩位專家簡歷周以真教授的發(fā)表有關CT的情況李國杰院士的發(fā)表有關CT的情況結(jié)論AtypicalconversationPerson:Whatdoyoudo?Me:Iamacomputerscienceprofessor.Person:IhaveaproblemwithmyPC,canyoufixit?Me:No,Idon’tthinkIcandothat.Person:YouwillnotfixmyPC?Me:IcannotfixmyPC,letaloneyours.Person:Thenwhatexactlydoyoudo?Me:Istudyalgorithms.Person:Oh,Iknowthat.Me:Really?Person:Yes!Ilearntlogarithmsinhighschool.AlgorithmsnotLogarithms!ALGORITHMAl-KhowarizmiWhatIsComputerScience?Letssolveaproblem!IncomputersciencewebuildAlgorithms…asequenceofsteps/instructionstosolveaproblemComputerScienceisaboutproblemsolvingNote:Hereweaskfor4volunteerstoactoutthepartsofthefarmer,thewolf,thesheepandthecarrot—identifiedbydifferenthats.Sometimesthechildrenneedalittlehelptosolvetheproblem.ProblemSolvingAfarmerhastogetasheep,acarrotandawolfovertherivertothegrassyfield.BUThecanonlytakeoneofthemwithhimatatime…BUTifleftalone,ProblemSolvingThewolfwilleatthesheepThesheepwilleatthecarrotComputerScientiststakethis...Andmakethis!周以真（JeannetteM.Wing）教授SheisthePresident'sProfessorofComputerScienceintheComputerScienceDepartmentatCarnegieMellonUniversity.SheistheAssistantDirectoroftheComputerandInformationScienceandEngineeringDirectorateattheNationalScienceFoundation.ShereceivedherS.B.andS.M.degreesinElectricalEngineeringandComputerSciencein1979andherPh.D.degreeinComputerSciencein1983,allfromtheMassachusettsInstituteofTechnology.From2004-2007,shewasHeadoftheComputerScienceDepartmentatCarnegieMellon.CurrentlyonleavefromCMU,Hergeneralresearchinterestsareintheareasofspecificationandverification,concurrentanddistributedsystems,programminglanguages,andsoftwareengineering.Hercurrentfocusisonthefoundationsoftrustworthycomputing.ProfessorWingisanAAASFellow,ACMFellow,andIEEEFellow.李國杰院士李國杰（1943.5-）男，湖南邵陽人。漢族，中國工程院院士，第三世界科學院院士。。1995年始任曙光公司董事長，2000年始任中國科學院計算技術研究所所長。2003年兼任中國科技大學計算機系系主任。1968年畢業(yè)于北京大學，1981年獲中國科學院工學碩士學位，1985年獲美國普渡大學博士學位。1985～1986年間在美國伊利諾依大學CSL實驗室工作。1987年回國工作于中國科學院計算技術研究所，1989年被聘為研究員。1990年被國家科委選聘為國家智能計算機研究開發(fā)中心主任?！癈omputationalThinking,”CACMViewpoint,March2006,pp.33-35被引用次數(shù)：255ComputationalThinking，講座，2007ComputationalThinking:TwoandaHalfYearsLater,講座，2008“Computationalthinkingandthinkingaboutcomputing”,TransactionsoftheRoyalSocietyA:2008被引用次數(shù)：9ComputationalThinking，講座，HeidelbergInstituteforTheoreticalStudies

Heidelberg,Germany8March2010NetworkingandInformationTechnology,報告，President’sCouncilofAdvisorsonScienceandTechnologyWashington,DCSeptember2,2010“ComputationalThinking,”CACMViewpoint,March2006,pp.33-35被引用次數(shù)：255

Whatiscomputationalthinking?SolvingproblemsDesigningsystemsUnderstandinghumanbehavior“Toreading,writing,andarithmetic,weshouldaddcomputationalthinkingtoeverychild’sanalyticalability.”計算思維計算思維是運用計算機科學的基礎概念進行問題求解，系統(tǒng)設計，以及人類行為理解的涵蓋了計算機科學之廣度的一系列思維活動。WhatisComputationalThinking?

Asking:Whatisthepowerandlimitofhumanandcomputerintelligence?Asking:Howdifficultistheproblem?Asking:Howcanitbesolved?Asking:Howcantechnologybeappliedtotheproblem?Asking:Whatcomputationalstrategiesmightbeemployed?（1）人所固有的能力與局限性？計算機的計算能力與局限性？（2）問題到底有多復雜？也即，問題解決的時間復雜性？空間復雜性？（3）問題解決的判定條件是什么？（4）什么樣的技術（各種建模技術）能被應用于當前的問題求解或討論之中？（5）什么樣的計算策略更有利于當前問題的解決？Whatit’snot…It’snotjustmoretechnicaldetailsforusingsoftwareIt’snotthinkinglikeacomputerIt’snotprogramming(necessarily)Itdoesn’talwaysrequireacomputerIt’snotyetonemorethingtoaddtoyourcurriculumCharacteristics?

Conceptualizing,notprogrammingFundamental,notroteskillAwaythathumans,notcomputers,thinkComplementsandcombinesmathematicalandengineeringthinkingIdeas,notartifactsForeveryone,everywhereComputationalThinkingConceptsAlgorithm—thekingpintermData—variables,databases,QueueAbstraction—conceptualizing,modularizingQuery—search,conditionals,BooleanSensing&Feedback—roboticsIterations—loops,recursionSystemsDailyExamplesofCTStoringLegopiecesscatteredonthefloorHashing–byshapeorbycolorLearninglongdivision,factoringAlgorithmsMovingFixingmysprinklertimerSimpleDailyExamplesLookingupanameinanalphabeticallysortedlistLinear:startatthetopBinarysearch:startinthemiddleStandinginlineatabank,supermarket,customs&immigrationPerformanceanalysisoftaskschedulingPuttingthingsinyourchild’sknapsackforthedayPre-fetchingandcachingTakingyourkidstosoccer,gymnastics,andswimpracticeTravelingsalesman(withmoreconstraints)CookingagourmetmealParallelprocessing:Youdon’twantthemeattogetcoldwhileyou’recookingthevegetables.CleaningoutyourgarageKeepingonlywhatyouneedvs.throwingoutstuffwhenyourunoutofspace.Storingawayyourchild’sLegopiecesscatteredontheLRfloorUsinghashing(e.g.,byshape,bycolor)Doinglaundry,gettingfoodatabuffetPipeliningthewash,dry,andironstages;plates,salad,entrée,dessertstationsEveningradeschool,welearnalgorithms(longdivision,factoring,GCD,…)andabstractdatatypes(sets,tables,…).CTappliedCOMPUTATIONALTHINKING*

SATURDAYPLENARYSESSION

JeannetteWing,CarnegieMellonUniversityABSTRACTMyvisionforthe21stCentury:Computationalthinkingwillbeafundamentalskillusedbyeveryoneintheworld.Justasreading,writing,andarithmeticarefundamentalskillseverychildlearns,computationalthinkingisaskillneededforeverycitizentofunctionintoday’sglobalsociety.Computationalthinkingisanapproachtosolvingproblems,buildingsystems,andunderstandinghumanbehaviorthatdrawsonthepowerandlimitsofcomputing.Computationalthinkingistheuseofabstractiontotacklecomplexityandtheuseofautomationtotacklescale.Thecombinationoftheautomationofabstractionunderliestheenormouscapabilityandreachofcomputing.InthistalkIwillarguethatcomputationalthinkinghasalreadybeguntoinfluencemanydisciplines,fromthesciencestothehumanities,butthatthebestisyettocome.Lookingtothefuture,wecananticipateevenmoreprofoundimpactofcomputationalthinkingonscience,technology,andsociety:onthewaysnewdiscoverieswillbemade,innovationwilloccur,andcultureswillevolve.Teachingcomputationalthinkingalsoraisesnewchallengesforeducation,especiallyinearlygrades.Whilewehavemodelsforteachingchildrenmathematicsandphysics,wedonotyethavesuchmodelsforteachingcomputationalthinking.Moreover,wehavetheuniqueopportunitytomakemosteffectiveuseofthecomputerasatooltoenhancethelearningofcomputationalthinking.Inthistalk,Iwillgiveexamplesofcomputationalthinking,includingonesfromourdailylives.Itisexcitingtoimaginethedaywhencomputationalthinkingwillbecommonplace.ComputationalThinking:

TwoandaHalfYearsLaterJeannetteM.WingPresident’sProfessorofComputerScience

CarnegieMellonUniversity

and

AssistantDirector

ComputerandInformationScienceandEngineeringDirectorate

NationalScienceFoundation

2008JeannetteM.WingOutlineComputationalThinkingAVisionforourFieldTheTwoA’stoCTResearchandEducationImplicationsTwoandaHalfYearsLater…ExternalResponseandImpactRealityCheckPre-KtoGreyK-6,7-9,10-12UndergraduatecoursesFreshmenyear“WaystoThinkLikeaComputerScientist”akaPrinciplesofComputingUpper-levelcoursesGraduate-levelcoursesComputationalartsandsciencesE.g.,entertainmenttechnology,computationallinguistics,…,computationalfinance,…,computationalbiology,computationalastrophysicsPost-graduateExecutiveandcontinuingeducation,seniorcitizensTeachers,notjuststudentsQuestionandChallengetoCommunityWhatareeffectivewaysoflearning(teaching)

computationalthinkingby(to)children?

-Whatconceptscanstudentsbestlearnwhen?Whatshouldweteachwhen?

WhatisouranalogytonumbersinK,algebrain7,andcalculusin12?

-WeuniquelyalsoshouldaskhowbesttointegrateTheComputer

withlearningandteachingtheconcepts.QuestionsWhatarethefundamentalconceptsofCT?Elemental?Whatwouldbeaneffectiveorderingoftheseconcepts?HowbestshouldweintegrateTheComputerwithteachingtheconcepts?Long-termviewAnalogyWhatphysicsdidforitselfdecadesago.Whatmathdidandcontinuestodoperiodically.It’sNOTjustcurriculumdesign.Howdochildrenlearnwhatwhen?Short-termagenda(suggestion)Workshop1Identifyconcepts/principles/skillsCommunityinputWorkshop2Proposeoneormoremodelsof“sequencing”theconceptsProposeastrategyforincorporatingitinanearlygradeorK-12curriculm.Nextsteps?Inparallel,workwithortrackothereffortsandorganizations.CollegesandUniversitiesareRevisitingCurriculaCarnegieMellon:TomCortina’s15-105MIT:JohnGuttag’s6.00(forfreshmen)GeorgiaTech:UG:“Threads”,MarkGuzdial,“LearningComputingwithRobots,”TuckerBalchandDeepakKumar(BrynMawr)Grad:AlexanderGrayandNickFeamsterColumbia:AlAhoPrinceton:PICASso,fornon-CSgraduatestudentsHarvard:AlyssaGoodman,InstituteforInnovativeComputingNorthwestern:CenterforConnectedLearningandComputer-BasedModeling…Villanova,Haverford,BrynMawr,Georgetown,…UWisconsin-LaCrosse,…CarnegieMellon:TomCortina’s15-105

ComputationalThinkingandThinkingAboutComputingJeannetteM.WingAssistantDirector

ComputerandInformationScienceandEngineeringDirectorate

NationalScienceFoundationandPresident’sProfessorofComputerScience

CarnegieMellonUniversityPhilosophicalSocietyofWashington

10October2008OutlineComputationalThinkingAVisionforourFieldThinkingaboutComputingDriversofourField5DeepQuestionsinComputingThinkingAboutComputing55CT&TCDriversofComputingScienceSocietyTechnology56CT&TCMoore’sLawEndingNanoQuantum“EconomicalFabricationofQuantumDot-ElectronicsUsingBiofunctionalizedProteinNanotubesasBuildingBlocks,”Matsui,CUNY,NSFCCFCAREERaward(2002-07).Bio-Nano-QuantumBioCredit:Credit:OxfordUniversityCredit:Tainano,Inc.57CT&TCMoreTechnologyTrendsDevicesInformation1.8zettabytes=1,800,000,000,000,000,000,000bytesCommunicationCredit:Nature58CT&TCDriversofComputingScienceSocietyTechnology59CT&TCSocietalTrendsDiversityinClassesHighExpectations24/7,100%,anyone,anything,anytime,anywhereDiversityinNumbers60CT&TCDriversofComputingScienceSocietyTechnologyWhatiscomputable?P=NP?Whatisintelligence?Whatisinformation?(How)canwebuildcomplex

systemssimply?61CT&TC5DeepQuestionsinComputingP=NP?Whatiscomputable?Whatisintelligence?Whatisinformation?(How)canwebuildcomplexsystemssimply?62CT&TCThe$1MQuestion:DoesP=NP?Themostimportantopenproblemintheoreticalcomputerscience.TheClayInstituteofmathematicsoffersonemilliondollarprizeforsolution!PNP-completeNPP=NP=NP-completeIfP

NPIfP=NPBooleansatisfiability(SAT)N-puzzleKnapsackHamiltoniancycleTravelingsalesmanSubgraphisomorphismSubsetsumCliqueVertexcoverIndependentsetGraphcoloring

63CT&TCWhatisComputable?Whatarethepowerandlimitsofcomputation?Whatisacomputer?

Whatisthepowerofcomputing,bymachineandhumantogether?NotjustaPCanymore:TheInternet,serverfarms,supercomputers,multi-cores,…,nano,bio,quantum,etc.Credit:Tainano,Inc.64CT&TCWhatisIntelligence?invariantrepresentations:OnIntelligence,

byJeffHawkins,creatorofPalmPilotandTreo“ComputingVersusHumanThinking,”PeterNaur,TuringAward2005Lecture,CACM,January2007.HumanandMachine65CT&TCWhatisInformation?FromnatureIt’snotjust0’sand1’sQubits“Biologyisaninformationscience.”Geologytoo.Molecules/chemicalsare

processorsofinformation(computer),

carriersofinformation(storage),and

channelsofinformation(communication)…ToknowledgeWearedrowningindata.

Dataisdirt;knowledgeisgold.Credit:OxfordUniversityCredit:EarthScopeCredit:ArindamBandyopadhyay66CT&TC(How)CanWeBuildComplexSystemsSimply?

Wehavecomplexityclassesfromtheory.Webuildcomplexsystemsthatdoamazing,butoftenunpredictable,things.Question:Isthereameaningofsystemcomplexity

thatspansthetheoryandpracticeofcomputing?Question:Dooursystemshavetobesocomplex?Canwebuildsystemswithsimpledesigns,thatareeasytounderstand,modify,andmaintain,yetprovidetherichcomplexityinfunctionalityofsystemsthatweenjoytoday?Question:Isthereacomplexitytheoryforsystemsasthereisforalgorithms?Credit:MarshallClemensTwoMessagesfortheGeneralPublicIntellectuallychallengingandengagingscientificproblemsincomputerscienceremaintobeunderstoodandsolved.LimitedonlybyourcuriosityandcreativityOnecanmajorincomputerscienceanddoanything.JustlikeEnglish,politicalscience,ormathematicsComputationalThinkingJeannetteM.WingAssistantDirector

ComputerandInformationScienceandEngineeringDirectorate

NationalScienceFoundationandPresident’sProfessorofComputerScience

CarnegieMellonUniversityHeidelbergInstituteforTheoreticalStudies

Heidelberg,Germany

8March2010MyGrandVisionComputationalthinkingwillbeafundamentalskillusedbyeveryoneintheworldbythemiddleofthe21stCentury.Justlikereading,writing,andarithmetic.Incestuous:Computingandcomputerswillenablethespreadofcomputationalthinking.Inresearch:scientists,engineers,…,historians,artistsIneducation:K-12studentsandteachers,undergrads,…J.M.Wing,“ComputationalThinking,”CACMViewpoint,March2006,pp.33-35.Paperoff/AutomationAbstractionsComputingistheAutomationofAbstractionsComputationalThinkingfocusesontheprocessofabstraction

-choosingtherightabstractions

-operatingintermsofmultiplelayersofabstractionsimultaneously

-definingtherelationshipsthebetweenlayersasinMathematicsMeasuresofa“Good”AbstractioninC.T.EfficiencyHowfast?Howmuchspace?Howmuchpower?CorrectnessDoesitdotherightthing?Doestheprogramcomputetherightanswer?Doesitdoanything?Doestheprogrameventuallyproduceananswer?[HaltingProblem]-ilitiesSimplicityandeleganceUsabilityModifiabilityMaintainabilityCost…asinEngineeringNEWComputationalThinking,PhilosophicallyComplementsandcombinesmathematicalandengineeringthinkingC.T.drawsonmathasitsfoundationsButweareconstrainedbythephysicsoftheunderlyingmachineC.T.drawsonengineeringsinceoursystemsinteractwiththerealworldButwecanbuildvirtualworldsunconstrainedbyphysicalrealityIdeas,notartifactsIt’snotjustthesoftwareandhardwarethattouchourdailylives,itwillbethecomputationalconceptsweusetoapproachliving.It’sforeveryone,everywhereSampleClassesofComputationalAbstractionsAlgorithmsE.g.,mergesort,binarysearch,stringmatching,clusteringDataStructuresE.g.,sequences,trees,graphs,networksStateMachinesE.g.,finiteautomata,TuringmachinesLanguagesE.g.,regularexpressions,…,VDM,Z,…,ML,Haskell,…,Java,PerlLogicsandsemanticsE.g.,Hoaretriples,temporallogic,modallogics,lambdacalculusHeuristicsE.g.,A*(best-firstgraphsearch),cachingControlStructuresParallel/sequentialcomposition,iteration,recursionCommunicationE.g.,synchronous/asynchronous,broadcast/P2P,RPC,sharedmemory/message-passingArchitecturesE.g.,layered,hierarchical,pipeline,blackboard,feedbackloop,client-server,parallel,distributed…NOTComputerliteracy,i.e.,howtouseWordandExcelorevenGoogleComputerprogramming,i.e.,beyondJavaProgramming101OneDiscipline,ManyComputationalMethodsComputationalThinkinginBiologyShotgunalgorithmexpeditessequencing

ofhumangenomeDNAsequencesarestringsinalanguageBooleannetworksapproximatedynamics

ofbiologicalnetworksCellsasaself-regulatorysystemarelikeelectroniccircuitsProcesscalculimodelinteractionsamongmoleculesStatechartsusedindevelopmentalgeneticsProteinkineticscanbemodeledascomputationalprocessesRobotAdamdiscoversroleof12genesinyeastPageRankalgorithminspiresecologicalfoodwebCredit:WikipediaModelCheckingPrimerFiniteStateMachinemodelMTemporalLogic

property

FF=

AGpAFp,EGp,EFpM’scomputationaltreeModelCheckerF

isfalsifiedhere.counterexampleyesModelCheckingProblemLetM

beafinitestatemachine.Let

beaspecificationintemporallogic.Findallstatess

of

Msuchthat:M,s

Efficientalgorithms:[CE81,CES86,Ku94,QS81,VW94]Efficientdatastructures:binarydecisiondiagrams[Br86]ModelCheckinginBiologyModelcheckingcanexplorestatespacesaslargeas276

1023,

14ordersofmagnitudegreaterthan

comparabletechniques[LJ07].

1.FiniteStateMachineM

represents3-residueprotein1’.BDD

efficientlyrepresentsM2.TemporalLogicFormula

a.Willtheproteinendupina

particularconfiguration?

b.Willthesecondresiduefold

beforethefirstone?

c.Willtheproteinfoldwithintms?

d.Whatistheprobabilitythat(c)?Goal:PredictRateofFoldingofProteinsMethodeasilyhandlesproteinsupto76residues.e.Doesthestateshavekfolded

residuesandhaveenergyc?EnergyProFKBP-12,ComputedviaMethodOneComputationalMethod,ManyDisciplinesMachineLearninghastransformedthefieldofStatistics.80ComputationalThinkingMachineLearningintheSciencesCredit:LiveScience-fMRIdataanalysistounderstandlanguage

viamachinelearningNeurosciencesCredit:SDSS-Browndwarfsandfossilgalaxiesdiscovery

viamachinelearning,datamining,datafederation

-Verylargemulti-dimensionaldatasetsanalysis

usingKD-treesAstronomy-Anti-inflammatorydrugs

-Chronichepatitis

-Mammograms

-RenalandrespiratoryfailureMedicine-TornadoformationMeteorologyCredit:EricNguyen,OklahomaUniversity81ComputationalThinkingMachineLearningEverywhereSportsCreditCardsWallStreetSupermarketsEntertainment:

Shopping,Music,TravelCredit:WikipediaCredit:Wikipedia82ComputationalThinking83ComputationalThinkingComputationalThinkinginDailyLife84ComputationalThinkingGettingMorningCoffeeattheCafeteriacoffeesodasugar,

creamersnapkinscupslidsstraws,

stirrers,

milk85ComputationalThinkingGettingMorningCoffeeattheCafeteriaEspeciallyInefficientWithTwoorMorePersons…coffeesodasugar,

creamersnapkinscupslidsstraws,

stirrers,

milk86ComputationalThinkingBetter:ThinkComputationally—Pipelining!coffeesodasugar,

creamersnapkinscupslidsstraws,

stirrers,

milkNetworkingandInformationTechnologyJeannetteM.Wing

President’sProfessorofComputerScienceandDepartmentHeadCarnegieMellonUniversity

FormerAssistantDirectorforComputerandInformationScienceandEngineeringNationalScienceFoundation

ComputerSciencePresident’sCouncilofAdvisorsonScienceandTechnology

Washington,DC

September2,201088ComputingTechnology(R)Evolution193519462010EconomicImpactSocialImpactLayersofAbstractionv

BuPR(u)=PR(v)

L(v)

MapReduceGFS,BigTable,ChubbySearchServerFarmPageRankReliability,,OperatingSystems,ConsensusDistributedSystems,Networking,StorageSystemsProgrammingLanguages,

SoftwareEngineeringAlgorithms,DataStructuresNaturalLanguageProcessing,

TextandInformation

Retrieval,UserInterfacesElectronics,DigitalCircuits,SignalProcessingComputerArchitecture,ParallelComputing四、李國杰院士對計