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 "G")

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

G

Galil-Giancarlo
Galil-Seiferas
gamma function
GBD-tree
GCD: see greatest common divisor
geometric optimization problem
global optimum
gnome sort
graph
graph coloring
graph concentration
graph drawing
graph isomorphism
graph partition
Gray code
greatest common divisor
greedy algorithm
greedy heuristic
grid drawing
grid file
Grover's algorithm

gamma function

(definition)

Definition: The gamma function of n, written Γ(n), is ∫ 0 e-xxn-1dx. Recursively Γ(n+1) = nΓ(n). For non-negative integers Γ(n+1) = n!.

Note: The gamma function is defined for all numbers whereas factorial is (strictly) only defined for non-negative integers.

Author: PEB

More information

MathWorld's gamma function


GBD-tree

(data structure)

Definition: A generalized BD-tree, hence the name, which stores spatially extended objects as a hierarchy of minimum bounding boxes. It is a balanced multiway tree which serves as a spatial access method.

Generalization (I am a kind of ...)
spatial access method.

Note: After [GG98, page 211].

Author: PEB

More information

Yutaka Ohsawa and Masao Sakauchi, A New Tree Type Data Structure with Homogeneous Nodes Suitable for a Very Large Spatial Database, Proc. Sixth International Conference on Data Engineering, February 5-9, 1990, Los Angeles, California, USA, pages 296-303.


geometric optimization problem

(definition)

Definition: An optimization problem induced by a collection of geometric objects.

Note: Since the variables and constraints come from physical situations, faster algorithms can often be developed. Adapted from [AS98, page 413].

Author: PEB


global optimum

(definition)

Definition: The best possible solution to a problem.

Note: Some search methods may get trapped in a local optimum and miss the global optimum.

Author: PEB


gnome sort

(algorithm)

Definition: Put items in order by comparing the current item with the previous item. If they are in order, move to the next item (or stop if the end is reached). If they are out of order, swap them and move to the previous item. If there is no previous item, move to the next item.

Generalization (I am a kind of ...)
stable sort, in-place sort.

