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
$8 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
 nary function
 NC manyone reducibility
 nearest neighbor
 negation
 network flow: see flow function
 network flow problem: see maximumflow 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
 NPcomplete
 NPcomplete language
 NPhard
 n queens
 nullary function: see 0ary 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
nary 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 manyone reducibility
(definition)
Definition:
A language L is NC manyone reducible or NC reducible to L', written L ≤_{m}^{NC} 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 4523, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 kway 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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 249, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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.)
NPcomplete.
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
NPcomplete
(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 NPcomplete 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 NPcomplete 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 NPcomplete (as far as we know). Other wellknown NPcomplete problems are satisfiability (SAT), traveling salesman, the bin packing problem, and the knapsack problem. (Strictly the related decision problems are NPcomplete.) "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 NPcompleteness, with sections like Why should we care?, Examples of problems in different classes, and how to prove a problem is NPcomplete. A compendium of NP optimization problems.
Scott Aaronson's Complexity Zoo
NPcomplete 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 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
NPhard
(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 NPcomplete problems, then the optimization version is NPhard.
Specialization (... is a kind of me.)
unbounded knapsack problem.
Note:
For example, "is there a Hamiltonian cycle with length less than k" is NPcomplete: it is easy to determine if a proposed certificate has length less than k. The optimization problem, "what is the shortest tour?", is NPhard, since there is no easy way to determine if a certificate is the shortest. Another NPcomplete problem is to decide if there exist k starshaped 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 starshaped polygons whose union is equal to a given simple polygon, is NPhard.
From Algorithms and Theory of Computation Handbook, page 1926, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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
