Algorithms

views updated

Algorithms

The word "algorithm" comes from the name of the ninth-century Persian mathematician Mohammed al-Khowarizmi. He wrote a widely read book entitled Kitab al jabr w'al-muqabala (Rules of Restoration and Reduction ). This book describes many procedures for the manipulation of decimal numbers.

Today, the term algorithm is used to describe a wide variety of procedures from the sequence of steps executed for the manipulation of integers to the series of actions involved in searching databases and the Internet.

An algorithm can be described informally or with mathematical rigor. Informally, it might be described as a basic set of steps that must be performed to reach a predetermined result. For example, in grade school, students learn to multiply two integers by carrying out a repetitive sequence of activities. If they proceed carefully according to the directions, they will eventually compute the product.

According to the more rigorous definition of an algorithm, the sequence of steps that are carried out must have five important features: finiteness, definiteness, input, output, and effectiveness.

Finiteness means that an algorithm is guaranteed to terminate after a finite number of steps as long as the integers are finite in length. When multiplying two integers, for example, the rules of the procedure will cause one to reach a point where no other steps are possible. For large integers, this might take a long time.

Definiteness means that each step in the sequence is clear and unambiguous. A cake-baking algorithm, for example, usually fails in this regard. Different cooks may define a dash of salt in slightly different ways.

Input means that zero or more values are available to the algorithm before it begins execution. For example, multiplication of two integers begins with the two integers. Long division begins with the divisor and the dividend. Searching the Internet begins with a collection of web pages and addresses.

Output means that one or more quantities are the result of the algorithm's execution of the inputs. In the case of long division, the results are the quotient and remainder. In the case of an Internet search, the result might be a collection of web pages or addresses.

Effectiveness means that each of the steps of the algorithm must be completed in some finite length of time.

All general-purpose digital computers, both past and present, execute algorithms. The algorithm is as central to computer technology as recipes are to the functioning of a gourmet restaurant. Without recipes, whether written on paper or stored in the mind of the chef, nothing gets cooked. Without algorithms, the whole notion of general-purpose digital computers makes little sense and nothing gets computed.

It is difficult to imagine doing multiplication or other tasks without algorithms. For example, try multiplying 3 by 5. Now, without using a calculator, multiply 3,456 by 2,139 without executing a repetitive sequence of steps.

The person or machine executing an algorithm need not be aware of the explanation or mathematical proof of why the algorithm works. Useful computations can be performed mechanically without any understanding of why the sequence of steps is guaranteed to produce the correct result.

History of Algorithms

Algorithms are not new. One of the oldest algorithms known is that of Greek mathematician Euclid (fl. 300 b.c.e.). Euclid's algorithm was designed to compute the greatest common divisor of two positive integers. For example, the greatest common divisor of 40 and 24 is 8 because 8 is the largest integer that divides 40 and 24 evenly. The greatest common divisor of 34,512 and 2,341,200 can also be found by using the repetitive procedure that Euclid's algorithm provides.

In 1937 the British mathematician Alan Turing (1912–1954) wrote a very important paper that introduced a simple mathematical device. His intention, in part, was to provide a formal and rigorous definition of algorithm. This mathematical formalization allowed Turing to prove statements about the capabilities and limitations of algorithms. It turns out, for example, that there are well-defined problems that have no algorithmic solution. The theory of algorithms is still an active area of research.

Algorithm discovery, enhancement, and implementation play increasingly important roles in modern life. New algorithms (sometimes called search engines) are being developed to search the Internet in ways that will allow people to gain useful information from a large and broad collection of data. Hardware algorithms are being improved to speed up the rate of instruction execution in modern machines. Software engineers implement algorithms as computer programs, which are used in an ever-widening variety of devices from hand-held personal data assistants to Internet browsers.

see also Boolean Algebra; Design Tools; Procedural Languages; Programming.

Michael J. McCarthy