Algorithm

  • flowchart of 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 ba 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).
    ada lovelace's diagram from "note g", the first published computer algorithm.

    in mathematics and computer science, an algorithm (əm/ (about this soundlisten)) is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.[1][2] algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks.

    as an effective method, an algorithm can be expressed within a finite amount of space and time,[3] and in a well-defined formal language[4] for calculating a function.[5] starting from an initial state and initial input (perhaps empty),[6] the instructions describe a computation that, when executed, proceeds through a finite[7] number of well-defined successive states, eventually producing "output"[8] 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.[9]

    the concept of algorithm has existed since antiquity. arithmetic algorithms, such as a division algorithm, was used by ancient babylonian mathematicians c. 2500 bc and egyptian mathematicians c. 1550 bc.[10] greek mathematicians later used algorithms in the sieve of eratosthenes for finding prime numbers,[11] and the euclidean algorithm for finding the greatest common divisor of two numbers.[12] arabic mathematicians such as al-kindi in the 9th century used cryptographic algorithms for code-breaking, based on frequency analysis.[13]

    the word algorithm itself is derived from the 9th-century persian mathematician muḥammad ibn mūsā al-khwārizmī, latinized algoritmi.[14] a partial formalization of what would become the modern concept of algorithm began with attempts to solve the entscheidungsproblem (decision problem) posed by david hilbert in 1928. later formalizations were framed as attempts to define "effective calculability"[15] or "effective method".[16] those formalizations included the gödelherbrandkleene 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–37 and 1939.

  • etymology
  • informal definition
  • formalization
  • design
  • implementation
  • computer algorithms
  • examples
  • algorithmic analysis
  • classification
  • continuous algorithms
  • legal issues
  • history: development of the notion of "algorithm"
  • see also
  • notes
  • bibliography
  • further reading
  • external links

Flowchart of 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 ba 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).
Ada Lovelace's diagram from "note G", the first published computer algorithm.

In mathematics and computer science, an algorithm (əm/ (About this soundlisten)) is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.[1][2] Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks.

As an effective method, an algorithm can be expressed within a finite amount of space and time,[3] and in a well-defined formal language[4] for calculating a function.[5] Starting from an initial state and initial input (perhaps empty),[6] the instructions describe a computation that, when executed, proceeds through a finite[7] number of well-defined successive states, eventually producing "output"[8] 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.[9]

The concept of algorithm has existed since antiquity. Arithmetic algorithms, such as a division algorithm, was used by ancient Babylonian mathematicians c. 2500 BC and Egyptian mathematicians c. 1550 BC.[10] Greek mathematicians later used algorithms in the sieve of Eratosthenes for finding prime numbers,[11] and the Euclidean algorithm for finding the greatest common divisor of two numbers.[12] Arabic mathematicians such as Al-Kindi in the 9th century used cryptographic algorithms for code-breaking, based on frequency analysis.[13]

The word algorithm itself is derived from the 9th-century Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī, Latinized Algoritmi.[14] A partial formalization of what would become the modern concept of algorithm began with attempts to solve the Entscheidungsproblem (decision problem) posed by David Hilbert in 1928. Later formalizations were framed as attempts to define "effective calculability"[15] or "effective method".[16] Those formalizations included the GödelHerbrandKleene 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–37 and 1939.