36967 research outputs found
Sort by
A New Algorithm for Generating Prime Implicants
No full text[[abstract]]This paper describes an algorithm which will generate all the prime implicants of a Boolean function. The algorithm is different from those previously given in the literature, and in many cases it is more efficient. It is proved that the algorithm will find all the prime implicants. The algorithm may possibly generate some nonprime implicants. However, using frequency orderings on literals, the experiments with the algorithm show that it usually generates very few ( possibly none) nonprime implicants. Furthermore, the algorithm may be used to find the minimal sums of a Boolean function. The algorithm is implemented by a computer program in the LISP language.[[fileno]]2030256010006[[department]]資訊工程學
A Heuristic Relaxation Method for Nonlinear Mapping in Cluster Analysis
No full text[[abstract]]A relaxation method mapping high-dimensional sample points to low-dimensional sample points is discussed. This method tries to preserve the local interdistance of sample points. Some special heuristics have been introduced to handle the difficulty arising from a large amount of data. Experimental results with handwritten character data and Iris data show that the method runs fast, converges rapidly, and requires a small amount of memory space.[[fileno]]2030256010008[[department]]資訊工程學
ON THE AVERAGE LENGTH OF DELAUNAY TRIANGULATIONS
No full text[[abstract]]We shall show that on the average, the total length of a Delaunay triangulation is of the same order as that of a minimum triangulation, under the assumption that our points are drawn from a homogeneous planar Poisson point distribution.[[fileno]]2030256010031[[department]]資訊工程學
On a Scheduling Problem where a Job Can Be Executed Only by a Limited Number of Processors
No full text[[abstract]]In this paper we consider a job scheduling problem where each job can be executed only by a subset of available processors. This problem arises when we are schedulinga set of cannons to be fired ona set of targets. Each cannon can destroy onlya subset of targets and we want the targets to be destroyed in the shortest possible time. We define what is meant bya balanced solution. We then consider three problems: How can we detect that there is a balanced solution? If this solution exists, find such a solution. If no such solution exists, find an optimal assignment which minimizes the makespan. We show that there are polynomial time algorithms to solve these problems.[[fileno]]2030256010033[[department]]資訊工程學
Recognizing Shortest Path Trees in Linear Time
No full text[[abstract]]Consider that T is a given spanning tree of an undirected graph G which contains n vertices and m edges. A shortest-path tree of graph G is a rooted spanning tree of G such that, from the root to any vertex, the path going along only tree edges is a shortest path. In this paper, an O(m + n)-time algorithm is proposed to determine whether T is a shortest-path tree of G.[[fileno]]2030256010058[[department]]資訊工程學
An Efficient Channel Routing Algorithm to Yield an Optimal Solution
No full text[[abstract]]An algorithm known as optimal channel routing (OCR) is proposed which finds an optimal solution for the channel routing problem in VLSI design. The algorithm is an A* algorithm with good heuristics and dominance rules for terminating unnecessary nodes in the searching tree. Experimental results, agreeing with theoretical analysis, show that it behaves quite well in average cases. An optimal solution is obtained for the Deutsch difficult case in 5.5-min-CPU time after the algorithm is implemented in Pascal and run on a VAX 11/750 computer.[[fileno]]2030256010062[[department]]資訊工程學
Geochemistry and Tectonic Setting of the Basement Rocks from Luzon Island, Philippines
No full text[[fileno]]2010101030001[[department]]物理
SYSTEM EFFECTS MIMIMIZED IN METER-CALIBRATION FACILITY
No full text[[abstract]]Results of recent research on the accuracy of orifice metering indicate that commercially available devices can be used accurately to determine system effects. The research by Chevron Oil Field Research Co. was aimed at reducing orifice metering errors. Measurement of natural-gas flow rate by orifice meters has long been an established practice. Considerable interest has been generated in recent years concerning the extent to which various aspects of the measurement process affect measurement accuracy. Among such parameters, fluid velocity distribution immediately upstream of an orifice plate is receiving increasing attention. Recent data by the U.S. National Bureau of Standards (NBS) showed that swirling flow can propagate a substantially longer distance in the piping system than was previously thought.[[fileno]]2010101010005[[department]]物理
Be-10 as a Tracer for the Rapid Erosion of Taiwan
No full text[[abstract]]Cosmogenic 10 Be was measured using accelerator mass spectrometry in soils and sediments to study the erosion of Taiwan, which has the highest denudation rate in the world. The river sediments in Taiwan have very low 10 Be concentrations, around 5 million atoms per gram, about 1/45 the world wide average. This is the direct consequence of its high sediment yield of more than 1000 mg/cm 2 /yr, 70 times the world average. Combining these values we found that, for Taiwan as a whole, the 10 Be output to the sea only slightly exceeds the input from the rain, a situation typical of many areas around the world. Therefore, even in this example of extremely rapid erosion, 10 Be seems to remain a useful indicator for erosion status. The total 10 Be inventory found in a soil profile from a geologically stable area is at least 18% of the maximum possible inventory. The minimum age thus estimated for the soil is 0.11 Ma, in reasonable agreement with estimates from other means. The maximum erosion rate for this area thus estimated is at most 0.14 mg/cm 2 /yr, four orders of magnitude slower than the average value observed for Taiwan. We also demonstrate that the shelf sediments around Taiwan have received the admixing of a 10 Be rich component from the ocean and would give a poor estimate for material eroded from Taiwan.[[fileno]]2010101010008[[department]]物理
