Algorithms and Data Structures Glossary (Starting with "Z")
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
Z
 Zeller's congruence
 0ary function
 0based indexing
 01 knapsack problem: see knapsack problem
 ZhuTakaoka
 Zipfian distribution
 Zipf's law
 zipper
 ZPP
Zeller's congruence
(algorithm)
Definition:
An algorithm to find the day of the week for any date.
Author: PEB
More information
Wikipedia entry for Zeller's congruence. A summary of the International Standard Date and Time Notation ISO 8601. The full ISO 8601:2004 standard.
Christian Zeller, KalenderFormeln, Acta Mathematica, 9:1316, Nov 1886.
0ary function
(definition)
Definition:
A function that takes no arguments.
Also known as nullary function.
Note:
Pronounced "zeroairy". By analogy to unary, binary, etc. A 0ary or nullary function that is pure (no state or interactions with external variables) must be a constant function.
Author: PEB
0based indexing
(definition)
Definition:
Indexing (an array) beginning with 0.
Aggregate parent (I am a part of or used in ...)
array.
Note:
That is, an array A with n items is accessed as A[0], A[1], ..., A[n1].
Author: PEB
ZhuTakaoka
(algorithm)
Definition:
A string matching algorithm that is a variant of the BoyerMoore algorithm. It uses two consecutive text characters to compute the bad character shift. It is faster when the alphabet or pattern is small, but the skip table grows quickly, slowing the preprocessing phase.
Author: BB
More information
R. F. Zhu and T. Takaoka, On improving the average case of the BoyerMoore string matching algorithm, J. Inform. Process. 10(3):173177 (1987).
Zipfian distribution
(definition)
Definition:
A distribution of probabilities of occurrence that follows Zipf's law.
Also known as Yule distribution.
Note:
The distribution of words is often proportional to a function like 1/n^{a}.
Author: PEB
Zipf's law
(definition)
Definition:
The probability of occurrence of words or other items starts high and tapers off. Thus, a few occur very often while many others occur rarely.
Formal Definition: P_{n} 1/n^{a}, where P_{n} is the frequency of occurrence of the n^{th} ranked item and a is close to 1.
Note:
In the English language words like "and," "the," "to," and "of" occur often while words like "undeniable" are rare. This law applies to words in human or computer languages, operating system calls, colors in images, etc., and is the basis of many (if not, all!) compression approaches. Named for George Kingsley Zipf.
Author: PEB
zipper
(data structure)
Definition:
A data structure equivalent to a binary tree that is "opened" so that some node is accessible. It consists of a pair: the current node, along with information to reconstruct the tree. Reconstruction information is called the path or context. A movetoleftchild operation returns the left subtree, along with a new path, which has (i) a Left value, (ii) the current node, (iii) the right subtree, and (iv) any previous path. A similar operation moves to the right child. A moveup operation returns a tree rebuilt from the path information and the current node, along with the previous path.
Note:
In functional programming languages, a zipper acts as a "pointer" into a tree. The name comes from visualizing the movetochild operation as unzipping a tree. (Instead of two halves, though, movetochild keeps the pieces in a kary tree: the path.)
Author: PEB
More information
Gérard Huet, The Zipper, Journal of Functional Programming, 7(5):549554, 1997.
ZPP
(definition)
Definition:
The class of languages for which a membership computation by a probabilistic Turing machine halts in polynomial time with no false acceptances or rejections, but randomly some "I don't know" answers. "ZPP" means "Zero error Probability in Polynomial" time.
Formal Definition: For a language, S, there exists a probabilistic Turing machine, M, that halts in polynomial time. M (correctly) accepts or rejects the string or, randomly, halts in an "I don't know" state.
Note:
By repeating the run, the correct answer will always be found, albeit with polynomial expected run time. After [Hirv01, page 19].
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
