Algorithm - Copy PDF

Preview

Summary

Algorithm - Copy...

Description

For other uses, see Algorithm (disambiguation).

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 In mathematics and computer science, an algorithm (/ˈ ælɡ ərɪðə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 1

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 name of the 9th-century mathematician Muh ḥammad ibn Mūsā al-Khwārizmī, whose nisba (identifying him as from Khwarazm) was Latinized as 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ö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–37 and 1939.

Contents 1

Etymology

2

Informal definition

3

Formalization

3.1

Expressing algorithms

4

Design

5

Implementation

6

Computer algorithms

7

Examples

7.1

Algorithm example

7.2

Euclid's algorithm

7.2.1 Computer language for Euclid's algorithm 7.2.2 An inelegant program for Euclid's algorithm

2

7.2.3 An elegant program for Euclid's algorithm 7.3

Testing the Euclid algorithms

7.4

Measuring and improving the Euclid algorithms

8

Algorithmic analysis

8.1

Formal versus empirical

8.2

Execution efficiency

9

Classification

9.1

By implementation

9.2

By design paradigm

9.3

Optimization problems

9.4

By field of study

9.5

By complexity

10

Continuous algorithms

11

Legal issues

12

History: Development of the notion of "algorithm"

12.1

Ancient Near East

12.2

Discrete and distinguishable symbols

12.3

Manipulation of symbols as "place holders" for numbers: algebra

12.4

Cryptographic algorithms

12.5

Mechanical contrivances with discrete states

12.6

Mathematics during the 19th century up to the mid-20th century

12.7

Emil Post (1936) and Alan Turing (1936–37, 1939)

12.8

J.B. Rosser (1939) and S.C. Kleene (1943)

12.9

History after 1950

3

13

See also

14

Notes

15

Bibliography

16

Further reading

17

External links

Etymology The word 'algorithm' has its roots in Latinizing the nisba, indicating his geographic origin, of the name of Persian mathematician Muhammad ibn Musa al-Khwarizmi to algorismus.[17] [18] Al-Khwārizmī (Arabized Persian ‫ الخخخخوارزمی‬c. 780–850) was a mathematician, astronomer, geographer, and scholar in the House of Wisdom in Baghdad,[11] whose name means 'the native of Khwarazm', a region that was part of Greater Iran and is now in Uzbekistan.[19][20]

About 825, al-Khwarizmi wrote an Arabic language treatise on the Hindu–Arabic numeral system, which was translated into Latin during the 12th century. The manuscript starts with the phrase Dixit Algorizmi ('Thus spake Al-Khwarizmi'), where "Algorizmi" was the translator's Latinization of Al-Khwarizmi's name.[21] Al-Khwarizmi was the most widely read mathematician in Europe in the late Middle Ages, primarily through another of his books, the Algebra.[22] In late medieval Latin, algorismus, English 'algorism', the corruption of his name, simply meant the "decimal number system".[23] In the 15th century, under the influence of the Greek word ἀ ριθμός (arithmos), 'number' (cf. 'arithmetic'), the Latin word was altered to algorithmus, and the corresponding English term 'algorithm' is first attested in the 17th century; the modern sense was introduced in the 19th century.[24]

In English, it was first used in about 1230 and then by Chaucer in 1391. English adopted the French term, but it wasn't until the late 19th century that "algorithm" took on the meaning that it has in modern English.[25]

4

Another early use of the word is from 1240, in a manual titled Carmen de Algorismo composed by Alexandre de Villedieu. It begins with:

Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.

which translates to:

Algorism is the art by which at present we use those Indian figures, which number two times five.

The poem is a few hundred lines long and summarizes the art of calculating with the new styled Indian dice (Tali Indorum), or Hindu numerals.[26]

5...