The Science of Algorithms

Conditions such as limited data storage capabilities and intricate, time-consuming programming procedures restricted the complexity of the algorithms utilized in early computing machines. However, as these limitations began to disappear, machines were applied to increasingly larger and more complex tasks. As attempts to express the composition of these tasks in algorithmic form began to tax the abilities of the human mind, more and more research efforts were directed toward the study of algorithms and the programming process. It was in this context that the theoretical work of mathematicians began to pay dividends. As a consequence of Gödel’s incompleteness theorem, mathematicians had already been investigating those questions regarding algorithmic processes that advancing technology was now raising. With that, the stage was set for the emergence of a new discipline known as computer science.

Today, computer science has established itself as the science of algorithms. The scope of this science is broad, drawing from such diverse subjects as mathematics, engineering, psychology, biology, business administration, and linguistics. Indeed, researchers in different branches of computer science may have very distinct definitions of the science. For example, a researcher in the field of computer architecture may focus on the task of miniaturizing circuitry and thus view computer science as the advancement and application of technology. But, a researcher in the field of database systems may see computer science as seeking ways to make information systems more useful. And, a researcher in the field of artificial intelligence may regard computer science as the study of intelligence and intelligent behavior. Thus, an introduction to computer science must include a variety of topics, which is a task that we will pursue in the following chapters. In each case, our goal will be to introduce the central ideas in the subject, the current topics of research, and some of the techniques being applied to advance knowledge in the area. With such a variety of topics, it is easy to lose track of the overall picture. We therefore pause to collect our thoughts by identifying some questions that

provide a focus for its study.

• Which problems can be solved by algorithmic processes?

• How can the discovery of algorithms be made easier?

• How can the techniques of representing and communicating algorithms

be improved?

• How can the characteristics of different algorithms be analyzed

and compared?

• How can algorithms be used to manipulate information?

• How can algorithms be applied to produce intelligent behavior?

• How does the application of algorithms affect society?

Note that the theme common to all these questions is the study of algorithms.

Abstraction

             The concept of abstraction so permeates the study of computer science and the design of computer systems that it behooves us to address it in this preliminary chapter. The term abstraction, as we are using it here, refers to the distinction between the external properties of an entity and the details of the entity’s internal composition. It is abstraction that allows us to ignore the internal details of a complex device such as a computer, automobile, or microwave oven and use it as a single, comprehensible unit. Moreover, it is by means of abstraction that such complex systems are designed and manufactured in the first place. Computers, automobiles, and microwave ovens are constructed from components, each of which is constructed from smaller components. Each component represents a level of abstraction at which the use of the component is isolated from the details of the component’s internal composition.

It is by applying abstraction, then, that we are able to construct, analyze, and manage large, complex computer systems, which would be overwhelming if viewed in their entirety at a detailed level. At each level of abstraction, we view the system in terms of components, called abstract tools, whose internal composition we ignore. This allows us to concentrate on how each component interacts with other components at the same level and how the collection as a whole forms a higher-level component. Thus we are able to comprehend the part of the system that is relevant to the task at hand rather than being lost in a sea of details.

We emphasize that abstraction is not limited to science and technology. It is an important simplification technique with which our society has created a lifestyle that would otherwise be impossible. Few of us understand how the various conveniences of daily life are actually implemented. We eat food and wear clothes that we cannot produce by ourselves. We use electrical devices and communication systems without understanding the underlying technology. We use the services of others without knowing the details of their professions. With each new advancement, a small part of society chooses to specialize in its implementation while the rest of us learn to use the results as abstract tools. In this manner, society’s warehouse of abstract tools expands, and society’s ability to progress increases.

Abstraction is a recurring theme in our study. We will learn that computing equipment is constructed in levels of abstract tools. We will also see that the development of large software systems is accomplished in a modular fashion in which each module is used as an abstract tool in larger modules. Moreover, abstraction plays an important role in the task of advancing computer science itself, allowing researchers to focus attention on particular areas within a complex field. In fact, the organization of this text reflects this characteristic of the science. Each chapter, which focuses on a particular area within the science, is often surprisingly independent of the others, yet together the chapters form a comprehensive overview of a vast field of study.