Algorithm: Difference between revisions

Revision as of 14:55, 10 April 2002

Revision as of 18:33, 10 April 2002

Line 1:

An '''algorithm''' is thea descriptionmethod of aor procedure tofor solvesolving a certain (mathematical) problem. Typically, an algorithm consistsis ofdescribed as a series of actions that have to be done plus an indication of whether and when they are to be repeated. One couldSome seepeople andefine ''algorithm'' asto aonly roughinclude formprocedures ofthat aeventually finish. Others define ''algorithm'' to also include procedures that run forever without stopping. Algorithms are often implemented as computer programprograms, but can also be implemented as circuits, or even performed directly by humans.

The word ''algorithm'' is a corruption of the word ''algorism'' which came from the name of [[al-Khwarizmi|Abu Ja'far Mohammed ibn Musa al-Khwarizmi]] (ca. 780 - ca. 850). He was the author of the book "''Kitab al-jabr w'al-muqabala''" (''Rules of Restoration and Reduction'') which introduced [[Algebra|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 eighteenth century. The word has nowadaysnow evolved to include all definite procedures for solving problems, including cooking :)

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 [[integer|integers]] A and B:

Line 9:

# Repeat steps 1 and 2 until A and B are equal, this number will then be the greatest common divisor of the original numbers.

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 [[graph theory|graphs]]. A [[graph exploration algorithm]] specifies rules for moving around a graph and is useful for such problems. Sometimes[[Probabilistic wealgorithm]]s are willing to tolerate a probabilitythose that themake proceduresome willchoices failrandomly. This is where [[probabilistic algorithm]]s come into play. Finally, [[parallel algorithm|parallel algorithms]] takes 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.

Line 30:

* [[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.

----

[[talk:Algorithm|/Talk]]