Algorithms have emerged in past years as an object of public interest and debate. However, this term is used to name very different conceptions. The chapter presents the different definitions of the term “algorithm,” especially the traditional conception of algorithms as used in informatics and the novel conception of (intelligent) algorithms that have emerged in the last years. The main contribution of the chapter is the characterization of both types of algorithms in terms of the problems they are intended to solve. Furthermore, the chapter contributes by analyzing other uses of the word “algorithm” where it is an inadequate term. Finally, the chapter discusses misconceptions on algorithms present in other disciplines, which is an obstacle to mutual understanding and a source of mismatch between the disciplines.
TopBackground
The word “algorithm” seems to derive from the name of the ninth-century Persian mathematician al-Khwarizmi (Knuth, 1985), altered under the influence of the Greek word “arithmos” (i.e., number)2. However, the word has a long tradition, first in mathematics and later in informatics. Along the centuries, mathematicians have proposed different methods to solve mathematical problems, which are precise enough to be considered algorithms. Although algorithms can be traced back to the Babylonians (Knuth, 1972), the oldest algorithms with a name are Greek, e.g., the sieve of Eratosthenes or Euclid’s algorithm. In subsequent centuries, the mathematicians elaborated many algorithms, mainly calculation formulae (e.g., how to solve a second-order equation) and precise methods (e.g., Gauss-Seidel method to solve systems of linear equations).
However, it was with the advent of computers that algorithms were studied systematically. Furthermore, their scope was widened from mathematical problems to information processing problems, such as sorting the elements in a sequence. Some authors even consider that “computer science is primarily the study of algorithms” (Knuth, 1985). Moreover, the possibility of automatically applying the algorithms by means of computers gave rise to some concerns on algorithms that did not exist previously, mainly the analysis of their efficiency (in their use of time and space) and the theoretical issues of computability and tractability.
The high relevance of algorithms within informatics was early reflected on curricula. Thus, the Association for Computing Machinery (ACM) Curriculum 68 (Atchison et al., 1968) had a first course B1, “Introduction to computing”, with the following initial descriptor: “algorithms, programs, and computers”. About twenty years later, the ACM and the Computer Society of the Institute of Electrical and Electronics Engineers (IEEE-CS) joined forces to develop curricular recommendations. The Denning report (Denning et al., 1989) was the first tangible outcome of this collaboration, setting the bases for future recommendations. It identified nine subareas of informatics, being “algorithms and data structures” the first one. It is introduced in the following way: “This area deals with specific classes of problems and their efficient solutions. Fundamental questions include: For given classes of problems, what are the best algorithms? (…) How general are algorithms −i.e., what classes of problems can be dealt with by similar methods?” This relevant situation did not change in subsequent curricular recommendations for computer science (e.g., ACM & IEEE-CS, 2013).