|
An algorithm (pronounced AL-go-rith-um) is a set of precise (i.e., unambiguous) rules that specify how to solve some problem or perform some task. Properties of algorithms generally include: input/output (i.e., receives input and generates output), precision (each step is precisely stated), determinism (the intermediate results of each step of execution are unique and are determined only by inputs and results of the previous step), termination (ends after a finite number of instructions execute), correctness (the output generated is correct) and generality (each algorithm applies to a set of inputs). Multiple, alternative algorithms can (and frequently do) exist for solving a specific problem. However, they will generally differ with regard to the resources (e.g., computer processor time and memory space) that they require. Correctly performing an algorithm might or might not solve a specified problem if the algorithm is flawed or not appropriate to the problem. The extent to which it can solve a problem depends on such factors as the degree of flaw or inappropriateness, the desired level of efficiency of the algorithm and the availability of alternatives. There are two main, closely related tasks in study of algorithms: designing an algorithm to solve a specific problem and analyzing a given algorithm. The design of algorithms is a creative task that requires not only the solution of new problems but also frequently the solution of old problems in new guises. Although it may seem dull to the layman, many people who have experience developing algorithms consider the field to be not only fun but even exciting. Historical Background The word algorithm is a distortion of the name of the Persian mathematician Mohammed ibn-Musa al-Khwarizmi, who lived from approximately 780 to 850 a.d. and who wrote an influential book about algebra. The automated weaving loom, which was invented in 1801 by Joseph Jacquard, was one of the earliest machines to perform tasks controlled by algorithms. The patterns formed in the fabric were determined by cards with holes punched in them that controlled the selection of threads (which differed in color, material, etc.). The first algorithm for a computer was written by Ada Byron in 1842 for Charles Babbage's analytical engine. Babbage, an English mathematician and philosopher, was the first person to propose the concept of a programmable computer. However, his mechanical device was never completed due to limitations on the technology available at that time, and thus the algorithm was never implemented on it. Byron (after whom the programming language Ada was named and whose father was the poet Lord Byron) wrote a set of notes which specified in detail a method for calculating Bernoulli numbers (one of the most interesting and important number sequences in mathematics) using Babbage's computer. Algorithms and Computers The study of algorithms, called algorithmics, is at the core of computer science. (However, algorithms are more than just a branch of computer science, and they are relevant to to most of science, technology and business.) Computer science is the study of the storage, transformation and transfer of information. The field extends all the way from the theoretical study of algorithms (including their design, efficiency and application) to the practical problems of implementing them in terms of computer hardware and software. Algorithms are essential to the way computers process information because a computer program is basically just an algorithm that tells computers what specific steps to perform, and in what sequence, in order to carry out a specified task. Algorithms are often studied abstractly (i.e., without the use of a specific programming language or other implementation). Thus, they resemble other fields of mathematics in that the analysis focuses on the underlying principles rather than on any specific implementation. The algorithms used in computational processes must be defined rigorously, that is, specified such that they apply to all possible situations that could occur. This includes a specifying of the computation steps, which is usually critical to the functioning of algorithms. Definitions of the term algorithm often require that the problem be solved in a finite number of steps. However, some algorithms include procedures that could run forever without terminating, although in such case it may be difficult to determine whether the algorithm successfully completes its task. Developers and users frequently want to know how much of specific resources (such as processor time and computer memory space) an algorithm will consume. Such information can be important for making decisions about which algorithms to use and about developing newer, more efficient (i.e., using less of some or all resources) algorithms. Various methods have been devised to obtain such information. Applications Algorithms have been developed to solve an extremely wide variety of problems. They range from something as seemingly simple as a recipe for creating some food to something as complex as landing a space vehicle on Mars. Other examples include (1) finding new, large prime numbers (a number that is not divisible by any other numbers except one and itself), (2) determining the fastest and or least expensive route for traffic from a particular source to a particular destination and (3) designing circuit patterns for microprocessors and other semiconductor chips. Some of the most common types of applications for algorithms used by computers are for (1) searching text, (2) sorting files or lines of text in alphabetic order, (3) compressing and decompressing data, (4) detecting errors in the transmission of data, (5) encrypting and decrypting data and (6) compiling (i.e., converting) source code, which is written by human in a programming language, into machine language so that it can be understood directly by computer processors. Although a number of algorithms are available for each of these applications, each has its advantages and disadvantages with regard to efficiency and other criteria. And there has been a ceaseless quest to develop new and more efficient algorithms for each of these and other applications. Classification Algorithms are typically classified according to their mode of internal operation. Although the internal operation can be difficult to comprehend for persons who have not studied algorithms intensively or have not had experience developing them, it can still be useful to at least be familiar with their names and basic concepts. They include: (1) divide-and-conquer: recursively reduce an instance of a problem to one or more smaller instances of the same problem until the instances are small enough to be directly expressible in the programming language employed. (2) dynamic progressive: construct progressively larger solutions to subproblems arising from the original problem and then use those solutions to obtain the final result. All subproblems that might potentially be needed are solved and stored in a table so that they do not need to be solved more than once. (3) genetic and evolutionary: mimic biological evolutionary processes such as mutation, natural selection, and recombination in order to find an optimal configuration for a specific system within specific constraints. (4) graph exploration: specify rules for moving around a graph (e.g., a chessboard). (5) greedy: make a series of simple decisions that are never reconsidered. A greedy algorithm builds a solution to a problem in steps, and a part of the solution is added in each iteration. (6) heuristic: find an approximate solution in situations in which the time or other resources to find a perfect solution are not practical. (7) parallel: run on a network of processors rather than a single processor in order to speed up computation tasks. (8) probabilistic: make some choices randomly (or pseudo-randomly). (9) recursive: invoke (i.e., make reference to) itself repeatedly until a predefined condition is obtained. Pseudocode Algorithms can be expressed in a variety of ways. Very simple algorithms can be stated using ordinary sentences in any human language. These and more complex algorithms can be shown schematically with flow charts. Programming languages and pseudocode can be used to express even highly complex algorithms. Pseudocode is a technique for describing a computer program by using more general wording rather than use the specific syntax and keywords of a programming language. This makes it is easier to understand the general workings of programs not only for non-programmers but also for programmers who are not familiar with a specific programming language. Pseudocode styles vary according to the author, and thus such code usually contains an introduction explaining the syntax used. Common applications for pseudocode include developing programs for later coding by programmers in specific programming languages and explaining concepts in computer text books. Pseudocode has the advantages over ordinary human language for specifying algorithms of precision, structure and generality. It derives its name from the fact that it resembles the source code of widely used programming languages such as C and Java. It is easier to write with pseudocode than with source code because it is only necessary that instructions are not ambiguous. Unlike source code, it is not necessary to be concerned about keywords, case (i.e, lower case and upper case) and details of punctuation. Algorithms can be incorporated into various types of media. They include the human memory, human-readable text written or printed on paper and computer programs that are stored on punched cards, magnetic tape, computer disks and semiconductor chips. Created July 29, 2005. |