Generally, an algorithm is a list of instructions for accomplishing some task, and the task can be anything that has a recognizable end-point (or result). Often some of the specific steps in the procedure are to be repeated until the task is done. A recipe is one kind of algorithm, and there can be different algorithms for accomplishing the same task: Some recipes for making potato salad, for example, have "peel the potato" before "boil the potato", while some have the "boil" step before the "peel" step (and others leave out the "peel" step entirely), but they all call for those steps to be repeated for however many potatoes there are, and they all end when the potato salad is ready to eat.
Algorithms are essential to the way computers process information, because a computer program is essentially an algorithm that tells the computer what specific steps to perform, in what specific order, to calculate the employees' paychecks or print the students' report cards. In that context, an algorithm is a well-defined method or procedure for solving a problem, usually a problem in mathematics or otherwise relating to the manipulation of information. Typically, an algorithm is described as a series of actions that have to be done plus an indication of whether and when they are to be repeated. Some people restrict the definition of algorithm to procedures that eventually finish, while others also include procedures that run forever without stopping. Algorithms are often implemented as computer programs but can also be implemented as electric circuits or even performed directly by humans.
As an example of an algorithm, here is one given to us by Euclid, and thus known as the Euclidean algorithm, for finding the greatest common divisor (GCD) of two positive integers A and B:
- Let A be the greater number of A and B, and B the lesser.
- Replace A by the difference A-B.
- Repeat steps 1 and 2 until A and B are equal, this number will then be the greatest common divisor of the original numbers.
The word algorithm is a corruption of the word algorism which came from the name of Abu Ja'far Mohammed ibn Musa al-Khwarizmi (ca. 780 - ca. 845). He was the author of the book Kitab al-jabr w'al-muqabala (Rules of Restoration and Reduction) which introduced algebra to people in the West. The word algebra itself originates from al-Jabr from the book title. The word algorism originally referred only to the rules of performing arithmetic using Arabic numerals but evolved into algorithm by the 18th century. The word has now evolved to include all definite procedures for solving problems and is sometimes used to describe procedures for humans doing physical tasks -- cooking, for instance. The remainder of this article relates to the definition of algorithm as advanced in this article's first sentence.
The lack of mathematical rigor in the "well-defined procedure" definition of algorithm posed some difficulties for mathematicians and logicians of the 19th and early 20th centuries. This problem was largely solved with the description of the Turing machine, an abstract model of a computer described by Alan Turing, and the demonstration that every method yet found for describing "well-defined procedures" advanced by other mathematicians could be emulated on a Turing machine (a statement known as the Church-Turing thesis). Nowadays, a formal criterion for an algorithm is that it is a procedure implementable on a completely-specified Turing machine or one of the equivalent formalisms.
Algorithms come in different flavours. A greedy algorithm works by making a series of simple decisions that are never reconsidered. A divide-and-conquer algorithm recursively reduces an instance of a problem to one or more smaller instances of the same problem, until the instances are small enough. A dynamic programming algorithm works bottom-up by building progressively larger solutions to subproblems arising from the original problem, and then uses those solutions to obtain the final result. Many problems (such as playing chess) can be modeled as problems on graphs. A graph exploration algorithm specifies rules for moving around a graph and is useful for such problems. Probabilistic algorithms are those that make some choices randomly. Finally, parallel algorithms take advantage of the availability of multiple processors to speed up the solution process.
Usually one is not only concerned with how to perform the work but also wishes to know how much of particular resources (such as time or storage) will be needed. Methods have been developed for the analysis of algorithms to obtain such quantitative answers.
A list of algorithms discussed in Wikipedia is available.
Related topics:
References
- Donald E Knuth: The Art of Computer Programming, Vol 1-3, Addison Wesley 1998. The standard reference.
- Gaston H. Gonnet and Ricardo Baeza-Yates: Example programs from Handbook of Algorithms and Data Structures, http://www.dcc.uchile.cl/~rbaeza/handbook/. Free source code for lots of important algorithms.