# Computer science eponyms: Difference between revisions

No edit summary |
No edit summary |
||

Line 351: | Line 351: | ||

* Tarjan's Dynamic Tree | * Tarjan's Dynamic Tree | ||

* Tarjan's Least Common Ancestors Algorithm | * Tarjan's Least Common Ancestors Algorithm | ||

* The nondeterministic '''Tarski–Kuratowski algorithm''' produces an upper bound for the complexity of a given formula in the arithmetical hierarchy and analytical hierarchy. | |||

* Thompson Automata | * Thompson Automata | ||

* Timsort | * Timsort |

## Revision as of 19:44, 29 June 2022

Computer science needs more eponyms, in the vein of Mordenkainen. Collect them all, and impress your friends! I might make a project one day of summarizing these entries, but I'd likely sell the result as a book.

**FIXME**Tarjan has something like 20,004 algorithms, and all of them are outstanding

Explicitly **not included** in this list are: general logic (Peano and Presburger arithmetic), mathematical entities not primarily associated with computer science (Markov's inequality, Chapman-Kolmogorov equation, Young tableaux), physical theories to which computer science is merely applied (Navier-Stokes equations, Taylor-Couette flow), or statistical entities not primarily associated with computer science (Ziph's Law, Pareto efficiency). Explicitly **included** are: terms from computer engineering (Mead-Conway rules, Ling adders) and mathematical entities primarily associated with computer science.

**UPDATE** the threshold for inclusion is now: De Morgan's Laws. If you're not more computer sciency than De Morgan's Laws, you ain't gettin' in. Dank 12:25, 3 October 2011 (CDT)

**Aanderaa–Rosenberg Conjecture**suggests that non-trivial monotonicity properties of undirected graphs can only be solved by*Ω(N*algorithms on^{2})*N*vertices (these are all evasive decision trees on all possible edges)**Adam7 Algorithm**is a 2D, 7-pass interlacing scheme optionally used by PNG due to Adam Costello**Adleman's Theorem**states that P/poly contains all problems solvable in randomized polynomial time**Adelson-Velskii-Landis Trees**are self-height-balancing binary search trees, optimizing for lookup over modification viz. red-black trees**Aho-Corasick Algorithm**extends the Knuth-Morris-Pratt automaton to match multiple strings in one pass of a text**Akra-Bazzi Method**generalizes the "master method" of Bentley, Haken, and Saxe for subproblems of significantly different size- Amdahl's Law
- Andersen's Algorithm
**Armstrong's axioms**are a set of inference rules which generate all functional dependencies of a relational database. Similarly, an**Armstrong relation**satisfies all the functional dependencies in the closure F^{+}(and only those dependencies).

- Backus-Naur Form
- Bajard-Kla-Muller algorithm
- Ball-Larus Heuristics
- Banerjee Inequality
- Barendregt convention
- Barendregt-Geuvers-Klop Conjecture
- Baskett, Chandy, Muntz and Palacios network
- Batcher's Odd-Even Merge
**Bayer Filter**mosaics arrange RGB color filters on a square array of photosensors, and are used in a majority of single-chip image sensors. It uses twice as many green sensors as red or blue, to mimic the physiology of the human eye**Bélády's anomaly**is the phenomenon in which increasing the number of page frames results in an*increase*in the number of page faults for certain memory access patterns, especially when using FIFO page replacement- Bell-La Padula model
- Bellman-Ford Algorithm
- Beneš network
- Bentley-Ottman Algorithm
- Berlekamp-Massey Algorithm
- Berman–Hartmanis conjecture
- Bernstein chaining
- Bernstein conditions
- Biba Integrity Model
- Blinn-Phong shading
- Blom's Scheme
- Bloom filter
- Bluestein's FFT
- Blum's axioms
- Blum's Speedup Theorem
- Blum-Blum-Shub random number generator
- Boehm-Demers-Weiser garbage collector
- Booth's Algorithm
- Borůvka's Algorithm
- Bowyer-Watson Algorithm
- Boyer-Moore Algorithm
- Bremermann's Limit
- Brent's Adder
**Brent's Algorithm**detects cycles using two pointers, and finds the length of the cycle directly**Brent's Method**is a hybrid root-finding algorithm combining bisection, the secant method, and inverse quadratic interpolation**Brent's Theorem**aka**Brent's Law**states that p < N processors can simulate N in T_p ≤ T_N + (T_1 - T_N)/p- Bresenham's Algorithm
- Brewer's Theorem
- Brodal Queue
- Broder's Method
- Bron-Kerbosch Algorithm
- Brooks-Iyengar Algorithm
- Buchberger Algorithm
- Burrows-Wheeler Transform
- Buzen's Algorithm

