Algorithm: Difference between revisions

Revision as of 00:31, 8 October 2002

Revision as of 06:36, 8 October 2002

Line 1:

[[de:Algorithmus]][[eo:Algoritmo]][[fr:Algorithme]][[pl:Algorytm]][[nl:algoritme]]

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 program]]s but can also be implemented as [[electric circuit]]s or even performed directly by [[human]]s.

An example of an algorithm is this rule (or method or procedure) for alphabetizing a list of names by repeating the specified steps until the job is done:

* Step 1. Compare the first 2 names on the list:

** a. If the 1st one is alphabetically ahead of the 2nd one, go to step 2.

** b. If the 2nd one is alphabetically ahead of the 1st one, swap the two of them and then go to step 2.

* Step 2. Pretend the 2nd and 3rd names on the list are the 1st and 2nd ones, and repeat step 1.

This is a rule either a human being or a computer can use to alphabetize a list -- it's called a "[[Bubble sort|bubble sort]]," because the entries that belong at the top of the list eventually float up to the top, but it's not a very efficient way to get the job done. So it's not a particularly good algorithm to use, but it's a fair example of what an algorithm is.

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. [[845]]). 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 [[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.