Computer science eponyms: Difference between revisions
No edit summary |
No edit summary |
||
| (48 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Computer science needs more eponyms, in the vein of [http://en.wikipedia.org/wiki/Mordenkainen#Spells Mordenkainen]. Collect them all, and impress your friends! I might make a project one day of [[book ideas|summarizing these entries]]. | Computer science needs more eponyms, in the vein of [http://en.wikipedia.org/wiki/Mordenkainen#Spells Mordenkainen]. Collect them all, and impress your friends! I might make a project one day of [[book ideas|summarizing these entries]]. | ||
Explicitly ''not included'' in this list are: general logic (Peano and Presburger arithmetic, Herbrandization), 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), nor 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). | |||
Of course, it can't be on the list unless I know about it, so [mailto:dankamongmen@gmail.com feed me eponyms]. | |||
'''UPDATE''' the threshold for inclusion is now: De Morgan's Laws. If you're not | '''UPDATE''' the threshold for inclusion is now: '''De Morgan's Laws'''. If you're not at least as computer sciency as '''De Morgan's Laws''', you ain't gettin' in. [[User:Dank|Dank]] 12:25, 3 October 2011 (CDT) | ||
| Line 17: | Line 17: | ||
* Amdahl's Law | * Amdahl's Law | ||
* Andersen's Algorithm | * Andersen's Algorithm | ||
* the '''Anderson–Björck Algorithm''' improves on the Illinois Algorithm, which is itself an improvement on the ''regula falsi'' method of solving for roots. | |||
* Angluin's algorithm | * Angluin's algorithm | ||
* '''Arikan's PAC Codes''' aka polarization-adjusted convolutional [https://en.wikipedia.org/wiki/Polar_code_(coding_theory) polar coding] outperform CRC-aided and purely convolutional polar codes, approaching the theoretical channel capacity for short blocklengths. | |||
* '''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). | * '''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). | ||
| Line 23: | Line 25: | ||
* Bajard-Kla-Muller algorithm | * Bajard-Kla-Muller algorithm | ||
* Ball-Larus Heuristics | * Ball-Larus Heuristics | ||
* Banerjee | * the '''Banerjee test''' can demonstrate the absence of [[Compiler_Design|control flow dependencies]] in certain types of loops | ||
* Barendregt convention | * Barendregt convention | ||
* Barendregt-Geuvers-Klop Conjecture | * Barendregt-Geuvers-Klop Conjecture | ||
* Barnes-Hut simulation | * Barnes-Hut simulation | ||
* the '''Barton-Nackman trick''' is an idiom in C++ effecting restricted template expansion | |||
* Baskett, Chandy, Muntz and Palacios network | * Baskett, Chandy, Muntz and Palacios network | ||
* Batcher's Odd-Even Merge | * 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 | * '''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 algorithm''' is the theoretically best cache-replacement algorithm, one which discards information that will not be needed until the furthest time into the future (this is not usually knowable) | |||
* '''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 | * '''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 | * Bell-La Padula model | ||
* the '''Bellman Equation''' specifies for a problem the necessary condition for optimality of dynamic programming | |||
* Bellman-Ford Algorithm | * Bellman-Ford Algorithm | ||
* Beneš network | * Beneš network | ||
| Line 40: | Line 45: | ||
* Bernstein conditions | * Bernstein conditions | ||
* Biba Integrity Model | * Biba Integrity Model | ||
* a '''Bleichenbacher Oracle''' signals whether padding is present in a ciphertext; it was used in the first public demonstration of an [https://en.wikipedia.org/wiki/Adaptive_chosen-ciphertext_attack adaptive chosen ciphertext attack] (1998) | |||
* Blinn-Phong shading | * Blinn-Phong shading | ||
* Blom's Scheme | * Blom's Scheme | ||
| Line 52: | Line 58: | ||
* Borůvka's Algorithm | * Borůvka's Algorithm | ||
* Bowyer-Watson Algorithm | * Bowyer-Watson Algorithm | ||
* <b>[https://en.wikipedia.org/wiki/Boyce%E2%80%93Codd_normal_form Boyce-Codd normal form]</b> is slightly stricter than 3NF (the third normal form), and guarantees elimination of all redundancy due to functional dependencies (1974) | |||
* Boyer-Moore Algorithm | * Boyer-Moore Algorithm | ||
* the <b>Brassard-Høyer-Tapp algorithm</b> solves the collision problem on a quantum computer in O(n<sup>⅓</sup>) queries | |||
* Bremermann's Limit | * Bremermann's Limit | ||
* '''Brent's Adder''' is logn + O(log1/2n) depth and O(nlg n) size | * '''Brent's Adder''' is logn + O(log1/2n) depth and O(nlg n) size | ||
* '''Brent's Algorithm''' detects cycles using two pointers, and finds the length of the cycle directly | * '''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 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 | * '''Brent's Theorem''' aka '''Brent's Law''' states that p < N processors can simulate N in T<sub>p</sub> ≤ T<sub>N</sub> + (T<sub>1</sub> - T<sub>N</sub>)/p | ||
* Bresenham's Algorithm | * Bresenham's Algorithm | ||
* Brewer's Theorem | * Brewer's Theorem | ||
| Line 65: | Line 73: | ||
* Brooks-Iyengar Algorithm | * Brooks-Iyengar Algorithm | ||
* Buchberger Algorithm | * Buchberger Algorithm | ||
* the '''Burnside-Dixon Algorithm''' calculates irreducible representations of finite groups | |||
* Burrows-Wheeler Transform | * Burrows-Wheeler Transform | ||
* Buzen's Algorithm | * Buzen's Algorithm | ||
| Line 79: | Line 88: | ||
* Chaitin–Kolmogorov random numbers | * Chaitin–Kolmogorov random numbers | ||
* Chakravala's Algorithm | * Chakravala's Algorithm | ||
* Chan's Algorithm | * '''Chan's Algorithm''' computes the optimal h-point convex hull of n 2- or 3-dimensional points in O(nlgh) | ||
* Chandy-Lamport Algorithm | * Chandy-Lamport Algorithm | ||
* the '''Chang-Roberts Algorithm''' elects leaders for distributed systems. | * the '''Chang-Roberts Algorithm''' elects leaders for distributed systems. | ||
* '''Chen's Algorithm''' is an exact quantum algorithm for testing 2-junta | |||
* '''Chen's Algorithm''' is a single-writer, multiple-reader, wait-free lock using Compare-and-Swap | |||
* the '''Chen-Teboulle Algorithm''' solves the proximal point algorithm efficiently for certain functions | |||
* Cheney's Algorithm | * Cheney's Algorithm | ||
* Chew's Second Algorithm | * Chew's Second Algorithm | ||
| Line 93: | Line 105: | ||
* Church-Rosser Theorem | * Church-Rosser Theorem | ||
* Church-Turing Thesis | * Church-Turing Thesis | ||
* the '''[https://clifford.at/cliffords-device.html Clifford Device]''' exploits <tt>if(0)</tt> to abstract block control via macros (note that e. g. [https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3355.htm N3355] calls this "Claire's Device" following a presumed transition, but Claire still seems to call it Clifford). | |||
* Clos network | * Clos network | ||
* Cobham Axioms | * Cobham Axioms | ||
| Line 110: | Line 123: | ||
* Crusader’s Convergence Algorithm | * Crusader’s Convergence Algorithm | ||
* Curry-Howard correspondence | * Curry-Howard correspondence | ||
* The <b>CVM algorithm</b> (Chakraborty, Variyam, Meel) approximates the number of distinct elements in a large set | |||
* Dadda Multiplier | * Dadda Multiplier | ||
* Damerau-Levenshtein distance | * Damerau-Levenshtein distance | ||
* Damm Algorithm | * Damm Algorithm | ||
* Davis-Putnam Algorithm | * The <b>Davis-Putnam Algorithm</b> verifies formulas in first order logic using the resolution method from prepositional logic. It requires exponential space in the worst case, and only terminates for valid formulae. | ||
* Davis-Putnam-Logemann-Loveland Algorithm | * The <b>Davis-Putnam-Logemann-Loveland Algorithm</b> improves on the basic DP algorithm, requiring linear space in the worst case and terminating for all formulae. | ||
* De Bruijn presentation | * De Bruijn presentation | ||
* De Bruijn string | * De Bruijn string | ||
| Line 121: | Line 135: | ||
* Delaunay's Triangulation | * Delaunay's Triangulation | ||
* Dennard Scaling | * Dennard Scaling | ||
* Deutsch gate | |||
* Diffie-Hellman Key Exchange | * Diffie-Hellman Key Exchange | ||
* Dijkstra's Algorithm | * Dijkstra's Algorithm | ||
| Line 132: | Line 147: | ||
* Earle latch | * Earle latch | ||
* Earley Parser | * Earley Parser | ||
* '''Edholm's law''' predicts doubling of bandwidth every 18 months across wireless, nomadic, and wired networks (and is getting some rather heavy lift from Moore's Law IMHO) | |||
* '''Edmonds's matching algorithm''' constructs maximum matchings on graphs in O(|E||V|²) | * '''Edmonds's matching algorithm''' constructs maximum matchings on graphs in O(|E||V|²) | ||
* Edmonds-Karp Algorithm | * Edmonds-Karp Algorithm | ||
| Line 138: | Line 154: | ||
* van Emde Boas trees | * van Emde Boas trees | ||
* Sieve of Eratosthenes | * Sieve of Eratosthenes | ||
* the '''Eytzinger layout''' stores binary trees in an array in a cache-friendly manner | |||
* Euclid's Algorithm | * Euclid's Algorithm | ||
| Line 143: | Line 160: | ||
* '''Falk diagrams''' graph various performance counters against time (typically expressed in cycles) | * '''Falk diagrams''' graph various performance counters against time (typically expressed in cycles) | ||
* Faugère F5 algorithm | * Faugère F5 algorithm | ||
* Fenwick trees | * '''Fenwick trees''' support efficient update of elements and calculate prefix sums in a table of numbers | ||
* Fiat-Shamir Heuristic | * Fiat-Shamir Heuristic | ||
* Fibonacci Heap | * Fibonacci Heap | ||
| Line 159: | Line 176: | ||
* Fruchterman-Reingold heuristic | * Fruchterman-Reingold heuristic | ||
* '''Fürer's algorithm''' multiplies two ''n''-digit numbers in ''O(nlgn*2<sup>O(lg*n)</sup>)'' | * '''Fürer's algorithm''' multiplies two ''n''-digit numbers in ''O(nlgn*2<sup>O(lg*n)</sup>)'' | ||
* the '''Ferguson-Forcade''' algorithm was the first for the integer relation problem (<i>Bull. Amer. Math 1979</i>) | |||
* Gabbay's separation theorem | * Gabbay's separation theorem | ||
| Line 193: | Line 211: | ||
* Hamming code | * Hamming code | ||
* Hamming distance | * Hamming distance | ||
* the '''Håstad, Just, Lagarias, and Schnorr (HJLS) algorithm''' improves on LLL for the integer relations problem (<i>SIAM J. Comput. 1989</i>) | |||
* '''Heap's algorithm''' generates all permutations of a set with minimum movement (<i>The Computer Journal 1963</i>) | |||
* '''Heckel's algorithm''' isolates changes between files, and is the basis for <tt>diff</tt> [https://dl.acm.org/doi/10.1145/359460.359467 CACM 1978] | * '''Heckel's algorithm''' isolates changes between files, and is the basis for <tt>diff</tt> [https://dl.acm.org/doi/10.1145/359460.359467 CACM 1978] | ||
* Hennessy-Milner Logic | * Hennessy-Milner Logic | ||
| Line 221: | Line 241: | ||
* Jensen's Device | * Jensen's Device | ||
* Johnson's Algorithm | * Johnson's Algorithm | ||
* the '''Jonker-Volgenant Algorithm''' improves '''Kuhn's Algorithm''' to solve the assignment problem in O(n³), Jonker-Volgenant 1987 | |||
* Kabsch Algorithm | * Kabsch Algorithm | ||
* Kadane's Algorithm | * Kadane's Algorithm | ||
* Kahan Summation Algorithm | * Kahan Summation Algorithm | ||
* '''Kahn's Algorithm''' topologically sorts a graph in O(|V| + |E|), Kahn 1962 | |||
* Kannan's Theorem | * Kannan's Theorem | ||
* '''Karatsuba's Algorithm''' multiplies two ''n''-digit numbers using ''n<sup>log<sub>2</sub>3</sup>'' single-digit mults | * '''Karatsuba's Algorithm''' multiplies two ''n''-digit numbers using ''n<sup>log<sub>2</sub>3</sup>'' single-digit mults | ||
| Line 250: | Line 272: | ||
* Koomey's Law | * Koomey's Law | ||
* Kosaraju's Algorithm | * Kosaraju's Algorithm | ||
* '''Krapchenko's Adder''' is an improvement over Brent's Adder, linear (3n + 6*2m, m= | * '''Krapchenko's Adder''' is an improvement over Brent's Adder, linear (3n + 6*2m, m=⌈lg n⌉) in size and logn + O(log1/2n) depth (m + 7(2m)1/2+16, m = ⌈lg n⌉). | ||
* Kruskal's Algorithm | * 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''. | * '''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''. | ||
* '''Kuhn's Algorithm''' (also known as '''Kuhn-Munkres''') solves the assignment problem in polynomial time, Kuhn 1955 | |||
* The '''[Karush-]Kuhn-Tucker conditions''' are a set of tests to determine whether an integer programming solution is optimal, Karush 1931 Kuhn-Tucker 1951 | |||
* Kung-Leiserson systolic array | * Kung-Leiserson systolic array | ||
* Kuroda Normal Form | * Kuroda Normal Form | ||
| Line 265: | Line 289: | ||
* Lehmer's GCD Algorithm | * Lehmer's GCD Algorithm | ||
* Lempel-Ziv-Welch compression | * Lempel-Ziv-Welch compression | ||
* the '''Lenstra-Lenstra-Lovász (LLL)''' algorithm was the first for the integer relation problem that supplied proofs (Math Ann. 1982) | |||
* Levenshtein automaton | * Levenshtein automaton | ||
* Levenshtein distance | * Levenshtein distance | ||
* '''Levialdi's transform''' progressively and deterministically degrades a bitmap | |||
* Levin reduction | * Levin reduction | ||
* Liang-Barsky algorithm | * Liang-Barsky algorithm | ||
| Line 283: | Line 309: | ||
* Mahaney's Theorem | * Mahaney's Theorem | ||
* Manning algorithm | * Manning algorithm | ||
* Margolus gate | |||
* Marzullo algorithm | * Marzullo algorithm | ||
* '''Matiyasevich's theorem''' proves that every [[Theory|recursively enumerable]] set is Diophantine, and thus proves that no algorithm exists for Hilbert's tenth problem | |||
* McFarling-style branch predictor | * McFarling-style branch predictor | ||
* Mead-Conway Rules | * Mead-Conway Rules | ||
| Line 290: | Line 318: | ||
* Merkle–Damgård construction | * Merkle–Damgård construction | ||
* The '''Metropolis-Hastings algorithm''' for MCMC obtains samples from a probability distribution that is [https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm difficult to directly sample] | * The '''Metropolis-Hastings algorithm''' for MCMC obtains samples from a probability distribution that is [https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm difficult to directly sample] | ||
* '''Meyer's flooding algorithm''' computes the [https://en.wikipedia.org/wiki/Watershed_(image_processing) watershed] for an image | |||
* Miller-Rabin Primality Test | * Miller-Rabin Primality Test | ||
* Minsky-Fenichel-Yochelson Algorithm | * Minsky-Fenichel-Yochelson Algorithm | ||
| Line 306: | Line 335: | ||
* Nevill-Manning algorithm | * Nevill-Manning algorithm | ||
* Nick's Class | * Nick's Class | ||
* '''Nielsen's law''' predicts slower growth for home bandwidth than computing power, suggesting that user experience will remain bandwidth-bound | |||
* '''Nielsen's usability heuristics''' are ten (rather debatable) guidelines forming a usability heuristic for interface design | |||
* Nisan's Generator | * Nisan's Generator | ||
* '''Ousterhout's dichotomy/fallacy''' a taxonomy of ''systems'' vs ''scripting'' languages | * '''Ogden's lemma''' extends the pumping lemma to context-free languages | ||
* '''Otsu's Method''' is used to perform automatic image thresholding | |||
* '''Ousterhout's dichotomy/fallacy''' is a taxonomy of ''systems'' vs ''scripting'' languages | |||
* Otway-Rees Protocol | * Otway-Rees Protocol | ||
| Line 314: | Line 347: | ||
* '''Paeth Filter''' performs 2D image compression in PNG | * '''Paeth Filter''' performs 2D image compression in PNG | ||
* PageRank Algorithm | * PageRank Algorithm | ||
* '''Parikh's theorem''' shows that a context free language that doesn't consider order of its terminal symbols can be expressed as a regular language, proving the existence of inherently ambiguous CFLs and that CFLs over singleton alphabets are regular. JACM 1966 | |||
* Peterson's Algorithm | * Peterson's Algorithm | ||
* Petri nets | * Petri nets | ||
| Line 319: | Line 353: | ||
* Phong shading | * Phong shading | ||
* Plotkin's Sticky Bit | * Plotkin's Sticky Bit | ||
* '''Plouffe's Inverter''' was an early symbolic inverter for floating point numbers | |||
* Pollaczek–Khinchine formula | * Pollaczek–Khinchine formula | ||
* Pollard's Kangaroo Algorithm | * Pollard's Kangaroo Algorithm | ||
| Line 339: | Line 374: | ||
* Rader-Brenner Algorithm | * Rader-Brenner Algorithm | ||
* Radovic-Hagersten lock | * Radovic-Hagersten lock | ||
* the '''Ramer-Douglas-Peucker algorithm''' decimates a series of line segments to a similar series of fewer line segments (1973) | |||
* Raymond's Algorithm | * Raymond's Algorithm | ||
* Reed-Muller code | * Reed-Muller code | ||
| Line 362: | Line 398: | ||
* Shamir's Secret Sharing Scheme | * Shamir's Secret Sharing Scheme | ||
* Shamos-Hoey Algorithm | * Shamos-Hoey Algorithm | ||
* '''Shar's Algortihm''' is a variation on the uniform binary search of Knuth. | |||
* Shor's Algorithm | * Shor's Algorithm | ||
* Sipser–Lautemann theorem | * Sipser–Lautemann theorem | ||
| Line 369: | Line 406: | ||
* Steensgaard's Algorithm | * Steensgaard's Algorithm | ||
* Stehlé-Zimmermann algorithm | * Stehlé-Zimmermann algorithm | ||
* Steinhaus-Johnson-Trotter algorithm | * '''Steiner tree problems''' are a class of combinatorial optimization problems involving determining the optimal interconnect of a graph under some objective function. | ||
* the '''Steinhaus-Johnson-Trotter algorithm''' generates all permutations of a set (<i>CACM 1964</i>) | |||
* Strassen's Algorithm | * Strassen's Algorithm | ||
* Suurballe's Algorithm | * Suurballe's Algorithm | ||
| Line 382: | Line 420: | ||
* Toda's theorem | * Toda's theorem | ||
* Todd–Coxeter algorithm | * Todd–Coxeter algorithm | ||
* Tomasulo's | * the '''Toffoli gate''' aka CCNOT is a 3-to-3 universal reversible gate (all other reversible gates can be constructed from it). there is no smaller universal set of reversible gates (the only reversible gates in 1 or 2 inputs are identity, NOT, and CNOT). | ||
* Tomasulo's AlgorithmRemember | |||
* Tonelli-Shanks Algorithm | * Tonelli-Shanks Algorithm | ||
* The '''Toom-Cook Algorithm''' multiplies two ''n''-digit numbers using ''n<sup>log(5)/log(3)</sup>'' single-digit mults | * The '''Toom-Cook Algorithm''' multiplies two ''n''-digit numbers using ''n<sup>log(5)/log(3)</sup>'' single-digit mults | ||
* Tupper's self-referential formula | * Tupper's self-referential formula | ||
* Turing Degree | * Turing Degree | ||
* Turing Machines | * '''Turing Machines''' were used to prove the undecidability of the Entscheidungsproblem in 1936, and have persisted as a rather less elegant model of computation than Church's λ-calculus. | ||
* the '''Turing Test''', originally the "imitation game", was proposed by Turing as a means of evaluating conversational artificial intelligence via questions-and-answers on a text channel. | * the '''Turing Test''', originally the "imitation game", was proposed by Turing as a means of evaluating conversational artificial intelligence via questions-and-answers on a text channel. Its use as a diagnostic is debatable at best. | ||
* Ukkonen's Algorithm | * Ukkonen's Algorithm | ||