Communications - August 2008 - Research Highlights (Page 21)

al recognition of being the language for computation. We help people find representations for real-world things and then prove things about their representations. In computer science we have invented new mathematics for analyzing algorithms. We explained why a binary search is so much faster than a linear search, and why a bubble sort is so much slower than a merge sort. We figured out how to parse programming languages efficiently, making the jobs of programmers so much easier. Our tools help programmers prove that their complicated programs actually work, meaning that users can sleep at night knowing that their airplanes won’t crash and their business software won’t ruin them. Our biggest triumph has been to show that over 3,000 common problems in science, engineering, and business are so difficult to solve that even the fastest supercomputers would take centuries on simple versions. We call this the P=NP issue. Whoever proves that P=NP would win all the math prizes and the ACM Turing Award. And no, proving P=NP does not boil down to proving N= 1.

the engineer

I love building things. My math friends like picturing things in their minds; I like holding things in my hands and putting them through their paces. You tell me what you want, what budget I have, and how much time I have, and I’ll find a way to build a computing system that does it. I don’t need everything to be figured out mathematically before I can start. I built your operating systems, your networks, your TCP and IP, your air traffic control system,

your banking systems, your game engines, and your search engines. I built your memory chips, your CPUs, your stacks, your graphics displays, your warehouse computers, your BlackBer-ries, and your iPods. I know how to make software and hardware artifacts reliable, dependable, usable, safe, and secure. I love the smells of solder, motherboards, routers, power supplies, and musty cable racks. Sometimes I even think I can smell rotting bugs in software. I’m so good at doing things faster, cheaper, and better that I keep on giving you Moore’s Law year after year.

the scientist

I love discovering new things about nature. Recently my friends in biology have discovered that DNA transcription is a natural information process. What an amazing discovery. Computation is not an artifact of a computer, it’s part of life! My friends in physics, economics, materials, chemistry, meteorology, oceanography, and cosmology are all making similar discoveries. What a great time for collaborations on new discoveries about those natural processes. But that’s not all I do. I discovered scientific principles for computing. My scientific analysis guided the design of the first electronic computers. My principle of locality helped us achieve high performance through caching in everything from chips to the Internet. I discovered fast algorithms for throughput and response time of large systems and networks, launching the performance evaluation industry. I brought the experimental method to architecture, program per-

formance improvement, large system design, mathematical software, modeling, and simulation. My greatest triumph in the CS realm has been with artificial intelligence. Now that they have accepted my methods, they are making remarkable advances with machines that mimic human intelligent behavior.

the Last Voice: the catalog Students begin by learning the use of computer programming as a problem-solving tool. Topics in procedural programming include expressions, control structures, simple data types, input-output, graphical interfaces, testing, debugging, and programming environments. The student then advances to problem solving with object-oriented programming. Topics include classes, inheritance, packages, collections, exceptions, polymorphism, and recursive thinking. A good deal of time will be spent on programming projects.

References

1. Denning, P. Who are we? Commun. ACM 44, 2 (Feb.

2001), 15–19.

2. Denning, P. The field of programmers myth. Commun.

ACM 47, 7 (July 2004), 15–20.

3. Denning, P. Recentering computer science. Commun.

ACM 48, 11 (Nov. 2005), 15–19.

4. Denning, P. et al. Computing as a discipline. Commun.

ACM 32, 1 (Jan. 1989), 9–23.

5. Dijkstra, E. The humble programmer. Commun. ACM 15, 10 (Oct. 1972), 859–866.

6. Shirky, C. Here Comes Everybody. Penguin, 2008.

7. Snyder, L. Fluency with Information Technology. Addison-Wesley, 2002.

8. Wing, J. Computational thinking. Commun. ACM 49, 3 (Mar. 2006), 33–35.

Peter J. Denning ( pjd@nps.edu) is the director of the Cebrowski Institute for Information Innovation and Superiority at the Naval Postgraduate School in Monterey, CA, and is a past president of ACM.