Questions? Call 888-624-8373

PAPERBACK + PDF
your price: $41.00
add to cart

PAPERBACK
list:$35.00
Web:$31.50
add to cart

PDF BOOK
your price: $27.00
add to cart

PDF CHAPTERS
your price: $3.40
select

Rights & Permissions

topleft topright

Computer Science: Reflections on the Field, Reflections from the Field (2004)
Computer Science and Telecommunications Board (CSTB)

Page
I
bottomleft bottomright
  E-mail
 Facebook
 Digg
 Stumble
 Twitter
More

The following HTML text is provided to enhance online readability. Many aspects of typography translate only awkwardly to HTML. Please use the page image as the authoritative form to ensure accuracy.

Computer Science: Reflections on the Field, Reflections from the Field

Computer Science

Reflections on the Field, Reflections from the Field

Committee on the Fundamentals of Computer Science:Challenges and Opportunities

Computer Science and Telecommunications Board

NATIONAL RESEARCH COUNCIL OF THE NATIONAL ACADEMIES

THE NATIONAL ACADEMIES PRESS
Washington, D.C. www.nap.edu

 Page
I

Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.

OCR for page R1
Computer Science: Reflections on the Field, Reflections from the Field Computer Science Reflections on the Field, Reflections from the Field Committee on the Fundamentals of Computer Science:Challenges and Opportunities Computer Science and Telecommunications Board NATIONAL RESEARCH COUNCIL OF THE NATIONAL ACADEMIES THE NATIONAL ACADEMIES PRESS Washington, D.C. www.nap.edu

OCR for page R2
Computer Science: Reflections on the Field, Reflections from the Field THE NATIONAL ACADEMIES PRESS 500 Fifth Street, N.W. Washington, DC 20001 NOTICE: The project that is the subject of this report was approved by the Governing Board of the National Research Council, whose members are drawn from the councils of the National Academy of Sciences, the National Academy of Engineering, and the Institute of Medicine. The members of the committee responsible for the report were chosen for their special competences and with regard for appropriate balance. Support for this project was provided by the National Science Foundation under grant No. CCR-9981754. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsor. International Standard Book Number 0-309-09301-5 (Book) International Standard Book Number 0-309-54529-3 (PDF) Copies of this report are available from the National Academies Press, 500 Fifth Street, N.W., Lockbox 285, Washington, DC 20055; (800) 624-6242 or (202) 334-3313 in the Washington metropolitan area; Internet, http://www.nap.edu. Copyright 2004 by the National Academy of Sciences. All rights reserved. Printed in the United States of America

OCR for page R3
Computer Science: Reflections on the Field, Reflections from the Field THE NATIONAL ACADEMIES Advisers to the Nation on Science, Engineering, and Medicine The National Academy of Sciences is a private, nonprofit, self-perpetuating society of distinguished scholars engaged in scientific and engineering research, dedicated to the furtherance of science and technology and to their use for the general welfare. Upon the authority of the charter granted to it by the Congress in 1863, the Academy has a mandate that requires it to advise the federal government on scientific and technical matters. Dr. Bruce M. Alberts is president of the National Academy of Sciences. The National Academy of Engineering was established in 1964, under the charter of the National Academy of Sciences, as a parallel organization of outstanding engineers. It is autonomous in its administration and in the selection of its members, sharing with the National Academy of Sciences the responsibility for advising the federal government. The National Academy of Engineering also sponsors engineering programs aimed at meeting national needs, encourages education and research, and recognizes the superior achievements of engineers. Dr. Wm. A. Wulf is president of the National Academy of Engineering. The Institute of Medicine was established in 1970 by the National Academy of Sciences to secure the services of eminent members of appropriate professions in the examination of policy matters pertaining to the health of the public. The Institute acts under the responsibility given to the National Academy of Sciences by its congressional charter to be an adviser to the federal government and, upon its own initiative, to identify issues of medical care, research, and education. Dr. Harvey V. Fineberg is president of the Institute of Medicine. The National Research Council was organized by the National Academy of Sciences in 1916 to associate the broad community of science and technology with the Academy’s purposes of furthering knowledge and advising the federal government. Functioning in accordance with general policies determined by the Academy, the Council has become the principal operating agency of both the National Academy of Sciences and the National Academy of Engineering in providing services to the government, the public, and the scientific and engineering communities. The Council is administered jointly by both Academies and the Institute of Medicine. Dr. Bruce M. Alberts and Dr. Wm. A. Wulf are chair and vice chair, respectively, of the National Research Council. www.national-academies.org