- Callahan-Koblenz algorithm
- Cannon's Algorithm
- Cantor-Zassenhaus Algorithm
- Carmack's Reverse
- Chaff Algorithm
- Chaitin's algorithm
- Chaitin's Constant
- Chaitin-Briggs algorithm
- Chaitin–Kolmogorov random numbers
- Chakravala's Algorithm
- Chan's Algorithm
- the
**Chang-Roberts Algorithm**elects leaders for distributed systems. - Cheney's Algorithm
- Chew's Second Algorithm
- Chien search
**Cholesky decomposition**expands Hermitian positive-definite matrices into products of a lower triangular matrix and its conjugate transpose. solved using the Cholesky–Crout and Cholesky–Banachiewicz algorithms.- Chomsky Hierarchy
- Chomsky Normal Form
- Chomsky-Schützenberger theorem
- Christofides Algorithm
- Church-Rosser Theorem
- Church-Turing Thesis
- Clos network
- Cobham Axioms
- Cobham's thesis
- Cocke-Younger-Kasami Algorithm
- Cohen-Sutherland algorithm
**Coffman conditions**enumerate the four conditions necessary and sufficient for deadlock within a system (mutual exclusion, hold-and-wait, a lack of preemption, and circular wait)- Commentz-Walter Algorithm
- Conway's Law
- Cook reduction
- the
**Cook-Levin Theorem**(sometimes just**Cook Theorem**) proves that the Boolean satisfiability problem is NP-complete. - the
**Cooley-Tukey Algorithm**is the workhorse algorithm for Fast Fourier Transforms. - the
**Coppersmith-Winograd Algorithm**multiplied matrices in the least time complexity from 1990-2010, and used the "laser method" employed by all improvements since. - Craig, Landin and Hagersten lock
- Cranfield method
- (preconditioned) Crank–Nicolson Algorithm
- Crusader’s Convergence Algorithm

- Dadda Multiplier
- Damerau-Levenshtein distance
- Damm Algorithm
- Davis-Putnam Algorithm
- Davis-Putnam-Logemann-Loveland Algorithm
- De Bruijn presentation
- De Bruijn string
- Dekker's Algorithm
- Delaunay's Triangulation
- Dennard Scaling
- Diffie-Hellman Key Exchange
- Dijkstra's Algorithm
- Dinic's Algorithm
**DiVincenzo's criteria**specify conditions necessary for a quantum computer- Dolev's Algorithm
- Doo-Sabin subdivision surface
- Duff's Device
- Dyck Language

- Earley Parser
**Edmonds's matching algorithm**constructs maximum matchings on graphs in O(|E||V|²)- Edmonds-Karp Algorithm
- Euclid's Algorithm

**Fagin's Theorem**states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP- Faugère F5 algorithm
- Fiat-Shamir Heuristic
- Fibonacci Heap
- Fisher-Yates shuffle
- Fletcher's Checksum
- Floyd's Algorithm
- Floyd-Steinberg dithering
- Flynn Taxonomy
- Ford-Fulkerson Algorithm
- Fortune's Algorithm
- Fox's Algorithm
- Fredkin gate
- Friedberg-Muchnik Theorem
- Fruchterman-Reingold heuristic
**Fürer's algorithm**multiplies two*n*-digit numbers in*O(nlgn*2*^{O(lg*n)})

