upload
National Institute of Standards and Technology
Domeniu: Technology
Number of terms: 2742
Number of blossaries: 0
Company Profile:
The National Institute of Standards and Technology (NIST) — known between 1901 and 1988 as the National Bureau of Standards (NBS) — is a measurement standards laboratory and a non-regulatory agency of the United States Department of Commerce. The institute's official mission is to promote U.S. ...
(1) A vertex of a directed graph with no incoming edges. More formally, a vertex with in-degree 0. (2) The vertex from which an edge of a directed graph leaves.
Industry:Computer science
(1) An acyclic network of inputs, logic gates, and outputs. Contrasted with a Turing machine, it has no memory. (2) A cycle in a graph.
Industry:Computer science
(1) Any function that is a constant times the logarithm of the argument: f(x)=c log x. (2) In complexity theory, when the measure of computation, m(n) (usually execution time or memory space), is bounded by a logarithmic function of the problem size, n. More formally m(n) = O(log n). (3) Sometimes imprecisely used to mean polylogarithmic.
Industry:Computer science
(1) Any function which is a constant times the argument plus a constant: f(x)&#61;c<sub>1</sub>x + c<sub>0</sub>. (2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by a linear function of the problem size, n. More formally m(n) &#61; O(n).
Industry:Computer science
(1) Any function which is the sum of constants times other constants to the power of the argument: f(x)&#61;Σ<sub>i&#61;0</sub><sup>k</sup> c<sub>i</sub>b<sub>i</sub><sup>xp<sub>i</sub></sup>. (2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by an exponential function of the problem size, n. More formally if there exists k > 1 such that m(n) &#61; Θ(k<sup>n</sup>) and there exists c such that m(n) &#61; O(c<sup>n</sup>).
Industry:Computer science
(1) Any function which is the sum of constants times powers of a logarithm of the argument: f(x)&#61;Σ<sub>i&#61;0</sub><sup>k</sup>c<sub>i</sub>log<sup>p<sub>i</sub></sup> x. (2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by a polylogarithmic function of the problem size, n. More formally m(n) &#61; O(log<sup>k</sup> n).
Industry:Computer science
(1) Any function which is the sum of constants times powers of the argument: f(x)&#61;Σ<sub>i&#61;0</sub><sup>k</sup> c<sub>i</sub>x<sup>p<sub>i</sub></sup>. (2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by a polynomial function of the problem size, n. More formally m(n) &#61; O(n<sup>k</sup>).
Industry:Computer science
(1) Any search algorithm that considers outgoing edges (children) of a vertex before any of the vertex's siblings, that is, outgoing edges of the vertex's predecessor in the search. Extremes are searched first. This is easily implemented with recursion. (2) An algorithm that marks all vertices in a directed graph in the order they are discovered and finished, partitioning the graph into a forest.
Industry:Computer science
(1) Dealing with or restricted to a space where location can be completely described with exactly k orthogonal axes. (2) Dealing with a space of any number of dimensions.
Industry:Computer science
(1) Extra information so the correctness of an answer to a decision problem can be quickly checked. (2) For any graph property P and graph G, a certificate for G is a graph G' such that G has property P if and only if G' has the property.
Industry:Computer science