Note: Complexity is O(n2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning.

This can be seen as an insertion sort that only keeps track of the current item. After having moved an item backward into place, it "walks" forward, checking the order of items as it goes, until it reaches the next item is out of place, which is beyond where progress left off.

This can be seen as a bidirectional bubble sort that intelligently reverses direction, instead of making complete passes.

Dick Grune, the inventor, calls this "the simplest sort algorithm."

Author: PEB


graph

(data structure)

Definition: A set of items connected by edges. Each item is called a vertex or node. Formally, a graph is a set of vertices and a binary relation between vertices, adjacency.

Formal Definition: A graph G can be defined as 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 is undirected, the adjacency relation defined by the edges is symmetric, or E ⊆ {{u,v} | u, v ∈ V} (sets of vertices rather than ordered pairs). If the graph does not allow self-loops, adjacency is irreflexive.

Specialization (... is a kind of me.)
directed graph, undirected graph, acyclic graph, directed acyclic graph, planar graph, biconnected graph, connected graph, complete graph, dense graph, sparse graph, hypergraph, multigraph, labeled graph, weighted graph, tree.

Aggregate child (... is a part of or used in me.)
vertex, edge, Implementations: adjacency-list representation, adjacency-matrix representation.

Note: Graphs are so general that many other data structures, such as trees, are just special kinds of graphs.

A graph is like a road map. Cities are vertices. Roads from city to city are edges. (How about junctions or branches in a road? You could consider junctions to be vertices, too. If you don't want to count them as vertices, a road may connect more than two cities. So strictly speaking you have hyperedges in a hypergraph. If you want to allow more than one road between each pair of cities, you have a multigraph, instead. It all depends on how you want to define it.)

Another way to think of a graph is as a bunch of dots connected by lines. Because mathematicians stopped talking to regular people long ago, the dots in a graph are called vertices, and the lines that connect the dots are called edges. The important things are edges and the vertices: the dots and the connections between them. The actual position of a given dot or the length or straightness of a given line isn't at issue. Thus the dots can be anywhere, and the lines that join them are infinitely stretchy. Moreover, a mathematical graph is not a comparison chart, nor a diagram with an x- and y-axis, nor a squiggly line on a stock report. A graph is simply dots and lines between them---pardon me, vertices and edges.
    Michael Bolton <mb@michaelbolton.net> 22 February 2000

Authors: PEB,PJT

More information

Journal of Combinatorics dynamic surveys DS8 and DS9 are a bibliography and glossary of graphs. Deepayan Chakrabarti and Christos Faloutsos, Graph Mining: Laws, Generators, and Algorithms, ACM Computing Surveys, Vol. 38, March 2006, Article 2.
A great list of graph generators and their strengths and weaknesses.


graph coloring

(definition)

Definition: See vertex coloring, edge coloring, or k-coloring.

Author: PEB


graph concentration

(definition)

Definition: Contracting a graph by removing a subset of the vertices.

Note: From Algorithms and Theory of Computation Handbook, page 47-39, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A


graph drawing

(classic problem)

Definition: The problem of representing a graph in a plane "neatly," for instance with a minimum number of edge crossings.

Author: PEB


graph isomorphism

(classic problem)

Definition: Determine if two graphs are isomorphic.

Author: PEB


graph partition

(classic problem)

Definition:Partition the vertices while keeping the cost of spanning edges low.

Aggregate child (... is a part of or used in me.)
graph.

Author: PEB


Gray code

(definition)

Definition: An ordering of 2n binary numbers such that only one bit changes from one entry to the next. Gray codes for 4 or more bits are not unique, even allowing for permutation or inversion of bits.

Aggregate parent (I am a part of or used in ...)
Karnaugh map.

Note: Gray codes are particularly useful in mechanical encoders since a slight change in position only affects one bit. Using a typical binary code, up to n bits could change, and slight misalignments between reading elements could cause wildly incorrect readings.

An n-bit Gray code corresponds to a Hamiltonian cycle on an n-dimensional hypercube.

A Gray code was used in a telegraph demonstrated by French engineer Émile Baudot in 1878. Frank Gray, a Bell Labs researcher, patented a method using the codes in 1953.

See the Wikipedia entry for Gray code for more information.

See the links for polynomial-time algorithms to convert between binary numbers and certain Gray codes.

Author: PEB

More information

Image of a Gray code rotary railroad control.

Frank Gray, Pulse Code Communication, U.S. Patent 2,632,058, filed 13 November 1947, issued 17 March 1953.


greatest common divisor

(algorithm)

Definition: (1) The greatest integer which is a divisor of given positive integers. For instance, GCD(30, 42) = 6. (2) An algorithm to find the same.

Also known as GCD, highest common factor.

Note: After [CLR90, page 804].

Author: PEB


greedy algorithm

(algorithmic technique)

Definition: An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems.

Specialization (... is a kind of me.)
Dijkstra's algorithm, Huffman coding, Kruskal's algorithm, optimal merge, Prim-Jarnik algorithm.

Note:Prim-Jarnik algorithm and Kruskal's algorithm are greedy algorithms that find the globally optimal solution, a minimum spanning tree. In contrast, any known greedy algorithm to find a Hamiltonian cycle might not find the shortest path, that is, a solution to the traveling salesman problem.

If there is no greedy algorithm that always finds the optimal solution for a problem, one may have to search (exponentially) many possible solutions to find the optimum. Greedy algorithms are usually quicker, since they don't consider the details of possible alternatives.

Author: PEB


greedy heuristic

(algorithmic technique)

Definition: Solve an optimization problem by finding locally optimal solutions.

Note: From Algorithms and Theory of Computation Handbook, page 1-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


grid drawing

(definition)

Definition: A graph drawing in which each vertex is represented by a point with integer coordinates.

Note: From Algorithms and Theory of Computation Handbook, page 9-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


grid file

(data structure)

Definition: A point access method which splits space into a nonperiodic grid. Each spatial dimension is divided by a linear hash. Small sets of points are referred to by one or more cells of the grid.

Note: After [GG98].

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