- Gabbay's separation theorem
- Gabow's Algorithm
- Gal's Accurate Tables
- Gale-Church Algorithm
- Gale-Shapley algorithm
- Gilbert-Johnson-Keerthi Algorithm
- Girard's Paradox
- Girvan-Newman Algorithm
- Givens rotation
- Glushkov Automata
- Goldreich-Goldwasser-Halevi scheme
- Gomory-Hu Tree
- Gordon–Newell theorem
- Gosper's Hack
- Gosper's Hypergeometric Algorithm
- Gosper's Loop Detection Algorithm
- Gouraud shading
- The
**Graham Scan**solves for the convex hull of a set of points in*O(NlgN)*. - The
**Graham-Andrew Algorithm**modifies the Graham Scan to solve for convex hulls in*O(N)*best case. - Graham-Denning Model
- Gram–Schmidt process
- Gray codes
- Greibach Normal Form
- Grover's Algorithm
- Grzegorczyk hierarchy
- Guruswami-Sudan Algorithm
- Gustafson's Law
**Gutmann's Method**is a 35-phase recipe for destroying data on ferromagnetic drives.- Guttman-Rosler transform

- Hamming code
- Hamming distance
**Heckel's algorithm**isolates changes between files, and is the basis for`diff`CACM 1978- Hennessy-Milner Logic
- Herlihy's wait-free hierarchy
- Hirschberg's Algorithm
- Hoare logic
- Holevo's Theorem
- Holland's schema theorem
- Hong-Kung bound
- Hopcroft-Karp Algorithm
- Hopfield net
- Horn clauses
- Householder transformation
- Huet's Zipper
- Hunt-McIlroy Algorithm

- Iliffe vector
- Immerman–Szelepcsényi theorem

- Jackson network
- Jackson's theorem
- Jaro-Winkler distance
- Jefferson's Time Warp
- Jelinek-Mercer smoothing
- Jensen's Device
- Johnson's Algorithm

- Kabsch Algorithm
- Kadane's Algorithm
- Kahan Summation Algorithm
- Kannan's Theorem
**Karatsuba's Algorithm**multiplies two*n*-digit numbers using*n*single-digit mults^{log23}- Karger's Algorithm
**Karn's algorithm**extracts accurate TCP RTT measures, Karn-Partridge 1987- Karmarkar's algorithm
- Karnaugh map
- Karp reduction
- Karp-Flatt metric
- Karp-Lipton Theorem
- Kamada-Kawai algorithm
- Kernighan-Lin algorithm
- Kirkpatrick-Seidel Algorithm
- Kleene Closure
- Kleene Plus
- Kleene Star
- Kleene–Rosser Paradox
- Kneser-Ney smoothing
- Knuth Shuffle
- Knuth-Morris-Pratt Algorithm
- Koenig Lookup
- Kohonen Algorithm
- Kohonen network
- Kolmogorov complexity
- Koomey's Law
- Kosaraju's Algorithm
- Krapchenko's Adder
- Kruskal's Algorithm
**Kryder's Law**asserted that areal density doubles every thirteen months (this has not been true for some time). Also known as the*Kryder rate*.- Kung-Leiserson systolic array
- Kuroda Normal Form

- Ladner's Theorem
- Lamport's Bakery Algorithm
- Lamport's Clock
- Lamport's Hash
- Lee-Seung algorithm
- Lehmer random number generator
- Lehmer's GCD Algorithm
- Lempel-Ziv-Welch compression
- Levenshtein automaton
- Levenshtein distance
- Levin reduction
- Liang-Barsky algorithm
- Lin-Kernighan Heuristic
- Linde-Buzo-Gray algorithm
- Ling adders
- Liskov's Substitution Principle
- Lloyd's algorithm
**Loss-DiVincenzo machines**are quantum computers based off electron spin as confined to quantum dots- Luby's algorithm
- Luhn Algorithm
- Luleå Algorithm

- Maekawa's Algorithm
- Mahaney's Theorem
- Manning algorithm
- Marzullo algorithm
- McFarling-style branch predictor
- Mead-Conway Rules
- Mealy machine
- Mellor-Crummey and Scott lock
- Merkle–Damgård construction
- The
**Metropolis-Hastings algorithm**for MCMC obtains samples from a probability distribution that is difficult to directly sample - Miller-Rabin Primality Test
- Minsky-Fenichel-Yochelson Algorithm
- Montgomery reduction
- Moore machine
- Moore's Law
- Morgensen-Scott encoding
- Möller-Trumbore algorithm

- Nagle's algorithm
- Nassi-Shneiderman diagram
- Needham-Schroeder Protocol
- Needleman-Wunsch Algorithm
- Neuman-Stubblebine Protocol
- Nevill-Manning algorithm
- Nick's Class
- Nisan's Generator

