Three algorithms for the search of oriented paths in digraphs are described, based in the generation of a tree, in which an BFS is done, in the first one, and a DFS is done, in the other two algorithms. The first one ...
详细信息
Three algorithms for the search of oriented paths in digraphs are described, based in the generation of a tree, in which an BFS is done, in the first one, and a DFS is done, in the other two algorithms. The first one is aimed at finding all the optimum paths between two vertices. The second one is aimed at solving this problem, as well as at finding the Hamiltonian paths beginning in a vertex, or at finding all the cycles of any order in the digraph. The third one is aimed at finding all the Eulerian paths or circuits. Two more algorithms, for the analysis of graph connectivity, using the same type of techniques are also described, one aimed at separating an unconnected graph into connected subgraphs, and the other aimed at searching for all existing bridges. All five algorithms are fully described and they are also implemented in a structured form, using QB as the programming language. A very compact scheme is proposed to store all the required information, using only one-dimension arrays without pointers, which allows simple programming languages to be used.
Whereas earlier work on spatiotemporal databases generally focused on geometries changing in discrete steps, the emerging area of moving objects databases supports geometries changing continuously. Two important abstr...
详细信息
Whereas earlier work on spatiotemporal databases generally focused on geometries changing in discrete steps, the emerging area of moving objects databases supports geometries changing continuously. Two important abstractions are moving point and moving region, modelling objects for which only the time-dependent position, or also the shape and extent are relevant, respectively. Examples of the first kind of moving entity are all kinds of vehicles, aircraft, people or animals;of the latter hurricanes, forest fires, forest growth or oil spills in the sea. The goal is to develop data models and query languages as well as DBMS implementations supporting such entities, enabling new kinds of database applications. In earlier work we have proposed an approach based on abstract data types. Hence, moving point or moving region are viewed as data types with suitable operations. For example, a moving point might be projected into the plane, yielding a curve, or a moving region be mapped to a function describing the development of its size, yielding a real-valued function. A careful design of a system of types and operations (an algebra) has been presented, emphasizing completeness, closure, consistency and genericity. This design was given at an abstract level, defining, for example, geometries in terms of infinite point sets. In the next step, a discrete model was presented, offering finite representations and data structures for all the types of the abstract model. The present paper provides the final step towards implementation by studying and developing systematically algorithms for (a large subset of) the operations. Some of them are relatively straightforward;others are quite complex. algorithms are meant to be used in a database context;we also address filtering techniques and practical issues such as large object management or numeric robustness in the context of an ongoing prototype implementation.
algorithms an developed simultaneously with systolic architectures for multidimensional adaptive filtering. Because of the extremely high data rate required for real-time video processing, even with the use of highly ...
详细信息
algorithms an developed simultaneously with systolic architectures for multidimensional adaptive filtering. Because of the extremely high data rate required for real-time video processing, even with the use of highly concurrent algorithms and architectures, there is a strong motivation to limit the size of any adaptation problem. The combination of the McClellan transformation as an efficient parametrization for a multidimensional least-squares;(LS) adaptive filter, coupled with systolic arrays to adapt and Implement the filter, yields a novel solution to the problem of adapting a large zero-phase finite impulse response (FIR) multidimensional filter, having arbitrary directional biases, with only a few parameters. Furthermore, it is shown that these filters can be adapted abruptly on a block-by-block basis without causing blocking effects. After developing a basic processing element for a systolic array realization of the Chebychev structure for the McClellan transformation, It Is shown that for a given 2-D transformation function, the adaptation of the I-D prototype filter becomes a small multichannel adaptation problem similar to adaptive army problems. For real-time video applications, such an adaptation algorithm can be performed efficiently using a systolic array of CORDIC processing elements. A similar approach is also taken in developing algorithms to adapt the 2-D transformation function.
Lithium-ion (Li-ion) batteries are ubiquitous sources of energy for portable electronic devices. Compared to alternative battery technologies, Li-ion batteries provide one of the best energy-to-weight ratios, exhibit ...
详细信息
Lithium-ion (Li-ion) batteries are ubiquitous sources of energy for portable electronic devices. Compared to alternative battery technologies, Li-ion batteries provide one of the best energy-to-weight ratios, exhibit no memory effect, and have low self-discharge when not in use. These beneficial properties, as well as decreasing costs, have established Li-ion batteries as a leading candidate for the next generation of automotive and aerospace applications. In the automotive sector, increasing demand for hybrid electric vehicles (HEVs), plug-in HEVs (PHEVs), and EVs has pushed manufacturers to the limits of contemporary automotive battery technology. This limitation is gradually forcing consideration of alternative battery technologies, such as Li-ion batteries, as a replacement for existing leadacid and nickel-metal-hydride batteries. Unfortunately, this replacement is a challenging task since automotive applications demand large amounts of energy and power and must operate safely, reliably, and durably at these scales. The article presents a detailed description and model of a Li-ion battery. It begins the section "Intercalation-Based Batteries" by providing an intuitive explanation of the fundamentals behind storing energy in a Li-ion battery. In the sections "Modeling Approach" and "Li-Ion Battery Model," it present equations that describe a Li-ion cell's dynamic behavior. This modeling is based on using electrochemical principles to develop a physics-based model in contrast to equivalent circuit models. A goal of this article is to present the electrochemical model from a controls perspective.
作者：
Koubková, AKoubek, VCharles Univ
Fac Math & Phys Dept Software Engn Prague 11800 1 Czech Republic Charles Univ
Fac Math & Phys Dept Theoret Comp Sci & Math Log Prague 11800 1 Czech Republic Charles Univ
Fac Math & Phys Inst Theoret Comp Sci Prague 11800 1 Czech Republic
Let sigma'(n) denote the number of all strongly connected graphs on the n-element set. We prove that sigma'(n) greater than or equal to 2(n2) (1- n(n - 1)/2(n-1)). Hence the algorithm computing a transitive cl...
详细信息
Let sigma'(n) denote the number of all strongly connected graphs on the n-element set. We prove that sigma'(n) greater than or equal to 2(n2) (1- n(n - 1)/2(n-1)). Hence the algorithm computing a transitive closure by a reduction to acyclic graphs has the expected time O(n(2)), under the assumption of uniform distribution of input graphs. Furthermore, we present a new algorithm constructing the transitive closure of an acyclic graph. (C) 2002 Elsevier Science B.V. All rights reserved.
The first results of the GPS/MET programme of sounding the Earth's atmosphere by means of a Low Earth Orbit satellite implemented with a Global Positioning System (GPS) receiver indicated that in the lower troposp...
详细信息
The first results of the GPS/MET programme of sounding the Earth's atmosphere by means of a Low Earth Orbit satellite implemented with a Global Positioning System (GPS) receiver indicated that in the lower troposphere, the phase and amplitude of the signal received undergo strong oscillations. This effect is a consequence of multipath propagation resulting from the complicated structure of the atmospheric refractivity in the tropical regions. In this paper, we propose a method of processing of the phase measurements based on the theory of diffraction. The method was tested in processing GPS/MET radio soundings. Comparison of the reconstructed profiles of the temperature and humidity with those derived from radio soundings and extracted from the NMC Global Atmospheric Circulation Model indicates validity of the method proposed.
The paper describes an algorithmic base for the CAD system for physical layout of large sea-of-gates chips. A solution is obtained by successive augmentation of a partial layout. A new, dynamically defined slice is ad...
详细信息
The paper describes an algorithmic base for the CAD system for physical layout of large sea-of-gates chips. A solution is obtained by successive augmentation of a partial layout. A new, dynamically defined slice is added to the partial solution in each step of the process. Two different techniques are proposed to find candidate cells for inclusion in the slice. Different methods are also proposed for positioning elements inside the slice. Global routing of the partial solution is used to guarantee routability and to direct future placement. The system achieved more than 75% use of the basic cells for two-layer metal CMOS technology with functional cells varying widely in size in both dimensions. It also almost always achieved a 100% completion rate for detailed routing.
algorithms play an increasing role in food retailing and distribution. Through a longitudinal study supported by qualitative interviews, we explore how such technologies have turned the sourcing of food into a highly ...
详细信息
algorithms play an increasing role in food retailing and distribution. Through a longitudinal study supported by qualitative interviews, we explore how such technologies have turned the sourcing of food into a highly automated transaction, moving from explore and exploit to embed and embalm. We demonstrate the impact that embedding algorithms can have on organizational processes and structures and that this may shift the balance of power within the value chain without being visible to management.
algorithms for calculating an aircraft's orientation angles based on the results of the numerical integration of Poisson's and quaternion equations are proposed. The algorithms in the presence of random errors...
详细信息
algorithms for calculating an aircraft's orientation angles based on the results of the numerical integration of Poisson's and quaternion equations are proposed. The algorithms in the presence of random errors of the matrix elements of direction cosines and quaternions are characterized by a significantly higher accuracy in comparison to the formulas for solving the formulated problem. The results of testing the mathematical modeling data under random errors, which confirm the increased accuracy of the calculation of the orientation angles, are given.
Numerical methods are outlined for computing the velocity potential, and its derivatives, for linearized three-dimensional wave motions due to a unit source with harmonic time dependence beneath a free surface. Two di...
详细信息
Numerical methods are outlined for computing the velocity potential, and its derivatives, for linearized three-dimensional wave motions due to a unit source with harmonic time dependence beneath a free surface. Two distinct cases are considered where the fluid depth is either infinite, or of constant finite depth. Efficient algorithms are developed in both cases, to replace the numerical evaluation of the relevant integrals by multi-dimensional approximations in economized polynomials. This technique is substantially faster than conventional direct methods based on numerical integration.
暂无评论