OCR for page R4
Computer Science: Reflections on the Field, Reflections from the Field This page intentionally left blank.

OCR for page R5
Computer Science: Reflections on the Field, Reflections from the Field COMMITTEE ON THE FUNDAMENTALS OF COMPUTER SCIENCE: CHALLENGES AND OPPORTUNITIES MARY SHAW, Carnegie Mellon University, Chair ALFRED V. AHO, Columbia University CHARLES H. BENNETT, IBM Research ALAN BIERMANN, Duke University EDWARD W. FELTEN, Princeton University JAMES D. FOLEY, Georgia Institute of Technology MARK D. HILL, University of Wisconsin at Madison JON M. KLEINBERG, Cornell University DAPHNE KOLLER, Stanford University JAMES R. LARUS, Microsoft Research TOM M. MITCHELL, Carnegie Mellon University CHRISTOS H. PAPADIMITRIOU, University of California, Berkeley LARRY L. PETERSON, Princeton University MADHU SUDAN, Massachusetts Institute of Technology KEVIN J. SULLIVAN, University of Virginia JEFFREY D. ULLMAN, Stanford University and Gradience Corporation Staff JON EISENBERG, Senior Program Officer and Study Director LYNETTE I. MILLETT, Program Officer D.C. DRAKE, Senior Project Assistant (through November 2003)

OCR for page R6
Computer Science: Reflections on the Field, Reflections from the Field COMPUTER SCIENCE AND TELECOMMUNICATIONS BOARD DAVID LIDDLE, U.S. Venture Partners, Co-Chair JEANNETTE M. WING, Carnegie Mellon University, Co-Chair ERIC BENHAMOU, 3Com Corporation DAVID D. CLARK, Massachusetts Institute of Technology, CSTB Member Emeritus WILLIAM DALLY, Stanford University MARK E. DEAN, IBM Systems Group DEBORAH L. ESTRIN, University of California, Los Angeles JOAN FEIGENBAUM, Yale University HECTOR GARCIA-MOLINA, Stanford University KEVIN KAHN, Intel Corporation JAMES KAJIYA, Microsoft Corporation MICHAEL KATZ, University of California, Berkeley RANDY H. KATZ, University of California, Berkeley WENDY A. KELLOGG, IBM T.J. Watson Research Center SARA KIESLER, Carnegie Mellon University BUTLER W. LAMPSON, Microsoft Corporation, CSTB Member Emeritus TERESA H. MENG, Stanford University TOM M. MITCHELL, Carnegie Mellon University DANIEL PIKE, GCI Cable and Entertainment ERIC SCHMIDT, Google Inc. FRED B. SCHNEIDER, Cornell University WILLIAM STEAD, Vanderbilt University ANDREW J. VITERBI, Viterbi Group, LLC CHARLES BROWNSTEIN, Director KRISTEN BATCH, Research Associate JENNIFER M. BISHOP, Program Associate JANET BRISCOE, Administrative Officer JON EISENBERG, Senior Program Officer RENEE HAWKINS, Financial Associate MARGARET MARSH HUYNH, Senior Project Assistant HERBERT S. LIN, Senior Scientist LYNETTE I. MILLETT, Program Officer JANICE SABUDA, Senior Project Assistant BRANDYE WILLIAMS, Staff Assistant For more information on CSTB, see its Web site at <http://www.cstb.org>, write to CSTB, National Research Council, 500 Fifth Street, N.W., Washington, DC 20001, call at (202) 334-2605, or e-mail the CSTB at cstb@nas.edu.