**Ousterhout's dichotomy/fallacy**a taxonomy of*systems*vs*scripting*languages- Otway-Rees Protocol

**Paeth-Tanaka Algorithm**rotates images via a method of three shears**Paeth Filter**performs 2D image compression in PNG- Peterson's Algorithm
- Petrick's method
- Phong shading
- Plotkin's Sticky Bit
- Pollaczek–Khinchine formula
- Pollard's Kangaroo Algorithm
**Pollard's ρ Algorithm**aka**Pollard's rho Algorithm**factors integers in running time expected to be proportional to the square root of the smallest prime factor of the number being factored- Popek-Goldberg virtualization requirements
- Post's correspondence problem
**Post's Lattice**is the lattice of all clones on {0,1}, ordered by inclusion. It is used to prove sets of connectives to be functionally complete (e.g. NAND and NOR both generate functionally complete Boolean algebras).- Postel's Law
- Prim's Algorithm
**Proebsting's Law**claims that compiler technology doubles computing power every 18 years- Prüfer Coding
- Prüfer Sequence

- Quines
- Quine-McLuskey algorithm

- Rabin Automata
- Rabin's Information Dispersal Algorithm
- Rabin-Karp Algorithm
- Rader-Brenner Algorithm
- Radovic-Hagersten lock
- Raymond's Algorithm
- Reed-Muller code
- Reed-Solomon correction code
- Ricart-Agrawala Algorithm
- Rice's Theorem
- Rice-Shapiro Theorem
- Risch Algorithm
- Rivest-Shamir-Adleman Algorithm
**Rocchio's Algorithm**classifies information relevance using nearest centroids- Ruppert's Algorithm

**Sattolo's Algorithm**generates a 1-cyclic derangement of an array (a permutation such that every element ends up in a new position)- Savitch's Theorem
- Schensted Algorithm
- Schlick's approximation
- The
**Schönhage–Strassen algorithm**multiplies two*n*-digit numbers in*O(nlgnlglgn)*bit complexity using FFTs - Schoof's Algorithm
- Schreier-Sims Algorithm
- Schwartzian transform
- Sethi-Ullman Algorithm
- Shamir's Secret Sharing Scheme
- Shamos-Hoey Algorithm
- Shor's Algorithm
- Sipser–Lautemann theorem
- Smith's Algorithm
- Smith-Waterman algorithm
- Solomonoff-Levin distribution
- Steensgaard's Algorithm
- Stehlé-Zimmermann algorithm
- Steinhaus-Johnson-Trotter algorithm
- Strassen's Algorithm
- Suurballe's Algorithm
- Sweeney-Robertson-Tocher division algorithm

- Tarjan's Algorithm
- Tarjan's Dynamic Tree
- Tarjan's Least Common Ancestors Algorithm
- The nondeterministic
**Tarski–Kuratowski algorithm**produces an upper bound for the complexity of a given formula in the arithmetical hierarchy and analytical hierarchy. - Thompson Automata
- Timsort
- Toda's theorem
- Todd–Coxeter algorithm
- Tomasulo's Algorithm
- Tonelli-Shanks Algorithm
- The
**Toom-Cook Algorithm**multiplies two*n*-digit numbers using*n*single-digit mults^{log(5)/log(3)} - Turing Degree
- Turing Machines

- Ukkonen's Algorithm

- Valiant-Vazirani Theorem
- Van Jacobson Channels
- Van Wijngaarden Grammars
- Verhoeff Algorithm
- Viola-Jones face detection
- Volder's algorithm
- von Neumann architecture

- Wagner-Fischer Algorithm
- Wallace Multiplier
- Wallace tree
- Warnsdorff's Algorithm
- The
**Williams State Machine**is a common parsing automaton for DEC virtual terminal input - Winograd's Algorithm
- Witten-Bell smoothing
- Wu's Line Algorithm
- Wu-Manber Algorithm
- Wyllie's List Ranking

- Yao's Principle
**Yeh's Algorithm**is a two-level adaptive training algorithm designed by Yeh and Patt in 1991. A branch history register is used to maintain branch behavior for a specific pattern of branch history, and 4-bit counters are used for each BTB set.

- Zhu-Takaoka Algorithm
- Zimmermann-Sassaman key-signing protocol
- Zobrist hashing