![GCD through successive subtractions](https://upload.wikimedia.org/wikipedia/commons/5/5e/GCD_through_successive_subtractions.svg)
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, an algorithm () is a
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked ...
sequence of
mathematically rigorous instructions, typically used to solve a class of specific
problems or to perform a
computation
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).
Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An es ...
.
Algorithms are used as specifications for performing
calculation
A calculation is a deliberate mathematical process that transforms one or more inputs into one or more outputs or ''results''. The term is used in a variety of senses, from the very definite arithmetical calculation of using an algorithm, to th ...
s and
data processing
Data processing is the collection and manipulation of digital data to produce meaningful information.
Data processing is a form of ''information processing'', which is the modification (processing) of information in any manner detectable by an ...
. More advanced algorithms can use
conditionals to divert the code execution through various routes (referred to as
automated decision-making
Automated decision-making (ADM) involves the use of data, machines and algorithms to make decisions in a range of contexts, including public administration, business, health, education, law, employment, transport, media and entertainment, with var ...
) and deduce valid
inference
Inferences are steps in reasoning, moving from premises to logical consequences; etymologically, the word '' infer'' means to "carry forward". Inference is theoretically traditionally divided into deduction and induction, a distinction that in ...
s (referred to as
automated reasoning
In computer science, in particular in knowledge representation and reasoning and metalogic, the area of automated reasoning is dedicated to understanding different aspects of reasoning. The study of automated reasoning helps produce computer progra ...
), achieving
automation
Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...
eventually. Using human characteristics as descriptors of machines in metaphorical ways was already practiced by
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
with terms such as "memory", "search" and "stimulus".
[Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia and Grafton, Anthony. Information: A Historical Companion, Princeton: Princeton University Press, 2021. p. 247]
In contrast, a
heuristic
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
is an approach to problem-solving that may not be fully specified or may not guarantee correct or optimal results, especially in problem domains where there is no well-defined correct or optimal result.
[David A. Grossman, Ophir Frieder, ''Information Retrieval: Algorithms and Heuristics'', 2nd edition, 2004, ] For example, social media
recommender system
A recommender system, or a recommendation system (sometimes replacing 'system' with a synonym such as platform or engine), is a subclass of information filtering system that provide suggestions for items that are most pertinent to a particular u ...
s rely on heuristics in such a way that, although widely characterized as "algorithms" in 21st-century popular media, cannot deliver correct results due to the nature of the problem.
As an
effective method
In logic, mathematics and computer science, especially metalogic and computability theory, an effective method Hunter, Geoffrey, ''Metalogic: An Introduction to the Metatheory of Standard First-Order Logic'', University of California Press, 1971 ...
, an algorithm can be expressed within a finite amount of space and time
["Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).] and in a well-defined
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
[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).] for calculating a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
. Starting from an initial state and initial input (perhaps
empty
Empty may refer to:
Music Albums
* ''Empty'' (God Lives Underwater album) or the title song, 1995
* ''Empty'' (Nils Frahm album), 2020
* ''Empty'' (Tait album) or the title song, 2001
Songs
* "Empty" (The Click Five song), 2007
* ...
), the instructions describe a computation that, when
execute
Execute, in capital punishment, is to put someone to death.
Execute may also refer to:
*Execution (computing), the running of a computer program
* ''Execute'' (album), a 2001 Garage hip-hop album by Oxide & Neutrino
* USS ''Execute'' (AM-232), an ...
d, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily
deterministic
Determinism is a philosophical view, where all events are determined completely by previously existing causes. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping motives and consi ...
; some algorithms, known as
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
s, incorporate random input.
Etymology
Around 825 AD, Persian scientist and polymath
Muḥammad ibn Mūsā al-Khwārizmī
Muhammad ( ar, مُحَمَّد; 570 – 8 June 632 CE) was an Arab religious, social, and political leader and the founder of Islam. According to Islamic doctrine, he was a prophet divinely inspired to preach and confirm the mono ...
wrote ''kitāb al-ḥisāb al-hindī'' ("Book of Indian computation") and ''kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī'' ("Addition and subtraction in Indian arithmetic").
In the early 12th century, Latin translations of said al-Khwarizmi texts involving the
Hindu–Arabic numeral system
The Hindu–Arabic numeral system or Indo-Arabic numeral system Audun HolmeGeometry: Our Cultural Heritage 2000 (also called the Hindu numeral system or Arabic numeral system) is a positional decimal numeral system, and is the most common syste ...
and
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
appeared, for example ''Liber Alghoarismi de practica arismetrice'', attributed to
John of Seville
John of Seville ( Latin: ''Johannes Hispalensis'' or ''Johannes Hispaniensis'') ( fl. 1133-53) was one of the main translators from Arabic into Castilian in partnership with Dominicus Gundissalinus during the early days of the Toledo School of Tr ...
, and ''Liber Algorismi de numero Indorum'', attributed to
Adelard of Bath
Adelard of Bath ( la, Adelardus Bathensis; 1080? 1142–1152?) was a 12th-century English natural philosopher. He is known both for his original works and for translating many important Arabic and Greek scientific works of astrology, astronom ...
.
Hereby, ''alghoarismi'' or ''algorismi'' is the
Latinization of Al-Khwarizmi's name; the text starts with the phrase ''Dixit Algorismi'', or "Thus spoke Al-Khwarizmi".
Around 1230, the English word ''
algorism
Algorism is the technique of performing basic arithmetic by writing numbers in place value form and applying a set of memorized rules and facts to the digits. One who practices algorism is known as an algorist. This positional notation system h ...
'' is attested and then by
Chaucer
Geoffrey Chaucer (; – 25 October 1400) was an English poet, author, and civil servant best known for '' The Canterbury Tales''. He has been called the "father of English literature", or, alternatively, the "father of English poetry". He w ...
in 1391, English adopted the French term.
In the 15th century, under the influence of the Greek word ἀριθμός (''arithmos'', "number"; ''cf.'' "arithmetic"), the Latin word was altered to ''algorithmus''.
Definition
One informal definition is "a set of rules that precisely defines a sequence of operations", which would include all
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components.
A computer program ...
s (including programs that do not perform numeric calculations), and (for example) any prescribed
bureaucratic
The term bureaucracy () refers to a body of non-elected governing officials as well as to an administrative policy-making group. Historically, a bureaucracy was a government administration managed by departments staffed with non-elected offi ...
procedure
or
cook-book recipe
A recipe is a set of instructions that describes how to prepare or make something, especially a dish of prepared food. A sub-recipe or subrecipe is a recipe for an ingredient that will be called for in the instructions for the main recipe.
His ...
. In general, a program is an algorithm only if it stops eventually—even though
infinite loop
In computer programming, an infinite loop (or endless loop) is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs ("pull the plug"). It may be intentional.
Overview
This differs from:
* ...
s may sometimes prove desirable. define an algorithm to be a set of instructions for determining an output, given explicitly, in a form that can be followed by either a computing machine or a human who could only carry out specific elementary operations on symbols''.''
The concept of ''algorithm'' is also used to define the notion of
decidability—a notion that is central for explaining how
formal system
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system.
A form ...
s come into being starting from a small set of
axiom
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or f ...
s and rules. In
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
, the time that an algorithm requires to complete cannot be measured, as it is not apparently related to the customary physical dimension. From such uncertainties, that characterize ongoing work, stems the unavailability of a definition of ''algorithm'' that suits both concrete (in some sense) and abstract usage of the term.
Most algorithms are intended to be
implemented as
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components.
A computer program ...
s. However, algorithms are also implemented by other means, such as in a
biological neural network
A neural circuit is a population of neurons interconnected by synapses to carry out a specific function when activated. Neural circuits interconnect to one another to form large scale brain networks.
Biological neural networks have inspired the ...
(for example, the
human brain
The human brain is the central organ of the human nervous system, and with the spinal cord makes up the central nervous system. The brain consists of the cerebrum, the brainstem and the cerebellum. It controls most of the activities of the ...
implementing
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
or an insect looking for food), in an
electrical circuit
An electrical network is an interconnection of electrical components (e.g., batteries, resistors, inductors, capacitors, switches, transistors) or a model of such an interconnection, consisting of electrical elements (e.g., voltage sources, ...
, or in a mechanical device.
History
Ancient algorithms
Since antiquity, step-by-step procedures for solving mathematical problems have been attested. This includes in
Babylonian mathematics
Babylonian mathematics (also known as ''Assyro-Babylonian mathematics'') are the mathematics developed or practiced by the people of Mesopotamia, from the days of the early Sumerians to the centuries following the fall of Babylon in 539 BC. Babyl ...
(around 2500 BC),
Egyptian mathematics
Ancient Egyptian mathematics is the mathematics that was developed and used in Ancient Egypt 3000 to c. , from the Old Kingdom of Egypt until roughly the beginning of Hellenistic Egypt. The ancient Egyptians utilized a numeral system for count ...
(around 1550 BC),
Indian mathematics
Indian mathematics emerged in the Indian subcontinent from 1200 BCE until the end of the 18th century. In the classical period of Indian mathematics (400 CE to 1200 CE), important contributions were made by scholars like Aryabhata, Brahmagupta ...
(around 800 BC and later),
The Ifa Oracle(around 500 BC),
Greek mathematics
Greek mathematics refers to mathematics texts and ideas stemming from the Archaic through the Hellenistic and Roman periods, mostly extant from the 7th century BC to the 4th century AD, around the shores of the Eastern Mediterranean. Greek mathem ...
(around 240 BC),
and
Arabic mathematics
Mathematics during the Golden Age of Islam, especially during the 9th and 10th centuries, was built on Greek mathematics (Euclid, Archimedes, Apollonius) and Indian mathematics (Aryabhata, Brahmagupta). Important progress was made, such as full ...
(around 800 AD).
The earliest evidence of algorithms is found in the Babylonian mathematics of ancient
Mesopotamia
Mesopotamia ''Mesopotamíā''; ar, بِلَاد ٱلرَّافِدَيْن or ; syc, ܐܪܡ ܢܗܪ̈ܝܢ, or , ) is a historical region of Western Asia situated within the Tigris–Euphrates river system, in the northern part of the F ...
(modern Iraq). A
Sumer
Sumer () is the earliest known civilization in the historical region of southern Mesopotamia (south-central Iraq), emerging during the Chalcolithic and early Bronze Ages between the sixth and fifth millennium BC. It is one of the cradles of c ...
ian clay tablet found in
Shuruppak
Shuruppak ( sux, , "the healing place"), modern Tell Fara, was an ancient Sumerian city situated about 55 kilometres (35 mi) south of Nippur on the banks of the Euphrates in Iraq's Al-Qādisiyyah Governorate. Shuruppak was dedicated to Ni ...
near
Baghdad
Baghdad (; ar, بَغْدَاد , ) is the capital of Iraq and the second-largest city in the Arab world after Cairo. It is located on the Tigris near the ruins of the ancient city of Babylon and the Sassanid Persian capital of Ctesiphon ...
and dated to described the earliest
division algorithm
A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software.
Divis ...
.
During the
Hammurabi dynasty ,
Babylonia
Babylonia (; Akkadian: , ''māt Akkadī'') was an ancient Akkadian-speaking state and cultural area based in the city of Babylon in central-southern Mesopotamia (present-day Iraq and parts of Syria). It emerged as an Amorite-ruled state c. ...
n clay tablets described algorithms for computing formulas. Algorithms were also used in
Babylonian astronomy
Babylonian astronomy was the study or recording of celestial objects during the early history of Mesopotamia.
Babylonian astronomy seemed to have focused on a select group of stars and constellations known as Ziqpu stars. These constellations m ...
. Babylonian clay tablets describe and employ algorithmic procedures to compute the time and place of significant astronomical events.
Algorithms for arithmetic are also found in ancient
Egyptian mathematics
Ancient Egyptian mathematics is the mathematics that was developed and used in Ancient Egypt 3000 to c. , from the Old Kingdom of Egypt until roughly the beginning of Hellenistic Egypt. The ancient Egyptians utilized a numeral system for count ...
, dating back to the
Rhind Mathematical Papyrus .
Algorithms were later used in ancient
Hellenistic mathematics
Greek mathematics refers to mathematics texts and ideas stemming from the Archaic through the Hellenistic and Roman periods, mostly extant from the 7th century BC to the 4th century AD, around the shores of the Eastern Mediterranean. Greek mathem ...
. Two examples are the
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime n ...
, which was described in the ''
Introduction to Arithmetic
The book ''Introduction to Arithmetic'' ( grc-gre, Ἀριθμητικὴ εἰσαγωγή, ''Arithmetike eisagoge'') is the only extant work on mathematics by Nicomachus (60–120 AD).
Summary
The work contains both philosophical prose and ...
'' by
Nicomachus
Nicomachus of Gerasa ( grc-gre, Νικόμαχος; c. 60 – c. 120 AD) was an important ancient mathematician and music theorist, best known for his works ''Introduction to Arithmetic'' and ''Manual of Harmonics'' in Greek. He was born in ...
,
and the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
, which was first described in ''
Euclid's Elements
The ''Elements'' ( grc, Στοιχεῖα ''Stoikheîa'') is a mathematical treatise consisting of 13 books attributed to the ancient Greek mathematician Euclid in Alexandria, Ptolemaic Egypt 300 BC. It is a collection of definitions, postulat ...
'' ().
Examples of ancient Indian mathematics included the
Shulba Sutras The ''Shulva Sutras'' or ''Śulbasūtras'' (Sanskrit: शुल्बसूत्र; ': "string, cord, rope") are sutra texts belonging to the Śrauta ritual and containing geometry related to fire-altar construction.
Purpose and origins
The ...
, the
Kerala School, and the
Brāhmasphuṭasiddhānta
The ''Brāhmasphuṭasiddhānta'' ("Correctly Established Doctrine of Brahma", abbreviated BSS)
is the main work of Brahmagupta, written c. 628. This text of mathematical astronomy contains significant mathematical content, including a good unders ...
.
The first cryptographic algorithm for deciphering encrypted code was developed by
Al-Kindi
Abū Yūsuf Yaʻqūb ibn ʼIsḥāq aṣ-Ṣabbāḥ al-Kindī (; ar, أبو يوسف يعقوب بن إسحاق الصبّاح الكندي; la, Alkindus; c. 801–873 AD) was an Arab Muslim philosopher, polymath, mathematician, physician ...
, a 9th-century Arab mathematician, in ''A Manuscript On Deciphering Cryptographic Messages''. He gave the first description of
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. Cryptanalysis is used to breach cryptographic sec ...
by
frequency analysis
In cryptanalysis, frequency analysis (also known as counting letters) is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers.
Frequency analysis is based on t ...
, the earliest codebreaking algorithm.
Computers
Weight-driven clocks
Bolter credits the invention of the weight-driven clock as "The key invention
f Europe in the Middle Ages
F, or f, is the sixth letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''ef'' (pronounced ), and the plural is ''efs''.
Hist ...
. In particular, he credits the
verge escapement
The verge (or crown wheel) escapement is the earliest known type of mechanical escapement, the mechanism in a mechanical clock that controls its rate by allowing the gear train to advance at regular intervals or 'ticks'. Its origin is unknown. V ...
mechanism that provides us with the tick and tock of a mechanical clock. "The accurate automatic machine" led immediately to "mechanical
automata
An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...
" beginning in the 13th century and finally to "computational machines"—the
difference engine
A difference engine is an automatic mechanical calculator designed to tabulate polynomial, polynomial functions. It was designed in the 1820s, and was first created by Charles Babbage. The name, the difference engine, is derived from the method ...
and analytical engines of
Charles Babbage
Charles Babbage (; 26 December 1791 – 18 October 1871) was an English polymath. A mathematician, philosopher, inventor and mechanical engineer, Babbage originated the concept of a digital programmable computer.
Babbage is considered ...
and Countess
Ada Lovelace
Augusta Ada King, Countess of Lovelace (''née'' Byron; 10 December 1815 – 27 November 1852) was an English mathematician and writer, chiefly known for her work on Charles Babbage's proposed mechanical general-purpose computer, the A ...
, mid-19th century. Lovelace is credited with the first creation of an algorithm intended for processing on a computer—Babbage's analytical engine, the first device considered a real
Turing-complete
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tur ...
computer instead of just a
calculator
An electronic calculator is typically a portable electronic device used to perform calculations, ranging from basic arithmetic to complex mathematics.
The first solid-state electronic calculator was created in the early 1960s. Pocket-sized ...
—and is sometimes called "history's first programmer" as a result, though a full implementation of Babbage's second device would not be realized until decades after her lifetime.
Electromechanical relay
Bell and Newell (1971) indicate that the
Jacquard loom
The Jacquard machine () is a device fitted to a loom that simplifies the process of manufacturing textiles with such complex patterns as brocade, damask and matelassé. The resulting ensemble of the loom and Jacquard machine is then called a Ja ...
(1801), a precursor to
Hollerith card
A punched card (also punch card or punched-card) is a piece of stiff paper that holds digital data represented by the presence or absence of holes in predefined positions. Punched cards were once common in data processing applications or to ...
s (punch cards, 1887), and "telephone switching technologies" were the roots of a tree leading to the development of the first computers. By the mid-19th century the
telegraph
Telegraphy is the long-distance transmission of messages where the sender uses symbolic codes, known to the recipient, rather than a physical exchange of an object bearing the message. Thus flag semaphore is a method of telegraphy, whereas p ...
, the precursor of the telephone, was in use throughout the world, its discrete and distinguishable encoding of letters as "dots and dashes" a common sound. By the late 19th century, the
ticker tape
Ticker tape was the earliest electrical dedicated financial communications medium, transmitting stock price information over telegraph lines, in use from around 1870 through 1970. It consisted of a paper strip that ran through a machine called ...
() was in use, as was the use of Hollerith cards in the 1890 U.S. census. Then came the
teleprinter
A teleprinter (teletypewriter, teletype or TTY) is an electromechanical device that can be used to send and receive typed messages through various communications channels, in both point-to-point and point-to-multipoint configurations. Initia ...
() with its punched-paper use of
Baudot code
The Baudot code is an early character encoding for telegraphy invented by Émile Baudot in the 1870s. It was the predecessor to the International Telegraph Alphabet No. 2 (ITA2), the most common teleprinter code in use until the advent of ASCII. ...
on tape.
Telephone-switching networks of
electromechanical relays (invented 1835) was behind the work of
George Stibitz
George Robert Stibitz (April 30, 1904 – January 31, 1995) was a Bell Labs researcher internationally recognized as one of the fathers of the modern digital computer. He was known for his work in the 1930s and 1940s on the realization of Boole ...
(1937), the inventor of the digital adding device. As he worked in Bell Laboratories, he observed the "burdensome' use of mechanical calculators with gears. "He went home one evening in 1937 intending to test his idea... When the tinkering was over, Stibitz had constructed a binary adding device". The mathematician
Martin Davis supported the particular importance of the electromechanical relay.
Formalization
![Diagram for the computation of Bernoulli numbers](https://upload.wikimedia.org/wikipedia/commons/c/cf/Diagram_for_the_computation_of_Bernoulli_numbers.jpg)
In 1928, a partial formalization of the modern concept of algorithms began with attempts to solve the ''
Entscheidungsproblem
In mathematics and computer science, the ' (, ) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "Yes" or "No" according to whether the statem ...
''(decision problem) posed by
David Hilbert
David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many a ...
. Later formalizations were framed as attempts to define "
effective calculability
In logic, mathematics and computer science, especially metalogic and computability theory, an effective method Hunter, Geoffrey, ''Metalogic: An Introduction to the Metatheory of Standard First-Order Logic'', University of California Press, 1971 or ...
" or "effective method". Those formalizations included the
Gödel–
Herbrand–
Kleene
Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...
recursive functions of 1930, 1934 and 1935,
Alonzo Church
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scienc ...
's
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
of 1936,
Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Govern ...
's
Formulation 1 of 1936, and
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
's
turing machines
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
of 1936–37 and 1939.
Representations
Algorithms can be expressed in many kinds of notation, including
natural languages
In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languages ...
,
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
,
flowchart
A flowchart is a type of diagram that represents a workflow or process. A flowchart can also be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving a task.
The flowchart shows the steps as boxes of va ...
s,
drakon-chart
DRAKON is a free and open source algorithmic visual programming and modeling language developed within the Buran space project following ergonomic design principles. The language provides a uniform way to represent flowcharts of any com ...
s,
programming languages
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
or
control table
Control tables are tables that control the control flow or play a major part in program control. There are no rigid rules about the structure or content of a control table—its qualifying attribute is its ability to direct control flow in some wa ...
s (processed by
interpreters). Natural language expressions of algorithms tend to be verbose and ambiguous and are rarely used for complex or technical algorithms. Pseudocode, flowcharts, drakon-charts, and control tables are structured ways to express algorithms that avoid many of the ambiguities common in statements based on natural language. Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer, but they are also often used as a way to define or document algorithms.
Turing machines
There is a wide variety of representations possible and one can express a given
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
program as a sequence of machine tables (see
finite-state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
,
state-transition table, and
control table
Control tables are tables that control the control flow or play a major part in program control. There are no rigid rules about the structure or content of a control table—its qualifying attribute is its ability to direct control flow in some wa ...
for more), as flowcharts and drakon-charts (see
state diagram
A state diagram is a type of diagram used in computer science and related fields to describe the behavior of systems. State diagrams require that the system described is composed of a finite number of states; sometimes, this is indeed the case, ...
for more), or as a form of rudimentary
machine code
In computer programming, machine code is any low-level programming language, consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). Each instruction causes the CPU to perform a very ...
or
assembly code
In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence b ...
called "sets of quadruples" (see
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
for more). Representations of algorithms can also be classified into three accepted levels of Turing machine description: high-level description, implementation description, and formal description.
[Sipser 2006:157] A high-level description describes qualities of the algorithm itself, ignoring how it is implemented on the Turing machine.
An implementation description describes the general manner in which the machine moves its head and stores data in order to carry out the algorithm, but doesn't give exact states.
In the most detail, a formal description gives the exact state table and list of transitions of the Turing machine.
Flowchart representation
The graphical aid called a
flowchart
A flowchart is a type of diagram that represents a workflow or process. A flowchart can also be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving a task.
The flowchart shows the steps as boxes of va ...
offers a way to describe and document an algorithm (and a computer program corresponding to it). Like the program flow of a Minsky machine, a flowchart always starts at the top of a page and proceeds down. Its primary symbols are only four: the directed arrow showing program flow, the rectangle (SEQUENCE, GOTO), the diamond (IF-THEN-ELSE), and the dot (OR-tie). The Böhm–Jacopini canonical structures are made of these primitive shapes. Sub-structures can "nest" in rectangles, but only if a single exit occurs from the superstructure. The symbols and their use to build the canonical structures are shown in the diagram.'
Algorithmic analysis
It is frequently important to know how much of a particular resource (such as time or storage) is theoretically required for a given algorithm. Methods have been developed for the analysis of algorithms to obtain such quantitative answers (estimates); for example, an algorithm that adds up the elements of a list of ''n'' numbers would have a time requirement of , using
big O notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
. At all times the algorithm only needs to remember two values: the sum of all the elements so far, and its current position in the input list. Therefore, it is said to have a space requirement of , if the space required to store the input numbers is not counted, or if it is counted.
Different algorithms may complete the same task with a different set of instructions in less or more time, space, or '
effort' than others. For example, a
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
algorithm (with cost ) outperforms a sequential search (cost ) when used for
table lookups on sorted lists or arrays.
Formal versus empirical
The
analysis, and study of algorithms is a discipline of
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, and is often practiced abstractly without the use of a specific
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
or implementation. In this sense, algorithm analysis resembles other mathematical disciplines in that it focuses on the underlying properties of the algorithm and not on the specifics of any particular implementation. Usually,
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
is used for analysis as it is the simplest and most general representation. However, ultimately, most algorithms are usually implemented on particular hardware/software platforms and their
algorithmic efficiency
In computer science, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm. An algorithm must be analyzed to determine its resource usage, and the efficiency of an algor ...
is eventually put to the test using real code. For the solution of a "one-off" problem, the efficiency of a particular algorithm may not have significant consequences (unless n is extremely large) but for algorithms designed for fast interactive, commercial or long life scientific usage it may be critical. Scaling from small n to large n frequently exposes inefficient algorithms that are otherwise benign.
Empirical testing is useful because it may uncover unexpected interactions that affect performance.
Benchmark
Benchmark may refer to:
Business and economics
* Benchmarking, evaluating performance within organizations
* Benchmark price
* Benchmark (crude oil), oil-specific practices
Science and technology
* Benchmark (surveying), a point of known elevati ...
s may be used to compare before/after potential improvements to an algorithm after program optimization.
Empirical tests cannot replace formal analysis, though, and are not trivial to perform in a fair manner.
Execution efficiency
To illustrate the potential improvements possible even in well-established algorithms, a recent significant innovation, relating to
FFT
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the ...
algorithms (used heavily in the field of image processing), can decrease processing time up to 1,000 times for applications like medical imaging. In general, speed improvements depend on special properties of the problem, which are very common in practical applications.
[Haitham Hassanieh, ]Piotr Indyk
Piotr Indyk is Thomas D. and Virginia W. Cabot Professor in the Theory of Computation Group at the Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology.
Academic biography
Indyk received the Magister (MA) ...
, Dina Katabi, and Eric Price,
ACM-SIAM Symposium On Discrete Algorithms (SODA)
, Kyoto, January 2012. See also th
sFFT Web Page
. Speedups of this magnitude enable computing devices that make extensive use of image processing (like digital cameras and medical equipment) to consume less power.
Design
Algorithm design refers to a method or a mathematical process for problem-solving and engineering algorithms. The design of algorithms is part of many solution theories, such as
divide-and-conquer or
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
within
operation research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...
. Techniques for designing and implementing algorithm designs are also called algorithm design patterns, with examples including the template method pattern and the decorator pattern. One of the most important aspects of algorithm design is resource (run-time, memory usage) efficiency; the
big O notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
is used to describe e.g., an algorithm's run-time growth as the size of its input increases.
Structured programming
Per the
Church–Turing thesis
In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of comp ...
, any algorithm can be computed by a model known to be
Turing complete
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
. In fact, it has been demonstrated that Turing completeness requires only four instruction types—conditional GOTO, unconditional GOTO, assignment, HALT. However, Kemeny and Kurtz observe that, while "undisciplined" use of unconditional GOTOs and conditional IF-THEN GOTOs can result in "
spaghetti code
Spaghetti code is a pejorative phrase for unstructured and difficult-to- maintain source code. Spaghetti code can be caused by several factors, such as volatile project requirements, lack of programming style rules, and software engineers with insu ...
", a programmer can write structured programs using only these instructions; on the other hand "it is also possible, and not too hard, to write badly structured programs in a structured language". Tausworthe augments the three
Böhm-Jacopini canonical structures: SEQUENCE, IF-THEN-ELSE, and WHILE-DO, with two more: DO-WHILE and CASE. An additional benefit of a structured program is that it lends itself to
proofs of correctness using
mathematical induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
.
Classification
There are various ways to classify algorithms, each with its own merits.
By implementation
One way to classify algorithms is by implementation means.
; Recursion
: A
recursive algorithm
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
is one that invokes (makes reference to) itself repeatedly until a certain condition (also known as termination condition) matches, which is a method common to
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
.
Iterative
Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
algorithms use repetitive constructs like
loop
Loop or LOOP may refer to:
Brands and enterprises
* Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live
* Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets
* Loop Mobile, an ...
s and sometimes additional data structures like
stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
s to solve the given problems. Some problems are naturally suited for one implementation or the other. For example,
towers of Hanoi
The Tower of Hanoi (also called The problem of Benares Temple or Tower of Brahma or Lucas' Tower and sometimes pluralized as Towers, or simply pyramid puzzle) is a mathematical game or puzzle consisting of three rods and a number of disks of va ...
is well understood using recursive implementation. Every recursive version has an equivalent (but possibly more or less complex) iterative version, and vice versa.
; Serial, parallel or distributed
: Algorithms are usually discussed with the assumption that computers execute one instruction of an algorithm at a time. Those computers are sometimes called serial computers. An
algorithm design
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...
ed for such an environment is called a serial algorithm, as opposed to
parallel algorithm
In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machin ...
s or
distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific ...
s. Parallel algorithms are algorithms that take advantage of computer architectures where multiple processors can work on a problem at the same time. Distributed algorithms are algorithms that use multiple machines connected to a computer network. Parallel and distributed algorithms divide the problem into more symmetrical or asymmetrical subproblems and collect the results back together. For example, a CPU would be an example of a parallel algorithm. The resource consumption in such algorithms is not only processor cycles on each processor but also the communication overhead between the processors. Some sorting algorithms can be parallelized efficiently, but their communication overhead is expensive. Iterative algorithms are generally parallelizable, but some problems have no parallel algorithms and are called inherently serial problems.
; Deterministic or non-deterministic
:
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far ...
s solve the problem with exact decision at every step of the algorithm whereas
non-deterministic algorithm
In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave diffe ...
s solve problems via guessing although typical guesses are made more accurate through the use of
heuristics
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
.
; Exact or approximate
: While many algorithms reach an exact solution,
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
s seek an approximation that is closer to the true solution. The approximation can be reached by either using a deterministic or a random strategy. Such algorithms have practical value for many hard problems. One of the examples of an approximate algorithm is the
Knapsack problem
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit an ...
, where there is a set of given items. Its goal is to pack the knapsack to get the maximum total value. Each item has some weight and some value. The total weight that can be carried is no more than some fixed number X. So, the solution must consider weights of items as well as their value.
; Quantum algorithm
:
Quantum algorithm
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequ ...
s run on a realistic model of
quantum computation
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
. The term is usually used for those algorithms which seem inherently quantum, or use some essential feature of
Quantum computing
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
such as
quantum superposition
Quantum superposition is a fundamental principle of quantum mechanics. It states that, much like waves in classical physics, any two (or more) quantum states can be added together ("superposed") and the result will be another valid quantum ...
or
quantum entanglement
Quantum entanglement is the phenomenon that occurs when a group of particles are generated, interact, or share spatial proximity in a way such that the quantum state of each particle of the group cannot be described independently of the state of ...
.
By design paradigm
Another way of classifying algorithms is by their design methodology or
paradigm
In science and philosophy, a paradigm () is a distinct set of concepts or thought patterns, including theories, research methods, postulates, and standards for what constitute legitimate contributions to a field.
Etymology
''Paradigm'' comes f ...
. There is a certain number of paradigms, each different from the other. Furthermore, each of these categories includes many different types of algorithms. Some common paradigms are:
;
Brute-force or exhaustive search
: Brute force is a method of problem-solving that involves systematically trying every possible option until the optimal solution is found. This approach can be very time-consuming, as it requires going through every possible combination of variables. However, it is often used when other methods are not available or too complex. Brute force can be used to solve a variety of problems, including finding the shortest path between two points and cracking passwords.
; Divide and conquer
: A
divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually
recursively
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
) until the instances are small enough to solve easily. One such example of divide and conquer is
merge sorting. Sorting can be done on each segment of data after dividing data into segments and sorting of entire data can be obtained in the conquer phase by merging the segments. A simpler variant of divide and conquer is called a ''decrease-and-conquer algorithm'', which solves an identical subproblem and uses the solution of this subproblem to solve the bigger problem. Divide and conquer divides the problem into multiple subproblems and so the conquer stage is more complex than decrease and conquer algorithms. An example of a decrease and conquer algorithm is the
binary search algorithm
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
.
; Search and enumeration
: Many problems (such as playing
chess) can be modeled as problems on
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
s. A
graph exploration algorithm
In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal ...
specifies rules for moving around a graph and is useful for such problems. This category also includes
search algorithm
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with eith ...
s,
branch and bound
Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate soluti ...
enumeration, and
backtracking
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
.
;
Randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
: Such algorithms make some choices randomly (or pseudo-randomly). They can be very useful in finding approximate solutions for problems where finding exact solutions can be impractical (see heuristic method below). For some of these problems, it is known that the fastest approximations must involve some
randomness
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...
. Whether randomized algorithms with
polynomial time complexity can be the fastest algorithm for some problems is an open question known as the
P versus NP problem
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used abov ...
. There are two large classes of such algorithms:
#
Monte Carlo algorithm
In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are Karger–Stein algorithm and Monte Carlo algorithm for minimum Feedba ...
s return a correct answer with high-probability. E.g.
RP is the subclass of these that run in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.
#
Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the ...
s always return the correct answer, but their running time is only probabilistically bound, e.g.
ZPP.
;
Reduction of complexity
: This technique involves solving a difficult problem by transforming it into a better-known problem for which we have (hopefully)
asymptotically optimal
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly en ...
algorithms. The goal is to find a reducing algorithm whose
complexity
Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence.
The term is generall ...
is not dominated by the resulting reduced algorithms. For example, one
selection algorithm
In computer science, a selection algorithm is an algorithm for finding the ''k''th smallest number in a list or array; such a number is called the ''k''th ''order statistic''. This includes the cases of finding the minimum, maximum, and median e ...
for finding the median in an unsorted list involves first sorting the list (the expensive portion) and then pulling out the middle element in the sorted list (the cheap portion). This technique is also known as ''
transform and conquer''.
;
Back tracking
: In this approach, multiple solutions are built incrementally and abandoned when it is determined that they cannot lead to a valid full solution.
Optimization problems
For
optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
s there is a more specific classification of algorithms; an algorithm for such problems may fall into one or more of the general categories described above as well as into one of the following:
;
Linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
: When searching for optimal solutions to a linear function bound to linear equality and inequality constraints, the constraints of the problem can be used directly in producing the optimal solutions. There are algorithms that can solve any problem in this category, such as the popular
simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...
. Problems that can be solved with linear programming include the
maximum flow problem
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such ...
for directed graphs. If a problem additionally requires that one or more of the unknowns must be an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
then it is classified in
integer programming
An integer programming problem is a mathematical optimization or Constraint satisfaction problem, feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programmin ...
. A linear programming algorithm can solve such a problem if it can be proved that all restrictions for integer values are superficial, i.e., the solutions satisfy these restrictions anyway. In the general case, a specialized algorithm or an algorithm that finds approximate solutions is used, depending on the difficulty of the problem.
;
Dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
: When a problem shows optimal substructures—meaning the optimal solution to a problem can be constructed from optimal solutions to subproblems—and
overlapping subproblem In computer science, a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than a ...
s, meaning the same subproblems are used to solve many different problem instances, a quicker approach called ''dynamic programming'' avoids recomputing solutions that have already been computed. For example,
Floyd–Warshall algorithm
In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with p ...
, the shortest path to a goal from a vertex in a weighted
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
can be found by using the shortest path to the goal from all adjacent vertices. Dynamic programming and
memoization
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization ...
go together. The main difference between dynamic programming and divide and conquer is that subproblems are more or less independent in divide and conquer, whereas subproblems overlap in dynamic programming. The difference between dynamic programming and straightforward recursion is in caching or memoization of recursive calls. When subproblems are independent and there is no repetition, memoization does not help; hence dynamic programming is not a solution for all complex problems. By using memoization or maintaining a
table
Table may refer to:
* Table (furniture), a piece of furniture with a flat surface and one or more legs
* Table (landform), a flat area of land
* Table (information), a data arrangement with rows and columns
* Table (database), how the table data ...
of subproblems already solved, dynamic programming reduces the exponential nature of many problems to polynomial complexity.
; The greedy method
: A
greedy algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
is similar to a dynamic programming algorithm in that it works by examining substructures, in this case not of the problem but of a given solution. Such algorithms start with some solution, which may be given or have been constructed in some way, and improve it by making small modifications. For some problems they can find the optimal solution while for others they stop at
local optima
In applied mathematics and computer science, a local optimum of an optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of candidate solutions. This is in contrast to a global optimum, which i ...
, that is, at solutions that cannot be improved by the algorithm but are not optimum. The most popular use of greedy algorithms is for finding the minimal spanning tree where finding the optimal solution is possible with this method.
Huffman Tree
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algor ...
,
Kruskal,
Prim
Prim may refer to:
People
* Prim (given name)
* Prim (surname)
Places
* Prim, Virginia, unincorporated community in King George County
*Dolní Přím, village in the Czech Republic; as Nieder Prim (Lower Prim) site of the Battle of Königgrätz
...
,
Sollin are greedy algorithms that can solve this optimization problem.
;The heuristic method
:In
optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
s,
heuristic algorithm
In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow for finding an approximate solution, or whe ...
s can be used to find a solution close to the optimal solution in cases where finding the optimal solution is impractical. These algorithms work by getting closer and closer to the optimal solution as they progress. In principle, if run for an infinite amount of time, they will find the optimal solution. Their merit is that they can find a solution very close to the optimal solution in a relatively short time. Such algorithms include
local search,
tabu search Tabu search is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986
and formalized in 1989.
Local (neighborhood) searches take a potential solution to a prob ...
,
simulated annealing
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. It ...
, and
genetic algorithm
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to gene ...
s. Some of them, like simulated annealing, are non-deterministic algorithms while others, like tabu search, are deterministic. When a bound on the error of the non-optimal solution is known, the algorithm is further categorized as an
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
.
Legal status
Algorithms, by themselves, are not usually patentable. In the United States, a claim consisting solely of simple manipulations of abstract concepts, numbers, or signals does not constitute "processes" (USPTO 2006), so algorithms are not patentable (as in
Gottschalk v. Benson
''Gottschalk v. Benson'', 409 U.S. 63 (1972), was a Supreme Court of the United States, United States Supreme Court case in which the Court ruled that a process claim directed to a numerical algorithm, as such, was not patentable because "the pate ...
). However practical applications of algorithms are sometimes patentable. For example, in
Diamond v. Diehr
''Diamond v. Diehr'', 450 U.S. 175 (1981), was a United States Supreme Court decision which held that controlling the execution of a physical process, by running a computer program did not preclude patentability of the invention as a whole. The hi ...
, the application of a simple
feedback
Feedback occurs when outputs of a system are routed back as inputs as part of a chain of cause-and-effect that forms a circuit or loop. The system can then be said to ''feed back'' into itself. The notion of cause-and-effect has to be handled ...
algorithm to aid in the curing of
synthetic rubber
A synthetic rubber is an artificial elastomer. They are polymers synthesized from petroleum byproducts. About 32-million metric tons of rubbers are produced annually in the United States, and of that amount two thirds are synthetic. Synthetic rubbe ...
was deemed patentable. The
patenting of software is controversial,
and there are criticized patents involving algorithms, especially
data compression
In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression ...
algorithms, such as
Unisys
Unisys Corporation is an American multinational information technology (IT) services and consulting company headquartered in Blue Bell, Pennsylvania. It provides digital workplace solutions, cloud, applications, and infrastructure solutions, e ...
's
LZW patent. Additionally, some cryptographic algorithms have export restrictions (see
export of cryptography
The export of cryptography is the transfer from one country to another of devices and technology related to cryptography.
In the early days of the Cold War, the United States and its allies developed an elaborate series of export control regulati ...
).
Examples
One of the simplest algorithms is to find the largest number in a list of numbers of random order. Finding the solution requires looking at every number in the list. From this follows a simple algorithm, which can be stated in a high-level description in English prose, as:
''High-level description:''
# If there are no numbers in the set, then there is no highest number.
# Assume the first number in the set is the largest number in the set.
# For each remaining number in the set: if this number is larger than the current largest number, consider this number to be the largest number in the set.
# When there are no numbers left in the set to iterate over, consider the current largest number to be the largest number of the set.
''(Quasi-)formal description:''
Written in prose but much closer to the high-level language of a computer program, the following is the more formal coding of the algorithm in
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
or
pidgin code
In computer programming, pidgin code is a mixture of several programming languages in the same program, or pseudocode that is a mixture of a programming language with natural language descriptions. Hence the name: the mixture is a programming lan ...
:
Input: A list of numbers ''L''.
Output: The largest number in the list ''L''.
if ''L.size'' = 0 return null
''largest'' ← ''L''
for each ''item'' in ''L'', do
if ''item'' > ''largest'', then
''largest'' ← ''item''
return ''largest''
See also
*
Abstract machine
An abstract machine is a computer science theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is analogous to a mathematical function in that it receives inputs and produces outputs based on pre ...
*
ALGOL
ALGOL (; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the ...
*
Algorithm aversion
*
Algorithm engineering
*
Algorithm characterizations
Algorithm characterizations are attempts to formalize the word algorithm. Algorithm does not have a generally accepted formal definition. Researchers are actively working on this problem. This article will present some of the "characterizations" o ...
*
Algorithmic bias
Algorithmic bias describes systematic and repeatable errors in a computer system that create " unfair" outcomes, such as "privileging" one category over another in ways different from the intended function of the algorithm.
Bias can emerge from ...
*
Algorithmic composition
Algorithmic composition is the technique of using algorithms to create music.
Algorithms (or, at the very least, formal sets of rules) have been used to compose music for centuries; the procedures used to plot voice-leading in Western counterpoin ...
*
Algorithmic entities Algorithmic entities refer to autonomous algorithms that operate without human control or interference. Recently, attention is being given to the idea of algorithmic entities being granted (partial or full) legal personhood. Professor Shawn Bayern a ...
*
Algorithmic synthesis
*
Algorithmic technique
*
Algorithmic topology Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular, computational geometry and computational complexity theory.
A primary concern of algorithmic topology, as its ...
*
Garbage in, garbage out
In computer science, garbage in, garbage out (GIGO) is the concept that flawed, or nonsense (garbage) input data produces nonsense output. Rubbish in, rubbish out (RIRO) is an alternate wording.
The principle applies to all logical argumentati ...
* ''
Introduction to Algorithms
''Introduction to Algorithms'' is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The book has been widely used as the textbook for algorithms courses at many universities and is co ...
'' (textbook)
*
Government by algorithm
Government by algorithm (also known as algorithmic regulation, regulation by algorithms, algorithmic governance, algocratic governance, algorithmic legal order or algocracy) is an alternative form of government or social ordering, where the usa ...
*
List of algorithms
The following is a list of well-known algorithms along with one-line descriptions for each.
Automated planning
Combinatorial algorithms
General combinatorial algorithms
* Brent's algorithm: finds a cycle in function value iterations using on ...
*
List of algorithm general topics
This is a list of algorithm general topics.
* Analysis of algorithms
* Ant colony algorithm
* Approximation algorithm
* Best and worst cases
* Big O notation
* Combinatorial search
* Competitive analysis (online algorithm), Competitive analysis
* ...
*
Regulation of algorithms
Regulation of algorithms, or algorithmic regulation, is the creation of laws, rules and public sector policies for promotion and regulation of algorithms, particularly in artificial intelligence and machine learning. For the subset of AI algorith ...
*
Theory of computation
In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., a ...
**
Computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
**
Computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
*
Computational mathematics
Computational mathematics is an area of mathematics devoted to the interaction between mathematics and computer computation.National Science Foundation, Division of Mathematical ScienceProgram description PD 06-888 Computational Mathematics 2006 ...
Notes
Bibliography
*
* Bell, C. Gordon and Newell, Allen (1971), ''Computer Structures: Readings and Examples'', McGraw–Hill Book Company, New York. .
* Includes a bibliography of 56 references.
* ,
* : cf. Chapter 3 ''Turing machines'' where they discuss "certain enumerable sets not effectively (mechanically) enumerable".
*
* Campagnolo, M.L.,
Moore, C., and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In ''Proc. of the 4th Conference on Real Numbers and Computers'', Odense University, pp. 91–109
* Reprinted in ''The Undecidable'', p. 89ff. The first expression of "Church's Thesis". See in particular page 100 (''The Undecidable'') where he defines the notion of "effective calculability" in terms of "an algorithm", and he uses the word "terminates", etc.
* Reprinted in ''The Undecidable'', p. 110ff. Church shows that the Entscheidungsproblem is unsolvable in about 3 pages of text and 3 pages of footnotes.
*
* Davis gives commentary before each article. Papers of
Gödel,
Alonzo Church
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scienc ...
,
Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...
,
Rosser, Kleene, and
Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Govern ...
are included; those cited in the article are listed here by author's name.
* Davis offers concise biographies of Gottfried Leibniz, Leibniz, George Boole, Boole, Gottlob Frege, Frege, Georg Cantor, Cantor, David Hilbert, Hilbert, Gödel and Turing with John von Neumann, von Neumann as the show-stealing villain. Very brief bios of Joseph-Marie Jacquard, Babbage,
Ada Lovelace
Augusta Ada King, Countess of Lovelace (''née'' Byron; 10 December 1815 – 27 November 1852) was an English mathematician and writer, chiefly known for her work on Charles Babbage's proposed mechanical general-purpose computer, the A ...
, Claude Shannon, Howard Aiken, etc.
*
*
*
* ,
* Yuri Gurevich
''Sequential Abstract State Machines Capture Sequential Algorithms'' ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pp. 77–111. Includes bibliography of 33 sources.
* , 3rd edition 1976[?], (pbk.)
* , . Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
* Presented to the American Mathematical Society, September 1935. Reprinted in ''The Undecidable'', p. 237ff. Kleene's definition of "general recursion" (known now as mu-recursion) was used by Church in his 1935 paper ''An Unsolvable Problem of Elementary Number Theory'' that proved the "decision problem" to be "undecidable" (i.e., a negative result).
* Reprinted in ''The Undecidable'', p. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in Kleene 1952:300) and name it "Church's Thesis"(Kleene 1952:317) (i.e., the Church thesis).
*
*
*
* Kosovsky, N.K. ''Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms'', LSU Publ., Leningrad, 1981
*
* A.A. Markov (1954) ''Theory of algorithms''. [Translated by Jacques J. Schorr-Kon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e., Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS .]
* Minsky expands his "...idea of an algorithm – an effective procedure..." in chapter 5.1 ''Computability, Effective Procedures and Algorithms. Infinite machines.''
* Reprinted in ''The Undecidable'', pp. 289ff. Post defines a simple algorithmic-like process of a man writing marks or erasing marks and going from box to box and eventually halting, as he follows a list of simple instructions. This is cited by Kleene as one source of his "Thesis I", the so-called
Church–Turing thesis
In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of comp ...
.
*
* Reprinted in ''The Undecidable'', p. 223ff. Herein is Rosser's famous definition of "effective method": "...a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps... a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer" (p. 225–226, ''The Undecidable'')
*
*
*
*
* Cf. in particular the first chapter titled: ''Algorithms, Turing Machines, and Programs''. His succinct informal definition: "...any sequence of instructions that can be obeyed by a robot, is called an ''algorithm''" (p. 4).
*
* . Corrections, ibid, vol. 43(1937) pp. 544–546. Reprinted in ''The Undecidable'', p. 116ff. Turing's famous paper completed as a Master's dissertation while at King's College Cambridge UK.
* Reprinted in ''The Undecidable'', pp. 155ff. Turing's paper that defined "the oracle" was his PhD thesis while at Princeton.
* United States Patent and Trademark Office (2006)
''2106.02 **>Mathematical Algorithms: 2100 Patentability'' Manual of Patent Examining Procedure (MPEP). Latest revision August 2006
* Zaslavsky, C. (1970). Mathematics of the Yoruba People and of Their Neighbors in Southern Nigeria. The Two-Year College Mathematics Journal, 1(2), 76–99. https://doi.org/10.2307/3027363
Further reading
*
*
*
*
*
*
* Donald Knuth, Knuth, Donald E. (2000).
Selected Papers on Analysis of Algorithms''. Stanford, California: Center for the Study of Language and Information.
* Knuth, Donald E. (2010).
''. Stanford, California: Center for the Study of Language and Information.
*
*
External links
*
*
*
Dictionary of Algorithms and Data Structures– National Institute of Standards and Technology
; Algorithm repositories
The Stony Brook Algorithm Repository– State University of New York at Stony Brook
Collected Algorithms of the ACM– Association for Computing Machinery, Associations for Computing Machinery
The Stanford GraphBase – Stanford University
{{Authority control
Algorithms,
Articles with example pseudocode
Mathematical logic
Theoretical computer science