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):
- a Sorting Algorithm, such as a Quicksort Algorithm.
- a Randomization Algorithm, such as a Blum Blum Shub Algorithm.
- an AI Algorithm, such as:
- a Learning Algorithm, such as:
- a Decision Tree Learning Algorithm, such as C4.5 algorithm .
- a Learning Algorithm, such as:
- a Euclid's Algorithm.
- an NLP Algorithm, such as a Word Sense Disambiguation Algorithm or a Word Sense Disambiguation Algorithm.
- a Graph Algorithm.
- a String Algorithm.
- a Pattern Matching Algorithm.
- a Number Theory Algorithm.
- a Cryptographic Algorithm.
- a Network Flow Algorithm.
- a Computational Geometry Algorithm.
- a Computational Gomplexity Theory Algorithm.
- an Approximation 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 algorithm ( /ˈælɡərɪðəm/ Template:Respell) is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.
- ↑ "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.