Check out my first novel, midnight's simulacra!

Computer science eponyms: Difference between revisions

From dankwiki
No edit summary
No edit summary
Line 16: Line 16:
* Amdahl's Law
* Amdahl's Law
* Andersen's Algorithm
* 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<sup>+</sup> (and only those dependencies).


* Backus-Naur Form
* Backus-Naur Form

Revision as of 22:51, 13 February 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 Ω(N2) algorithms on 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
  • 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
  • Chang-Roberts Algorithm
  • 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
  • Cook-Levin Theorem
  • Cooley-Tukey Algorithm
  • Coppersmith-Winograd Algorithm
  • 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
  • Fürer's algorithm multiplies two n-digit numbers in O(nlgn*2O(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
  • Graham Scan
  • 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 nlog23 single-digit mults
  • 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
  • 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
  • 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
  • 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-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
  • 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 nlog(5)/log(3) single-digit mults
  • 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
  • Zhu-Takaoka Algorithm
  • Zimmermann-Sassaman key-signing protocol
  • Zobrist hashing