Algorithm: Difference between revisions

Revision as of 14:42, 21 October 2013

Revision as of 14:44, 21 October 2013

Line 1:

{{Use mdy dates|date=June 2013}}

[[Image:Euclid flowchart 1.png|thumb|lright| [[Flow chart]] 1ofof an algorithm ([[Euclid's algorithm]]) for calculating the greatest common divisor (g.c.d.) of two numbers ''a'' and ''b'' in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" (or true) (more accurately the ''number'' ''b'' in ___location B is greater than or equal to the ''number'' ''a'' in ___location A) THEN, the algorithm specifies B ← B − A (meaning the number ''b'' − ''a'' replaces the old ''b''). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A. (Algorithm derived from Scott 2009:13; symbols and drawing style from Tausworthe 1977).]]

In English and [[mathematics]] and [[computer science]], an '''algorithm''' ({{IPAc-en|audio=en-us-algorithm.ogg|ˈ|æ|l|ɡ|ə|r|ɪ|ð|əm}} {{respell|AL|gə-ri-dhəm}}) 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 [[wikt:finite|finite]] list<ref>"Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).</ref> of well-defined instructions<ref>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).</ref> for calculating a [[Function (mathematics)|function]].<ref>"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).</ref> Starting from an initial state and initial input (perhaps [[null string|empty]]),<ref>"An algorithm has [[zero]] or more inputs, i.e., [[quantity|quantities]] which are given to it initially before the algorithm begins" (Knuth 1973:5).</ref> the instructions describe a [[computation]] that, when [[Execution (computing)|executed]], proceeds through a finite <ref>"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).</ref> number of well-defined successive states, eventually producing "output"<ref>"An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).</ref> 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.<ref>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.</ref>