Algorithm: Difference between revisions

Revision as of 04:12, 5 August 2024

Revision as of 19:35, 9 August 2024

Line 3:

{{Use mdy dates|date=September 2017}}{{Copyedit|date=April 2024}}

{{Essay|date=April 2024}}

[[File:GCD through successive subtractions.svg|thumb|Flowchart of using successive subtractions to find the [[greatest common divisor]] of number ''r'' and ''s''|alt=In a loop, subtract the larger number against the smaller number. Halt the loop when the subtraction will make a number negative. Assess two numbers, whether one of them is equal to zero or not. If yes, take the other number as the greatest common divisor. If no, put the two numbernumbers in the subtraction loop again.]]

In [[mathematics]] and [[computer science]], an '''algorithm''' ({{IPAc-en|audio=en-us-algorithm.ogg|ˈ|æ|l|ɡ|ə|r|ɪ|ð|əm}}) is a [[mwod:finite|finite]] sequence of [[Rigour#Mathematics|mathematically rigorous]] instructions, typically used to solve a class of specific [[Computational problem|problem]]s or to perform a [[computation]].<ref name=":0">{{Cite web|url=https://www.merriam-webster.com/dictionary/algorithm|title=Definition of ALGORITHM|work=Merriam-Webster Online Dictionary |language=en |access-date=2019-11-14 |archive-url=https://web.archive.org/web/20200214074446/https://www.merriam-webster.com/dictionary/algorithm |archive-date=February 14, 2020|url-status=live}}</ref> Algorithms are used as specifications for performing [[calculation]]s and [[data processing]]. More advanced algorithms can use [[Conditional (computer programming)|conditional]]s to divert the code execution through various routes (referred to as [[automated decision-making]]) and deduce valid [[inference]]s (referred to as [[automated reasoning]]), achieving [[automation]] eventually. Using human characteristics as descriptors of machines in metaphorical ways was already practiced by [[Alan Turing]] with terms such as "memory", "search" and "stimulus".<ref name=":1">Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia and Grafton, Anthony. Information: A Historical Companion, Princeton: Princeton University Press, 2021. p. 247</ref>

In contrast, a [[Heuristic (computer science) |heuristic]]] 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.<ref name=":2">David A. Grossman, Ophir Frieder, ''Information Retrieval: Algorithms and Heuristics'', 2nd edition, 2004, {{isbn|1402030045}}</ref> For example, social media [[recommender system]]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]], an algorithm can be expressed within a finite amount of space and time<ref name=":3">"Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).</ref> and in a well-defined [[formal language]]<ref name=":4">Well defined with respect toconcerning the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).</ref> for calculating a [[Function (mathematics)|function]].<ref>"an algorithm is a procedure for computing a ''function'' (with respect toconcerning some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).</ref> Starting from an initial state and initial input (perhaps [[Empty string|empty]]),<ref>"An algorithm has [[zero]] or more inputs, i.e., [[Quantity|quantities]] which are given to it initially before the algorithm begins" (Knuth 1973:5).</ref> the instructions describe a computation that, when [[Execution (computing)|execute]]d, proceeds through a finite<ref>"A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method{{'"}} (Knuth 1973:5).</ref> number of well-defined successive states, eventually producing "output"<ref>"An algorithm has one or more outputs, i.e., quantities which have a specified relation to the inputs" (Knuth 1973:5).</ref> and terminating at a final ending state. The transition from one state to the next is not necessarily [[deterministic]]; some algorithms, known as [[randomized algorithm]]s, incorporate random input.<ref>Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without the use of continuous methods or analogueanalog devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers 1987:2).</ref>

== Etymology ==

Around 825 AD, Persian scientist, and polymath [[Al-Khwarizmi|Muḥammad ibn Mūsā al-Khwārizmī]] 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").<ref name=":0" /> In the early 12th century, Latin translations of said al-Khwarizmi texts involving the [[Hindu–Arabic numeral system]] and [[arithmetic]] appeared, for example ''Liber Alghoarismi de practica arismetrice'', attributed to [[John of Seville]], and ''Liber Algorismi de numero Indorum'', attributed to [[Adelard of Bath]].<ref name=":1" /> Hereby, ''alghoarismi'' or ''algorismi'' is the [[Latinisation of names|Latinization]] of Al-Khwarizmi's name; the text starts with the phrase ''Dixit Algorismi'', or "Thus spoke Al-Khwarizmi".<ref name=":2" /> Around 1230, the English word ''[[algorism]]'' is attested and then by [[Geoffrey Chaucer|Chaucer]] in 1391, English adopted the French term.<ref name=":3" /><ref name=":4" />{{Clarification needed|date=April 2024}} In the 15th century, under the influence of the Greek word ἀριθμός (''arithmos'', "number"; ''cf.'' "arithmetic"), the Latin word was altered to ''algorithmus''.{{Citation needed|date=April 2024}}

== Definition ==

{{For|a detailed presentation of the various points of view on the definition of "algorithm"|Algorithm characterizations}}

One informal definition is "a set of rules that precisely defines a sequence of operations",<ref>Stone 1973:4</ref>{{request quotation | reason = Stone (1972) suggests on page 4: "...any sequence of instructions that cana berobot obeyedcan by a robotobey, is called an algorithm"|date=July 2020}} which would include all [[computer program]]s (including programs that do not perform numeric calculations), and (for example) any prescribed [[bureaucratic]] procedure<ref>

{{cite book |last1=Simanowski |first1=Roberto |author-link1=Roberto Simanowski |url=https://books.google.com/books?id=RJV5DwAAQBAJ |title=The Death Algorithm and Other Digital Dilemmas |date=2018 |publisher=MIT Press |isbn=9780262536370 |series=Untimely Meditations |volume=14 |___location=Cambridge, Massachusetts |page=147 |translator1-last=Chase |translator1-first=Jefferson |quote=[...] the next level of abstraction of central bureaucracy: globally operating algorithms. |access-date=27 May 2019 |archive-url=https://web.archive.org/web/20191222120705/https://books.google.com/books?id=RJV5DwAAQBAJ |archive-date=December 22, 2019 |url-status=live}}

</ref>

Line 23:

</ref> In general, a program is an algorithm only if it stops eventually<ref>Stone requires that "it must terminate in a finite number of steps" (Stone 1973:7–8).</ref>—even though [[infinite loop#Intentional looping|infinite loop]]s may sometimes prove desirable. {{Harvtxt|Boolos|Jeffrey|1974, 1999|ref=CITEREFBoolosJeffrey1999}} 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''.''<ref>Boolos and Jeffrey 1974,1999:19</ref>

The concept of ''algorithm'' is also used to define the notion of [[decidability (logic)|decidability]]—a—an notionidea that is central for explaining how [[formal system]]s come into being starting from a small set of [[axiom]]s and rules. In [[logic]], the time that an algorithm requires to complete cannot be measured, as it is not apparently relatedunrelated to the customary physical dimension. From suchSuch uncertainties, that characterize ongoing work, stemsstem from 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 [[Implementation|implement]]ed as [[computer program]]s. However, algorithms are also implemented by other means, such as in a [[biological neural network]] (for example, the [[human brain]] implementing [[arithmetic]] or an insect looking for food), in an [[electrical circuit]], or in a mechanical device.

== History ==