最坏情况下X3SAT最大海明距离问题最小上界

X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离。提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支。给出了多种化简规则,这些规则很好地提高了算法的时间效率。证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的O(1.7107n)缩小到O(1.6760n),其中n为公式中变量的数目。     

SCHEDULING PARALLEL PROGRAM TASKS WITH NON-NEGLIGIBLE INTERTASK COMMUNICATIONS ON TO NUMA MULTIPROCESSOR SYSTEMS

The purpose of this paper is to examine the impact of scheduling parallel tasks onto non-uniform memory access (NUMA) shared-memory multiprocessor systems by considering non-negligible intertask communications and communication contentions. Communication contentions arise from the communication medium having insufficient capacity to serve all transmissions, thereby causing significant contention delays. Therefore, a new scheduling algorithm, herein referred to as the Extended Critical Path (ECP) algorithm is proposed. The proposed algorithm schedules parallel tasks by considering non-negligible intertask communications and the contentions among shared communication resources. Moreover, it ensures performance within a factor of two of the optimum for general directed acyclic task graphs (DATGs). Experimental results demonstrate the superiority of the ECP algorithm over the scheduling algorithms presented in previous literature.     

认知定位系统的自适应精度研究

为了能够实现定位精度的自适应,本文分析了认知无线电定位系统(cognitive positioning systems,CPS)的原理。该系统利用频谱及环境感知等模块中的传感器单元来获取所需的定位参数,并将其与到达时间(time of arrival,TOA)定位估计算法相结合,以克拉美罗下界(Cramer-Rao lower bound,CRLB)为准则分析最大似然(maximum likelihood,ML)定位精度自适应算法。本文还对单径和多径环境条件下定位精度自适应性能进行了比较。仿真结果表明,该算法能够实现定位精度的自适应,并能通过改善系统可用的频带带宽、分散频谱的数目、信号的调制方式等因素来提高定位精度。     

基于不变式生成的循环停机性验证

循环的停机性验证是程序验证中的一个难点。程序不变式用来描述程序变量的取值关系,其中线性不变式可以帮助描述程序变量间的线性关系,循环不变式能够有效刻画循环中的变量关系。本文基于线性不变式和多项式循环不变式的生成,将循环的停机性验证转化为求解一个最优化问题,给出了一个实用的程序停机性验证框架。基于该框架可以自动地验证程序的停机性,并给出循环的复杂度上界。实验结果说明了该方法的实用性。     

On problem transformability in VLSI

The two basic performance parameters that capture the complexity of any VLSI chip are the area of the chip,A, and the computation time,T. A systematic approach for establishing lower bounds onA is presented. This approach relatesA to the bisection flow, . A theory of problem transformation based on , which captures bothAT ² andA complexity, is developed. A fundamental problem, namely, element uniqueness, is chosen as a computational prototype. It is shown under general input/output protocol assumptions that any chip that decides ifn elements (each with (1+)lognbits) are unique must have =(nlogn), and thus, AT²=(n ²log² n), andA= (nlogn). A theory of VLSI transformability reveals the inherentAT ² andA complexity of a large class of related problems.This work was supported in part by the Semiconductor Research Corporation under contract RSCH 84-06-049-6.     

Roll force,torque, lever arm coefficient,and strain distribution in edge rolling

Due to the growing importance of width control in strip and plate mills, edge rolling is currently an im-portant process in hot rolling mills. Research in edge rolling has been carried out, and in the present ar-ticle, models for roll force, torque, and lever arm coefficient are derived using the upper bound method. A simple, kinematically admissible deformation zone and velocity field, independent of friction in the roll gap, is proposed, and the energy dissipation rate is derived. The formula for energy dissipation rate has, in practice, no limitation because all edge rolling geometries are safely in the area where the formula is valid. Roll force and torque are derived by means of two independent integrals. Thus, the lever arm coef-ficient is evaluated from the expressions for roll force and torque using conventional rolling theory. Roll-ing trials report good agreement with theory. Measured roll forces are similar to calculated forces. Furthermore, the shape of the dogbone that arises during edge rolling is in fairly good agreement with the calculated dogbone shape. Deviations are due to the deviation from ideally plastic material in the ex-periments. Also, the strain distribution over the dogbone is similar to the proposed deformation zone. Thus, a new formula has been developed to a stage that it can be implemented in width control systems for edge rolling stands in hot strip and plate mills.     

The Structure of the Irreversibly Bound Adhesion Promoter-Substrate Interfacial Layer of γ-Aminopropylsilanetriol on Crystalline Si, as Measured by XPS and FTIR

The irreversibly bound interfacial layer deposited by the γ-aminopropysilanetriol adhesion promoter onto a crystalline silicon substrate, which remains even after profuse washing, was found by XPS to have resulted from the fragmentation and rearrangement of the original γ-aminopropylsilanetriol molecule. A mechanism is proposed, involving the homolytic scission of the terminal N-C bond. One of the subsequent reactions is believed to involve hydrogen loss by abstraction and the formation of a terminal vinyl group, which bonds to the substrate. Support for this mechanism is found in IR spectroscopy of this layer.     

An efficient procedure for finding best compromise solutions to the multi-objective assignment problem

In this paper, we consider the problem of determining a best compromise solution for the multi-objective assignment problem. Such a solution minimizes a scalarizing function, such as the weighted Tchebychev norm or reference point achievement functions. To solve this problem, we resort to a ranking (or k-best) algorithm which enumerates feasible solutions according to an appropriate weighted sum until a condition, ensuring that an optimal solution has been found, is met. The ranking algorithm is based on a branch and bound scheme. We study how to implement efficiently this procedure by considering different algorithmic variants within the procedure: choice of the weighted sum, branching and bounding schemes. We present an experimental analysis that enables us to point out the best variants, and we provide experimental results showing the remarkable efficiency of the procedure, even for large size instances.     

Natural rubber–ethylene‐propylene‐diene rubber covulcanization: Effect of reinforcing fillers

Filled covulcanizates of elastomer blend comprising natural rubber (NR) and ethylene‐propylene‐diene rubber (EPDM) of commercial importance were successfully prepared by using a multifunctional rubber additive; namely, bis(diisopropyl)thiophosphoryl disulfide (DIPDIS). A Two‐stage vulcanization technique further improved the physicochemical properties of the blend vulcanizates by restricting, through the formation of polar rubber bound intermediates, the migration of curative and filler from lower to highly unsaturated rubber. Scanning electron microscopy studies indicate homogeneity and coherency in the morphology of the two‐stage vulcanizates. © 2002 Wiley Periodicals, Inc. J Appl Polym Sci 84: 1001–1010, 2002; DOI 10.1002/app.10361