---
title: Algorithm
slug: algorithm
qid: 
snapshot: enwiki-001376037819
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1376037819
tags: [127661143, 20476448, 22909140, 22909141, 23118434, 23302980, 23603337, 23617849, 24623845, 24723435, 24745122, 25574325, 28269683, 28374593, 49505187, 58064606, 87800745, 89061594, 96369911]
---

# Algorithm

> [!note] Provenance
> Snapshot `enwiki-001376037819` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1376037819> · Licensed CC BY-SA 4.0

of two numbers.|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 numbers in the subtraction loop again. In mathematics and computer science, an algorithm ( ) is any well-defined set of instructions that when followed terminates after a finite number of steps that comprise a solution to a given computational problem. Advanced algorithms may utilize loops and involve many conditionals that decide the next step based on the inputs provided, resulting in long sequences of steps before halting, but all algorithms terminate by definition. In contrast to algorithms, heuristics might be applied to problems for which it is not possible for an algorithmic solution to exist, e.g., because the problem is undecidable or there is otherwise no way to define the correct or optimal result. For example, although social media recommender systems are erroneously called "algorithms" in popular media, they are accurately classified as heuristics, because there is no objective criteria by which a recommendation produced by such a system can be judged as "correct".…

of two numbers.|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 numbers in the subtraction loop again. In mathematics and computer science, an algorithm ( ) is any well-defined set of instructions that when followed terminates after a finite number of steps that comprise a solution to a given computational problem. Advanced algorithms may utilize loops and involve many conditionals that decide the next step based on the inputs provided, resulting in long sequences of steps before halting, but all algorithms terminate by definition. In contrast to algorithms, heuristics might be applied to problems for which it is not possible for an algorithmic solution to exist, e.g., because the problem is undecidable or there is otherwise no way to define the correct or optimal result. For example, although social media recommender systems are erroneously called "algorithms" in popular media, they are accurately classified as heuristics, because there is no objective criteria by which a recommendation produced by such a system can be judged as "correct". As an effective method, an algorithm can be expressed within both a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and input, a computation occurs at each step, eventually producing output and terminating. Randomized algorithms incorporate random inputs which can be used to simulate non-deterministic output even though the transitions between states are deterministic. ==Representations== Algorithms can be expressed in many kinds of notation, including natural languages, pseudocode, flowcharts, drakon-charts, programming languages or control tables. 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 expressions of algorithms that avoid common ambiguities of natural language. Programming languages are primarily for expressing algorithms in a computer-executable form but are also used to define or document algorithms. ===Formal versus empirical=== The analysis, and study of algorithms is a discipline of computer science. Algorithms are often studied abstractly, without referencing a specific programming language or implementation. Like other mathematical disciplines, it focuses on the algorithm's properties, not implementation. Pseudocode is typical for analysis as it is a simple and general representation. Most algorithms are implemented on particular hardware/software platforms and their algorithmic efficiency is tested using real code. The efficiency of a particular algorithm may be insignificant for many "one-off" problems but it can be critical for algorithms designed for fast, interactive, commercial, or long-life scientific usage. Increasing the input size often exposes inefficient algorithms that are otherwise benign. Empirical testing is useful for uncovering unexpected interactions that affect performance. Benchmarks may be used to compare before/after potential improvements to an algorithm after program optimization. Empirical tests cannot fully replace formal analysis, and are difficult to perform fairly. if L.size = 0 return null largest ← L[0] for each item in L, do if item > largest, then largest ← item return largest Algorithm = Logic + Control Algorithm aversion Algorithm engineering Algorithm characterizations Algorithmic bias Algorithmic composition Algorithmic entities Algorithmic synthesis Algorithmic technique Algorithmic topology Computational mathematics Garbage in, garbage out Introduction to Algorithms (textbook) Government by algorithm List of algorithms List of algorithm books List of algorithm general topics Medium is the message Outline of algorithms Regulation of algorithms Theory of computation Computability theory Computational complexity theory Yuri Gurevich, Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pp.&nbsp;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.&nbsp;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.&nbsp;255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p.&nbsp;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.&nbsp;28&nbsp;cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v.&nbsp;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.&nbsp;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. Reprinted in The Undecidable, p.&nbsp;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.&nbsp;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.&nbsp;4). . Corrections, ibid, vol. 43(1937) pp.&nbsp;544–546. Reprinted in The Undecidable, p.&nbsp;116ff. Turing's famous paper completed as a Master's dissertation while at King's College Cambridge UK. Reprinted in The Undecidable, pp.&nbsp;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 NIST Releases First 3 Finalized Post-Quantum Encryption Standards. https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards ==Further reading== Jon Kleinberg, Éva Tardos(2006): Algorithm Design, Pearson/Addison-Wesley, ISBN 978-0-32129535-4 Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms . Stanford, California: Center for the Study of Language and Information. Knuth, Donald E. (2010). Selected Papers on Design of Algorithms . 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 – Associations for Computing Machinery The Stanford GraphBase – Stanford University
