Algorithm (nonfiction): Difference between revisions

From Gnomon Chronicles
Jump to navigation Jump to search
(Created page with "In mathematics (nonfiction) and computer science (nonfiction), an '''algorithm''' is a self-contained step-by-step set of Operation (nonfiction)|operations (nonficti...")
 
No edit summary
 
(20 intermediate revisions by the same user not shown)
Line 1: Line 1:
In [[mathematics (nonfiction)]] and [[computer science (nonfiction)]], an '''algorithm''' is a self-contained step-by-step set of [[Operation (nonfiction)|operations (nonfiction)]] to be performed.
[[File:Euclid's_algorithm.svg|thumb|Flow chart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" (or true) (more accurately the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number b − a replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A.]]In [[Mathematics (nonfiction)|mathematics]] and [[Computer science (nonfiction)|Computer science]], an '''algorithm''' is a self-contained step-by-step set of operations to be performed.


== Description ==
== Quotations ==


Algorithms exist that perform [[calculation (nonfiction)]], [[data processing (nonfiction)]], and [[automated reasoning (nonfiction)]].
Cory Doctorow on Rob Smith's ''Rage Inside the Machine'':


An algorithm is an effective method that can be expressed within a finite amount of [[space (nonfiction)]] and [[time (nonfiction)]] and in a well-defined [[formal language (nonfiction)]] for calculating a [[Mathematical function (nonfiction)|mathematical function (nonfiction)]].
<blockquote>Smith shows how the parts of machine learning that do work refute some of the uglier philosophical ideas that have risen in currency as algorithms have taken over our society -- just as the Victorians had their "blind watchmaker," the rise of evolutionary algorithms has given a new lease on life to eugenic theories about survival of the fittest and the need to purify and protect the "best" among us.</blockquote>


== Process ==
Source: [https://boingboing.net/2019/06/26/kids-mag-highlights-for-c.html Rage Inside the Machine: an insightful, brilliant critique of AI's computer science, sociology, philosophy and economics] by Cory Doctorow @ Boing Boing


Starting from an [[initial state (nonfiction)]] and [[initial input (nonfiction)]] (perhaps [[empty (nonfiction)]]), the [[Instruction (nonfiction)|instructions (nonfiction)]] describe a [[computation (nonfiction)]] that, when [[Execution (nonfiction)|executed (nonfiction)]], proceeds through a [[finite number (nonfiction)]] of [[well-defined successive states (nonfiction)]], eventually producing [[output (nonfiction)]] and [[terminating at a final ending state (nonfiction)]].
== In the News ==


== Randomized algorithms ==
<gallery>
File:Ascleplius Myrmidon Halting Problem.jpg|link=On Halting Problems|Asclepius Myrmidon publishes new analysis of unregistered [[On Halting Problems|halting problem algorithms]], predicts emergence of new algorithms for [[crimes against mathematical constants]].
File:Numbered cake pops.jpg|link=Numbered cake algorithm|[[Numbered cake algorithm]] used to build new type of [[scrying engine]].
</gallery>


The transition from one [[state (nonfiction)]] to the next is not necessarily deterministic; some algorithms, known as [[Randomized algorithm (nonfiction)|randomized algorithms (nonfiction)]], incorporate [[random input (nonfiction)]].
== Fiction cross-reference ==


== History ==
* [[Gnomon Algorithm]]
 
* [[Mathematics]]
The concept of algorithm has existed for centuries, however a partial formalization of what would become the modern algorithm began with attempts to solve the ''[[Entscheidungsproblem (nonfiction)]]'' (the "decision problem") posed by [[David Hilbert (nonfiction)]] in 1928.
 
== Effective calculability ==
 
Subsequent formalizations were framed as attempts to define "effective calculability" or "effective method".
 
Those formalizations included:
 
* The Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935
* [[Alonzo Church (nonfiction)]]'s [[lambda calculus (nonfiction)]] of 1936
* Emil Post's "Formulation 1" of 1936
* [[Alan Turing (nonfiction)]]'s [[Turing machine (nonfiction)|Turing machines (nonfiction)]] of 1936–7 and 1939.
 
Giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem.
 
== Algorithm analysis ==
 
[[Analysis of algorithms (nonfiction)]] is an important part of a broader [[computational complexity theory (nonfiction)]], which provides theoretical estimates for the resources needed by any algorithm which solves a given [[computational problem (nonfiction)]].
 
These estimates provide an insight into reasonable directions of search for [[algorithmic efficiency (nonfiction)]].


== Nonfiction cross-reference ==
== Nonfiction cross-reference ==


* [[Algorithm design (nonfiction)]]
* [[Computer science (nonfiction)]]
* [[Algorithmic efficiency (nonfiction)]]
* [[Breadth-first search (nonfiction)]]
* [[Analysis of algorithms (nonfiction)]]
* [[Depth-first search (nonfiction)]]
* [[Automated reasoning (nonfiction)]]
* [[Automaton (nonfiction)]]
* [[Calculation (nonfiction)]]
* [[Combinatorics (nonfiction)]]
* [[Computational complexity theory (nonfiction)]]
* [[Computational problem (nonfiction)]]
* [[Data processing (nonfiction)]]
* [[Entscheidungsproblem (nonfiction)]]
* [[Function (mathematics) (nonfiction)]]
* [[Genetic algorithm (nonfiction)]]
* [[Gnomon Algorithm (nonfiction)]]
* [[Kruskal's algorithm (nonfiction)]]
* [[Mathematical model (nonfiction)]]
* [[Mathematics (nonfiction)]]
* [[Mathematics (nonfiction)]]
* [[Maze generation algorithm (nonfiction)]]
* [[Prim's algorithm (nonfiction)]] - a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph
* [[Mental model (nonfiction)]]
* [[Theory of computation (nonfiction)]]
* [[Round-off error (nonfiction)]]
* [[Signal processing (nonfiction)]]


== Fiction cross-reference ==
Publications:
 
* ''Numerical Recipes'' - a series of books on algorithms and numerical analysis by William H. Press, Saul A. Teukolsky, William T. Vetterling and Brian P. Flannery. In various editions, the books have been in print since 1986. The most recent edition was published in 2007.


* [[Gnomon Algorithm]]
On the web: [http://numerical.recipes/ numerical.recipes].


== External links ==
External links:


* [https://en.wikipedia.org/wiki/Algorithm Algorithm] @ Wikipedia
* [https://en.wikipedia.org/wiki/Algorithm Algorithm] @ Wikipedia
* [http://fiftyexamples.readthedocs.io/en/latest/algorithms.html Background: Algorithms] @ 50 Examples
* [https://freedom-to-tinker.com/2017/05/31/what-does-it-mean-to-ask-for-an-explainable-algorithm/ What does it mean to ask for an “explainable” algorithm?] by Ed Felten
[[Category:Nonfiction (nonfiction)]]
[[Category:Algorithms (nonfiction)]]
[[Category:Computation (nonfiction)]]
[[Category:Mathematics (nonfiction)]]

Latest revision as of 14:28, 28 June 2019

Flow chart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" (or true) (more accurately the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number b − a replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A.

In mathematics and Computer science, an algorithm is a self-contained step-by-step set of operations to be performed.

Quotations

Cory Doctorow on Rob Smith's Rage Inside the Machine:

Smith shows how the parts of machine learning that do work refute some of the uglier philosophical ideas that have risen in currency as algorithms have taken over our society -- just as the Victorians had their "blind watchmaker," the rise of evolutionary algorithms has given a new lease on life to eugenic theories about survival of the fittest and the need to purify and protect the "best" among us.

Source: Rage Inside the Machine: an insightful, brilliant critique of AI's computer science, sociology, philosophy and economics by Cory Doctorow @ Boing Boing

In the News

Fiction cross-reference

Nonfiction cross-reference

Publications:

  • Numerical Recipes - a series of books on algorithms and numerical analysis by William H. Press, Saul A. Teukolsky, William T. Vetterling and Brian P. Flannery. In various editions, the books have been in print since 1986. The most recent edition was published in 2007.

On the web: numerical.recipes.

External links:

Retrieved from "https://gnomonchronicles.com/w/index.php?title=Algorithm_(nonfiction)&oldid=42351"