OCR for page R7
Computer Science: Reflections on the Field, Reflections from the Field Preface The blossoming of computer science (CS) research is evident in the information technology that has migrated from a specialized tool confined to the laboratory or corporate back office to a ubiquitous presence in machines and devices that now figure in the lives of virtually every individual. This widespread diffusion of information technology can obscure the nature of computer science research underlying the IT—from the perspective of many outside the field, computer science is seen not as a basic area of systematic inquiry but as a tool to support other endeavors. Mindful of these issues, the National Science Foundation’s Computer and Information Science and Engineering Directorate asked the Computer Science and Telecommunications Board of the National Academies to conduct a study that would improve understanding of CS research among the scientific community at large, policymakers, and the general public. By describing in accessible form the field’s intellectual character and by conveying a sense of its vibrancy through a set of examples, the committee also aims to prepare readers for what the future might hold and inspire CS researchers to help create it. This volume, the product of that study, is divided into two parts that contain nine chapters. The volume’s prelude, “Emily Shops at VirtualEmporia.com,” takes a now-familiar use of computing—shopping online—and illustrates how CS research has made this seemingly simple activity possible.

OCR for page R8
Computer Science: Reflections on the Field, Reflections from the Field Part One—Chapter 1, “The Essential Character of Computer Science”—offers the committee’s concise characterization of CS research. Like CS researchers more generally, the committee members evince a wide range of perspectives that mirror the broad reach of computation into the very fabric of our intellectual and physical lives. Recognizing the richness and diversity of the field, the committee expressly decided not to provide either a comprehensive list of research topics or a taxonomy of research areas, nor to develop criteria for what research is inside and outside of CS. Instead, the committee’s approach is to describe some key ideas that lie at the core of CS but not to define boundaries. Part Two—Chapters 2 through 9—comprises two dozen essays written by committee members, participants in a June 6-7, 2001, symposium organized by the committee, and other invited authors. The essays describe several aspects of CS research and some of the results from the perspectives of their authors. By providing this diverse set of views on CS research, the committee aims to express some of the spark that motivates and excites CS researchers. The essays have a deliberately historical focus, for three reasons: (1) as described above, the committee decided not to present a research agenda, either explicit or implicit; (2) other publications look at current, hot topics in CS and these tend, in any case, to become dated quickly; and (3) results that have proven durable best illustrate the strengths of CS. The prelude and Part One are intended to be accessible to all readers (as are many of the essays). But because this report is also intended to reach scientists and engineers from a variety of disciplines, a few of the essays do presume some familiarity with some technical concepts. The committee would like to thank all of the participants in the June 2001 symposium; presentations and informal discussions at that event provided important input to the committee. Julie Sussman, PPA, provided a number of helpful suggestions concerning the manuscript. The reviewers listed below provided many valuable suggestions for improvement. Mary Shaw, Chair Committee on the Fundamentals of Computer Science: Challenges and Opportunities

OCR for page R9
Computer Science: Reflections on the Field, Reflections from the Field Acknowledgment of Reviewers This report has been reviewed in draft form by individuals chosen for their diverse perspectives and technical expertise, in accordance with procedures approved by the National Research Council’s Report Review Committee. The purpose of this independent review is to provide candid and critical comments that will assist the institution in making its published report as sound as possible and to ensure that the report meets institutional standards for objectivity, evidence, and responsiveness to the study charge. The review comments and draft manuscript remain confidential to protect the integrity of the deliberative process. We wish to thank the following individuals for their review of this report: David D. Clark, Massachusetts Institute of Technology Robert L. Constable, Cornell University Ronald Fedkiw, Stanford University Joan Feigenbaum, Yale University Juris Hartmanis, Cornell University James Jay Horning, Intertrust Anna R. Karlin, University of Washington Richard Karp, University of California, Berkeley Wendy A. Kellogg, IBM Research Monica S. Lam, Stanford University Butler W. Lampson, Microsoft Research Fred B. Schneider, Cornell University Lynn Andrea Stein, Olin College

OCR for page R10
Computer Science: Reflections on the Field, Reflections from the Field Gerald Jay Sussman, Massachusetts Institute of Technology Thomas N. Theis, IBM T.J. Watson Research Center Jeanette M. Wing, Carnegie Mellon University Margaret H. Wright, New York University Although the reviewers listed above provided many constructive comments and suggestions, they were not asked to endorse the conclusions or recommendations nor did they see the final draft of the report before its release. The review of this report was overseen by Lawrence Snyder, University of Washington. Appointed by the National Research Council, he was responsible for making certain that an independent examination of this report was carried out in accordance with institutional procedures and that all review comments were carefully considered. Responsibility for the final content of this report rests entirely with the authoring committee and the institution.

