Information Technology Reference
In-Depth Information
CHAPTER
The Role of Theory in
Computer Science
Computer science is the study of computers and programs, the collections of instructions that
direct the activity of computers. Although computers are made of simple elements, the tasks
they perform are often very complex. The great disparity between the simplicity of computers
and the complexity of computational tasks offers intellectual challenges of the highest order. It
is the models and methods of analysis developed by computer science to meet these challenges
that are the subject of theoretical computer science.
Computer scientists have developed models for machines, such as the random-access and
Turing machines; for languages, such as regular and context-free languages; for programs, such
as straight-line and branching programs; and for systems of programs, such as compilers and
operating systems. Models have also been developed for data structures, such as heaps, and for
databases, such as the relational and object-oriented databases.
Methodsofanalysishavebeendevelopedtostudy the efficiency of algorithms and their
data structures, the expressibility of languages and the capacity of computer architectures to
recognize them, the classification of problems by the time and space required to solve them,
their inherent complexity, and limits that hold simultaneously on computational resources for
particular problems. This topic examines each of these topics in detail except for the first,
analysis of algorithms and data structures, which it covers only briefly.
This chapter provides an overview of the topic. Except for the mathematical preliminaries,
thetopicsintroducedherearerevisitedlater.
3
Search WWH ::
Custom Search