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 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).
Ada Lovelace's diagram from "note G", the first published computer algorithm
Logical NAND algorithm implemented electronically in 7400 chip
Flowchart examples of the canonical Böhm-Jacopini structures: the SEQUENCE (rectangles descending the page), the WHILE-DO and the IF-THEN-ELSE. The three structures are made of the primitive conditional GOTO (IF test THEN GOTO step xxx, shown as diamond), the unconditional GOTO (rectangle), various assignment operators (rectangle), and HALT (rectangle). Nesting of these structures inside assignment-blocks result in complex diagrams (cf. Tausworthe 1977:100, 114).
The example-diagram of Euclid's algorithm from T.L. Heath (1908), with more detail added. Euclid does not go beyond a third measuring and gives no numerical examples. Nicomachus gives the example of 49 and 21: "I subtract the less from the greater; 28 is left; then again I subtract from this the same 21 (for this is possible); 7 is left; I subtract this from 21, 14 is left; from which I again subtract 7 (for this is possible); 7 is left, but 7 cannot be subtracted from 7." Heath comments that "The last phrase is curious, but the meaning of it is obvious enough, as also the meaning of the phrase about ending 'at one and the same number'."(Heath 1908:300).
A graphical expression of Euclid's algorithm to find the greatest common divisor for 1599 and 650.
"Inelegant" is a translation of Knuth's version of the algorithm with a subtraction-based remainder-loop replacing his use of division (or a "modulus" instruction). Derived from Knuth 1973:2–4. Depending on the two numbers "Inelegant" may compute the g.c.d. in fewer steps than "Elegant".
Alan Turing's statue at Bletchley Park

Algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

- Algorithm

500 related topics

Relevance

Randomized algorithm

Figure 2: Successful run of Karger's algorithm on a 10-vertex graph. The minimum cut has size 3 and is indicated by the vertex colours.
Figure 1: Contraction of vertex A and B

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure.

Heuristic (computer science)

Technique designed for solving a problem more quickly when classic methods are too slow or for finding an approximate solution when classic methods fail to find any exact solution.

Graph of a given by z = f(x, y) = −(x² + y²) + 4. The global maximum at (x, y, z) = (0, 0, 4) is indicated by a blue dot.

Heuristics underlie the whole field of Artificial Intelligence and the computer simulation of thinking, as they may be used in situations where there are no known algorithms.

Data processing

Data processing is, generally, "the collection and manipulation of items of data to produce meaningful information."

Example of data collection in the biological sciences: Adélie penguins are identified and weighed each time they cross the automated weighbridge on their way to or from the sea.

Data analysis uses specialized algorithms and statistical calculations that are less often observed in a typical general business environment.

Computer science

Study of computation, automation, and information.

Charles Babbage, sometimes referred to as the "father of computing".
Ada Lovelace published the first algorithm intended for processing on a computer.

Computer science spans theoretical disciplines (such as algorithms, theory of computation, and information theory) to practical disciplines (including the design and implementation of hardware and software).

Muhammad ibn Musa al-Khwarizmi

Persian polymath from Khwarazm, who produced vastly influential works in mathematics, astronomy, and geography.

A page from al-Khwārizmī's Algebra
Page from a Latin translation, beginning with "Dixit algorizmi"
Algorists vs. abacists, depicted in a sketch from 1508 CE
Page from Corpus Christi College MS 283. A Latin translation of al-Khwārizmī's Zīj.
Daunicht's reconstruction of the section of al-Khwārizmī's world map concerning the Indian Ocean.
A 15th-century version of Ptolemy's Geography for comparison.
Earliest extant map of the Nile, in al-Khwārazmī's Kitāb ṣūrat al- arḍ
A stamp issued 6 September 1983 in the Soviet Union, commemorating al-Khwārizmī's (approximate) 1200th birthday.
Statue of Al-Khwārizmī in Uzbekistan.

His name gave rise to the terms algorism and algorithm, as well as Spanish, Italian and Portuguese terms algoritmo, and Spanish guarismo and Portuguese algarismo meaning "digit".

Cryptography

Practice and study of techniques for secure communication in the presence of adversarial behavior.

