Computational Thinking

1 0 Computational ThinkingJeannette M. WingPresident s Professor of Computer Science and Department HeadComputer Science DepartmentCarnegie Mellon UniversityMicrosoft Asia Faculty Summit26 October 2012 Tianjin, China2 Computational ThinkingJeannette M. WingMy Grand Vision Computational thinkingwill 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, .. Wing, Computational Thinking , CACMV iewpoint, March 2006, pp. off ~wing/ 3 Computational ThinkingJeannette M. WingAutomationAbstractionsComputing is the Automation of AbstractionsComputational Thinkingfocuses 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 Machine2.

2 Human3. Network [Machine + Human]4 Computational ThinkingJeannette M. WingMeasures of a Good Abstraction in 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 EngineeringNEW5 Computational ThinkingJeannette M. WingComputational Thinking , Philosophically Complements and combines mathematical and engineering Thinking draws on math as its foundations But we are constrained by the physics of the underlying machine draws on engineering since our systems interact with the real world But we can build virtual worlds unconstrained by physical reality Ideas, not artifacts It s not just the software and hardware that touch our daily lives, it will be the Computational concepts we use to approach living.

3 It s for everyone, everywhere6 Computational ThinkingJeannette M. WingSample Classes of Computational Abstractions Algorithms , mergesort, binary search, string matching, clustering Data Structures , sequences, tables, trees, graphs, networks State Machines , finite automata, Turing machines Languages , regular expressions, .., VDM, Z, .., ML, Haskell, .., Java, Python Logics and semantics , Hoare triples, temporal logic, modal logics, lambda calculus Heuristics , A* (best-first graph search), caching Control Structures Parallel/sequential composition, iteration, recursion Communication , synchronous/asynchronous, broadcast/P2P, RPC, shared memory/message-passing Architectures , layered, hierarchical, pipeline, blackboard, feedback loop, client-server, parallel, distributed, fault-tolerant ..NOT Computer literacy, , how to use Word and Excel or even Google or Bing Computer programming, , 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 computer human or machine can effectively carry out.

4 Computational Thinking is what comes before any computing technology thought of by a human, knowing full well the power of ThinkingJeannette M. Wing8 Computational ThinkingJeannette M. WingExamples of Computational Thinking in Other Disciplines9 Computational ThinkingJeannette M. WingOne Discipline, Many Computational Methods10 Computational ThinkingJeannette M. WingComputational Thinking in Biology Shotgun algorithmexpedites sequencingof human genome Abstract interpretation in systems biology Model checking applied to arrhythmia,diabetes, pancreatic cancer DNA sequences are strings in a language Boolean networksapproximate dynamicsof biological networks Cells as a self-regulatory system are like electronic circuits Process calculimodel interactions among molecules Statechartsused in developmental genetics Protein kinetics can be modeled as Computational processes Robot Adam discovers role of 12 genes in yeast PageRank algorithminspires ecological food webInsight: Models and languages for expressing Computational processes are good for expressing the dynamics of biological ThinkingJeannette M.

5 WingModel Checking PrimerModel CheckerFiniteState Machine model MTemporal LogicpropertyFFis falsified =AG pAF p, EG p, EF p12 Model Checking in Biology2. Temporal Logic Formula 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 NF B 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 2011]Single-Cell Diabetes-Cancer Model1. State Machine Model 249states13 Computational ThinkingJeannette M.

6 WingOne Computational Method,Many DisciplinesMachine Learning has transformed the field of 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 formationMeteorology15 Computational ThinkingJeannette M. WingMachine Learning EverywhereSportsCredit CardsWall StreetSupermarketsEntertainment:Shopping , Music, Travel16 Computational ThinkingJeannette M. Wing17 Computational ThinkingJeannette M. Wing?18 Computational ThinkingJeannette M. Wing19 Computational ThinkingJeannette M. WingAnswer: Yes, by BoostingAlgorithms ( , [FS99])Question (Kearns): Can a Set of Weak Learners Create a Single Strong One?

7 20 Computational ThinkingJeannette M. Wing21 Computational ThinkingJeannette M. Wing22 Computational ThinkingJeannette M. Wing23 Computational ThinkingJeannette M. Wing24 Computational ThinkingJeannette M. Wing25 Computational ThinkingJeannette M. Wing26 Computational ThinkingJeannette M. Wing27 Computational ThinkingJeannette M. WingComputational Thinking in the Sciences and Beyond28 Computational ThinkingJeannette M. WingCT in Other Sciences-Atomistic calculations are used to explorechemical phenomena-Optimization and searching algorithmsidentify best chemicals for improvingreaction conditions to improve yieldsChemistry[York, Minnesota]-Adiabatic quantum computing: How quickly is convergence?-Genetic algorithms discover laws of for Sky, Sea, Ice, Land, Life, People, , composable, modular,traceability, allowing multiple projectionsalong any dimension, data element, or query-Cornell s NSF Expedition on Computational SustainabilityGeosciences29 Computational ThinkingJeannette M.

8 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,..)30 Computational 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, , 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 ITHealthcare31 Computational ThinkingJeannette M.

9 WingCT for Society-eHeritageProject, 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?Nat l Endowment for the Humanities (US),JISC (UK), SSHRC (Canada)-Music, English, Art, Design, Photography, ..Humanities32 Computational ThinkingJeannette M. WingEducational Implications33 Computational 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 , entertainment technology, Computational linguistics.

10 , Computational finance, .., Computational biology, Computational astrophysics Post-graduate Executive and continuing education, senior citizens Teachers, not just students34 Computational ThinkingJeannette M. WingEducation Implications for K-12 What 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 and Challenge for the Computing Community:Computer scientists are now working with educators and cognitive learning scientists toaddress these ThinkingJeannette M. WingComputational Thinking in Daily Life37 Computational ThinkingJeannette M. WingGetting Morning Coffee at the NSF Cafeteriacoffee soda sugar,creamersnapkinscupslidsstraws,stir rers,milk38 Computational ThinkingJeannette M.