Algorithms and Data Structures Glossary (Starting with "U")
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
U
- UB-tree
- UKP: see unbounded knapsack problem
- unary function
- unbounded knapsack problem
- uncomputable function
- uncomputable problem
- undecidable language
- undecidable problem
- undirected graph
- uniform circuit complexity
- uniform circuit family
- uniform hashing
- uniform matrix
- union
- union of automata
- universal B-tree: see UB-tree
- universal hashing
- universal state
- universal Turing machine
- universe
- UnShuffle sort
- unsolvable problem
- unsorted list
- upper triangular matrix
unary function
(definition)
Definition:
A function which takes one argument.
Author: PEB
unbounded knapsack problem
(classic problem)
Definition:
Given types of items of different values and volumes, find the most valuable set of items that fit in a knapsack of fixed volume. The number of items of each type is unbounded. This is an NP-hard combinatorial optimization problem.
Formal Definition: There is a knapsack of capacity c > 0 and N types of items. Each item of type t has value vt > 0 and weight wt > 0. Find the number nt > 0 of each type of item such that they fit, ∑t=1N ntwt ≤ c, and the total value, ∑t=1N ntvt, is maximized.
Also known as UKP.
Author: PEB
uncomputable function
(definition)
Definition:
A function that cannot be computed by any algorithm --- equivalently, not by any Turing machine.
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
undecidable language
(definition)
Definition:
A language for which the membership cannot be decided by an algorithm --- equivalently, cannot be recognized by a Turing machine that halts for all inputs.
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
undecidable problem
(definition)
Definition:
A problem that cannot be solved for all cases by any algorithm whatsoever---equivalently, whose associated language cannot be recognized by a Turing machine that halts for all inputs.
Specialization (... is a kind of me.)
halting problem, Post's correspondence problem.
Note:
From Algorithms and Theory of Computation Handbook, page 24-19 or 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
undirected graph
(data structure)
Definition:
A graph whose edges are unordered pairs of vertices. That is, each edge connects two vertices.
Formal Definition: A graph G is a pair (V,E), where V is a set of vertices, and E is a set of edges between the vertices E ⊆ {{u,v} | u, v ∈ V}. If the graph does not allow self-loops, adjacency is irreflexive, that is E ⊆ {{u,v} | u, v ∈ V ∧ u ≠ v}.
Note:
An undirected graph may be represented as a directed graph with two directed edges, one "to" and one "from," for each undirected edge.
Author: PEB
uniform circuit complexity
(definition)
Definition:
The study of complexity classes defined by uniform circuit families.
Note:
From Algorithms and Theory of Computation Handbook, page 27-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
uniform circuit family
(definition)
Definition:
A sequence of circuits, one for each input length n, that can be efficiently generated by a Turing machine.
Note:
From Algorithms and Theory of Computation Handbook, page 27-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
uniform hashing
(algorithm)
Definition:
A conceptual method of open addressing for a hash table. A collision is resolved by putting the item in the next empty place given by a probe sequence which is independent of sequences for all other key.
Note:
Since the probe sequences are independent, this is free of clustering. This is conceptual because real probe sequences are unlikely to be completely independent.
Author: PEB
uniform matrix
(data structure)
Definition:
A matrix having the same number of items in each row.
Specialization (... is a kind of me.)
square matrix, rectangular matrix.
Author: PEB
union
(definition)
Definition:
The union of two sets is a set having all members in either set.
Note:
The union of {2, 3, 5} and {7, 5, 8} is {2, 3, 5, 7, 8}.
Author: PEB
union of automata
(algorithm)
Definition:
Find an automaton that accepts everything which the automata accept individually.
Author: PEB
universal hashing
(definition)
Definition:
A scheme that chooses randomly from a set of hash functions.
Note:
From Algorithms and Theory of Computation Handbook, page 2-14, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
universal state
(definition)
Definition:
A state in an alternating Turing machine from which the machine accepts only if all possible moves lead to acceptance.
Note:
From Algorithms and Theory of Computation Handbook, page 24-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
universal Turing machine
(definition)
Definition:
A Turing machine that is capable of simulating any other Turing machine by encoding the latter.
Note:
From Algorithms and Theory of Computation Handbook, pages 24-19 and 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
universe
(definition)
Definition:
All potential elements of a set.
Author: PEB
UnShuffle sort
(algorithm)
Definition:
A distribution sort with two phases. In the first phase, the inputs are distributed among doubly-ended queues keeping the items in each queue ordered and creating a new queue when there is no place on an existing queue. The second phase is an ideal merge in which the item to be removed is determined by keeping the queues in a priority queue.
Generalization (I am a kind of ...)
distribution sort.
Aggregate child (... is a part of or used in me.)
ideal merge, pile, priority queue.
Note:
The doubly-ended queue with ordered items is called a pile. The UnShuffle algorithm is the most efficient available for sorting data streams that exhibit low entropy, i.e., are already mostly sorted or contains runs of sorted elements. The run time is Θ(N) for sorted input. The general case is NK/2 + N log K where K is the entropy of the input and is manifest in the number of piles generated during the distribution phase.
Author: ASK
More information
Art S. Kagel, Unshuffle Algorithm, Not Quite a Sort?, Computer Language Magazine, 3(11), November 1985.
unsolvable problem
(definition)
Definition:
A computational problem that cannot be solved by a Turing machine. The associated function is called an uncomputable function.
Note:
From Algorithms and Theory of Computation Handbook, page 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
unsorted list
(definition)
Definition:
A list whose order of items, if any, is not known.
Note:
The list need not be out of order, simply that it is not known to be in order.
Author: PR
upper triangular matrix
(data structure)
Definition:
A matrix that is only defined at (i,j) when i ≤ j.
Generalization (I am a kind of ...)
matrix.
Specialization (... is a kind of me.)
strictly upper triangular matrix.
Note:
For example It may be more compactly represented in an array by storing entry (i,j) in location n(i-1) + j - i(i-1)/2 = (2n-i)(i-1)/2 + j one-based indexing.
Author: PEB
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
|