OCR for page R11
Computer Science: Reflections on the Field, Reflections from the Field Contents PRELUDE EMILY SHOPS AT VIRTUALEMPORIA.COM   1 PART ONE THE ESSENTIAL CHARACTER OF COMPUTER SCIENCE   9 1   THE ESSENTIAL CHARACTER OF COMPUTER SCIENCE   11      What Is Computer Science?,   12      Salient Characteristics of Computer Science Research,   15      Computer Science Research Involves Symbols and Their Manipulation,   15      Computer Science Research Involves the Creation and Manipulation of Abstraction,   17      Computer Science Research Creates and Studies Algorithms,   19      Computer Science Research Creates Artificial Constructs, Notably Unlimited by Physical Laws,   19      Computer Science Research Exploits and Addresses Exponential Growth,   20      Computer Science Research Seeks the Fundamental Limits on What Can Be Computed,   21      Computer Science Research Often Focuses on the Complex, Analytic, Rational Action That Is Associated with Human Intelligence,   23

OCR for page R12
Computer Science: Reflections on the Field, Reflections from the Field PART TWO SELECTED PERSPECTIVES ON COMPUTER SCIENCE   25 2   EXPONENTIAL GROWTH, COMPUTABILITY, AND COMPLEXITY   27      Harnessing Moore’s Law, Mark D. Hill, University of Wisconsin, Madison   28      Computability and Complexity, Jon Kleinberg, Cornell University, and Christos Papadimitriou, University of California, Berkeley   37      Quantum Information Processing, Charles H. Bennett, IBM Research   51 3   SIMULATION   57      The Real Scientific Hero of 1953, Steven Strogatz, Cornell University   58      Making a Computational Splash, Ronald Fedkiw, Stanford University   61 4   ABSTRACTION, REPRESENTATION, AND NOTATIONS   65      Abstraction: Imposing Order on Complexity in Software Design, Mary Shaw, Carnegie Mellon University   66      Programming Languages and Computer Science, Alfred V. Aho, Columbia University, and James Larus, Microsoft Research   74 5   DATA, REPRESENTATION, AND INFORMATION   79      Database Systems: A Textbook Case of Research Paying Off, Jim Gray, Microsoft Research   80      Computer Science Is to Information as Chemistry Is to Matter, Michael Lesk, Rutgers University   88      History and the Fundamentals of Computer Science, Edward L. Ayers, University of Virginia   96 6   ACHIEVING INTELLIGENCE   101      The Experiment-Analyze-Generalize Loop in Computer Science Research: A Case Study, Tom Mitchell, Carnegie Mellon University   103      “I’m Sorry Dave, I’m Afraid I Can’t Do That”: Linguistics, Statistics, and Natural-Language Processing Circa 2001, Lillian Lee, Cornell University   111

OCR for page R13
Computer Science: Reflections on the Field, Reflections from the Field      Computer Game Playing: Beating Humanity at Its Own Game, Daphne Koller, Stanford University, and Alan Biermann, Duke University   119 7   BUILDING COMPUTING SYSTEMS OF PRACTICAL SCALE   127      The Internet: An Experiment That Escaped from the Lab, Larry Peterson, Princeton University, and David Clark, Massachusetts Institute of Technology   129      Many-to-Many Communication: A New Medium, Amy Bruckman, Georgia Institute of Technology   134      Cryptography, Madhu Sudan, Massachusetts Institute of Technology   144      Strategies for Software Engineering Research, Mary Shaw, Carnegie Mellon University   151 8   RESEARCH BEHIND EVERYDAY COMPUTATION   159      How You Got Microsoft Word, Jeffrey Ullman, Stanford University and Gradience Corporation   161      VisiCalc, Spreadsheets, and Programming for the Masses, Or “How a Killer App Was Born,” James D. Foley, Georgia Institute of Technology   167      Internet Searching, Peter Norvig, Google Inc.   174 9   PERSONAL STATEMENTS OF PASSION ABOUT COMPUTER SCIENCE RESEARCH   179      The Legacy of Computer Science, Gerald Jay Sussman, Massachusetts Institute of Technology   180      Fairy Tales, Allen Newell, Carnegie Mellon University   184      Revisiting “What Is Computer Science,” Allen Newell, Carnegie Mellon University   189 APPENDIX Agenda of July 25-26, 2001, Symposium   193

OCR for page R14
Computer Science: Reflections on the Field, Reflections from the Field This page intentionally left blank.