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.

2 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. 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?

3 [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.

4 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.

5 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. 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.

6 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.

7 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.

8 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. 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.

9 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?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.

10 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.