Computational thinking and Problem solving

Computational Thinking and Thinking About Computing and introduction to computational thinking and data science pdf free download
DavidCooper Profile Pic
Published Date:11-07-2017
Your Website URL(Optional)
Computational Thinking and Thinking About Computing Jeannette M. Wing President’s Professor of Computer Science Carnegie Mellon University © 2008 Jeannette M. WingMy Grand Vision for the Field • Computational thinking will be a fundamental skill used by everyone in the world by the middle of the st 21 Century. – Just like reading, writing, and arithmetic. – Imagine every child knowing how to think like a computer scientist – 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 CISE AC website; paper and talks off CT&TC 4 Jeannette M. WingExamples of Computational Thinking • How difficult is this problem and how best can I solve it? – Theoretical computer science gives precise meaning to these and related questions and their answers. • C.T. is thinking recursively. • C.T. is reformulating a seemingly difficult problem into one which we know how to solve. – Reduction, embedding, transformation, simulation • C.T. is choosing an appropriate representation or modeling the relevant aspects of a problem to make it tractable. • C.T. is interpreting code as data and data as code. • C.T. is using abstraction and decomposition in tackling a large complex task. • C.T. is judging a system’s design for its simplicity and elegance. • C.T. is type checking, as a generalization of dimensional analysis. • C.T. is prevention, detection, and recovery from worst-case scenarios through redundancy, damage containment, and error correction. • C.T. is modularizing something in anticipation of multiple users and prefetching and caching in anticipation of future use. • C.T. is calling gridlock deadlock and avoiding race conditions when synchronizing meetings. • C.T. is using the difficulty of solving hard AI problems to foil computing agents. • C.T. is taking an approach to solving problems, designing systems, and understanding human behavior that draws on concepts fundamental to computer science. Please tell me your favorite examples of computational thinking CT&TC 5 Jeannette M. WingSimple Daily Examples • Looking up a name in an alphabetically sorted list – Linear: start at the top – Binary search: start in the middle • Standing in line at a bank, supermarket, customs & immigration – Performance analysis of task scheduling • Putting things in your child’s knapsack for the day – Pre-fetching and caching • Taking your kids to soccer, gymnastics, and swim practice – Traveling salesman (with more constraints) • Cooking a gourmet meal – Parallel processing: You don’t want the meat to get cold while you’re cooking the vegetables. • Cleaning out your garage – Keeping only what you need vs. throwing out stuff when you run out of space. • Storing away your child’s Lego pieces scattered on the LR floor – Using hashing (e.g., by shape, by color) • Doing laundry, getting food at a buffet – Pipelining the wash, dry, and iron stages; plates, salad, entrée, dessert stations • Even in grade school, we learn algorithms (long division, factoring, GCD, …) and abstract data types (sets, tables, …). CT&TC 6 Jeannette M. WingThe First A to Computational Thinking • Abstractions are our “mental” tools • The abstraction process includes – Choosing the right abstractions – Operating simultaneously at multiple layers of abstraction – Defining the relationships the between layers CT&TC 7 Jeannette M. WingThe Second A to Computational Thinking • The power of our “mental” tools is amplified by our “metal” tools. •Automation is mechanizing our abstractions, abstraction layers, and their relationships – Mechanization is possible due to precise and exacting notations and models – There is some “computer” below (human or machine, virtual or physical) CT&TC 8 Jeannette M. WingTwo A’s to C.T. Combined • Computing is the automation of our abstractions – They give us the audacity and ability to scale. • Computational thinking – choosing the right abstractions, etc. – choosing the right “computer” for the task CT&TC 9 Jeannette M. WingCT in Other Sciences, Math, and Engineering Biology - Shotgun algorithm expedites sequencing of human genome - DNA sequences are strings in a language - Protein structures can be modeled as knots - Protein kinetics can be modeled as computational processes - Cells as a self-regulatory system are like electronic circuits Brain Science - Modeling the brain as a computer - Vision as a feedback loop - Analyzing fMRI data with machine learning CT&TC 11 Jeannette M. WingCT in Other Sciences, Math, and Engineering Chemistry Madden, Fellow of Royal Society of Edinburgh - Atomistic calculations are used to explore chemical phenomena - Optimization and searching algorithms identify best chemicals for improving reaction conditions to improve yields York, Minnesota Geology - Modeling the earth’s surface to the sun, from the inner core to the surface - Abstraction boundaries and hierarchies of complexity model the earth and our atmosphere CT&TC 12 Jeannette M. WingCT in Other Sciences, Math, and Engineering Astronomy - Sloan Digital Sky Server brings a telescope to every child - KD-trees help astronomers analyze very large multi-dimensional datasets Mathematics - Discovering E8 Lie Group: 18 mathematicians, 4 years and 77 hours of supercomputer time (200 billion numbers). Profound implications for physics (string theory) - Four-color theorem proof Engineering (electrical, civil,mechanical, aero&astro, …) - Calculating higher order terms implies more precision, which implies reducing weight, waste, costs in fabrication - Boeing 777 tested via computer simulation alone, not in a wind tunnel CT&TC 13 Jeannette M. WingCT for Society Economics - Automated mechanism design underlies electronic commerce, e.g., ad placement, on-line auctions, kidney exchange - MIT PhDs in CS are quants on Wall Street Social Sciences - Social networks explain phenomena such as MySpace, YouTube - Statistical machine learning is used for recommendation and reputation services, e.g., Netflix, affinity card CT&TC 14 Jeannette M. WingCT for Society Medicine - Robotic surgery - Electronic health records require privacy technologies - Scientific visualization enables virtual colonoscopy Law - Stanford CL approaches include AI, temporal logic, state machines, process algebras, petri nets - POIROT Project on fraud investigation is creating a detailed ontology of European law - Sherlock Project on crime scene investigation CT&TC 15 Jeannette M. WingCT for Society Entertainment -Games -Movies - Dreamworks uses HP data center to renderShrek and Madagascar - Lucas Films uses 2000-node data center to produce Pirates of the Caribbean. Arts - Art (e.g., Robotticelli) -Drama Sports -Music - Lance Armstrong’s cycling -Photography computer tracks man and machine statistics - Synergy Sports analyzes digital videos NBA games CT&TC 16 Jeannette 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 students CT&TC 18 Jeannette M. WingQuestion and Challenge to Community What are effective ways of learning (teaching) computational thinking by (to) children? -What concepts can students best learn when? What should we 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 Computer with learning and teaching the concepts. CT&TC 19 Jeannette M. WingRecursion: Towers of Hanoi Goal: Transfer the entire tower to one of the other pegs, moving only one disk at a time and never a larger one onto a smaller. CT&TC 20 Jeannette M. WingData Abstraction and Representation stack queue tree (upside down) representation invariant array and pointer CT&TC 21 Jeannette M. WingComposition and Decomposition CT&TC 22 Jeannette M. WingSorting and Search CT&TC 23 Jeannette M. WingIntractability: Traveling Salesman Problem: A traveling salesperson needs to visit n cities. Is there a route of at most d in length? O(n) n = 16 → 242 days n = 25 → 5x1015 centuries CT&TC 24 Jeannette M. Wing

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.