- 行业: Technology
- Number of terms: 2742
- Number of blossaries: 0
- Company Profile:
The National Institute of Standards and Technology (NIST) — known between 1901 and 1988 as the National Bureau of Standards (NBS) — is a measurement standards laboratory and a non-regulatory agency of the United States Department of Commerce. The institute's official mission is to promote U.S. ...
Given a set of points in a plane and an integer k ≤ ( n OVER 2 ), find the line between pairs of points which has the k<sup>th</sup> smallest slope.
Industry:Computer science
Given an array A of n elements and a positive integer k ≤ n, find the k<sup>th</sup> smallest element of A and partition the array such that A(1), ..., A(k-1) ≤ A(k) ≤ A(k+1), ..., A(n).
Industry:Computer science
Given an encoding α of a boolean circuit α, inputs x<sub>1</sub>, ... , x<sub>n</sub> and a designated output y, the problem of deciding if output y of α is true on input x<sub>1</sub>, ... , x<sub>n</sub>.
Industry:Computer science
Given items of different values and volumes, find the most valuable set of items that fit in a knapsack of fixed volume. Formal Definition: There is a knapsack of capacity c > 0 and N items. Each item has value v<sub>i</sub> > 0 and weight w<sub>i</sub> > 0. Find the selection of items (δ<sub>i</sub> = 1 if selected, 0 if not) that fit, ∑<sub>i=1</sub><sup>N</sup> δ<sub>i</sub>w<sub>i</sub> ≤ c, and the total value, ∑<sub>i=1</sub><sup>N</sup> δ<sub>i</sub>v<sub>i</sub>, is maximized.
Industry:Computer science
Given materials of different values per unit volume and maximum amounts, find the most valuable mix of materials which fit in a knapsack of fixed volume. Since we may take pieces (fractions) of materials, a greedy algorithm finds the optimum. Take as much as possible of the material that is most valuable per unit volume. If there is still room, take as much as possible of the next most valuable material. Continue until the knapsack is full.
Industry:Computer science
Given materials of different values per unit volume and maximum amounts, find the most valuable mix of materials which fit in a knapsack of fixed volume. Since we may take pieces (fractions) of materials, a greedy algorithm finds the optimum. Take as much as possible of the material that is most valuable per unit volume. If there is still room, take as much as possible of the next most valuable material. Continue until the knapsack is full.
Industry:Computer science
Given n tape drives, one input and n-1 work drives, distribute a portion of the input to n-2 tapes, then merge them onto the final tape reading the n-2 backward. Repeat until n-2 (backward) merged runs have been created, at which time they are merged. Continue building up powers of n-2 batches until done.
Industry:Computer science
Given three posts (towers) and n disks of decreasing sizes, move the disks from one post to another one at a time without putting a larger disk on a smaller one. The minimum is 2<sup>n</sup>-1 moves. The "ancient legend" was invented by De Parville in 1884.
A solution using recursion is: to move n disks from post A to post B 1) recursively move the top n-1 disks from post A to C, 2) move the n<sup>th</sup> disk from A to B, and 3) recursively move the n-1 disks from C to B. A solution using iteration is: on odd-numbered moves, move the smallest disk clockwise. On even-numbered moves, make the single other move which is possible.
Industry:Computer science
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 v<sub>t</sub> > 0 and weight w<sub>t</sub> > 0. Find the number n<sub>t</sub> > 0 of each type of item such that they fit, ∑<sub>t=1</sub><sup>N</sup> n<sub>t</sub>w<sub>t</sub> ≤ c, and the total value, ∑<sub>t=1</sub><sup>N</sup> n<sub>t</sub>v<sub>t</sub>, is maximized.
Industry:Computer science