Lorenz cipher machine, used in World War II to encrypt communications of the German High Command
Alphabet shift ciphers are believed to have been used by Julius Caesar over 2,000 years ago. This is an example with k = 3. In other words, the letters in the alphabet are shifted three in one direction to encrypt and three in the other direction to decrypt.
Reconstructed ancient Greek scytale, an early cipher device
First page of a book by Al-Kindi which discusses encryption of messages
16th-century book-shaped French cipher machine, with arms of Henri II of France
Enciphered letter from Gabriel de Luetz d'Aramon, French Ambassador to the Ottoman Empire, after 1546, with partial decipherment
Symmetric-key cryptography, where a single key is used for encryption and decryption
One round (out of 8.5) of the IDEA cipher, used in most versions of PGP and OpenPGP compatible software for time-efficient encryption of messages
Public-key cryptography, where different keys are used for encryption and decryption.
Whitfield Diffie and Martin Hellman, authors of the first published paper on public-key cryptography.
In this example the message is only signed and not encrypted. 1) Alice signs a message with her private key. 2) Bob can verify that Alice sent the message and that the message has not been modified.
Variants of the Enigma machine, used by Germany's military and civil authorities from the late 1920s through World War II, implemented a complex electro-mechanical polyalphabetic cipher. Breaking and reading of the Enigma cipher at Poland's Cipher Bureau, for 7 years before the war, and subsequent decryption at Bletchley Park, was important to Allied victory.
Poznań monument (center) to Polish cryptanalysts whose breaking of Germany's Enigma machine ciphers, beginning in 1932, altered the course of World War II
NSA headquarters in Fort Meade, Maryland

Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed around computational hardness assumptions, making such algorithms hard to break in actual practice by any adversary.

Cryptanalysis

Cryptanalysis (from the Greek kryptós, "hidden", and analýein, "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems.

Close-up of the rotors in a cipher machine
First page of Al-Kindi's 9th century Manuscript on Deciphering Cryptographic Messages
The decrypted Zimmermann Telegram.
The Bombe replicated the action of several Enigma machines wired together. Each of the rapidly rotating drums, pictured above in a Bletchley Park museum mockup, simulated the action of an Enigma rotor.

Global deduction – the attacker discovers a functionally equivalent algorithm for encryption and decryption, but without learning the key.

Euclidean algorithm

Efficient method for computing the greatest common divisor of two integers (numbers), the largest number that divides them both without a remainder.

Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common "unit" length. The length DC being shorter, it is used to "measure" BA, but only once because the remainder EA is less than DC. EA now measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right Nicomachus's example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300).
A 24-by-60 rectangle is covered with ten 12-by-12 square tiles, where 12 is the GCD of 24 and 60. More generally, an a-by-b rectangle can be covered with square tiles of side-length c only if c is a common divisor of a and b.
The Euclidean algorithm was probably invented before Euclid, depicted here holding a compass in a painting of about 1474.
Plot of a linear Diophantine equation, 9x + 12y = 483. The solutions are shown as blue circles.
The Stern–Brocot tree, and the Stern–Brocot sequences of order i for i = 1, 2, 3, 4
Number of steps in the Euclidean algorithm for gcd(x,y). Lighter (red and yellow) points indicate relatively few steps, whereas darker (violet and blue) points indicate more steps. The largest dark area follows the line y = Φx, where Φ is the golden ratio.

It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules,

Computation

Arithmetic tables for children, Lausanne, 1835

Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).

Turing machine

Mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules.

A physical Turing machine model. A true Turing machine would have unlimited tape on both sides, however, physical models can only have a finite amount of tape.
The head is always over a particular square of the tape; only a finite stretch of squares is shown. The instruction to be performed (q4) is shown over the scanned square. (Drawing after Kleene (1952) p. 375.)
Here, the internal state (q1) is shown inside the head, and the illustration describes the tape as being infinite and pre-filled with "0", the symbol serving as blank. The system's full state (its "complete configuration") consists of the internal state, any non-blank symbols on the tape (in this illustration "11B"), and the position of the head relative to those symbols including blanks, i.e. "011B". (Drawing after Minsky (1967) p. 121.)
The "3-state busy beaver" Turing machine in a finite-state representation. Each circle represents a "state" of the table—an "m-configuration" or "instruction". "Direction" of a state transition is shown by an arrow. The label (e.g. 0/P,R) near the outgoing state (at the "tail" of the arrow) specifies the scanned symbol that causes a particular transition (e.g. 0) followed by a slash /, followed by the subsequent "behaviors" of the machine, e.g. "P print" then move tape "R right". No general accepted format exists. The convention shown is after McClusky (1965), Booth (1967), Hill, and Peterson (1974).
The evolution of the busy beaver's computation starts at the top and proceeds to the bottom.
An implementation of a Turing machine
A Turing machine realization using Lego pieces
Another Turing machine realization

Despite the model's simplicity, it is capable of implementing any computer algorithm.