# Algorithm

An algorithm is a formal operation composed of a sequence of more basic formal operations.

**AKA:**Computing Procedure.**Context:**- It must have one or more Algorithm Outputs.
- It can have zero or more Algorithm Inputs.
- It can have zero or more Tunable Parameters.
- It can make use of a Data Structure.
- It can be defined by an Algorithm Definition.
- It can be a member of an Algorithm Family.
- It can follow an Algorithm Strategy, such as a dynamic programming strategy.
- It can implemented by a Computational System (to solve a computational task.
- It can terminate after some finite number of Formal Operations.
- It can range from being a Computationally Expensive Algorithm to being a Computationally Inexpensive Algorithm.
- It can range from being a Memory Intensive Algorithm to being a Memory Unintensive Algorithm.
- It can range from being a Domain Specific Algorithm to being a General Purpose Algorithm (such as an optimization algorithm).
- It can range from being a Deterministic Algorithm (with deterministic operation transitions) to being a Randomized Algorithm.
- It can range from being an Offline Algorithm/Batch Algorithm to being an Online Algorithm.
- It can be a member of an Algorithm Family.
- It can be analyzed by:
- an Algorithm Empirical Analysis (Accuracy, Time, Disk Reads, ...)
- an Algorithm Complexity Analysis (Time Complexity, Space Complexity, etc.)

- It can be modeled by a Universal Turing Machine.
- It can be composed of algorithm components, such as an Algorithm Phase.
- …

**Example(s):**- The Blum Blum Shub Algorithm is a Random Number Generation Algorithm.
- The C4.5 Algorithm is a Decision Tree Learning Algorithm.
- The Quicksort Algorithm, a Sorting Algorithm.
- The Euclid's Algorithm.
- an NLP Algorithm, such as a Word Sense Disambiguation Algorithm or a Word Sense Disambiguation Algorithm.
- …

**Counter-Example(s):**- A Task, such as a Sorting Task, a Classification Task, or a Busy Beaver Task.
- A Computing System, such as Microsoft Excel, or Google Search Service.

**See:**Function, Algorithmic.

## References

- http://en.wikipedia.org/wiki/List_of_algorithms
- http://www.wikidata.org/wiki/Q8366
- procedure for calculation

### 2013

- (Wikipedia, 2013) ⇒ http://en.wikipedia.org/wiki/Algorithm
- In mathematics and computer science, an
**algorithm**( /ˈælɡərɪðəm/ Template:Respell) is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.An algorithm is an effective method expressed as a finite list

^{[1]}of well-defined instructions^{[2]}for calculating a function.^{[3]}Starting from an initial state and initial input (perhaps empty),^{[4]}the instructions describe a computation that, when executed, proceeds through a finite^{[5]}number of well-defined successive states, eventually producing "output"^{[6]}and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.^{[7]}Though al-Khwārizmī's

*algorism*referred to the rules of performing arithmetic using Hindu-Arabic numerals and the systematic solution of linear and quadratic equations, a partial formalization of what would become the modern*algorithm*began with attempts to solve the Entscheidungsproblem (the "decision problem") posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define “effective calculability"^{[8]}or "effective method";^{[9]}those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's “Formulation 1” of 1936, and Alan Turing's Turing machines of 1936–7 and 1939. Giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem.^{[10]}

- In mathematics and computer science, an

- ↑ "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
- ↑ Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).
- ↑ "an algorithm is a procedure for computing a
*function*(with respect to some chosen notation for integers) … this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1). - ↑ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).
- ↑ "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5).
- ↑ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).
- ↑ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2.
- ↑ Kleene 1943 in Davis 1965:274
- ↑ Rosser 1939 in Davis 1965:225
- ↑ Moschovakis, Yiannis N. (2001). "What is an algorithm?". In Engquist, B.; Schmid, W..
*Mathematics Unlimited — 2001 and beyond*. Springer. pp. 919–936 (Part II). ISBN 9783540669135. http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8093.

### 2011

- (Yedidia, 2011) ⇒ Jonathan S. Yedidia. (2011). “Message-passing Algorithms for Inference and Optimization." Journal of Statistical Physics 145, no. 4
- QUOTE: No algorithm can be discussed in isolation from the problem it is solving. BP and DC Message-passing algorithms are used to solve inference problems, optimization problems, and constraint satisfaction problems.

### 2009

- http://en.wiktionary.org/wiki/algorithm
- A precise step-by-step plan for a computational procedure that begins with an input value and yields an output value in a finite number of steps.

- (WordNet, 2009) ⇒ http://wordnetweb.princeton.edu/perl/webwn?s=algorithm
- S: (n) algorithm, algorithmic rule, algorithmic program (a precise rule (or set of rules) specifying how to solve some problem)

### 2002

- (Melli, 2002) ⇒ Gabor Melli. (2002). “Data Mining Glossary.
- Algorithm: A well specified sequence of steps that accepts an input and produces an output. See also Data Mining Algorithm.

### 1990

- (Cormen et al., 1990) ⇒ Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. (1990). “Introduction to Algorithms.” MIT Press.
- Informally, an
**algorithm**is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

- Informally, an