Algorithms and Data Structures Glossary
(Starting with "N")
By
www.nist.gov,
Gaithersburg, Maryland, U.S.A.
paul
. black [at] nist . gov
http://www.nist.gov/dads
Become a member of TranslationDirectory.com at just
$12 per month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
N
- naive string search: see brute force string search
- nand
- n-ary function
- NC many-one reducibility
- nearest neighbor
- negation
- network flow: see flow function
- network flow problem: see maximum-flow problem
- next state
- NFA: see nondeterministic finite state machine
- NFTA: see nondeterministic finite tree automaton
- NIST
- node
- nonbalanced merge
- nonbalanced merge sort
- nondeterministic
- nondeterministic algorithm
- nondeterministic finite automaton: see nondeterministic finite state machine
- nondeterministic finite state machine
- nondeterministic finite tree automaton
- nondeterministic polynomial time: see NP
- nondeterministic tree automaton
- nondeterministic Turing machine
- nonterminal node: see internal node
- nor
- not
- Not So Naive
- NP
- NP-complete
- NP-complete language
- NP-hard
- n queens
- nullary function: see 0-ary function
- null tree
- NYSIIS
nand
(definition)
Definition:
Negated conjunction: 0 AND 0 = 1, 0 AND 1 = 1, 1 AND 0 = 1, 1 AND 1 = 0.
Note:
NAND is equivalent to AND followed by NOT. It is of particular interest because all possible boolean functions can be built with combinations of NANDs, and a NAND gate is easily built.
Author: PEB
n-ary function
(definition)
Definition:
(1) A function with exactly n arguments. (2) A function which takes any number of arguments, or a variable number of arguments.
Note:
By analogy with unary, binary, etc.
Author: PEB
NC many-one reducibility
(definition)
Definition:
A language L is NC many-one reducible or NC reducible to L', written L ≤mNC L' if there is a function f in FNC such that x ∈ L if and only if f(x) ∈ L'.
Note:
From Algorithms and Theory of Computation Handbook, page 45-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
nearest neighbor
(classic problem)
Definition:
Find the point (rectangle, line, etc.) that is closest to another point.
Author: PEB
More information
A Voronoi diagram divides a plane into regions of nearest neighbors.
negation
(definition)
Definition:
The negation of 0 is 1; the negation of 1 is 0.
Author: PEB
next state
(definition)
Definition:
The state immediately following the current state, defined by the transition function of a finite state machine and the input.
Author: LH
NIST
(definition)
Definition:
The United States National Institute of Standards and Technology.
Author: PEB
node
(definition)
Definition:
(1) A unit of reference in a data structure. Also called a vertex in graphs and trees. (2) A collection of information which must be kept at a single memory location.
Author: PEB
nonbalanced merge sort
(algorithm)
Definition:
A k-way merge sort in which the number of input and output data streams is different for any particular pass. Typically P input streams are merged and distributed to T output streams on one pass followed by a merge of the T inputs and distribution to P outputs.
Author: ASK
nondeterministic
(definition)
Definition:
Permitting more than one choice of next move at some step in a computation.
Note:
From Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
nondeterministic algorithm
(algorithmic technique)
Definition:
A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step. It is not random, as in randomized algorithm, or indeterminate. Rather it has the supercomputational characteristic of choosing the optimal behavior.
Note:
Conceptually a nondeterministic algorithm could run on a deterministic computer with an unlimited number of parallel processors. Each time more than one step is possible, new processes are instantly forked to try all of them. When one successfully finishes, that result is returned. Thus the computation is as fast as if it always chooses the right step. This notion is defined for theoretic analysis and specifying. Nondeterministic algorithms compute the same class of functions as deterministic algorithms, but the complexity may be much less. Every nondeterministic algorithm can be turned into a deterministic algorithm, possibly with exponential slow down. Consider searching an unordered array. A linear search has Θ(n) expected time. A nondeterministic search has constant expected time.
int search(key k, array a)
{
return oracleRandom(0, sizeof(a));
} where oracleRandom() returns (the right) number between 0 and the size of the array in constant time.
Author: PEB
nondeterministic finite state machine
(definition)
Definition:
A finite state machine whose transition function maps inputs symbols and states to a (possibly empty) set of next states. The transition function also may map the null symbol (no input symbol needed) and states to next states.
Also known as NFA, nondeterministic finite automaton.
Note:
Any such machine may be converted to a deterministic finite state machine, although the number of states may increase by an exponential amount.
Thanks to Thorsten Jens (thojens@gmx.de) and Yaacov Yesha (yayesha@cs.umbc.edu) for correcting this entry. 17 January 2001.
Author: PEB
nondeterministic finite tree automaton
(definition)
Definition:
A nondeterministic finite state machine that accepts finitary trees rather than just strings. The tree nodes are marked with the letters of the alphabet of the automaton, and the transition function encodes the next states for each branch of the tree. The acceptance condition is modified accordingly.
Also known as NFTA.
Author: SKS
More information
Tree Automata Techniques and Applications page.
nondeterministic tree automaton
(definition)
Definition:
A nondeterministic finite state machine that accepts infinite trees rather than just strings. The tree nodes are marked with the letters of the alphabet of the automaton, and the transition function encodes the next states for each branch of the tree. The expressive power of such automata varies depending on the acceptance conditions of the trees.
Author: SKS
More information
Tree Automata Techniques and Applications page.
nondeterministic Turing machine
(definition)
Definition:
A Turing machine which has more than one next state for some combinations of contents of the current cell and current state. An input is accepted if any move sequence leads to acceptance.
Note:
A nondeterministic Turing machine is a probabilistic Turing machine ignoring the probabilities.
From Algorithms and Theory of Computation Handbook, page 24-9, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
nor
(definition)
Definition:
Negated disjunction: 0 NOR 0 = 1, 0 NOR 1 = 0, 1 NOR 0 = 0, 1 NOR 1 = 0.
Note:
NOR is equivalent to OR followed by NOT. It is of interest because all possible boolean functions can be built with combinations of NORs.
Author: PEB
not
(definition)
Definition:
Negation: NOT 0 = 1, NOT 1 = 0. Also known as complement.
Author: PEB
NP
(definition)
Definition:
The complexity class of decision problems for which answers can be checked by an algorithm whose run time is polynomial in the size of the input. Note that this doesn't require or imply that an answer can be found quickly, only that any claimed solution can be verified quickly. "NP" is the class that a Nondeterministic Turing machine accepts in Polynomial time.
Also known as nondeterministic polynomial time.
Specialization (... is a kind of me.)
NP-complete.
Note:
For instance, a "yes" answer to the question, "is there a Hamiltonian cycle, or tour, of a certain graph?" can be quickly checked given a certificate for the answer. We can quickly check that the path which is the certificate, indeed, starts and ends at the same vertex, contains every other vertex exactly once, and only uses valid edges. Another example is that a purported sorting of an input can be verified in O(n log n). This can be done by sorting the input (again), then comparing it with the purported sorting.
Being in NP doesn't require that a negative answer, e.g. "there is no tour", can be quickly checked.
Author: PEB
More information
History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to P vs. NP. Wikipedia entry on Complexity classes P and NP. Scott Aaronson's Complexity Zoo
NP-complete
(definition)
Definition:
The complexity class of decision problems for which answers can be checked for correctness, given a certificate, by an algorithm whose run time is polynomial in the size of the input (that is, it is NP) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly, and a quick algorithm to solve this problem can be used to solve all other NP problems quickly.
Generalization (I am a kind of ...)
NP.
Note:
A trivial example of NP, but (presumably) not NP-complete is finding the bitwise AND of two strings of N boolean bits. The problem is NP, since one can quickly (in time Θ(N)) verify that the answer is correct, but knowing how to AND two bit strings doesn't help one quickly find, say, a Hamiltonian cycle or tour of a graph. So bitwise AND is not NP-complete (as far as we know). Other well-known NP-complete problems are satisfiability (SAT), traveling salesman, the bin packing problem, and the knapsack problem. (Strictly the related decision problems are NP-complete.) "NP" comes from the class that a Nondeterministic Turing machine accepts in Polynomial time.
Author: PEB
More information
History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to P vs. NP. Eppstein's longer, but very good introduction to NP-completeness, with sections like Why should we care?, Examples of problems in different classes, and how to prove a problem is NP-complete. A compendium of NP optimization problems.
Scott Aaronson's Complexity Zoo
NP-complete language
(definition)
Definition:
A language in NP such that every language in NP can be reduced to it in polynomial time.
Note:
From Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
NP-hard
(definition)
Definition:
The complexity class of decision problems that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time. When a decision version of a combinatorial optimization problem is proved to belong to the class of NP-complete problems, then the optimization version is NP-hard.
Specialization (... is a kind of me.)
unbounded knapsack problem.
Note:
For example, "is there a Hamiltonian cycle with length less than k" is NP-complete: it is easy to determine if a proposed certificate has length less than k. The optimization problem, "what is the shortest tour?", is NP-hard, since there is no easy way to determine if a certificate is the shortest. Another NP-complete problem is to decide if there exist k star-shaped polygons whose union is equal to a given simple polygon, for some parameter k. The optimization problem, i.e., finding the minimum number (least k) of star-shaped polygons whose union is equal to a given simple polygon, is NP-hard.
From Algorithms and Theory of Computation Handbook, page 19-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
More information
History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to P vs. NP. Scott Aaronson's Complexity Zoo
n queens
(classic problem)
Definition:
Place n chess queens on an n × n board such that no queen can attack another. Efficiently find all possible placements.
Note:
A backtracking algorithm may be efficient enough for small values of n.
Author: PEB
null tree
(definition)
Definition:
(1) A tree which is empty. (2) A tree whose leaf nodes all have a null value.
Author: PR
NYSIIS
(algorithm)
Definition:
Convert a name to a phonetic coding of up to six characters.
Generalization (I am a kind of ...)
phonetic coding, algorithm.
Author: PEB
More information
Robert L. Taft, Name Search Techniques, New York State Identification and Intelligence System, Special Report No. 1, Albany, New York, 1970.
Published - April 2009
Find free glossaries at TranslationDirectory.com
Find free dictionaries at TranslationDirectory.com
Subscribe to free TranslationDirectory.com newsletter
Need more translation jobs from translation agencies? Click here!
Translation agencies are welcome to register here - Free!
Freelance translators are welcome to register here - Free!
Submit your glossary or dictionary for publishing at TranslationDirectory.com
|
