Book contents
- Frontmatter
- Contents
- Preface
- Contributors
- 1 The Complexity of Algorithms
- 2 Building Novel Software: the Researcher and the Marketplace
- 3 Prospects for Artificial Intelligence
- 4 Structured Parallel Programming: Theory meets Practice
- 5 Computer Science and Mathematics
- 6 Paradigm Merger in Natural Language Processing
- 7 Large Databases and Knowledge Re-use
- 8 The Global-yet-Personal Information System
- 9 Algebra and Models
- 10 Real-time Computing
- 11 Evaluation of Software Dependability
- 12 Engineering Safety-Critical Systems
- 13 Semantic Ideas in Computing
- 14 Computers and Communications
- 15 Interactive Computing in Tomorrow's Computer Science
- 16 On the Importance of Being the Right Size
- References
- Index
1 - The Complexity of Algorithms
Published online by Cambridge University Press: 10 December 2009
- Frontmatter
- Contents
- Preface
- Contributors
- 1 The Complexity of Algorithms
- 2 Building Novel Software: the Researcher and the Marketplace
- 3 Prospects for Artificial Intelligence
- 4 Structured Parallel Programming: Theory meets Practice
- 5 Computer Science and Mathematics
- 6 Paradigm Merger in Natural Language Processing
- 7 Large Databases and Knowledge Re-use
- 8 The Global-yet-Personal Information System
- 9 Algebra and Models
- 10 Real-time Computing
- 11 Evaluation of Software Dependability
- 12 Engineering Safety-Critical Systems
- 13 Semantic Ideas in Computing
- 14 Computers and Communications
- 15 Interactive Computing in Tomorrow's Computer Science
- 16 On the Importance of Being the Right Size
- References
- Index
Summary
Abstract
The modern theory of algorithms dates from the late 1960s when the method of asymptotic execution time measurement began to be used. It is argued that the subject has both an engineering and a scientific wing. The engineering wing consists of well understood design methodologies while the scientific one is concerned with theoretical underpinnings. The key issues of both wings are surveyed. Finally some personal opinions on where the subject will go next are offered.
Introduction
The concept of ‘algorithm’ is the oldest one in computer science. It is of such antiquity in fact that it may appear presumptuous for computer scientists to claim it as part of their subject. However, although algorithms have been part of scientific tradition for millennia it was not until the computer era that they assumed the major role they now play in these traditions. Indeed, until a few decades ago most scientists would have been hard-pressed to give significant examples of any algorithms at all. Yet algorithms have been routinely used for centuries. Generations of school children learnt the algorithms for addition, subtraction, multiplication, and division and could use them with all the blinkered competence of a mechanical computer. Few of them would ever have stopped to wonder how it was that they allowed the computation, in a matter of moments, of quantities far beyond what could be counted or imagined. These elementary algorithms are amazingly efficient but it was not until the computer era that questions of efficiency were seriously addressed. Had they been so addressed the mathematical curriculum might have been different.
- Type
- Chapter
- Information
- Computing TomorrowFuture Research Directions in Computer Science, pp. 1 - 20Publisher: Cambridge University PressPrint publication year: 1996
- 1
- Cited by