大学计算机基础大学计算机基础 (3).pdf
0Computational Thinking2Computational ThinkingJeannette M.WingMy Grand Vision Computational thinking will be a fundamental skill used by everyone in the world by the middle of the 21stCentury.Just like reading,writing,and arithmetic.Incestuous:Computing and computers will enable the spread of computational thinking.In research:scientists,engineers,historians,artists In education:K-12 students and teachers,undergrads,J.M.Wing,“Computational Thinking,”CACM Viewpoint,March 2006,pp.33-35.Paper off http:/www.cs.cmu.edu/wing/3Computational ThinkingJeannette M.WingAutomationAbstractionsComputing is the Automation of AbstractionsComputational Thinking focuses on the process of abstraction-choosing the right abstractions-operating in terms of multiple layers of abstraction simultaneously-defining the relationships the between layersas in Mathematicsguided by the following concerns1.Machine2.Human3.Network Machine+Human4Computational ThinkingJeannette M.WingMeasures of a“Good”Abstraction in C.T.Efficiency How fast?How much space?How much power?Correctness Does it do the right thing?Does the program compute the right answer?Does it do anything?Does the program eventually produce an answer?Halting Problem-ilities Simplicity and elegance Scalability Usability Modifiability Maintainability Cost as in EngineeringNEW5Computational ThinkingJeannette M.WingComputational Thinking,PhilosophicallyComplements and combines mathematical and engineering thinking C.T.draws on math as its foundations But we are constrained by the physics of the underlying machine C.T.draws on engineering since our systems interact with the real world But we can build virtual worlds unconstrained by physical realityIdeas,not artifacts Its not just the software and hardware that touch our daily lives,it will be the computational concepts we use to approach living.Its for everyone,everywhere6Computational ThinkingJeannette M.WingSample Classes of Computational AbstractionsAlgorithmsE.g.,mergesort,binary search,string matching,clusteringData StructuresE.g.,sequences,tables,trees,graphs,networksState MachinesE.g.,finite automata,Turing machinesLanguagesE.g.,regular expressions,VDM,Z,ML,Haskell,Java,PythonLogics and semanticsE.g.,Hoare triples,temporal logic,modal logics,lambda calculusHeuristicsE.g.,A*(best-first graph search),cachingControl StructuresParallel/sequential composition,iteration,recursionCommunicationE.g.,synchronous/asynchronous,broadcast/P2P,RPC,shared memory/message-passingArchitecturesE.g.,layered,hierarchical,pipeline,blackboard,feedback loop,client-server,parallel,distributed,fault-tolerantNOT Computer literacy,i.e.,how to use Word and Excel or even Google or Bing Computer programming,i.e.,beyond Java Programming 101In Summary Computational Thinking is the thought processes involved in formulating a problem and expressing its solution in a way that a computerhuman or machinecan effectively carry out.Computational Thinking is what comes before any computing technologythought of by a human,knowing full well the power of automation.7Computational ThinkingJeannette M.Wing8Computational ThinkingJeannette M.WingExamples of Computational Thinking in Other Disciplines9Computational ThinkingJeannette M.WingOne Discipline,Many Computational Methods10Computational ThinkingJeannette M.WingComputational Thinking in Biology Shotgun algorithm expedites sequencingof human genome Abstract interpretation in systems biology Model checking applied to arrhythmia,diabetes,pancreatic cancer DNA sequences are strings in a language Boolean networks approximate dynamicsof biological networks Cells as a self-regulatory system are like electronic circuits Process calculi model interactions among molecules Statecharts used in developmental genetics Protein kinetics can be modeled as computational processes Robot Adam discovers role of 12 genes in yeast PageRank algorithm inspires ecological food webInsight:Models and languages for expressing computational processes are good for expressing the dynamics of biological processes.11Computational ThinkingJeannette M.WingModel Checking PrimerModel CheckerFinite State Machine model MTemporal LogicpropertyFF Fis falsified here.counterexampleyesF=F=AG pAF p,EG p,EF p12Model Checking in Biology2.Temporal Logic Formula F Fa.Do diabetes risk factors influencethe risk of cancer or cancer prognosis?“Diabetic risk factors might not increase cancer risk in normal cells,but they will promote cell proliferation if the cell is in a precancerous or cancerous stage characterized by losses of the tumor-suppressor proteins ARF and INK4a.”b.What signaling components arecommon to both diabetes and cancer?c.The oscillations of NFB and thenegative feedback of P53-MDM have measured in many in vitro experiments,after the cells were stimulated by externalsignals.Do these phenomena exist incells subjected to diabetic risk factors?Gong,Zuliani,Clarke 2011Single-Cell Diabetes-Cancer Model1.State Machine Model 249states13Computational ThinkingJeannette M.WingOne Computational Method,Many DisciplinesMachine Learning has transformed the field of Statistics.14Computational ThinkingJeannette M.WingMachine Learning in the SciencesCredit:LiveScience-fMRI data analysis to understand languagevia machine learningNeurosciencesCredit:SDSS-Brown dwarfs and fossil galaxies discoveryvia machine learning,data mining,data federation-Very large multi-dimensional datasets analysisusing KD-treesAstronomy-Anti-inflammatory drugs-Chronic hepatitis-Mammograms-Renal and respiratory failureMedicine-Tornado formationMeteorology15Computational ThinkingJeannette M.WingMachine Learning EverywhereSportsCredit CardsWall StreetSupermarketsEntertainment:Shopping,Music,Travel16Computational ThinkingJeannette M.Wing17Computational ThinkingJeannette M.Wing?18Computational ThinkingJeannette M.Wing19Computational ThinkingJeannette M.WingAnswer:Yes,by Boosting Algorithms(e.g.,FS99)Question(Kearns):Can a Set of Weak Learners Create a Single Strong One?20Computational ThinkingJeannette M.Wing21Computational ThinkingJeannette M.Wing22Computational ThinkingJeannette M.Wing23Computational ThinkingJeannette M.Wing24Computational ThinkingJeannette M.Wing25Computational ThinkingJeannette M.Wing26Computational ThinkingJeannette M.Wing27Computational ThinkingJeannette M.WingComputational Thinking in the Sciences and Beyond28Computational ThinkingJeannette M.WingCT in Other Sciences-Atomistic calculations are used to explorechemical phenomena-Optimization and searching algorithmsidentify best chemicals for improvingreaction conditions to improve yieldsChemistryYork,Minnesota-Adiabatic quantum computing:How quickly is convergence?-Genetic algorithms discover laws of physics.Physics-Abstractions for Sky,Sea,Ice,Land,Life,People,etc.-Hierarchical,composable,modular,traceability,allowing multiple projectionsalong any dimension,data element,or query-Cornells NSF Expedition on Computational SustainabilityGeosciences29Computational ThinkingJeannette M.WingCT in Math and Engineering-Discovering E8 Lie Group:18 mathematicians,4 years and 77 hours ofsupercomputer time(200 billion numbers).Profound implications for physics(string theory)-Four-color theorem proofCredit:WikipediaCredit:WikipediaMathematics-Calculating higher order terms implies more precision,which implies reducing weight,waste,costs in fabricatio-Boeing 777 tested via computer simulation alone,not in a wind tunnel-Hybrid automata for modeling and analyzing cyber-physical systemsCredit:BoeingEngineering(electrical,civil,mechanical,aero&astro,)30Computational ThinkingJeannette M.WingLaw-Inventions discovered through automated search are patentable-Stanford CL approaches include AI,temporal logic,state machines,process algebras,Petri nets-POIROT Project on fraud investigation is creating a detailedontology of European law-Sherlock Project on crime scene investigationCT for Society-Automated mechanism design underlies electronic commerce,e.g.,ad placement,on-line auctions,kidney exchange-Internet marketplace requires revisiting Nash equilibria model-Use intractability for voting schemes to circumvent impossibility resultsEconomics-Algorithmic medicine-Software design principles and debugging applied to prescriptions of painkillers-ONC SHARP Program,NSF Smart Health and Wellness Program,NITRD Senior Steering Group on Health ITHealthcare31Computational ThinkingJeannette M.WingCT for Society-eHeritage Project,Microsoft Research Asia-Digital Forma Urbis Romae Project,Stanford-Cathedral Saint Pierre,Columbia-metaLAB,HarvardArchaeology-Crowd sourcing as a new way of getting news tips from sources-Algorithmic approach to validate credibility of sources-Digital Media and Learning Initiative,MacArthur FoundationJournalism-Digging into Data Challenge:What could you do with a million books?Natl Endowment for the Humanities(US),JISC(UK),SSHRC(Canada)-Music,English,Art,Design,Photography,Humanities32Computational ThinkingJeannette M.WingEducational Implications33Computational ThinkingJeannette M.WingPre-K to Grey K-6,7-9,10-12 Undergraduate courses Freshmen year“Ways to Think Like a Computer Scientist”aka Principles of Computing Upper-level courses Graduate-level courses Computational arts and sciences E.g.,entertainment technology,computational linguistics,computational finance,computational biology,computational astrophysics Post-graduate Executive and continuing education,senior citizens Teachers,not just students34Computational ThinkingJeannette M.WingEducation Implications for K-12What is an effective way of learning(teaching)computational thinking by(to)K-12?-What concepts can students(educators)best learn(teach)when?What is our analogy to numbers in K,algebra in 7,and calculus in 12?-We uniquely also should ask how best to integrate The Computerwith teaching the concepts.Question and Challenge for the Computing Community:Computer scientists are now working with educators and cognitive learning scientists toaddress these questions.35Computational ThinkingJeannette M.WingComputational Thinking in Daily Life37Computational ThinkingJeannette M.WingGetting Morning Coffee at the NSF Cafeteriacoffee soda sugar,creamersnapkinscupslidsstraws,stirrers,milk38Computational ThinkingJeannette M.WingGetting Morning Coffee at the NSF Cafeteriacoffee soda sugar,creamersnapkinscupslidsstraws,stirrers,milk39Computational ThinkingJeannette M.WingGetting Morning Coffee at the NSF CafeteriaEspecially Inefficient With Two or More Personscoffee soda sugar,creamersnapkinscupslidsstraws,stirrers,milk40Computational ThinkingJeannette M.WingBetter:Think ComputationallyPipelining!coffee soda sugar,creamersnapkinscupslidsstraws,stirrers,milkComputational Thinking at NSF42Computational ThinkingJeannette M.WingComputational Thinking for Scientists and EngineersFY08$48M,FY11 Budget Request$100M43Computational ThinkingJeannette M.WingRange of Disciplines in CDI Awards in Inaugural Year(FY08)Aerospace engineeringAstrophysics and cosmologyAtmospheric sciencesBiochemistryBiomaterialsBiophysicsChemical engineeringCivil engineeringCommunications science and engineeringComputer scienceCosmologyEcosystemsGenomicsGeosciencesLinguisticsMaterials engineeringMathematicsMechanical engineeringMolecular biologyNanocomputingNeuroscienceProteomicsRoboticsSocial sciencesStatisticsStatistical physicsSustainability advances via Computational Thinking44Computational ThinkingJeannette M.Wing“to develop competencies in computational thinking”Computational Thinkingin EducationCMU and Other Colleges and Universities CMU:Redesign of Intro Courses“15-110:Principles of Computer Science.An introduction to computer science,based on the principles of computational thinking.Many taking this course will be nonmajors,but we will also use it as the entry point for any entering student with limited programming experience.”Bryant,Stehlik,Sutner,Introductory Computer Science Education at Carnegie Mellon University:A Deans Perspective,CMU-CS-10-140,August 2010Examples:Brown,Bryn Mawr,Colorado State University,Columbia,Eastern Michigan University,Georgetown,Georgia Tech,Harvard,Haverford,Harvey Mudd,Kent State,MIT,Northwestern,Princeton,Rochester Institute of Technology,St Josephs U,U of Alabama-Birmingham,U of Florida,UNC-Charlotte,U of Puerto Rico,UTexas-Arlington,University of Waterloo,U of Wisconsin-La Crosse,Vanderbilt,Villanova,William&Mary,46Computational ThinkingJeannette M.WingIndustry Support47Jeannette M.Winghttp:/ of links to further web resources,including lesson plans for K-12 teachers in science and mathematics.US National EffortsCSTB Reports:The Report of a Workshop on Pedagogical Aspects of Computational Thinking 2011Report of a Workshop on the Scope and Nature of Computational Thinking 2010CS Principles:http:/csprinciples.org-With NSF support,revision of CS AP coursesHigh SchoolComputer Science Education Act(H.R.5929)2010-proposed by PA Senator Casey and CO Representative Polis.Congresshttp:/www.csta.acm.org/-Computational Thinking Resource Set:A Problem-Solving Tool for Every Classrooom-K-12 Computer Science StandardsK-12International EffortsThe Computer Science and Informatics panel said“Computational thinking is influencing all disciplines.”United KingdomBritish Royal Society(2012):Shut down or restart?report“Computational thinking”offers insightful ways to view how information operates in many natural and engineered systems.3.Every child should have the opportunity to learn Computing at school.We believe that:Every child should be expected to be digitally literate by the end of compulsory education,in the same way that every child is expected to be able to read and write.IrelandNational University of Ireland MaynoothB.Sc.in Computational ThinkingUK Research Assessment(2009):International EffortsEuropeAsia“aims to deliver enrichment courses to pre-tertiary students to deepen their infocomm skills by supporting course fees for students to take up computer science courses anchored in computational thinking.”Latin Americahttp:/ East51Computational ThinkingJeannette M.WingComputational Thinking,International52Computational ThinkingJeannette M.WingSpread the Word Help make computational thinking commonplace!To fellow faculty,students,researchers,administrators,teachers,parents,principals,guidance counselors,school boards,teachers unions,congressmen,policy makers,53Thank you!Thank you!54Computational ThinkingJeannette M.WingReferences(Representative Only)Computational ThinkingUniversity of Edinburgh,http:/www.inf.ed.ac.uk/research/programmes/comp-think/Wing06 J.M.Wing,“Computational Thinking,”CACM Viewpoint,March 2006,pp.33-35,http:/www.cs.cmu.edu/wing/Model Checking,Temporal Logic,Binary Decisions DiagramsBr86 Randal Bryant,“Graph-Based Algorithms for Boolean Function Manipulation,”IEEE Trans.Computers,35(8):677-691(1986).CE81 E.M.Clarke and E.A.Emerson,“The Design and Synthesis of Synchronization Skeletons Using Temporal Logic,”Proceedings of the Workshop on Logics of Programs,IBM Watson Research Center,Yorkto
