Algorithms and Data Structures Glossary Free glossaries at TanslationDirectory.com translation jobs
Home Free Glossaries Free Dictionaries Post Your Translation Job! Free Articles Jobs for Translators

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



A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

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
j
i 1776
-911
--88
---1

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



A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

 

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






Free Newsletter

Subscribe to our free newsletter to receive news from us:

 

Menu

Use More Glossaries
Use Free Dictionaries
Use Free Translators
Submit Your Glossary
Read Translation Articles
Register Translation Agency
Submit Your Resume
Obtain Translation Jobs
Subscribe to Free Newsletter
Buy Database of Translators
Obtain Blacklisted Agencies
Vote in Polls for Translators
Read News for Translators
Advertise Here
Read our FAQ
Read Testimonials
Use Site Map

Advertisements

translation directory

christianity portal
translation jobs


 

 
Copyright © 2003-2024 by TranslationDirectory.com
Legal Disclaimer
Site Map