Computational Thinking
Jeannette Wing
Assistant Director
Computer and Information Science and Engineering Directorate
National Science Foundation
About the Lecture
The author’s vision for the 21st Century: Computational thinking will be a fundamental skill used by everyone in the world. To reading, writing, and arithmetic, we should add computational thinking to every child’s analytical ability. Computational thinking involves solving problems, designing systems, and understanding human behavior by drawing on the concepts fundamental to computer science. Thinking like a computer scientist means more than being able to program a computer. It requires thinking at multiple levels of abstraction. This talk will give many examples of computational thinking, argue that it has already influenced other disciplines, and promote the idea that teaching computational thinking can inspire future generations to enter the field of computer science.
About the Speaker
JEANNETTE M. WING is the Assistant Director of the Computer and Information Science and Engineering Directorate at the National Science Foundation. She is on leave from her position as President’s Professor of Computer Science in the Computer Science Department at Carnegie Mellon University. From 2004 to 2007, she was Head of the Computer Science Department at Carnegie Mellon. Her general research interests are in the areas of specification and verification, concurrent and distributed systems, and programming languages. Her current focus is on the foundations of trustworthy computing. She has served on the editorial board of eleven journals. She has been a member of many advisory boards, including: the Networking and Information Technology (NITRD) Technical Advisory Group to the President’s Council of Advisors on Science and Technology (PCAST), the National Academies of Science’s Computer Science and Telecommunications Board, ACM Council, the DARPA Information Science and Technology (ISAT) Board, NSF’s CISE Advisory Committee, Microsoft’s Trustworthy Computing Academic Advisory Board, and the Intel Research Pittsburgh’s Advisory Board. She is a member of the Sloan Research Fellowships Program Committee. She is a member of AAAS, ACM, IEEE, Sigma Xi, Phi Beta Kappa, Tau Beta Pi, and Eta Kappa Nu. She is an AAAS Fellow, ACM Fellow, and IEEE Fellow. She received her S.B. and S.M. degrees in Electrical Engineering and Computer Science in 1979 and her Ph.D. degree in Computer Science in 1983, all from the Massachusetts Institute of Technology.
Minutes
President Kenneth Haapala called the 2,242nd meeting to order at 8:16 pm October 10, 2008 in the Powell Auditorium of the Cosmos Club. The minutes of the 2,241st meeting were read and approved despite.
Mr. Haapala then introduced the speaker of the evening, Jeannette Wing, currently at the National Science Foundation on leave from Carnegie Mellon University. Ms. Wing spoke on “Computational Thinking.”
Ms. Wing said her grand vision for the future is that computational thinking will be a fundamental skill used by everyone in the world by the middle of the 21st century. Just like reading, writing, and arithmetic, every child will do it. It will be incestuous; computers and computing will enable the spread of computational thinking.
She gave a large number of examples of characteristics of computational thinking. They were:
asking how difficult a problem is and how best it can be solved
thinking recursively
reformulating difficult problems into solvable ones
choosing an appropriate representation or modeling relevant aspects of a problem to make it tractable
interpreting code as data and data as code
using abstraction and decomposition in tackling a large complex task
judging a system’s design for its simplicity and elegance
type checking, as a generalization of dimensional analysis
prevention, detection, and recovery from worst-case scenarios through redundancy, damage containment, and error correction
modularizing something in anticipation of multiple users and prefetching and caching in anticipation of future use.
calling gridlock deadlock and avoiding race conditions when synchronizing meetings
using the difficulty of solving hard AI problems to foil computing agents
taking an approach to solving problems, designing systems, and understanding human behavior that draws on concepts fundamental to computer science
Fundamental to computational thinking are abstraction and automation. Abstractions are our “mental” tools. The process involves choosing the right abstractions, operating at multiple layers of abstraction, and defining relationships between the layers. Automation is mechanizing our abstractions, abstraction layers, and their relationships. Computing is the automation of our abstractions and computational thinking involves choosing the right abstractions and choosing the right computer for the task.
Computational thinking in sciences, mathematics, and engineering has accomplished surprising things. For example, the Sloan Digital Sky Server brings a telescope to every child and the four-color theorem was proven. The Boeing 777 was tested by computer simulation, not in a wind tunnel. In medicine, robotic surgery has become possible. Computers have become very useful in games. Movies like “Shrek” and “Pirates of the Caribbean” depend heavily on computational thinking.
Ms. Wing discussed five deep questions in computing. They are:
Does P = NP?
What is computable?
What is intelligence?
What is information?
Can we or How can we build complex systems simply?
The first, does P = NP, she said, is the most important open problem in theoretical computer science. A prize of $1 million is offered for its solution. Unfortunately, your recording secretary does not understand the question and cannot explain it to you. [Wikipedia]
What is computable, she said, involves further questions. What are the power and limits of computation? Computing is done not by a single computer any more. There are the internet, server farms, and supercomputers. There is unknown potential in computing by humans and machines working together.
What is intelligence remains to be resolved. How the definition of intelligence might be affected by computers and computational thinking is also open.
What is information is another open question. Ms. Wing is sure now that it isn’t just 0's and 1's; qubits have entered the picture. She reflected briefly on the difference between data and knowledge, saying “Data is dirt; knowledge is gold.”
About can we or how we can build complex systems simply, she asks if there is a complexity theory for systems as there is for algorithms. Is there a meaning of system complexity that applies to computing? Do our systems have to be so complex?
She concluded with two propositions. Intellectually challenging and engaging scientific problems in computer science remain to be understood and solved. The limits are our curiosity and creativity. Second, one can major in computer science and do anything, just like English, political science, or mathematics.
In the question period, she clarified the idea of thinking like a computer scientist. Just as we hope every child has mathematical ability, she hopes every child will have computational thinking skills. They will know the difference between a random and an efficient approach to a problem. She advocates the recognition and use of the deeper abstractions, no so much the sheer computational power. She also sees value in encouraging people in other disciplines to use computational thinking.
To a question about quantum computing, she said it does raise questions we don’t have the answers to. Clearly we will be able to solve some questions more efficiently, but we don’t know what that class of problems is.
As an example of computational thinking, one person discussed the concept of light-years being used by 3rd graders. He wants them to think of light-years as the units rather than to translate light-years into miles.
A landscape designer discussed how he deals with concepts, in terms of abstractions such as line, form, color, and comfort. He said he didn’t know it, but guessed he’d been using computational thinking all along. Ms Wing agreed, with a smile.
There was a brief discussion of how lawyers think. It resulted in a rude remark which your recording secretary is too kind to repeat.
Someone asked about the prospects of coming up with an algorithm to decide what you are going to store. Ms. Wing expressed hope for the same thing. She said even Google is not very useful anymore. It translates all questions to keywords and retrieves all documents based on keywords.
The definition of algorithm came up. Ms. Wing said an algorithm is a step by step procedure of handling inputs and outputs that produces a particular goal.
Mr. Haapala thanked our speaker and presented to her a plaque commemorating the occasion.
Mr. Haapala introduced 14 new members. He announced formation of a committee on elections. He mentioned that the president-elect may not be able to assume the presidency.
He made the parking announcement.
He announced the next meeting, on the history of probability, a subject of which Mr. Haapala is fond. Sticks and bones, the St. Petersburg paradox, and expectations generally, warm his heart. Finally, at 9:36 pm, he adjourned the 2,242nd meeting to the social hour.
Attendance: 62
The weather: Cool and cloudy
The temperature: 12°C
Respectfully submitted,
Ronald O. Hietala,
Recording secretary