COMPUTING
Edited by E.G. Coffman, Jr., J.K. Lenstra and A.H.G. Rinnooy Kan
PREFACE
The origins of computing and operations research as modern scientific disciplines can both be traced back some 45 years. This is not entirely coincidental, since both may be looked upon as outcomes of the technological advances of the second world war. In spite of several notable exceptions, these disciplines developed largely along separate lines in the first 25 years of growth. To be sure, operations research has always been a principal computer user, but in this respect it differed little from other scientific disciplines and broad application areas in business and industry. It has only been in the last 20 years that the two disciplines have grown hand in hand, creating a permanent bond in academia and industry. Students in these fields soon learn, in overlapping courses of study, that many of the leading contributors in one field are equally well known for major contributions in the other.
Nowhere is the symbiotic relationship between operations research and computer science more evident than in the design and analysis of algorithms, often called algorithmics, which lies at the heart of both disciplines. Classical problems in operations research formed the basis of many of the fundamental algorithms used as prototypes in the theory of algorithms and complexity. The platform for this theory also consisted of mathematical tools in applied probability and combinatorics that were supplied by operations researchers. In their turn, computer scientists have discovered more efficient algorithms for operations research problems, quite often by introducing novel techniques for structuring information. Of equal importance to operations research has been the general methodology developed by computer scientists for the design and analysis of numerical and combinatorial algorithms, and for identifying the inherent complexity of computational problems. As a result, the study of algorithmics in this volume has become an essential part of optimization, the subject of Volume 1 of this series, and of the computations that accompany stochastic modeling, the subject of Volume 2 of this series.
The chapters in this volume can be grouped into three parts. We have already commented on the material of Part 11, which covers algorithmics. Chapters 6-9 break this subject down into matrix computations, fundamental algorithms and data structures, design and analysis of efficient algorithms, and computational complexity.
The study of algorithmics is preceded in Part 1 by an introductory course in the design and operation of computers and computer systems. Chapters 1-5 comprise a standard decomposition into computer hardware, programming languages, operating systems, databases, and software engineering. The reader might argue that much of this material is not essential to the computer user, any more than an understanding of internal combustion engines is needed by drivers of automobiles. Yet a knowledge of basic principles can prove very useful in appreciating the potential and limitations of computer systems, and in coping with unusual problems that arise in applications. Conveying this knowledge along with perspectives on the history and future of computers is the burden of Part 1.
Part 111 brings out the relation between computer systems and operations research applications. Chapter 10 reviews the use of stochastic models in computer system performance evaluation. In representing computer systems as case studies in operations research, it forms another link with Volume 2. Chapters 11 and 12 investigate the computer's role in the problem-solving process. Chapter 11 concerns one of the central methodologies of operations research: mathematical programming. During four decades of development, mathematical programming systems have matured greatly, thereby providing an active meeting ground for computer science and operations research. Chapter 12 studies user interfaces, i.e., the hardware, languages, and software packages designed to facilitate the interactive use of computers. The chapter discusses techniques for enhancing expressiveness in user-computer communication and for designing systems that help the user acquire insights into problem structures.
This volume was designed and written for use in the operations research and management science community. Apart from the background provided by Chapters 1-5, the emphasis is on the computational tools, algorithms, languages, and systems that assist the problem solver. This objective explains the selection of material and, in particular, the omission of material on the mathematical foundations of computing, e.g., the theories of automata, recursive functions, and formal languages. There are several other topics in computer science that have been omitted, either because they were not yet in vogue or because their impact on operations research was not yet significant when the book was designed. The most prominent example is the area of artificial intelligence, knowledge-based systems and computational learning. Another example is computational geometry; however, a chapter on this subject will be included in Volume 5 of this series.
We are pleased to express our gratitude to everyone who contributed to the realization of this volume. Many thanks are due to the authors, most of whom are willing to contribute to a handbook series which is only peripheral to their own area of interest. We are also grateful to Jan van Leeuwen, George Nemhauser and David Shmoys for their help and suggestions throughout the project, and to a number of other colleagues, who reviewed individual chapters and have to remain unnamed.
E.G. Coffinan, Jr.
J.K. Lenstra
A.H.G. Rinnooy Kan
Complete chapters on ScienceDirect
[Description and order information]
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company