List of algorithms: Difference between revisions

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
VisualWikitext
imported>SdkbBot
m Removed erroneous space and general fixes (task 1)
 
imported>Comp.arch
mNo edit summary
 
(One intermediate revision by one other user not shown)
Line 2: Line 2:
An [[algorithm]] is fundamentally a set of rules or defined procedures that is typically designed and used to solve a specific problem or a broad set of problems.
An [[algorithm]] is fundamentally a set of rules or defined procedures that is typically designed and used to solve a specific problem or a broad set of problems.


Broadly, algorithms define process(es), sets of rules, or methodologies that are to be followed in calculations, data processing, data mining, pattern recognition, automated reasoning or other problem-solving operations. With the increasing automation of services, more and more decisions are being made by algorithms. Some general examples are; risk assessments, anticipatory policing, and pattern recognition technology.<ref>{{Cite web |title=algorithm |url=https://www.law.cornell.edu/wex/algorithm |access-date=2023-10-26 |website=LII / Legal Information Institute |language=en}}</ref>
Broadly, algorithms define process(es), sets of rules, or methodologies that are to be followed in calculations, data processing, data mining, pattern recognition, automated reasoning or other problem-solving operations. With the increasing automation of services, more and more decisions are being made by algorithms. Some general examples are risk assessments, anticipatory policing, and pattern recognition technology.<ref>{{Cite web |title=algorithm |url=https://www.law.cornell.edu/wex/algorithm |access-date=2023-10-26 |website=LII / Legal Information Institute |language=en}}</ref>


The following is a '''list of well-known algorithms''' along with one-line descriptions for each.
The following is a '''list of well-known algorithms'''.


==Automated planning==
==Automated planning==
Line 15: Line 15:
* [[Cycle detection#Brent's algorithm|Brent's algorithm]]: finds a cycle in function value iterations using only two iterators<ref>{{Cite journal |last=Gegenfurtner |first=Karl R. |date=1992-12-01 |title=PRAXIS: Brent's algorithm for function minimization |journal=Behavior Research Methods, Instruments, & Computers |language=en |volume=24 |issue=4 |pages=560–564 |doi=10.3758/BF03203605 |issn=1532-5970|doi-access=free }}</ref>
* [[Cycle detection#Brent's algorithm|Brent's algorithm]]: finds a cycle in function value iterations using only two iterators<ref>{{Cite journal |last=Gegenfurtner |first=Karl R. |date=1992-12-01 |title=PRAXIS: Brent's algorithm for function minimization |journal=Behavior Research Methods, Instruments, & Computers |language=en |volume=24 |issue=4 |pages=560–564 |doi=10.3758/BF03203605 |issn=1532-5970|doi-access=free }}</ref>
* [[Floyd's cycle-finding algorithm]]: finds a cycle in function value iterations<ref>{{Cite web |date=2013-09-30 |title=richardshin.com {{!}} Floyd's Cycle Detection Algorithm |url=http://www.richardshin.com/floyds-cycle-detection-algorithm/ |access-date=2023-10-26 |language=en-US}}</ref>
* [[Floyd's cycle-finding algorithm]]: finds a cycle in function value iterations<ref>{{Cite web |date=2013-09-30 |title=richardshin.com {{!}} Floyd's Cycle Detection Algorithm |url=http://www.richardshin.com/floyds-cycle-detection-algorithm/ |access-date=2023-10-26 |language=en-US}}</ref>
* [[Gale–Shapley algorithm]]: solves the [[stable matching problem]]<ref>{{cite web |author=Tesler, G.|url=https://mathweb.ucsd.edu/~gptesler/154/slides/154_galeshapley_20-handout.pdf|website=mathweb.ucsd.edu|title=Ch. 5.9: Gale-Shapley Algorithm|date= 2020|publisher=[[University of California San Diego]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref><ref>{{cite web|last1=Kleinberg|first1=Jon |last2=Tardos|first2=Éva |url=https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf|website=www.cs.princeton.edu|title=Algorithmn Design: 1. Stable Matching|date= 2005|publisher=[[Pearson PLC|Pearson]]-[[Addison Wesley]]: [[Princeton University]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref><ref>{{cite web |last1=Goel|first1=Ashish |editor1-last=Ramseyer|editor1-first=Geo |url=https://web.stanford.edu/~ashishg/cs261/win21/notes/l5_note.pdf|website=web.stanford.edu|title=CS261 Winter 2018- 2019 Lecture 5: Gale-Shapley Algorith|date= 21 January 2019|publisher=[[Stanford University]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref>
* [[Gale–Shapley algorithm]]: solves the [[stable matching problem]]<ref>{{cite web |author=Tesler, G.|url=https://mathweb.ucsd.edu/~gptesler/154/slides/154_galeshapley_20-handout.pdf|website=mathweb.ucsd.edu|title=Ch. 5.9: Gale-Shapley Algorithm|date= 2020|publisher=[[University of California San Diego]]|access-date=26 April 2025}}</ref><ref>{{cite web|last1=Kleinberg|first1=Jon |last2=Tardos|first2=Éva |url=https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf|website=cs.princeton.edu|title=Algorithmn Design: 1. Stable Matching|date= 2005|publisher=[[Pearson PLC|Pearson]]-[[Addison Wesley]]: [[Princeton University]]|access-date=26 April 2025}}</ref><ref>{{cite web |last=Goel|first=Ashish |editor-last=Ramseyer|editor-first=Geo |url=https://web.stanford.edu/~ashishg/cs261/win21/notes/l5_note.pdf|website=web.stanford.edu|title=CS261 Winter 2018- 2019 Lecture 5: Gale-Shapley Algorith|date= 21 January 2019|publisher=[[Stanford University]]|access-date=26 April 2025}}</ref>
* [[Pseudorandom number generator]]s (uniformly distributed—see also [[List of random number generators#Pseudorandom number generators (PRNGs)|List of pseudorandom number generators]] for other PRNGs with varying degrees of convergence and varying statistical quality):{{citation needed|date=June 2024}}
* [[Pseudorandom number generator]]s (uniformly distributed—see also [[List of random number generators#Pseudorandom number generators (PRNGs)|List of pseudorandom number generators]] for other PRNGs with varying degrees of convergence and varying statistical quality):{{citation needed|date=June 2024}}
** [[ACORN (PRNG)|ACORN generator]]
** [[ACORN (PRNG)|ACORN generator]]
Line 24: Line 24:


===Graph algorithms===
===Graph algorithms===
{{further|Graph theory|:Category:Graph algorithms}}
{{further|:Category:Graph algorithms|Graph theory}}
* [[Coloring algorithm]]: Graph coloring algorithm.
* [[Coloring algorithm]]: Graph coloring algorithm.
* [[Hopcroft–Karp algorithm]]: convert a bipartite graph to a [[maximum cardinality matching]]
* [[Hopcroft–Karp algorithm]]: convert a bipartite graph to a [[maximum cardinality matching]]
* [[Hungarian algorithm]]: algorithm for finding a [[perfect matching]]
* [[Hungarian algorithm]]: algorithm for finding a [[perfect matching]]
* [[Prüfer sequence|Prüfer coding]]: conversion between a labeled tree and its [[Prüfer sequence]]
* [[Prüfer coding]]: conversion between a labeled tree and its [[Prüfer sequence]]
* [[Tarjan's off-line lowest common ancestors algorithm]]: computes [[lowest common ancestor]]s for pairs of nodes in a tree
* [[Tarjan's off-line lowest common ancestors algorithm]]: computes [[lowest common ancestor]]s for pairs of nodes in a tree
* [[Topological sorting|Topological sort]]: finds linear order of nodes (e.g. jobs) based on their dependencies.
* [[Topological sorting|Topological sort]]: finds linear order of nodes (e.g. jobs) based on their dependencies.
Line 63: Line 63:
** [[Reverse-delete algorithm]]
** [[Reverse-delete algorithm]]
* [[Nonblocking minimal spanning switch]] say, for a [[telephone exchange]]
* [[Nonblocking minimal spanning switch]] say, for a [[telephone exchange]]
* [[Vehicle routing problem]]
** Clarke and Wright Saving algorithm
* [[Shortest path problem]]
* [[Shortest path problem]]
** [[Bellman–Ford algorithm]]: computes [[shortest path problem|shortest paths]] in a weighted graph (where some of the edge weights may be negative)
** [[Bellman–Ford algorithm]]: computes [[shortest path problem|shortest paths]] in a weighted graph (where some of the edge weights may be negative)
Line 75: Line 73:
** [[Christofides algorithm]]
** [[Christofides algorithm]]
** [[Nearest neighbour algorithm]]
** [[Nearest neighbour algorithm]]
* [[Vehicle routing problem]]
** Clarke and Wright Saving algorithm
* [[Warnsdorff's rule]]: a heuristic method for solving the [[Knight's tour]] problem
* [[Warnsdorff's rule]]: a heuristic method for solving the [[Knight's tour]] problem


====Graph search====
====Graph search====
{{further|State space search|Graph search algorithm}}
{{further|Graph search algorithm|State space search}}
* [[A* search algorithm|A*]]: special case of best-first search that uses heuristics to improve speed
* [[A* search algorithm|A*]]: special case of best-first search that uses heuristics to improve speed
* [[B*]]: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals)
* [[B*]]: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals)
Line 95: Line 95:
* [[Jump point search]]: an optimization to A* which may reduce computation time by an order of magnitude using further heuristics
* [[Jump point search]]: an optimization to A* which may reduce computation time by an order of magnitude using further heuristics
* [[Lexicographic breadth-first search]] (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph
* [[Lexicographic breadth-first search]] (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph
* [[SSS*]]: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm
* [[Uniform-cost search]]: a [[Tree traversal|tree search]] that finds the lowest-cost route where costs vary
* [[Uniform-cost search]]: a [[Tree traversal|tree search]] that finds the lowest-cost route where costs vary
* [[SSS*]]: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm


====Subgraphs====
====Subgraphs====
Line 103: Line 103:
** [[MaxCliqueDyn maximum clique algorithm]]: find a [[maximum clique]] in an undirected graph
** [[MaxCliqueDyn maximum clique algorithm]]: find a [[maximum clique]] in an undirected graph
* [[Strongly connected components]]
* [[Strongly connected components]]
** [[Kosaraju's algorithm]]
** [[Path-based strong component algorithm]]
** [[Path-based strong component algorithm]]
** [[Kosaraju's algorithm]]
** [[Tarjan's strongly connected components algorithm]]
** [[Tarjan's strongly connected components algorithm]]
* [[Subgraph isomorphism problem]]
* [[Subgraph isomorphism problem]]
Line 130: Line 130:
====Selection algorithms====
====Selection algorithms====
{{main|Selection algorithm}}
{{main|Selection algorithm}}
* [[Introselect]]
* [[Quickselect]]
* [[Quickselect]]
* [[Introselect]]


====Sequence search====
====Sequence search====
* [[Linear search]]: locates an item in an unsorted sequence
* [[Linear search]]: locates an item in an unsorted sequence
* [[Selection algorithm]]: finds the ''k''th largest item in a sequence
* [[Selection algorithm]]: finds the ''k''th largest item in a sequence
* [[Ternary search]]: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa
* [[Sorted list]]s
* [[Sorted list]]s
** [[Binary search algorithm]]: locates an item in a sorted sequence
** [[Binary search algorithm]]: locates an item in a sorted sequence
** [[Eytzinger binary search]]: cache friendly binary search algorithm <ref>{{Cite web |title=Eytzinger Binary Search - Algorithmica |url=https://algorithmica.org/en/eytzinger |access-date=2023-04-09}}</ref>
** [[Fibonacci search technique]]: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of [[Fibonacci numbers]]
** [[Fibonacci search technique]]: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of [[Fibonacci numbers]]
** [[Jump search]] (or block search): linear search on a smaller subset of the sequence
** [[Jump search]] (or block search): linear search on a smaller subset of the sequence
** [[Interpolation search|Predictive search]]: binary-like search which factors in [[magnitude (mathematics)|magnitude]] of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search.
** [[Interpolation search|Predictive search]]: binary-like search which factors in [[magnitude (mathematics)|magnitude]] of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search.
** [[Uniform binary search]]: an optimization of the classic binary search algorithm
** [[Uniform binary search]]: an optimization of the classic binary search algorithm
** [[Eytzinger binary search]]: cache friendly binary search algorithm <ref>{{Cite web |title=Eytzinger Binary Search - Algorithmica |url=https://algorithmica.org/en/eytzinger |access-date=2023-04-09}}</ref>
* [[Ternary search]]: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa


====Sequence merging====
====Sequence merging====
{{main|Merge algorithm}}
{{main|Merge algorithm}}
* [[k-way merge algorithm]]
* Simple merge algorithm
* Simple merge algorithm
* [[k-way merge algorithm]]
* Union (merge, with elements on the output not repeated)
* Union (merge, with elements on the output not repeated)


Line 154: Line 154:
{{further|Permutation}}
{{further|Permutation}}
* [[Fisher–Yates shuffle]] (also known as the Knuth shuffle): randomly shuffle a finite set
* [[Fisher–Yates shuffle]] (also known as the Knuth shuffle): randomly shuffle a finite set
* [[Heap's algorithm|Heap's permutation generation algorithm]]: interchange elements to generate next permutation
* [[Schensted algorithm]]: constructs a pair of [[Young tableau]]x from a permutation
* [[Schensted algorithm]]: constructs a pair of [[Young tableau]]x from a permutation
* [[Steinhaus–Johnson–Trotter algorithm]] (also known as the Johnson–Trotter algorithm): generates permutations by transposing elements
* [[Steinhaus–Johnson–Trotter algorithm]] (also known as the Johnson–Trotter algorithm): generates permutations by transposing elements
* [[Heap's algorithm|Heap's permutation generation algorithm]]: interchange elements to generate next permutation


====Sequence combinations====
====Sequence combinations====
Line 182: Line 182:
** [[Slowsort]]
** [[Slowsort]]
** [[Stooge sort]]
** [[Stooge sort]]
** [[Stalin sort]]: all elements that are not in order are removed from the list<ref>{{cite web | title=A "Sorting" algorithm | website=Code Golf Stack Exchange | date=October 30, 2018 | url=https://codegolf.stackexchange.com/questions/174964/a-sorting-algorithm | access-date=April 4, 2025}}</ref>
* Hybrid
* Hybrid
** [[Flashsort]]
** [[Flashsort]]
Line 188: Line 187:
** [[Timsort]]: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7.
** [[Timsort]]: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7.
* Insertion sorts
* Insertion sorts
** [[Cycle sort]]: in-place with theoretically optimal number of writes
** [[Insertion sort]]: determine where the current item belongs in the list of sorted ones, and insert it there
** [[Insertion sort]]: determine where the current item belongs in the list of sorted ones, and insert it there
** [[Library sort]]
** [[Library sort]]
Line 193: Line 193:
** [[Shellsort|Shell sort]]: an attempt to improve insertion sort
** [[Shellsort|Shell sort]]: an attempt to improve insertion sort
** [[Tree sort]] (binary tree sort): build binary tree, then traverse it to create sorted list
** [[Tree sort]] (binary tree sort): build binary tree, then traverse it to create sorted list
** [[Cycle sort]]: in-place with theoretically optimal number of writes
* Merge sorts
* Merge sorts
** [[Merge sort]]: sort the first and second half of the list separately, then merge the sorted lists
** [[Merge sort]]: sort the first and second half of the list separately, then merge the sorted lists
Line 229: Line 228:
* [[Kadane's algorithm]]: finds the contiguous subarray with largest sum in an array of numbers
* [[Kadane's algorithm]]: finds the contiguous subarray with largest sum in an array of numbers
* [[Longest common substring problem]]: find the longest string (or strings) that is a substring (or are substrings) of two or more strings
* [[Longest common substring problem]]: find the longest string (or strings) that is a substring (or are substrings) of two or more strings
* [[Matching wildcards]]
** [[Krauss matching wildcards algorithm]]: an open-source non-recursive algorithm
** [[InterNetNews|Rich Salz]]' [[wildmat]]: a widely used [[Open-source software|open-source]] [[recursion|recursive]] algorithm
* [[Substring search]]
* [[Substring search]]
** [[Aho–Corasick string matching algorithm]]: [[trie]] based algorithm for finding all substring matches to any of a finite set of strings
** [[Aho–Corasick string matching algorithm]]: [[trie]] based algorithm for finding all substring matches to any of a finite set of strings
** [[Boyer–Moore–Horspool algorithm]]: Simplification of Boyer–Moore
** [[Boyer–Moore string-search algorithm]]: amortized linear ([[sublinear]] in most times) algorithm for substring search
** [[Boyer–Moore string-search algorithm]]: amortized linear ([[sublinear]] in most times) algorithm for substring search
** [[Boyer–Moore–Horspool algorithm]]: Simplification of Boyer–Moore
** [[Knuth–Morris–Pratt algorithm]]: substring search which bypasses reexamination of matched characters
** [[Knuth–Morris–Pratt algorithm]]: substring search which bypasses reexamination of matched characters
** [[Rabin–Karp string search algorithm]]: searches multiple patterns efficiently
** [[Rabin–Karp string search algorithm]]: searches multiple patterns efficiently
** [[Zhu–Takaoka string matching algorithm]]: a variant of Boyer–Moore
** [[Zhu–Takaoka string matching algorithm]]: a variant of Boyer–Moore
* [[Ukkonen's algorithm]]: a [[linear-time]], [[online algorithm]] for constructing [[suffix tree]]s
* [[Ukkonen's algorithm]]: a [[linear-time]], [[online algorithm]] for constructing [[suffix tree]]s
* [[Matching wildcards]]
** [[InterNetNews|Rich Salz]]' [[wildmat]]: a widely used [[Open-source software|open-source]] [[recursion|recursive]] algorithm
** [[Krauss matching wildcards algorithm]]: an open-source non-recursive algorithm


==Computational mathematics==
==Computational mathematics==
Line 270: Line 269:
* [[Cone algorithm]]: identify surface points
* [[Cone algorithm]]: identify surface points
* [[Convex hull algorithms]]: determining the [[convex hull]] of a [[Set (mathematics)|set]] of points
* [[Convex hull algorithms]]: determining the [[convex hull]] of a [[Set (mathematics)|set]] of points
** [[Chan's algorithm]]
** [[Gift wrapping algorithm]] or Jarvis march
** [[Graham scan]]
** [[Graham scan]]
** [[Kirkpatrick–Seidel algorithm]]
** [[Quickhull]]
** [[Quickhull]]
** [[Gift wrapping algorithm]] or Jarvis march
** [[Chan's algorithm]]
** [[Kirkpatrick–Seidel algorithm]]
* [[Euclidean distance map|Euclidean distance transform]]: computes the distance between every point in a grid and a discrete collection of points.
* [[Euclidean distance map|Euclidean distance transform]]: computes the distance between every point in a grid and a discrete collection of points.
* [[Geometric hashing]]: a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an [[affine transformation]]
* [[Geometric hashing]]: a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an [[affine transformation]]
Line 292: Line 291:
* [[Triangulation (geometry)|Triangulation]]
* [[Triangulation (geometry)|Triangulation]]
** [[Delaunay triangulation]]
** [[Delaunay triangulation]]
*** [[Chew's second algorithm]]: create quality [[constrained Delaunay triangulation]]s
*** [[Ruppert's algorithm]] (also known as Delaunay refinement): create quality Delaunay triangulations
*** [[Ruppert's algorithm]] (also known as Delaunay refinement): create quality Delaunay triangulations
*** [[Chew's second algorithm]]: create quality [[constrained Delaunay triangulation]]s
** [[Marching triangles]]: reconstruct two-dimensional surface geometry from an unstructured [[point cloud]]
** [[Marching triangles]]: reconstruct two-dimensional surface geometry from an unstructured [[point cloud]]
** [[Polygon triangulation]] algorithms: decompose a polygon into a set of triangles
** [[Polygon triangulation]] algorithms: decompose a polygon into a set of triangles
** [[Quasitriangulation]]
** [[Voronoi diagram]]s, geometric [[duality (mathematics)|dual]] of [[Delaunay triangulation]]
** [[Voronoi diagram]]s, geometric [[duality (mathematics)|dual]] of [[Delaunay triangulation]]
*** [[Bowyer–Watson algorithm]]: create voronoi diagram in any number of dimensions
*** [[Bowyer–Watson algorithm]]: create voronoi diagram in any number of dimensions
*** [[Fortune's Algorithm]]: create voronoi diagram
*** [[Fortune's Algorithm]]: create voronoi diagram
** [[Quasitriangulation]]


===Number theoretic algorithms===
===Number theoretic algorithms===
Line 309: Line 308:
** [[Baby-step giant-step]]
** [[Baby-step giant-step]]
** [[Index calculus algorithm]]
** [[Index calculus algorithm]]
** [[Pohlig–Hellman algorithm]]
** [[Pollard's rho algorithm for logarithms]]
** [[Pollard's rho algorithm for logarithms]]
** [[Pohlig–Hellman algorithm]]
* [[Euclidean algorithm]]: computes the [[greatest common divisor]]
* [[Euclidean algorithm]]: computes the [[greatest common divisor]]
* [[Extended Euclidean algorithm]]: also solves the equation ''ax''&nbsp;+&nbsp;''by''&nbsp;=&nbsp;''c''
* [[Extended Euclidean algorithm]]: also solves the equation ''ax''&nbsp;+&nbsp;''by''&nbsp;=&nbsp;''c''
Line 326: Line 325:
** [[Special number field sieve]]
** [[Special number field sieve]]
** [[Trial division]]
** [[Trial division]]
* [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|Lenstra–Lenstra–Lovász algorithm]] (also known as LLL algorithm): find a short, nearly orthogonal [[Lattice (group)|lattice]] [[Basis (linear algebra)|basis]] in polynomial time
* [[Modular square root]]: computing square roots modulo a prime number
** [[Berlekamp's root finding algorithm]]
** [[Cipolla's algorithm]]
** [[Tonelli–Shanks algorithm]]
* [[Multiplication algorithm]]s: fast multiplication of two numbers
* [[Multiplication algorithm]]s: fast multiplication of two numbers
** [[Karatsuba algorithm]]
** [[Karatsuba algorithm]]
** [[Schönhage–Strassen algorithm]]
** [[Schönhage–Strassen algorithm]]
** [[Toom–Cook multiplication]]
** [[Toom–Cook multiplication]]
* [[Modular square root]]: computing square roots modulo a prime number
** [[Tonelli–Shanks algorithm]]
** [[Cipolla's algorithm]]
** [[Berlekamp's root finding algorithm]]
* [[Odlyzko&ndash;Schönhage algorithm]]: calculates nontrivial zeroes of the [[Riemann zeta function]]
* [[Odlyzko&ndash;Schönhage algorithm]]: calculates nontrivial zeroes of the [[Riemann zeta function]]
* [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|Lenstra–Lenstra–Lovász algorithm]] (also known as LLL algorithm): find a short, nearly orthogonal [[Lattice (group)|lattice]] [[Basis (linear algebra)|basis]] in polynomial time
* [[Primality test]]s: determining whether a given number is [[prime number|prime]]
* [[Primality test]]s: determining whether a given number is [[prime number|prime]]
** [[AKS primality test]]
** [[AKS primality test]]
Line 347: Line 346:


===Numerical algorithms===
===Numerical algorithms===
{{further|Numerical analysis|List of numerical analysis topics}}
{{further|List of numerical analysis topics|Numerical analysis}}


====Differential equation solving====
====Differential equation solving====
{{further|Differential equation}}
{{further|Differential equation}}
* [[Backward Euler method]]
* [[Euler method]]
* [[Euler method]]
* [[Backward Euler method]]
* [[Trapezoidal rule (differential equations)]]
* [[Linear multistep method]]s
* [[Linear multistep method]]s
* [[Runge–Kutta methods]]
** [[Euler integration]]
* [[Multigrid method]]s (MG methods), a group of algorithms for solving differential equations using a hierarchy of discretizations
* [[Multigrid method]]s (MG methods), a group of algorithms for solving differential equations using a hierarchy of discretizations
* [[Partial differential equation]]:
* [[Partial differential equation]]:
** [[Crank–Nicolson method]] for diffusion equations
** [[Finite difference method]]
** [[Finite difference method]]
** [[Crank–Nicolson method]] for diffusion equations
** [[Lax–Wendroff method|Lax–Wendroff]] for wave equations
** [[Lax–Wendroff method|Lax–Wendroff]] for wave equations
* [[Runge–Kutta methods]]
** [[Euler integration]]
* [[Trapezoidal rule (differential equations)]]
* [[Verlet integration]] ({{IPA|fr|vɛʁˈlɛ}}): integrate Newton's equations of motion
* [[Verlet integration]] ({{IPA|fr|vɛʁˈlɛ}}): integrate Newton's equations of motion


Line 367: Line 366:
{{further|Special functions}}
{{further|Special functions}}
* [[Computing π|Computation of π]]:
* [[Computing π|Computation of π]]:
** [[Bailey–Borwein–Plouffe formula]]: (BBP formula) a spigot algorithm for the computation of the nth binary digit of π
** [[Borwein's algorithm]]: an algorithm to calculate the value of 1/π
** [[Borwein's algorithm]]: an algorithm to calculate the value of 1/π
** [[Chudnovsky algorithm]]: a fast method for calculating the digits of π
** [[Gauss–Legendre algorithm]]: computes the digits of [[pi]]
** [[Gauss–Legendre algorithm]]: computes the digits of [[pi]]
** [[Chudnovsky algorithm]]: a fast method for calculating the digits of π
** [[Bailey–Borwein–Plouffe formula]]: (BBP formula) a spigot algorithm for the computation of the nth binary digit of π
* [[Division algorithm]]s: for computing quotient and/or remainder of two numbers
* [[Division algorithm]]s: for computing quotient and/or remainder of two numbers
** [[Goldschmidt division]]
** [[Long division]]
** [[Long division]]
** [[Newton–Raphson division]]: uses [[Newton's method]] to find the [[Multiplicative inverse|reciprocal]] of D, and multiply that reciprocal by N to find the final quotient Q.
** [[Non-restoring division]]
** [[Restoring division]]
** [[Restoring division]]
** [[Non-restoring division]]
** [[SRT division]]
** [[SRT division]]
** [[Newton–Raphson division]]: uses [[Newton's method]] to find the [[Multiplicative inverse|reciprocal]] of D, and multiply that reciprocal by N to find the final quotient Q.
* Exponentiation:
** [[Goldschmidt division]]
** [[Addition-chain exponentiation]]: exponentiation by positive integer powers that requires a minimal number of multiplications
** [[Exponentiating by squaring]]: an algorithm used for the fast computation of [[Arbitrary-precision arithmetic|large integer]] powers of a number
* Hyperbolic and Trigonometric Functions:
* Hyperbolic and Trigonometric Functions:
** [[BKM algorithm]]: computes [[Elementary function (differential algebra)|elementary functions]] using a table of logarithms
** [[BKM algorithm]]: computes [[Elementary function (differential algebra)|elementary functions]] using a table of logarithms
** [[CORDIC]]: computes hyperbolic and trigonometric functions using a table of arctangents
** [[CORDIC]]: computes hyperbolic and trigonometric functions using a table of arctangents
* Exponentiation:
** [[Addition-chain exponentiation]]: exponentiation by positive integer powers that requires a minimal number of multiplications
** [[Exponentiating by squaring]]: an algorithm used for the fast computation of [[Arbitrary-precision arithmetic|large integer]] powers of a number
* [[Montgomery reduction]]: an algorithm that allows [[modular arithmetic]] to be performed efficiently when the modulus is large
* [[Montgomery reduction]]: an algorithm that allows [[modular arithmetic]] to be performed efficiently when the modulus is large
* [[Multiplication algorithm]]s: fast multiplication of two numbers
* [[Multiplication algorithm]]s: fast multiplication of two numbers
Line 409: Line 408:


====Interpolation and extrapolation====
====Interpolation and extrapolation====
{{further|Interpolation|Extrapolation}}
{{further|Extrapolation|Interpolation}}
* [[Birkhoff interpolation]]: an extension of polynomial interpolation
* [[Birkhoff interpolation]]: an extension of polynomial interpolation
* [[Cubic interpolation]]
* [[Cubic interpolation]]
Line 432: Line 431:
====Linear algebra====
====Linear algebra====
{{further|Numerical linear algebra}}
{{further|Numerical linear algebra}}
* Krylov methods (for large sparse matrix problems; third most-important numerical method class of the 20th century as ranked by SISC; after fast-fourier and fast-multipole)
* [[Eigenvalue algorithm]]s
* [[Eigenvalue algorithm]]s
** [[Arnoldi iteration]]
** [[Arnoldi iteration]]
Line 442: Line 440:
** [[Rayleigh quotient iteration]]
** [[Rayleigh quotient iteration]]
* [[Gram–Schmidt process]]: orthogonalizes a set of vectors
* [[Gram–Schmidt process]]: orthogonalizes a set of vectors
* Krylov methods (for large sparse matrix problems; third most-important numerical method class of the 20th century as ranked by SISC; after fast-fourier and fast-multipole)
* [[Matrix multiplication algorithm]]s
* [[Matrix multiplication algorithm]]s
** [[Cannon's algorithm]]: a [[distributed algorithm]] for [[matrix multiplication]] especially suitable for computers laid out in an N × N mesh
** [[Cannon's algorithm]]: a [[distributed algorithm]] for [[matrix multiplication]] especially suitable for computers laid out in an N × N mesh
Line 451: Line 450:
** [[Biconjugate gradient method]]: solves systems of linear equations
** [[Biconjugate gradient method]]: solves systems of linear equations
** [[Conjugate gradient]]: an algorithm for the numerical solution of particular systems of linear equations
** [[Conjugate gradient]]: an algorithm for the numerical solution of particular systems of linear equations
** [[Gaussian elimination]]
** [[Gauss–Jordan elimination]]: solves systems of linear equations
** [[Gauss–Jordan elimination]]: solves systems of linear equations
** [[Gauss–Seidel method]]: solves systems of linear equations iteratively
** [[Gauss–Seidel method]]: solves systems of linear equations iteratively
** [[Gaussian elimination]]
** [[Levinson recursion]]: solves equation involving a [[Toeplitz matrix]]
** [[Levinson recursion]]: solves equation involving a [[Toeplitz matrix]]
** [[Stone's method]]: also known as the strongly implicit procedure or SIP, is an algorithm for solving a sparse linear system of equations
** [[Stone's method]]: also known as the strongly implicit procedure or SIP, is an algorithm for solving a sparse linear system of equations
** [[Successive over-relaxation]] (SOR): method used to speed up convergence of the [[Gauss–Seidel method]]
** [[Successive over-relaxation]] (SOR): method used to speed up convergence of the [[Gauss–Seidel method]]
** [[Tridiagonal matrix algorithm]] (Thomas algorithm): solves systems of tridiagonal equations
** [[Tridiagonal matrix algorithm]] (Thomas algorithm): solves systems of tridiagonal equations
* [[SMAWK Algorithm]]
* [[Sparse matrix]] algorithms
* [[Sparse matrix]] algorithms
** [[Cuthill–McKee algorithm]]: reduce the [[bandwidth (matrix theory)|bandwidth]] of a [[symmetric sparse matrix]]
** [[Cuthill–McKee algorithm]]: reduce the [[bandwidth (matrix theory)|bandwidth]] of a [[symmetric sparse matrix]]
Line 488: Line 488:
{{main|Mathematical optimization}}[[Hybrid algorithm|Hybrid]] Algorithms
{{main|Mathematical optimization}}[[Hybrid algorithm|Hybrid]] Algorithms
* [[Alpha–beta pruning]]: search to reduce number of nodes in minimax algorithm
* [[Alpha–beta pruning]]: search to reduce number of nodes in minimax algorithm
* [[A hybrid BFGS-Like method]] (see more https://doi.org/10.1016/j.cam.2024.115857)
* [[Branch and bound]]
* [[Branch and bound]]
* [[Bruss algorithm]]: see [[odds algorithm]]
* [[Bruss algorithm]]: see [[odds algorithm]]
Line 494: Line 495:
** [[Greedy randomized adaptive search procedure]] (GRASP): successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a local search
** [[Greedy randomized adaptive search procedure]] (GRASP): successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a local search
** [[Hungarian method]]: a combinatorial optimization algorithm which solves the [[assignment problem]] in polynomial time
** [[Hungarian method]]: a combinatorial optimization algorithm which solves the [[assignment problem]] in polynomial time
* [[Conjugate gradient method]]s (see more https://doi.org/10.1016/j.jksus.2022.101923)
* [[Constraint satisfaction]]{{anchor|Constraint satisfaction}}
* [[Constraint satisfaction]]{{anchor|Constraint satisfaction}}
** General algorithms for the constraint satisfaction
** [[AC-3 algorithm]] general algorithms for the constraint satisfaction
*** [[AC-3 algorithm]]
*** [[Difference map algorithm]]
*** [[Min conflicts algorithm]]
** [[Chaff algorithm]]: an algorithm for solving instances of the [[Boolean satisfiability problem]]
** [[Chaff algorithm]]: an algorithm for solving instances of the [[Boolean satisfiability problem]]
** [[Davis–Putnam algorithm]]: check the validity of a first-order logic formula
** [[Davis–Putnam algorithm]]: check the validity of a first-order logic formula
** [[Difference map algorithm]] general algorithms for the constraint satisfaction
** [[DPLL algorithm|Davis–Putnam–Logemann–Loveland algorithm]] (DPLL): an algorithm for deciding the satisfiability of propositional logic formula in [[conjunctive normal form]], i.e. for solving the [[CNF-SAT]] problem
** [[DPLL algorithm|Davis–Putnam–Logemann–Loveland algorithm]] (DPLL): an algorithm for deciding the satisfiability of propositional logic formula in [[conjunctive normal form]], i.e. for solving the [[CNF-SAT]] problem
** [[Exact cover]] problem
** [[Exact cover]] problem
** [[Min conflicts algorithm]] general algorithms for the constraint satisfaction
*** [[Algorithm X]]: a [[nondeterministic algorithm]]
*** [[Algorithm X]]: a [[nondeterministic algorithm]]
*** [[Dancing Links]]: an efficient implementation of Algorithm X
*** [[Dancing Links]]: an efficient implementation of Algorithm X
Line 515: Line 516:
*** [[Fitness proportionate selection]] – also known as roulette-wheel selection
*** [[Fitness proportionate selection]] – also known as roulette-wheel selection
*** [[Stochastic universal sampling]]
*** [[Stochastic universal sampling]]
*** [[Tournament selection]]
*** [[Truncation selection]]
*** [[Truncation selection]]
*** [[Tournament selection]]
** [[Memetic algorithm]]
** [[Memetic algorithm]]
** [[Swarm intelligence]]
** [[Swarm intelligence]]
Line 527: Line 528:
* [[Hyperparameter optimization#Grid search|Grid Search]]
* [[Hyperparameter optimization#Grid search|Grid Search]]
* [[Harmony search]] (HS): a [[metaheuristic]] algorithm mimicking the improvisation process of musicians
* [[Harmony search]] (HS): a [[metaheuristic]] algorithm mimicking the improvisation process of musicians
* [[A hybrid HS-LS conjugate]] [[gradient algorithm]] (see https://doi.org/10.1016/j.cam.2023.115304)
* [[Interior point method]]
* [[Interior point method]]
* [[Line search]]
* {{anchor|Linear programming}}[[Linear programming]]
* {{anchor|Linear programming}}[[Linear programming]]
** [[Benson's algorithm]]: an algorithm for solving linear [[vector optimization]] problems
** [[Benson's algorithm]]: an algorithm for solving linear [[vector optimization]] problems
Line 537: Line 540:
** [[Karmarkar's algorithm]]: The first reasonably efficient algorithm that solves the [[linear programming]] problem in [[polynomial time]].
** [[Karmarkar's algorithm]]: The first reasonably efficient algorithm that solves the [[linear programming]] problem in [[polynomial time]].
** [[Simplex algorithm]]: an algorithm for solving [[linear programming]] problems
** [[Simplex algorithm]]: an algorithm for solving [[linear programming]] problems
* [[Line search]]
* [[Local search (optimization)|Local search]]: a metaheuristic for solving computationally hard optimization problems
* [[Local search (optimization)|Local search]]: a metaheuristic for solving computationally hard optimization problems
** [[Random-restart hill climbing]]
** [[Random-restart hill climbing]]
Line 555: Line 557:
* [[Stochastic tunneling]]
* [[Stochastic tunneling]]
* [[Subset sum problem|Subset sum]] algorithm
* [[Subset sum problem|Subset sum]] algorithm
* [[A hybrid HS-LS conjugate]] [[gradient algorithm]] (see https://doi.org/10.1016/j.cam.2023.115304)
* [[A hybrid BFGS-Like method]] (see more https://doi.org/10.1016/j.cam.2024.115857)
* [[Conjugate gradient method]]s (see more https://doi.org/10.1016/j.jksus.2022.101923)


==Computational science==
==Computational science==
Line 564: Line 563:
===Astronomy===
===Astronomy===
* [[Doomsday algorithm]]: day of the week
* [[Doomsday algorithm]]: day of the week
* various [[Computus|Easter algorithms]] are used to calculate the day of Easter
* [[Zeller's congruence]] is an algorithm to calculate the day of the week for any Julian or Gregorian calendar date
* [[Zeller's congruence]] is an algorithm to calculate the day of the week for any Julian or Gregorian calendar date
* various [[Computus|Easter algorithms]] are used to calculate the day of Easter


===Bioinformatics===
===Bioinformatics===
Line 571: Line 570:
{{see also|List of algorithms#Sequence alignment|l1=Sequence alignment algorithms}}
{{see also|List of algorithms#Sequence alignment|l1=Sequence alignment algorithms}}
* [[Basic Local Alignment Search Tool]] also known as BLAST: an algorithm for comparing primary biological sequence information
* [[Basic Local Alignment Search Tool]] also known as BLAST: an algorithm for comparing primary biological sequence information
* [[Bloom filter|Bloom Filter]]: probabilistic data structure used to test for the existence of an element within a set. Primarily used in bioinformatics to test for the existence of a [[k-mer]] in a sequence or sequences.
* [[Kabsch algorithm]]: calculate the optimal alignment of two sets of points in order to compute the [[RMSD|root mean squared deviation]] between two protein structures.
* [[Kabsch algorithm]]: calculate the optimal alignment of two sets of points in order to compute the [[RMSD|root mean squared deviation]] between two protein structures.
* [[Velvet (algorithm)|Velvet]]: a set of algorithms manipulating [[de Bruijn graph]]s for genomic [[sequence assembly]]
* [[Maximum parsimony (phylogenetics)]]: an algorithm for finding the simplest phylogenetic tree to explain a given character matrix.
* [[Sorting by signed reversals]]: an algorithm for understanding genomic evolution.
* [[Sorting by signed reversals]]: an algorithm for understanding genomic evolution.
* [[Maximum parsimony (phylogenetics)]]: an algorithm for finding the simplest phylogenetic tree to explain a given character matrix.
* [[UPGMA]]: a distance-based phylogenetic tree construction algorithm.
* [[UPGMA]]: a distance-based phylogenetic tree construction algorithm.
* [[Bloom filter|Bloom Filter]]: probabilistic data structure used to test for the existence of an element within a set. Primarily used in bioinformatics to test for the existence of a [[k-mer]] in a sequence or sequences.
* [[Velvet (algorithm)|Velvet]]: a set of algorithms manipulating [[de Bruijn graph]]s for genomic [[sequence assembly]]


===Geoscience===
===Geoscience===
{{further|Geoscience}}
{{further|Geoscience}}
* [[Geohash]]: a public domain algorithm that encodes a decimal latitude/longitude pair as a hash string
* [[Vincenty's formulae]]: a fast algorithm to calculate the distance between two latitude/longitude points on an ellipsoid
* [[Vincenty's formulae]]: a fast algorithm to calculate the distance between two latitude/longitude points on an ellipsoid
* [[Geohash]]: a public domain algorithm that encodes a decimal latitude/longitude pair as a hash string


===Linguistics===
===Linguistics===
Line 601: Line 600:
* [[Demon algorithm]]: a [[Monte Carlo method]] for efficiently sampling members of a [[microcanonical ensemble]] with a given energy
* [[Demon algorithm]]: a [[Monte Carlo method]] for efficiently sampling members of a [[microcanonical ensemble]] with a given energy
* [[Featherstone's algorithm]]: computes the effects of forces applied to a structure of joints and links
* [[Featherstone's algorithm]]: computes the effects of forces applied to a structure of joints and links
* [[Glauber dynamics]]: a method for simulating the Ising Model on a computer
* [[Ground state]] approximation
* [[Ground state]] approximation
** [[Variational method]]
** [[Variational method]]
Line 610: Line 610:
* [[Sweep and prune]]: a broad phase algorithm used during [[collision detection]] to limit the number of pairs of solids that need to be checked for collision
* [[Sweep and prune]]: a broad phase algorithm used during [[collision detection]] to limit the number of pairs of solids that need to be checked for collision
* [[VEGAS algorithm]]: a method for reducing error in [[Monte Carlo simulation]]s
* [[VEGAS algorithm]]: a method for reducing error in [[Monte Carlo simulation]]s
* [[Glauber dynamics]]: a method for simulating the Ising Model on a computer


===Statistics===
===Statistics===
Line 626: Line 625:
** [[Expectation-maximization algorithm]]
** [[Expectation-maximization algorithm]]
** [[Fuzzy clustering]]: a class of clustering algorithms where each point has a degree of belonging to clusters
** [[Fuzzy clustering]]: a class of clustering algorithms where each point has a degree of belonging to clusters
*** [[FLAME clustering]] (Fuzzy clustering by Local Approximation of MEmberships): define clusters in the dense parts of a dataset and perform cluster assignment solely based on the neighborhood relationships among objects
*** [[Fuzzy clustering#Fuzzy c-means clustering|Fuzzy c-means]]
*** [[Fuzzy clustering#Fuzzy c-means clustering|Fuzzy c-means]]
*** [[FLAME clustering]] (Fuzzy clustering by Local Approximation of MEmberships): define clusters in the dense parts of a dataset and perform cluster assignment solely based on the neighborhood relationships among objects
** [[KHOPCA clustering algorithm]]: a local clustering algorithm, which produces hierarchical multi-hop clusters in static and mobile environments.
** [[k-means clustering]]: cluster objects based on attributes into partitions
** [[k-means clustering]]: cluster objects based on attributes into partitions
** [[k-means++]]: a variation of this, using modified random seeds
** [[k-means++]]: a variation of this, using modified random seeds
** [[k-medoids]]: similar to k-means, but chooses datapoints or [[medoid]]s as centers
** [[k-medoids]]: similar to k-means, but chooses datapoints or [[medoid]]s as centers
** [[KHOPCA clustering algorithm]]: a local clustering algorithm, which produces hierarchical multi-hop clusters in static and mobile environments.
** [[Linde–Buzo–Gray algorithm]]: a vector quantization algorithm to derive a good codebook
** [[Linde–Buzo–Gray algorithm]]: a vector quantization algorithm to derive a good codebook
** [[Lloyd's algorithm]] (Voronoi iteration or relaxation): group data points into a given number of categories, a popular algorithm for [[k-means clustering]]
** [[Lloyd's algorithm]] (Voronoi iteration or relaxation): group data points into a given number of categories, a popular algorithm for [[k-means clustering]]
Line 637: Line 636:
** [[Single-linkage clustering]]: a simple agglomerative clustering algorithm
** [[Single-linkage clustering]]: a simple agglomerative clustering algorithm
** [[SUBCLU]]: a subspace clustering algorithm
** [[SUBCLU]]: a subspace clustering algorithm
** [[WACA clustering algorithm]]: a local clustering algorithm with potentially multi-hop structures; for dynamic networks
** [[Ward's method]]: an agglomerative clustering algorithm, extended to more general Lance–Williams algorithms
** [[Ward's method]]: an agglomerative clustering algorithm, extended to more general Lance–Williams algorithms
** [[WACA clustering algorithm]]: a local clustering algorithm with potentially multi-hop structures; for dynamic networks
* [[Estimation theory|Estimation Theory]]
* [[Estimation theory|Estimation Theory]]
** [[Expectation-maximization algorithm]] A class of related algorithms for finding maximum likelihood estimates of parameters in probabilistic models
** [[Expectation-maximization algorithm]] A class of related algorithms for finding maximum likelihood estimates of parameters in probabilistic models
*** [[Ordered subset expectation maximization]] (OSEM): used in [[medical imaging]] for [[positron emission tomography]], [[single-photon emission computed tomography]] and [[X-ray]] computed tomography.
*** [[Ordered subset expectation maximization]] (OSEM): used in [[medical imaging]] for [[positron emission tomography]], [[single-photon emission computed tomography]] and [[X-ray]] computed tomography.
** [[Kalman filter]]: estimate the state of a linear [[dynamical system|dynamic system]] from a series of noisy measurements
** [[Odds algorithm]] (Bruss algorithm) Optimal online search for distinguished value in sequential random input
** [[Odds algorithm]] (Bruss algorithm) Optimal online search for distinguished value in sequential random input
** [[Kalman filter]]: estimate the state of a linear [[Dynamical system|dynamic system]] from a series of noisy measurements
* [[False nearest neighbor algorithm]] (FNN) estimates [[fractal dimension]]
* [[False nearest neighbor algorithm]] (FNN) estimates [[fractal dimension]]
* [[Hidden Markov model]]
* [[Hidden Markov model]]
** [[Baum–Welch algorithm]]: computes maximum likelihood estimates and [[Maximum a posteriori|posterior mode]] estimates for the parameters of a hidden Markov model
** [[Baum–Welch algorithm]]: computes maximum likelihood estimates and [[maximum a posteriori|posterior mode]] estimates for the parameters of a hidden Markov model
** [[Forward-backward algorithm]]: a dynamic programming algorithm for computing the probability of a particular observation sequence
** [[Forward–backward algorithm]]: a dynamic programming algorithm for computing the probability of a particular observation sequence
** [[Viterbi algorithm]]: find the most likely sequence of hidden states in a hidden Markov model
** [[Viterbi algorithm]]: find the most likely sequence of hidden states in a hidden Markov model
* [[Partial least squares regression]]: finds a linear model describing some predicted variables in terms of other observable variables
* [[Partial least squares regression]]: finds a linear model describing some predicted variables in terms of other observable variables
Line 666: Line 665:
===Computer graphics===
===Computer graphics===
{{further|Computer graphics}}
{{further|Computer graphics}}
* [[Binary space partitioning]]
* [[Clipping (computer graphics)|Clipping]]
* [[Clipping (computer graphics)|Clipping]]
** [[Line clipping]]
** [[Line clipping]]
Line 681: Line 681:
** [[Marching squares]]: generates contour lines for a two-dimensional scalar field
** [[Marching squares]]: generates contour lines for a two-dimensional scalar field
** [[Marching tetrahedrons]]: an alternative to [[Marching cubes]]
** [[Marching tetrahedrons]]: an alternative to [[Marching cubes]]
* [[Discrete Green's theorem]]: is an algorithm for computing double integral over a generalized rectangular domain in constant time. It is a natural extension to the summed area table algorithm
* [[Discrete Green's theorem]]: is an algorithm for computing double integral over a generalized rectangular domain in constant time. It is a natural extension to the summed area table algorithm
* [[Flood fill]]: fills a connected region of a multi-dimensional array with a specified symbol
* [[Flood fill]]: fills a connected region of a multi-dimensional array with a specified symbol
* [[Global illumination]] algorithms: Considers direct illumination and reflection from other objects.
* [[Global illumination]] algorithms: Considers direct illumination and reflection from other objects.
Line 709: Line 709:
* [[Slerp]] (spherical linear interpolation): quaternion interpolation for the purpose of animating 3D rotation
* [[Slerp]] (spherical linear interpolation): quaternion interpolation for the purpose of animating 3D rotation
* [[Summed area table]] (also known as an integral image): an algorithm for computing the sum of values in a rectangular subset of a grid in constant time
* [[Summed area table]] (also known as an integral image): an algorithm for computing the sum of values in a rectangular subset of a grid in constant time
* [[Binary space partitioning]]


===Cryptography===
===Cryptography===
Line 743: Line 742:
** [[Elliptic-curve Diffie–Hellman]] (ECDH)
** [[Elliptic-curve Diffie–Hellman]] (ECDH)
* [[Key derivation function]]s, often used for [[password hashing]] and [[key stretching]]
* [[Key derivation function]]s, often used for [[password hashing]] and [[key stretching]]
** [[Argon2]]
** [[bcrypt]]
** [[bcrypt]]
** [[PBKDF2]]
** [[PBKDF2]]
** [[scrypt]]
** [[scrypt]]
** [[Argon2]]
* [[Message authentication code]]s (symmetric authentication algorithms, which take a key as a parameter):
* [[Message authentication code]]s (symmetric authentication algorithms, which take a key as a parameter):
** [[keyed-hash message authentication code|HMAC]]: keyed-hash message authentication
** [[keyed-hash message authentication code|HMAC]]: keyed-hash message authentication
Line 757: Line 756:
** [[Advanced Encryption Standard]] (AES), winner of [[NIST]] competition, also known as [[Rijndael]]
** [[Advanced Encryption Standard]] (AES), winner of [[NIST]] competition, also known as [[Rijndael]]
** [[Blowfish (cipher)|Blowfish]]
** [[Blowfish (cipher)|Blowfish]]
** [[Twofish]]
** [[Salsa20#ChaCha variant|ChaCha20]] updated variant of Salsa20
** [[Threefish]]
** [[Data Encryption Standard]] (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
** [[Data Encryption Standard]] (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
** [[International Data Encryption Algorithm|IDEA]]
** [[International Data Encryption Algorithm|IDEA]]
** [[RC4 (cipher)]]
** [[RC4 (cipher)]]
** [[Salsa20]]
** [[Threefish]]
** [[Tiny Encryption Algorithm]] (TEA)
** [[Tiny Encryption Algorithm]] (TEA)
** [[Salsa20]], and its updated variant [[Salsa20#ChaCha variant|ChaCha20]]
** [[Twofish]]
* [[Post-quantum cryptography]]
* [[Post-quantum cryptography]]
* [[Proof-of-work system|Proof-of-work algorithms]]
* [[Proof-of-work system|Proof-of-work algorithms]]
Line 769: Line 769:
===Digital logic===
===Digital logic===
* Boolean minimization
* Boolean minimization
** [[Espresso heuristic logic minimizer]]: a fast algorithm for Boolean function minimization
** [[Petrick's method]]: another algorithm for Boolean simplification
** [[Quine–McCluskey algorithm]]: also called as Q-M algorithm, programmable method for simplifying the Boolean equations
** [[Quine–McCluskey algorithm]]: also called as Q-M algorithm, programmable method for simplifying the Boolean equations
** [[Petrick's method]]: another algorithm for Boolean simplification
** [[Espresso heuristic logic minimizer]]: a fast algorithm for Boolean function minimization


===Machine learning and statistical classification===
===Machine learning and statistical classification===
Line 790: Line 790:
** [[LPBoost]]: [[linear programming]] boosting
** [[LPBoost]]: [[linear programming]] boosting
* [[Bootstrap aggregating]] (bagging): technique to improve stability and classification accuracy
* [[Bootstrap aggregating]] (bagging): technique to improve stability and classification accuracy
* [[Cluster analysis|Clustering]]: a class of [[unsupervised learning]] algorithms for grouping and bucketing related input vector
* [[Computer Vision]]
* [[Computer Vision]]
** [[Grabcut]] based on [[Graph cuts in computer vision|Graph cuts]]
** [[Grabcut]] based on [[Graph cuts in computer vision|Graph cuts]]
Line 795: Line 796:
** [[C4.5 algorithm]]: an extension to ID3
** [[C4.5 algorithm]]: an extension to ID3
** [[ID3 algorithm]] (Iterative Dichotomiser 3): use heuristic to generate small decision trees
** [[ID3 algorithm]] (Iterative Dichotomiser 3): use heuristic to generate small decision trees
* [[Cluster analysis|Clustering]]: a class of [[unsupervised learning]] algorithms for grouping and bucketing related input vector
* [[k-nearest neighbors]] (k-NN): a non-parametric method for classifying objects based on closest training examples in the [[feature space]]
* [[k-nearest neighbors]] (k-NN): a non-parametric method for classifying objects based on closest training examples in the [[feature space]]
* [[Linde–Buzo–Gray algorithm]]: a vector quantization algorithm used to derive a good codebook
* [[Linde–Buzo–Gray algorithm]]: a vector quantization algorithm used to derive a good codebook
Line 831: Line 831:
* [[GLR parser]]: an algorithm for parsing any [[context-free grammar]] by [[Masaru Tomita]]. It is tuned for deterministic grammars, on which it performs almost [[linear time]] and O(n<sup>3</sup>) in worst case.
* [[GLR parser]]: an algorithm for parsing any [[context-free grammar]] by [[Masaru Tomita]]. It is tuned for deterministic grammars, on which it performs almost [[linear time]] and O(n<sup>3</sup>) in worst case.
* [[Inside-outside algorithm]]: an O(n<sup>3</sup>) algorithm for re-estimating production probabilities in [[probabilistic context-free grammar]]s
* [[Inside-outside algorithm]]: an O(n<sup>3</sup>) algorithm for re-estimating production probabilities in [[probabilistic context-free grammar]]s
* [[Lexical analysis]]
* [[LL parser]]: a relatively simple [[linear time]] parsing algorithm for a limited class of [[context-free grammar]]s
* [[LL parser]]: a relatively simple [[linear time]] parsing algorithm for a limited class of [[context-free grammar]]s
* [[LR parser]]: A more complex [[linear time]] parsing algorithm for a larger class of [[context-free grammar]]s. Variants:
* [[LR parser]]: A more complex [[linear time]] parsing algorithm for a larger class of [[context-free grammar]]s. Variants:
** [[Canonical LR parser]]
** [[Canonical LR parser]]
** [[Look-ahead LR parser|LALR (look-ahead LR) parser]]
** [[Look-ahead LR parser|LALR (look-ahead LR) parser]]
** [[Operator-precedence parser]]
** [[Operator-precedence parser]]
** [[Simple LR parser|SLR (Simple LR) parser]]
** [[Simple LR parser]]
** [[Simple precedence parser]]
** [[Simple precedence parser]]
* [[Packrat parser]]: a [[linear time]] parsing algorithm supporting some [[context-free grammar]]s and [[parsing expression grammar]]s
* [[Packrat parser]]: a [[linear time]] parsing algorithm supporting some [[context-free grammar]]s and [[parsing expression grammar]]s
* [[Pratt parser]]
* [[Recursive descent parser]]: a [[top-down parsing|top-down parser]] suitable for LL(''k'') grammars
* [[Recursive descent parser]]: a [[top-down parsing|top-down parser]] suitable for LL(''k'') grammars
* [[Shunting-yard algorithm]]: converts an infix-notation math expression to postfix
* [[Shunting-yard algorithm]]: converts an infix-notation math expression to postfix
* [[Pratt parser]]
* [[Lexical analysis]]


===Quantum algorithms===
===Quantum algorithms===
Line 896: Line 896:
** [[Byte pair encoding]] (BPE)
** [[Byte pair encoding]] (BPE)
** [[Deflate]]
** [[Deflate]]
** [[Lempel–Ziv]]
** [[Abraham Lempel|Lempel]]–[[Jacob Ziv|Ziv]]
*** [[LZ77 and LZ78]]
*** [[LZ77 and LZ78]]
*** [[LZJB|Lempel–Ziv Jeff Bonwick]] (LZJB)
*** [[LZJB|Lempel–Ziv Jeff Bonwick]] (LZJB)
*** [[Lempel–Ziv–Markov chain algorithm]] (LZMA)
*** [[Lempel–Ziv–Markov chain algorithm]] (LZMA)
*** [[Lempel–Ziv–Oberhumer]] (LZO): speed oriented
*** [[Lempel–Ziv–Oberhumer]] (LZO): speed oriented
*** [[LZRW|Lempel–Ziv Ross Williams]] (LZRW)
*** [[Lempel–Ziv–Stac]] (LZS)
*** [[Lempel–Ziv–Stac]] (LZS)
*** [[Lempel–Ziv–Storer–Szymanski]] (LZSS)
*** [[Lempel–Ziv–Storer–Szymanski]] (LZSS)
Line 906: Line 907:
*** [[LZWL]]: syllable-based variant
*** [[LZWL]]: syllable-based variant
*** [[LZX]]
*** [[LZX]]
*** [[LZRW|Lempel–Ziv Ross Williams]] (LZRW)
* [[Entropy encoding]]: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols
* [[Entropy encoding]]: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols
** [[Arithmetic coding]]: advanced [[entropy]] coding
** [[Arithmetic coding]]: advanced [[entropy]] coding
Line 948: Line 948:
** [[Wavelet compression]]: form of data compression well suited for [[image compression]] (sometimes also video compression and audio compression)
** [[Wavelet compression]]: form of data compression well suited for [[image compression]] (sometimes also video compression and audio compression)
* [[Transform coding]]: type of data compression for "natural" data like audio signals or photographic images
* [[Transform coding]]: type of data compression for "natural" data like audio signals or photographic images
* [[Vector quantization]]: technique often used in lossy data compression
* [[Video compression]]
* [[Video compression]]
* [[Vector quantization]]: technique often used in lossy data compression


===Digital signal processing===
===Digital signal processing===
Line 963: Line 963:
* [[Fast folding algorithm]]: an efficient algorithm for the detection of approximately periodic events within time series data
* [[Fast folding algorithm]]: an efficient algorithm for the detection of approximately periodic events within time series data
* [[Gerchberg–Saxton algorithm]]: Phase retrieval algorithm for optical planes
* [[Gerchberg–Saxton algorithm]]: Phase retrieval algorithm for optical planes
* [[Goertzel algorithm]]: identify a particular frequency component in a signal. Can be used for [[DTMF]] digit decoding.
* [[Goertzel algorithm]]: identify a particular frequency component in a signal. Can be used for [[DTMF]] digit decoding.
* [[Karplus-Strong string synthesis]]: physical modelling synthesis to simulate the sound of a hammered or plucked string or some types of percussion
* [[Karplus-Strong string synthesis]]: physical modelling synthesis to simulate the sound of a hammered or plucked string or some types of percussion


====Image processing====
====Image processing====
{{further|Digital image processing}}
{{further|Digital image processing}}
* Contrast Enhancement
 
** [[Histogram equalization]]: use histogram to improve image contrast
* [[Adaptive histogram equalization]]: histogram equalization which adapts to local changes in contrast - Contrast Enhancement
** [[Adaptive histogram equalization]]: histogram equalization which adapts to local changes in contrast
* [[Blind deconvolution]]: image de-blurring algorithm when [[point spread function]] is unknown.
* [[Connected-component labeling]]: find and label disjoint regions
* [[Connected-component labeling]]: find and label disjoint regions
* [[Dithering]] and [[half-toning]]
* [[Dithering]] and [[half-toning]]
Line 977: Line 977:
** [[Ordered dithering]]
** [[Ordered dithering]]
** [[Riemersma dithering]]
** [[Riemersma dithering]]
* Elser [[difference-map algorithm]]: a search algorithm for general constraint satisfaction problems. Originally used for [[X-ray crystallography|X-Ray diffraction]] microscopy
* Elser [[difference-map algorithm]]: a search algorithm for general constraint satisfaction problems. Originally used for [[X-ray crystallography|X-Ray diffraction]] microscopy
* [[Feature detection (computer vision)|Feature detection]]
* [[Feature detection (computer vision)|Feature detection]]
** [[Canny edge detector]]: detect a wide range of edges in images
** [[Canny edge detector]]: detect a wide range of edges in images
Line 984: Line 984:
** [[Marr–Hildreth algorithm]]: an early [[edge detection]] algorithm
** [[Marr–Hildreth algorithm]]: an early [[edge detection]] algorithm
** [[Scale-invariant feature transform|SIFT]] (Scale-invariant feature transform): is an algorithm to detect and describe local features in images.
** [[Scale-invariant feature transform|SIFT]] (Scale-invariant feature transform): is an algorithm to detect and describe local features in images.
** {{visible anchor|SURF ([[speeded up robust features|Speeded Up Robust Features]])}}: is a robust local feature detector, first presented by Herbert Bay et al. in 2006, that can be used in computer vision tasks like object recognition or 3D reconstruction. It is partly inspired by the SIFT descriptor. The standard version of SURF is several times faster than SIFT and claimed by its authors to be more robust against different image transformations than SIFT.<ref>{{cite web |url=http://www.vision.ee.ethz.ch/~surf/eccv06.pdf |title=Archived copy |website=www.vision.ee.ethz.ch |access-date=13 January 2022 |archive-url=https://web.archive.org/web/20070221214147/http://www.vision.ee.ethz.ch/~surf/eccv06.pdf |archive-date=21 February 2007 |url-status=dead}}</ref><ref>{{cite web |url=http://glorfindel.mavrinac.com/~aaron/school/pdf/bay06_surf.pdf |title=Archived copy |access-date=2013-10-05 |url-status=dead |archive-url=https://web.archive.org/web/20131006113018/http://glorfindel.mavrinac.com/~aaron/school/pdf/bay06_surf.pdf |archive-date=2013-10-06 }}</ref>
** {{visible anchor|SURF ([[speeded up robust features|Speeded Up Robust Features]])}}: is a robust local feature detector, first presented by [[Herbert Bay]] et al. in 2006, that can be used in computer vision tasks like object recognition or 3D reconstruction. It is partly inspired by the SIFT descriptor. The standard version of SURF is several times faster than SIFT and claimed by its authors to be more robust against different image transformations than SIFT.<ref>{{cite web |url=http://www.vision.ee.ethz.ch/~surf/eccv06.pdf |title=Archived copy |website=vision.ee.ethz.ch |access-date=13 January 2022 |archive-url=https://web.archive.org/web/20070221214147/http://www.vision.ee.ethz.ch/~surf/eccv06.pdf |archive-date=21 February 2007 |url-status=dead}}</ref><ref>{{cite web |url=http://glorfindel.mavrinac.com/~aaron/school/pdf/bay06_surf.pdf |title=Archived copy |access-date=2013-10-05 |url-status=dead |archive-url=https://web.archive.org/web/20131006113018/http://glorfindel.mavrinac.com/~aaron/school/pdf/bay06_surf.pdf |archive-date=2013-10-06 }}</ref>
* [[Histogram equalization]]: use histogram to improve image contrast - Contrast Enhancement
* [[Richardson–Lucy deconvolution]]: image de-blurring algorithm
* [[Richardson–Lucy deconvolution]]: image de-blurring algorithm
* [[Blind deconvolution]]: image de-blurring algorithm when [[point spread function]] is unknown.
* [[Median filtering]]
* [[Median filtering]]
* [[Seam carving]]: content-aware image resizing algorithm
* [[Seam carving]]: content-aware image resizing algorithm
Line 1,072: Line 1,072:


===Process synchronization===
===Process synchronization===
{{further|Process synchronization}}
{{further|Process scheduler|Process synchronization}}
{{further|Process scheduler}}
* [[Dekker's algorithm]]
* [[Dekker's algorithm]]
* [[Lamport's Bakery algorithm]]
* [[Lamport's Bakery algorithm]]

Latest revision as of 22:58, 9 November 2025

Template:Short description An algorithm is fundamentally a set of rules or defined procedures that is typically designed and used to solve a specific problem or a broad set of problems.

Broadly, algorithms define process(es), sets of rules, or methodologies that are to be followed in calculations, data processing, data mining, pattern recognition, automated reasoning or other problem-solving operations. With the increasing automation of services, more and more decisions are being made by algorithms. Some general examples are risk assessments, anticipatory policing, and pattern recognition technology.[1]

The following is a list of well-known algorithms.

Automated planning

Script error: No such module "labelled list hatnote".

Combinatorial algorithms

Script error: No such module "labelled list hatnote".

General combinatorial algorithms

Graph algorithms

Script error: No such module "labelled list hatnote".

Graph drawing

Script error: No such module "labelled list hatnote".

Network theory

Script error: No such module "labelled list hatnote".

Routing for graphs

Graph search

Script error: No such module "labelled list hatnote".

Subgraphs

Sequence algorithms

Script error: No such module "labelled list hatnote".

Approximate sequence matching

Selection algorithms

Script error: No such module "Labelled list hatnote".

Sequence search

Sequence merging

Script error: No such module "Labelled list hatnote".

Sequence permutations

Script error: No such module "labelled list hatnote".

Sequence combinations

Script error: No such module "labelled list hatnote".

Sequence alignment

Sequence sorting

Script error: No such module "Labelled list hatnote". Script error: No such module "Unsubst".

Subsequences

Script error: No such module "labelled list hatnote".

Substrings

Script error: No such module "labelled list hatnote".

Computational mathematics

Script error: No such module "labelled list hatnote". Script error: No such module "Labelled list hatnote".

Abstract algebra

Script error: No such module "labelled list hatnote".

Computer algebra

Script error: No such module "labelled list hatnote".

Geometry

Template:Main category Script error: No such module "labelled list hatnote".

Number theoretic algorithms

Script error: No such module "labelled list hatnote".

Numerical algorithms

Script error: No such module "labelled list hatnote".

Differential equation solving

Script error: No such module "labelled list hatnote".

Elementary and special functions

Script error: No such module "labelled list hatnote".

Geometric

Interpolation and extrapolation

Script error: No such module "labelled list hatnote".

Linear algebra

Script error: No such module "labelled list hatnote".

Script error: No such module "anchor".

Monte Carlo

Script error: No such module "labelled list hatnote".

Numerical integration

Script error: No such module "labelled list hatnote".

Root finding

Script error: No such module "Labelled list hatnote".

Optimization algorithms

Script error: No such module "Labelled list hatnote".Hybrid Algorithms

Computational science

Script error: No such module "labelled list hatnote".

Astronomy

Bioinformatics

Script error: No such module "labelled list hatnote". Script error: No such module "Labelled list hatnote".

Geoscience

Script error: No such module "labelled list hatnote".

  • Geohash: a public domain algorithm that encodes a decimal latitude/longitude pair as a hash string
  • Vincenty's formulae: a fast algorithm to calculate the distance between two latitude/longitude points on an ellipsoid

Linguistics

Script error: No such module "labelled list hatnote".

Medicine

Script error: No such module "labelled list hatnote".

Physics

Script error: No such module "labelled list hatnote".

Statistics

Script error: No such module "labelled list hatnote".

Computer science

Script error: No such module "labelled list hatnote".

Computer architecture

Script error: No such module "labelled list hatnote".

  • Tomasulo algorithm: allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially

Computer graphics

Script error: No such module "labelled list hatnote".

Cryptography

Script error: No such module "labelled list hatnote".

Digital logic

Machine learning and statistical classification

Script error: No such module "Labelled list hatnote". Script error: No such module "labelled list hatnote".

Programming language theory

Script error: No such module "labelled list hatnote".

Parsing

Script error: No such module "labelled list hatnote".

Quantum algorithms

Script error: No such module "labelled list hatnote".

Theory of computation and automata

Script error: No such module "labelled list hatnote".

Information theory and signal processing

Script error: No such module "Labelled list hatnote".

Coding theory

Script error: No such module "labelled list hatnote".

Error detection and correction

Script error: No such module "labelled list hatnote".

Lossless compression algorithms

Script error: No such module "Labelled list hatnote".

Lossy compression algorithms

Script error: No such module "Labelled list hatnote".

Digital signal processing

Script error: No such module "labelled list hatnote".

Image processing

Script error: No such module "labelled list hatnote".

Software engineering

Script error: No such module "labelled list hatnote".

Database algorithms

Script error: No such module "labelled list hatnote".

Distributed systems algorithms

Script error: No such module "labelled list hatnote".

Memory allocation and deallocation algorithms

Networking

Script error: No such module "labelled list hatnote".

Operating systems algorithms

Script error: No such module "labelled list hatnote".

Process synchronization

Script error: No such module "labelled list hatnote".

Scheduling

Script error: No such module "labelled list hatnote".

I/O scheduling

Script error: No such module "labelled list hatnote". Script error: No such module "Unsubst".

Disk scheduling

See also

References

Template:Reflist

Template:Algorithmic paradigms

  1. ↑ Script error: No such module "citation/CS1".
  2. ↑ Script error: No such module "Citation/CS1".
  3. ↑ Script error: No such module "citation/CS1".
  4. ↑ Script error: No such module "citation/CS1".
  5. ↑ Script error: No such module "citation/CS1".
  6. ↑ Script error: No such module "citation/CS1".
  7. ↑ Script error: No such module "citation/CS1".
  8. ↑ Script error: No such module "citation/CS1".
  9. ↑ Script error: No such module "citation/CS1".
  10. ↑ Script error: No such module "citation/CS1".
Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=List_of_algorithms&oldid=3124574"